1. 两数之和
- 1.1 思路
- 1.2 代码
2.两数相加
- 2.1 思路
- 2.2 代码
3. 无重复字符的最长子串
- 3.1 思路
- 3.2 代码
4. 寻找两个正序数组的中位数
- 4.1 思路
- 4.2 代码
5. 最长回文串
- 5.1 思路
- 5.2 代码
6. Z字型变换
- 6.1 思路
- 6.2 代码
7. 整数反转
- 7.1 思路
- 7.2 代码
8. 字符串转换整数（atoi）
- 8.1 思路
- 8.2 代码
10.正则表达式匹配
- 10.1 思路
- 10.2 代码

学算法抓住两点：

思路搞懂【为什么这么做？】
写代码的熟练度。【尽可能自己调试出来】

ACWING 拓扑图。

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

1.1 思路

暴力做法。暴力枚举两重~。
排序来做 + 双指针。nlogn
si，看前面有没有target - si的。O(1)的时间复杂度看一个数是否存在。哈希表插入查询都是O（1）的时间复杂度，所以总的时间复杂度是O（n）【如果是红黑树，复杂度是logn】
1.2 代码
2.两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

2.1 思路

小学数学写竖式，每位相加 % 10,记录进位。从个位开始算，
循环到进位为0 并且链表为空的。

2.2 代码

特判头结点的时候，可以加一个虚拟头结点。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int t = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(t % 10);
            cur = cur.next;
            t /= 10;
        }
        return dummy.next;
    }
}

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

3.1 思路

双指针、滑动窗口。

给一个序列，找答案，考虑：怎么把所有情况都枚举到？
总共有大概n^2个子串，怎么把所有情况枚举到？

分成n类，以每个字符为结尾作为一类。i位置，往前找j，能让j最小并且
i~j之间没有重复字符。i往右走的时候，j也必定不走或者往右走。

哈希表记录元素和元素出现的次数。i增加的时候，进入元素。
j也往右走。

3.2 代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int left = 0, right = 0;
        Map<Character,Integer> charCounts = new HashMap<>();
        while (right < s.length()) {
            char inChar = s.charAt(right);
            charCounts.put(inChar,charCounts.getOrDefault(inChar,0) + 1);
            while (charCounts.get(inChar) > 1) {
                char outChar = s.charAt(left++);
                charCounts.put(outChar,charCounts.get(outChar) - 1);
            }
            res = Math.max(res,right - left + 1);
            right++;
        }
        return res;
    }
}

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

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

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

4.1 思路

奇数个数的话，自然是中间值，偶数个数的话，自然是两个数的平均值。

递归

求一下这两个数组从小到大排列，第k个数是什么？
分解成子问题：先看一下两个数组中第K/2个数是什么？
1.1 A[k/2] < B[k/2] 。A数组中的0~k/2 个元素必定不是第k个数。
1.2 A[k/2] > B[k/2]。B数组中的0 ~ k/2 个元素必定不是第k个数。
1.3 A[k/2] = B[k/2]。说明恰好是第K个元素。

每次都会删除k/2 个元素k= k/2。 k = 1 的时候，找最小值最可以了。
时间复杂度就是log(n + m)

4.2 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        // 让nums1 的size 更小。
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        // nums1 已经遍历完了。
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);

        // si 不能越界。
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;

        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        if (totalLength % 2 == 0) {
            int left = findKthNumInTwoArray(nums1,0,nums2,0,totalLength / 2);
            int right = findKthNumInTwoArray(nums1,0,nums2,0,totalLength / 2 + 1);
            return (left + right ) / 2.0;
        } else {
            return findKthNumInTwoArray(nums1,0,nums2,0,totalLength / 2 + 1);
        }
    }

    private int findKthNumInTwoArray(int[] nums1,int s1,
                                    int[] nums2,int s2,int k) {
        if (nums1.length - s1 > nums2.length - s2) {
            return findKthNumInTwoArray(nums2,s2,nums1,s1,k);
        }
        if (nums1.length == s1) {
            return nums2[s2 + k - 1];
        }
        if (k == 1) {
            return nums1[s1] < nums2[s2] ? nums1[s1] : nums2[s2];
        }
        // nums1 找下标为 s1 + k/2 - 1的元素。 nums2 找下标为 s2 + k - k/2 -1 的元素。
        int si = Math.min(s1 + k / 2, nums1.length);
        int sj = s2 + k / 2;
        if (nums1[si - 1] < nums2[sj - 1]) {
            return findKthNumInTwoArray(nums1,si,nums2,s2,k - (si - s1));
        } else {
            return findKthNumInTwoArray(nums1,s1,nums2,sj, k - k/2);
        }


    }
}

5. 最长回文串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

5.1 思路

马拉车算法，O（n）太偏了。
二分 + hash算法【比较难】。Acwing 139题。

首先看回文串：奇数的时候中间无所谓，偶数的时候要两两配对。
枚举中心，双指针往两边走，要么两边指向的字符不一样，要么越界。[l+ 1, r-1]是回文串。(枚举中心n次，复杂度n^2)
1. 奇数情况，中心点初始化为i，l 初始化为 i -1 ，r初始化为i+1.
2. 偶数情况，l初始化为i，r初始化为i+1.

dp，开数组。

5.2 代码

class Solution {
 public String longestPalindrome(String s) {
     if (s == null || s.length() == 0) {
         return "";
     }
     int maxLength = 1;
     int beginIndex = 0;
     for (int i = 0; i < s.length(); i++) {
         // 奇数长度的回文串、
         int l = i - 1, r = i + 1;
         while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
             l--;
             r++;
         }
         // [l+1 , r -1]是回文串。长度 r - l -1
         if (r - l - 1 > maxLength) {
             maxLength = r - l - 1;
             beginIndex = l + 1;
         }
         // 偶数长度的回文串
         l = i;
         r = i + 1;
          while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
             l--;
             r++;
         }
         // [l+1 , r -1]是回文串。长度 r - l -1
         if (r - l - 1 > maxLength) {
             maxLength = r - l - 1;
             beginIndex = l + 1;
         }

     }

     return s.substring(beginIndex,beginIndex + maxLength);
 }
}

6. Z字型变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

6.1 思路

类似于加密解密的系统。

先把数字按照Z字形排列一下，

（改成N字变换更好）找规律：

第一行是等差数列，因为第一列往下数了n-1个数，再往右上数了n-1个数，所以第一行下一个数是数了 2n -2 个数，等差数列。
最后一行，n-1 开头，2 * n - 2的等差数列
中间行：拆成竖列的数，等差为2 n-2 ，斜线上的数，也是公差2n-2的等差数列。是两个等差数列数列合并。斜线上的等差数列是以2n-2- 竖线上第一个数开头。
6.2 代码

也可以看蛇形矩阵这个题。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        // 第一行是索引0 ，索引公差是 2 * numRows - 2
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) {
                for (int j = i ; j < s.length(); j += 2 * numRows - 2) {
                    sb.append(s.charAt(j));
                }
            } else {
                // 有两个等差数列。第一个等差数列首项是i 第二个等差数列首项是 
                int j = 2 * numRows - 2 - i;
                int k = i;
                for (;k < s.length() || j < s.length();k += 2 * numRows - 2,j += 2 * numRows - 2 ) {
                    if (k < s.length()) {
                        sb.append(s.charAt(k));
                    }
                    if (j < s.length()) {
                        sb.append(s.charAt(j));
                    }
                }
            }
        }
        return sb.toString();
    }
}

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

注意：不能用long存。

7.1 思路

首先把数的每一位开始抠，% 10—> 个位数， / 10 抹掉个位数。

r = 0，r * 10 + 抠出来的个位数。

秦九韶算法的应用。

注意：正数 % 一个数是正数，负数 % 一个数是负数。发现这个算法也使用于负数。

7.2 代码

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x) {
            // 判断溢出。10res + x % 10 > max 整理一下就可以
            if (x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
            // 10 res + x % 10 <  min
            if (x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

8. 字符串转换整数（atoi）

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。

将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。

如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。

返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

8.1 思路

用longlong存
1. 1. 先把空格都去掉。

只用int

8.2 代码

```java class Solution { public: int myAtoi(string str) {

 int res = 0;
 int k = 0;
 // 空格字符都去掉。
 while (k < str.size() && str[k] == ' ') k ++ ;
 if (k == str.size()) return 0;

 int minus = 1;
 if (str[k] == '-') minus = -1, k ++ ;
 if (str[k] == '+')
     if (minus == -1) return 0;
     else k ++ ;

 while (k < str.size() && str[k] >= '0' && str[k] <= '9') {
     int x = str[k] - '0';
     // 正数的情况。
     if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX;

     // 负数的情况。-res * 10 - x < min
     if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;

     // 负数的绝对值比正数的绝对值多1.不特判会溢出。
     // 因为我们的res存的是绝对值。
     if (-res * 10 - x == INT_MIN) return INT_MIN;

     res = res * 10 + x;
     k ++ ;
 }

 res *= minus;
 return res;

} };



<a name="hE4ey"></a>
# 9.回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。<br /> 

示例 1：

输入：x = 121<br />输出：true

<a name="OlZjj"></a>
## 9.1 思路

1. 特判一下。
1. 用string 再reverse一下，看是否一样。
1. longlong把这个串倒序一下再比较~。
1. 不用把整个数都翻转，可以只用翻转一半。

<a name="KSXGG"></a>
## 9.2 代码
这个代码还是不要这么写了~
```java
class Solution {
public:
    bool isPalindrome(int x) {
        //特判
        if (x < 0 || x && x % 10 == 0) return false;
        int s = 0;
        while (s <= x)
        {
            s = s * 10 + x % 10;
            if (s == x || s == x / 10) return true; // 分别处理整数长度是奇数或者偶数的情况
            x /= 10;
        }
        return false;
    }
};

10.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。

10.1 思路

.* 可以匹配任何字符。

dp分析法：【递归循环】

状态表示。f(i,j)，所有的匹配方式（* 可以有多种解读）是否存在一个。

状态计算

*要枚举一下。

10.2 代码

class Solution {
public:
    vector<vector<int>>f;
    int n, m;
    bool isMatch(string s, string p) {
        n = s.size();
        m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string &s, string &p)
    {
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
        {
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }
};

class Solution {
    public boolean isMatch(String s, String p) {
        if (p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (j < p.length() && p.charAt(j) == '*') {
                    continue;
                }
                if (i > 0 && p.charAt(j - 1) != '*') {
                    dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                    && dp[i - 1][j - 1];

                } else if (j >= 2 && p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i][j - 2] || (i > 0 && dp[i - 1][j] && ( s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2)=='.'));
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

Week1 1~10

1. 两数之和

1.1 思路

1.2 代码

2.两数相加

2.1 思路

2.2 代码

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

3.1 思路

3.2 代码

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

4.1 思路

4.2 代码

5. 最长回文串

5.1 思路

5.2 代码

6. Z字型变换

6.1 思路

6.2 代码

7. 整数反转

7.1 思路

7.2 代码

8. 字符串转换整数（atoi）

8.1 思路

8.2 代码

10.正则表达式匹配

10.1 思路

10.2 代码