1.两数之和

考点：哈希查找O(1)更快速

难点在于想一个不是暴力遍历的算法

由于哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 降低时间复杂度

曾经想过全部存进hash map里再查找，但其实可以存入的时候判断，边存边查找

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");//如果最终都没有结果则抛出异常
    }
}

2.两数相加

和以前做过的大数相加很像！

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //定义一个新联表伪指针，用来指向头指针，返回结果
        ListNode prev = new ListNode(0);
        //定义一个进位数的指针，用来存储当两数之和大于10的时候，
        int carry = 0;
        //定义一个可移动的指针，用来指向存储两个数之和的位置
        ListNode cur = prev;
        //当l1 不等于null或l2 不等于空时，就进入循环
        while(l1!=null || l2!=null){
            //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int x= l1 !=null ? l1.val : 0;
             //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int y = l2 !=null ? l2.val : 0;
            //将两个链表的值，进行相加，并加上进位数
            int sum = x + y + carry;
            //计算进位数
            carry = sum / 10;
            //计算两个数的和，此时排除超过10的请况（大于10，取余数）
            sum = sum % 10;
            //将求和数赋值给新链表的节点，
            //注意这个时候不能直接将sum赋值给cur.next = sum。这时候会报，类型不匹配。
            //所以这个时候要创一个新的节点，将值赋予节点
            cur.next = new ListNode(sum);
            //将新链表的节点后移
            cur = cur.next;
            //当链表l1不等于null的时候，将l1 的节点后移
            if(l1 !=null){
                l1 = l1.next;
            }
            //当链表l2 不等于null的时候，将l2的节点后移
            if(l2 !=null){
                l2 = l2.next;
            } 
        }
        //如果最后两个数，相加的时候有进位数的时候，就将进位数，赋予链表的新节点。
        //两数相加最多小于20，所以的的值最大只能时1
        if(carry == 1){
            cur.next = new ListNode(carry);
        }
        //返回链表的头节点
        return prev.next;
    }
}

3.无重复字符的最长子串

考点：滑动窗口

程序的本质是模拟人的思考！

滑动窗口就是队列，右边进队，直到出现重复时左边出队，直到窗口里没有重复

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

右界不用特意操作，因为它是+1，+1地涨上去，记得在循环里+1就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;//长度为0直接结束
        unordered_set<char> lookup;//unordered_set ：元素无序且只能出现一次
        int maxStr = 0;//记录最长子串长度
        int left = 0;//左边框下标
        for(int i = 0; i < s.size(); i++){//i右边框下标
            while (lookup.find(s[i]) != lookup.end()){//s[i]新加进来的右边框元素
                lookup.erase(s[left]);//s[left]左边框元素，由于这里是容器，所以需要一位一位erase，如果用数组模拟，直接把left指针移动一大段即可，但数组模拟又不好查找，故还是题目里的写法最好
                left ++;
            }
            maxStr = max(maxStr,i-left+1);//还能这样直接写？
            lookup.insert(s[i]);
    }
        return maxStr;
        
    }
};

知识点：

set:不重复且有序

multiset:元素可以重复，且元素有序

unordered_set ：元素无序且只能出现一次

unordered_multiset ： 元素无序可以出现多次

尾后迭代器：指向容器中最后一个元素之后的位置的迭代器。

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
//头文件
#include<set>
//初始化定义
set<int> s;
//返回第一个元素地址
s.begin()
//返回尾后迭代器
s.end()
//插入一个元素O(logN)	
s.insert(element)
//删除定位器iterator指向的值O(logN)
erase(iterator)
//删除键值key_value的值O(logN)
erase(key_value)
//元素个数
s.size()
//查找set中的某一元素，有则返回该元素对应的迭代器，无则返回尾后迭代器
s.find(element)
s.end()==s.find(element)//用于判断容器里没有查找的元素
//查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现
s.count(element)
//判断set容器是否为空
s.empty()
//返回大于等于k的第一个元素的迭代器
s.lower_bound(k)
//返回大于k的第一个元素的迭代器
s.upper_bound(k)

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

解法一

考点：归并排序

先将两个数组合并，然后根据奇数，还是偶数，返回中位数。

难点是中间的几个条件判断不好写

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
49
50
51
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] nums;
    int m = nums1.length;
    int n = nums2.length;
    nums = new int[m + n];//建一个新数组，把他们排进来
    if (m == 0) {//特殊情况：第一个数组为空
        if (n % 2 == 0) {
            return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        } else {

            return nums2[n / 2];
        }
    }
    if (n == 0) {//特殊情况：第二个数组为空
        if (m % 2 == 0) {
            return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        } else {
            return nums1[m / 2];
        }
    }

    int count = 0;//新数组的下标
    int i = 0, j = 0;
    while (count != (m + n)) {//循环结束条件
        if (i == m) {//第一个数组到头了
            while (j != n) {
                nums[count++] = nums2[j++];
            }
            break;
        }
        if (j == n) {//第二个数组到头了
            while (i != m) {
                nums[count++] = nums1[i++];
            }
            break;
        }

        if (nums1[i] < nums2[j]) {//把数字往里排
            nums[count++] = nums1[i++];
        } else {
            nums[count++] = nums2[j++];
        }
    }

    if (count % 2 == 0) {//排完了，求中位数
        return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
    } else {
        return nums[count / 2];
    }
}

时间复杂度：遍历全部数组 (m+n)

空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)

解法二

想要时间复杂度O(log(m+n))必须要像二分查找那样，一次排除一半的数

考点：求第k最小数，奇数偶数求中位数的情况合并公式

时间复杂度O(log(m+n))

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    //以下是将奇数和偶数求中位数的情况合并的公式：都求出一左一右两个数，偶数就是两个取平均值的数，奇数则会求出来同一个数
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //以上两行的工作是：求出一左一右两个数分别是第几小的数？
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    //求第k最小数就是每次排除k/2个，在剩余的里面再求第k-k/2最小数，这是个递归过程
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {//end start：蓝格子范围 k：求第k最小数
        int len1 = end1 - start1 + 1;//len1：第一个数组的蓝格子长度
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);//用递归来实现归一操作！
        if (len1 == 0) return nums2[start2 + k - 1];//len1空了

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);//结束条件，第一最小数，就返回更小的那个

        int i = start1 + Math.min(len1, k / 2) - 1;//i，j就是箭头
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {//递归的精髓！
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

解法三

本题还有一种更加优雅的解法！这次不想看了，下次再来

5.最长回文子串

解法一

考点：动态规划

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。

（这个特点有点像递归）

基于这个特点，可以得出状态转移方程

动态规划的边界条件：子串的长度为 1 或 2

画图画出来是个size*size的棋盘格上半部分

动态规划就是根据前格的true or false+一个额外条件，来判断本格的true or false，把这半个棋盘格填完，就能得出最大值

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
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {//特殊情况1：只有一个字符
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));//这里把vector写成静态的，可以直接用普通数组
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;//棋盘格上的对角线元素直接填
        }
        // 递推开始
        // 先枚举子串长度
        //思考一种枚举方法，要把所有组合都考虑到，而且要从内核向外，能够填表
        for (int L = 2; L <= n; L++) {//L是子串长度，先固定长度，移动边界，长度由2慢慢增上去，动态规划是由内核而外（由边界条件向外）（先因再果）才能填表，这是和递归不一样的地方，递归是由果溯因
            for (int i = 0; i < n; i++) {//i是左边界
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {//先由附加的一个条件大类
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {//附加条件成立，再分成两条路：由前人推出，或边界条件直接得出
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

解法二

考点：中心扩展

其实和动态规划的想法是一样的，只是没有列表，空间复杂度减少了

中心：回文中心

遍历枚举每一个回文中心并尝试向两边扩展，直到无法扩展为止。

至于回文中心是一个字符还是两个字符的问题，不需要分类讨论，left，right两根指针往外扩张，起始位置时，一个中心时，left和right都指向它

类似的奇偶归一处理在中位数那边也遇到过，思考一下有没有什么可总结的~

本题的细节再想想是怎么写出来的，比如return {left + 1, right - 1};

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
class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {//left，right是扩张的起始位置
        while (left >= 0 && right < s.size() && s[left] == s[right]) {//条件成立就一直扩张
            --left;
            ++right;
        }
        return {left + 1, right - 1};//扩张到最大返回
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;//这两个用于记录最长串
        for (int i = 0; i < s.size(); ++i) {//遍历一遍，i是回文中心
            auto [left1, right1] = expandAroundCenter(s, i, i);//奇外扩
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);//偶外扩
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

解法三

考点：Manacher算法

一种复杂的专业算法，戳这里看

6.Z字形变换

就是模拟人的思路！把人脑的思路拆解！

体会一个非常妙的点：用flag实现了i的周期性变化：123212321

动画见这里

自变量为往后遍历的这个过程，因变量是每个字符的行数，记录行数，最后以行数为自变量输出

和以下有点相似：

画圆按时间线拉长，拉成sin cos三角函数

这个过程可以拆解为：

画圆：自变量为时间，因变量是纵坐标，记录纵坐标，最后以横坐标为自变量输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows < 2)//特殊情况
            return s;
        vector<string> rows(numRows);
        int i = 0, flag = -1;
        for (char c : s) {//这是什么语法？
            rows[i].push_back(c);
            if (i == 0 || i == numRows -1)
                flag = - flag;
            i += flag;//用flag实现了i的周期性变化：123212321
        }
        string res;
        for (const string &row : rows)
            res += row;
        return res;
    }
};

6.整数反转