LeetCode 30天刷题计划

为了在一个月内高效地刷题，下面的计划每天安排了2道题目，总共60道题目。题目难度从简单到困难逐步增加，题目涵盖了常见的算法和数据结构主题。

第1周

第1天

1. Two Sum

function twoSum(nums: number[], target: number): number[] {
    let res : [number, number] = [0, 0];
    let map : Map<number, number> = new Map();

    for (let i = 0;i< nums.length ;i ++) {
        if (map.has(nums[i]) && map.get(nums[i]) !== i) {
            res = [i, map.get(nums[i])];
            break;
        } else {
            map.set(target - nums[i], i);
        }
    }

   return res;

};

2. Reverse Integer

function reverse(x: number): number {
    const num: number = Math.abs(x);

    const str: string = String(x).split('').reverse().join('');

    const res = x < 0 ? -parseInt(str) : parseInt(str);
    if (res < -Math.pow(2, 31) || res > Math.pow(2, 31)) return 0
    return res
};

第2天

3. Palindrome Number

我自己的解法：双指针

function isPalindrome(x: number): boolean {
    if (x < 0) return false;
    if (x < 10) return true;
    
    const str = x + '';

    let p1 = 0;
    let p2 = str.length - 1;

    while(p2 - p1 >= 0) {
        if (str.charAt(p1) !== str.charAt(p2)) return false;
        
        p1 += 1;
        p2 -= 1;
    }

    return true;

};

网上有人更简单

var isPalindrome = function(x) {
    let y=Number(x.toString().split('').reverse().join(''))
    return y===x
};

4. Roman to Integer

function intToRoman(num: number): string {
    let y: number = num;
    let r: string = '';
    if (y >= 1000) {
        const n = Math.floor(y / 1000);
        y = y % 1000;

        for (let i = 0; i < n; i++) {
            r += 'M';
        }
    }
    if (y >= 900) {
        y -= 900;
        r += 'CM';
    }
    if (y >= 500) {
        const n = Math.floor((y - 500) / 100);
        y = y % 100;
        r += 'D';
        for (let i = 0; i < n; i++) {
            r += 'C';
        }
    }

    if (y >= 400) {
        y -= 400;
        r += 'CD';
    }

    if (y >= 100) {
        const n = Math.floor(y / 100);
        y = y % 100;

        for (let i = 0; i < n; i++) {
            r += 'C';
        }
    }

    if (y >= 90) {
        y -= 90;

        r += 'XC';
    }

    if (y >= 50) {
        const n = Math.floor((y - 50) / 10);
        y = y % 10;
        r += 'L';
        for (let i = 0; i < n; i++) {
            r += 'X';
        }
    }
    if (y >= 40) {
        y -= 40;
        r += 'XL';
    }

    if (y >= 10) {
        const n = Math.floor(y / 10);
        y = y % 10;

        for (let i = 0; i < n; i++) {
            r += 'X';
        }
    }

    if (y >= 9) {
        y = 0;
        r += 'IX';
    } else if (y >= 5) {
        const n = y - 5;
        y = 0;
        r += 'V';
        for (let i = 0; i < n; i++) {
            r += 'I';
        }
    } else if (y === 4) {
        y = 0;
        r += 'IV';
    } else {
        for (let i = 0; i < y; i++) {
            r += 'I';
        }
        y = 0;
    }

    return r;
};

第3天

5. Longest Common Prefix

function longestCommonPrefix(strs: string[]): string {
    let res = strs[0];
    
    while(res.length) {
        let allHas: boolean = true;
        for (let s of strs) {
            if (s.indexOf(res) !== 0) {
                allHas = false;
                break;
            }
        }

        if (allHas) return res;

        if (!allHas) {
           res = res.substring(0, res.length - 1);
        }

    }


    return '';

};

6. Valid Parentheses

function isValid(s: string): boolean {
    const map = new Map();
    map.set('{', '}');
    map.set('(', ')');
    map.set('[', ']');

    const stack: string[] = [];
    for (let c of s) {
        if (map.has(c)) {
            stack.push(c)
        } else {
            const i = stack.pop();
            if (map.get(i) !== c) {
                return false;
            }
        }
    }
    return stack.length === 0;
};

第4天

7. Merge Two Sorted Lists
   非递归

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const res = new ListNode(0, null);
    let p = res;

    while (list1 && list2) {
        if (list1.val > list2.val) {
            p.next = list2;
            list2 = list2.next;
        } else {
            p.next = list1;
            list1 = list1.next;
        }
        p = p.next;
    }

    if (list1) p.next = list1;
    if (list2) p.next = list2;


    return res.next;
};

8. Remove Duplicates from Sorted Array

function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0

    let p = 0, q = 1;

    while (q < nums.length) {
        if (nums[p] === nums[q]) {
            q++;
        } else {
            p++;
            nums[p] = nums[q]
        }
    }


    return p + 1;

};

第5天

9. Remove Element

function removeElement(nums: number[], val: number): number {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) nums[i] = null;
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === null) {

            for (let j = i + 1; j < nums.length; j++) {
                if (nums[j] !== null) {
                    nums[i] = nums[j];
                    nums[j] = null;
                    break;
                }
            }
        }
    }

    while (nums.length > 0 && nums[nums.length - 1] === null) {
        nums.pop();
    }

    return nums.length;
};

10. Implement strStr()

function strStr(haystack: string, needle: string): number {
    if (haystack === needle) return 0;
    for (let i = 0; i < haystack.length; i++) {
        for (let j = 0; j <= needle.length ; j++) {
            if ( i + j > haystack.length) return -1
            if (j === needle.length) return i;


            if (haystack.charAt(i + j) !== needle.charAt(j)) {
                break
            }

        }
    }

    return -1;
};

第6天

11. Search Insert Position

思路：二分查找
注意点：边界问题
时间复杂度：log（n）
空间复杂度：O（1）

function searchInsert(nums: number[], target: number): number {
    let start = 0; let end = nums.length - 1;

    if (target <= nums[0]) return 0;

    while (start <= end) {
        const mid = Math.ceil((start + end) / 2);
        if (nums[mid] < target) start = mid + 1;
        else end = mid - 1;
    }

    return start;
};

12. Count and Say

function countAndSay(n: number): string {
    let str = '1';
    for (let i = 2; i <= n; i++) {
        const sb = [];
        let start = 0;
        let pos = 0;

        while (pos < str.length) {
            while(pos < str.length && str[pos] === str[start]) {
                pos ++;
            }
            sb.push('' + (pos - start) + str[start]);
            start = pos
        }

        str = sb.join('');
    }

    return str;
};

第7天

13. Maximum Subarray

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let pre = nums[0];
    let max = nums[0];

    for (let i of nums.slice(1, nums.length)) {
        pre = Math.max(i, pre + i);
        max = Math.max(max, pre);
    }

    return max;
};

时间复杂度0（n）
思路：动态规划

14. Length of Last Word

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    const strs = s.trim().split(' ')
    return strs[strs.length - 1].length;
};

第2周

第8天

15. Plus One

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for (let i = digits.length - 1; i >=0 ; i--) {
        const value = digits[i];
        if ((value + 1) % 10 !== 0 ) {
            digits[i] = value + 1;

            return digits;
        } 
        digits[i] = 0
    }

    digits.unshift(1);
    return digits;
};

时间复杂度0（n）,n为数据大小

16. Add Binary

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    let res = "", aArr = a.split(''), bArr = b.split('');
    let flag = 0;
    while (aArr.length || bArr.length) {
        let va, vb;
        va = aArr.length ? aArr.pop() : 0;
        vb = bArr.length ? bArr.pop() : 0;

        res = (parseInt(va, 10) + parseInt(vb, 10) + flag) % 2 + '' + res;
        flag = Math.floor(parseInt(va, 10) + parseInt(vb) + flag  % 2)
    }

    if (flag) {
        res = '1' + res;
    }

    return res;
};

时间复杂度0（n）,n为最大数组的长度

第9天

17. Climbing Stairs

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for(let i = 1; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }

    return r;
};

思路：动态规划 + 滑动窗口
时间复杂度： O（n）

18. Remove Duplicates from Sorted List
    var deleteDuplicates = function (head) {

    if (!head || !head.next) return head

    let p = head;
    while (p.next) {
    if (p.val === p.next.val) {
    p.next = p.next.next;
    } else {
    p = p.next;
    }

    }
    return head;

};

时间复杂度 O（n）n为链表长度

第10天

19. Merge Sorted Array

var merge = function (nums1, m, nums2, n) {
    let p = 0, q = 0, size = m;
    while (p < size || q < n) {
        const a = nums1[p], b = nums2[q];
        if (a > b) {
            // 插入a
            size++;
            insert(nums1, size, p, b,);
            q++;
        } else if (p >= size) {
            nums1[p] = b;
            q++;
        }
        p++;
    }

};
时间复杂度 O（m + n）

function insert(arr, len, index, value) {
    let cur = len - 1;
    while (cur >= index) {
        if (cur > index) arr[cur] = arr[cur - 1];
        else {
            arr[cur + 1] = arr[cur];
            arr[cur] = value;
        }

        cur--;
    }
}

20. Binary Tree Inorder Traversal

var inorderTraversal = function(root) {
    const res = [];

    function tra(node) {
        if (!node) return;

        tra(node.left);
        res.push(node.val);
        tra(node.right)
    }

    tra(root);

    return res;
};

时间复杂度O（n）n为节点个数

第11天

21. Symmetric Tree

var isSymmetric = function (root) {

    function same(tree1, tree2) {
        if (!tree1 && !tree2) return true;
        if (tree1 && tree2) {
            return tree1.val === tree2.val && same(tree1.left, tree2.right) && same(tree1.right, tree2.left)
        }

        return false;
    }


    return same(root.left, root.right)
};

时间复杂度O(n) n为树节点个数

22. Maximum Depth of Binary Tree

/**
 * 深度优先
 * @param {TreeNode} root
 * @return {number}
 */

var maxDepth = function (root) {
    if (!root) {
        return 0
    }

    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

广度优先

var maxDepth = function (root) {
    if (!root) return 0;

    const queue = [root];
    let res = 0;

    while (queue.length > 0) {
        let size = queue.length;

        while (size > 0) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }

            if (node.right) {
                queue.push(node.right)
            }

            size--;
        }
        res++;
    }

    return res;

};

第12天

23. Best Time to Buy and Sell Stock
24. Single Number

第13天

25. Linked List Cycle
26. Min Stack

第14天

27. Number of 1 Bits
28. Happy Number

第3周

第15天

29. Reverse Linked List
30. Intersection of Two Linked Lists

第16天

31. Find the Duplicate Number
32. Missing Number

第17天

33. Contains Duplicate
34. Product of Array Except Self

第18天

35. Maximum Product Subarray
36. Find Minimum in Rotated Sorted Array

第19天

37. Search in Rotated Sorted Array
38. Find Peak Element

第20天

39. First Missing Positive
40. Longest Consecutive Sequence

第21天

41. Valid Sudoku
42. Sudoku Solver

第4周

第22天

43. Word Search
44. Word Search II

第23天

45. Set Matrix Zeroes
46. Spiral Matrix

第24天

47. Rotate Image
48. Kth Largest Element in an Array

第25天

49. Top K Frequent Elements
50. Sort Colors

第26天

51. Minimum Window Substring
52. Longest Substring Without Repeating Characters

第27天

53. Longest Palindromic Substring
54. Longest Repeating Character Replacement

第28天

55. Permutation in String
56. Find All Anagrams in a String

第29天

57. Longest Increasing Subsequence
58. Word Break

第30天

59. House Robber
60. Coin Change

结论

按照上述计划每天刷2道题目，可以在一个月内完成60道算法题。题目涵盖了常见的算法和数据结构主题，逐步提高难度。希望这个计划能帮助你高效地在LeetCode上刷题，提升算法和编程能力。