算法刷题之路

发表于2021-07-14更新于2021-08-07

算法断断续续刷了这么久。一直没有好的效果。新开此贴详细记录刷题过程，并用Javaa和C++同时实现。

专题一 LeetCode HOT 100

94.二叉树的中序遍历（Easy)

题目描述：给定一个二叉树的根节点 root ，返回它的中序遍历.

思路1：直接递归实现
Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root,list);
        return list;
    }
    void inorder(TreeNode root,List<Integer> list){
        if(root!=null){
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }
}

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了94.22%的用户

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& vec) {
        if (root) {
        inorder(root->left, vec);
        vec.push_back(root->val);
        inorder(root->right, vec);
        }

    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        inorder(root, vec);
        return vec;
    }
};
1
2
执行用时：4 ms, 在所有 C++ 提交中击败了41.84%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了59.96%的用户

思路2：迭代
Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack <TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.8 MB, 在所有 Java 提交中击败了19.11%的用户

C++版本

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        stack<TreeNode*> stack;
        while(root!=){

        }
        return vec;
    }
};

5.最长回文子串（Medium)

题目描述：给你一个字符串 s，找到 s 中最长的回文子串

示例1:

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2:

1
2
输入：s = "cbbd"
输出："bb"

示例3:

1
2
输入：s = "a"
输出："a"

提示：

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

思路1：中心扩展法

中心扩展法步骤

  1. 遍历所有字符。从该字符进行左右对比（实现对比函数，返回最长子串的左右位置）
  2. 求出每个字符最长回文子串并与之前的中心字符求出的会文字串对比得到最长子串。
  • 要点1：若字符串个数<=1,直接返回。
  • 要点2：可以从第1个字符开始遍历。倒数第二个一个字符结束
  • 要点3：只需要记录子串的结束和结尾坐标，并比较其大小，并记录遍历字符的位置k。无需求出每个字符最长子串
  • 要点4：奇数和偶数字符串可用同一个对比函数
  • 要点5：根据字符串左右下标位置求奇偶性根据k求子串

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
   public static String longestPalindrome(String s) {
        int n = s.length();
        //预判断
        if (n <= 1) {
            return s;
        }
        //start,end：最长回文子串的左右标记
        int start;
        int end;
        //max：最长回文子串的长度，n：最长回文串中心点（奇数回文串情况）
        int max = 1;
        int k = 0;

        for (int i = 0; i < n - 1; i++) {
            int lenOdd = getPalind(s, i, i);//奇数情况
            int lenEven = getPalind(s, i, i + 1);//偶数情况
            int imax = lenOdd > lenEven ? lenOdd : lenEven;
            if (imax > max) {//更新最长回文子串信息
                max = imax;
                k = i;
            }
        }
        //两种情况分别处理
        if (max % 2 == 0) {
            start = k - (max / 2) + 1;
            end = k + (max / 2);
        } else {
            start = k - (max - 1) / 2;
            end = k + (max - 1) / 2;
        }
        return s.substring(start, end + 1);

    }

    private static int getPalind(String s, int left, int right) {
        while (((left >= 0) && (right < s.length())) 
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return (right - left) - 1;//长度为right-left+1,此处right和left各多一位。因此-2
    }



}

1
2
执行用时：25 ms, 在所有 Java 提交中击败了88.46%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了98.34%的用户

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n==1){
            return s;
        }

        int start,end,k=0;
        int max = 1;
        for(int i = 0;i<n-1;i++){
            int maxOdd = getPalind(s,i,i);
            int maxEnev = getPalind(s,i,i+1);
            int imax = maxOdd>maxEnev?maxOdd:maxEnev;

            if(imax>max){
                max = imax;
                k = i;
            }
        }

        if (max % 2 == 0) {
            start = k - (max / 2) + 1;
        } else {
            start = k - (max - 1) / 2;
        }
        return s.substr(start, max);//Java与C++中substr参数不同，C++第二个为个数，Java为取不到的末尾下标

    }

    int getPalind(string s,int left,int right){
        while(((left>=0)&&(right<s.size()))&&s[left]==s[right]){
            left--;
            right++;
        }
        return right - left -1;
    }
};
1
2
执行用时：68 ms, 在所有 C++ 提交中击败了68.49%的用户
内存消耗：225.7 MB, 在所有 C++ 提交中击败了37.85%的用户

思路2：动态规划

Java:

1
2
3
4
class Solution {

}

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了94.22%的用户

C++:

1
2
3
class Solution {

};
1
2
执行用时：4 ms, 在所有 C++ 提交中击败了41.84%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了59.96%的用户

4. 寻找两个正序数组的中位数（Hard)

题目描述：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数

示例1:

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例2:

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例3:

1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例4:

1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例5:

1
2
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

思路1：xxxx

Java:

1
2
3
4
class Solution {

}

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了94.22%的用户

C++:

1
2
3
class Solution {

};
1
2
执行用时：4 ms, 在所有 C++ 提交中击败了41.84%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了59.96%的用户

11.盛最多水的容器（Hard)

思路：双指针

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public static int maxArea(int[] height) {
        int n = height.length;
        if(n<2){
            return 0;
        }
        int left = 0;
        int right = n-1;
        int result = 0;
        while (left<right){
            int max = getMin(height[left],height[right])*(right-left);
            result = getMax(max,result);
            if(height[left]<height[right]){
                ++left;
            }else {
                --right;
            }
        }
        return result;
    }

    static int getMin(int left,int right){
        return left>right?right:left;
    }
    static int getMax(int a,int b){
        return a>b?a:b;
    }
}

1
2
执行用时：4 ms, 在所有 Java 提交中击败了79.48%的用户
内存消耗：51.9 MB, 在所有 Java 提交中击败了32.47%的用户

C++:

1
2
3
class Solution {

};
1
2
执行用时：4 ms, 在所有 C++ 提交中击败了41.84%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了59.96%的用户

5.模板（medium)

题目描述：xx

示例1:

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

提示：

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

思路1：xxxx

Java:

1
2
3
4
class Solution {

}

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了94.22%的用户

C++:

1
2
3
class Solution {

};
1
2
执行用时：4 ms, 在所有 C++ 提交中击败了41.84%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了59.96%的用户