Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

大致意思：

给定一个整数数组，返回两个数字的索引，使它们相加到特定目标数值。

您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int>result;
        for(int i = 0; i < size - 1; i++) {
            for(int j = i+1; j < size; j++){
                if (nums[i] + nums[j] == target) {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
    }
};

第一次在LeetCode上做算法题，重拾了很久没接触过的代码，采用了暴力解法

思路：暴力求解，直接遍历vector中的值进行相加求和

注意：暴力求解可能会遇到两个坑

1、对 j 的取值范围不清，j = i导致可能会在同一个数上进行求和

2、同上，j = 0可能会在开头就满足了两数相同但是和可以得到target

PS: 看到solution之后惊了，原来算法要考虑复杂度的问题，貌似暴力遍历的话时间复杂度是O（n^2）

solution基本都是用哈希表方式解决，遍历列表中的n个元素只需要一次

solution（Java）：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

前言

1.两数之和

难度系数：🚩

🚀 题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：

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

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 
🚀 答案
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    res[0]=i;
                    res[1]=j;
                    break;
                }
            }
        }
        return res;
    }
}

2.两数相加

难度系数：🚩

🚀 题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。

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

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

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

🚀 答案
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //结果链表虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        //结果链表工作指针
        ListNode cur = dummyNode;
        //定义进位
        int carry = 0;
        //模拟两数相加
        while(l1 != null || l2 != null){
            //本题难点：如果l1为空，l2不为空，则将l1的空对应值置为0，否则置为l1.val。l2亦然。
            //此处需要画图理解。
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;
            //两数原始和（0-18）
            int sum = x + y + carry;
            //进位
            carry = sum / 10;
            //两数和（0-9）
            sum = sum % 10;
            //sum = sum / 10; 这里第一次搞错了，记录。
            //新建链表结点，将val赋值为sum
            cur.next = new ListNode(sum);
            //指针后移到新结点上
            cur = cur.next;
            //两个工作指针后移
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        //难点：最后的进位是特殊情况，需要增加新结点并赋val值为1
        if(carry == 1){
            cur.next = new ListNode(1);
        }
        //返回结果链表的头结点
        return dummyNode.next;
    }
}

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

难度系数：🚩🚩

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

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

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 
🚀 答案
class Solution {
    public int lengthOfLongestSubstring(String s) {
       //如果s为空，length不大于0，是一个空串，就没有向下执行的必要了
        if(s != null && s.length() > 0 && s != ""){
            //String -> char[]
            char[] strChar = s.toCharArray();
            // 存储最长字串 key:char值，value:index下标
            ArrayList<String> maxStr = new ArrayList<>();
            //临时的字串存储空间
            ArrayList<String> tempStr = new ArrayList<>();
            //循环
            for(int i=0; i<strChar.length; i++){
                //char -> String
                String str = new String(new char[]{strChar[i]});
                //判断str是否存在于tempStr中
                if(tempStr.contains(str)){
                    //先判断tempStr的长度是否大于等于maxStr的长度,大于，才能将最长字串覆盖
                    if(tempStr.size() > maxStr.size()){
                        maxStr = new ArrayList<>(tempStr);
                    }
                    //存储重复字符
                    int reIndex = tempStr.indexOf(str);
                    // 删除tempStr中的重复字节及其之前的字符
                    for(int j=0;j<=reIndex;j++){
                        tempStr.remove(0);
                    }
                }
                //将当前字符存入tempStr中
                tempStr.add(str);
            }
            //最终判断
            if(tempStr.size() > maxStr.size()){
                maxStr = tempStr;
            }
            //返回最长字串的长度
            return maxStr.size();
        }
        return 0;
    }
}

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

难度系数：🚩🚩🚩

🚀 题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。


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

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

🚀 答案
class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int n1=a.length,n2=b.length,n3=n1+n2,aindex=0,bindex=0;
		boolean ds=n3%2==0;
		int end = n3/2+1;
		int ne=0,ne1=0,ne2=0;
	    for(int i=0;i<end;i++) {
	    	ne = bindex==n2 || ( aindex<n1 &&a[aindex]<=b[bindex] )? a[aindex++]:b[bindex++];
	    	if(i==end-2) ne1=ne;
	    	if(i==end-1) ne2=ne;
	    }
		return ds?(double)(ne1+ne2)/2:ne2;
    }
}

5.最长回文子串

难度系数：🚩🚩

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

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

示例 2：
输入：s = "cbbd"
输出："bb"

🚀 答案
本题利用了中心扩展法
class Solution {
    public String longestPalindrome(String s) {
        char[] cs = s.toCharArray();
        int res = 0;
        int max = 0;
        int start = 0, end = 0;
        String ans = "";
        for(int i = 0;i < cs.length; i++){
            int left = i - 1, right = i + 1;
            while(left >= 0 && cs[left] == cs[i]) left--;
            while(right < cs.length && cs[right] == cs[i]) right++;
            while(left >= 0 && right < cs.length && cs[left] == cs[right]){
                left--;
                right++;
            }
            max = Math.max(max, right - left - 1);
            res = right - left - 1;
            //System.out.println(" i = " + i + " l = " + left + " r = " + right);
            if(res == max){
                //left和right退出循环的话会多移动一位，所以要移动回去
                start = left + 1;
                end = right - 1;
                //System.out.println(start + "  " + end);
            }
        }
        //左闭右开区间，所以end + 1
        return s.substring(start, end + 1);
    }
}

6. Z字形变换

难度系数：🚩🚩

🚀 题目
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
 

示例 1：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 2：

输入：s = "A", numRows = 1
输出："A"


🚀 答案

每行初始值为i;
第1行和第n行，每次加a = (2n-1)；
中间其余行，每次加b，b初始值为a-2i，其余b = a - b

class Solution {
    public String convert(String s, int numRows) {
        if(numRows==1){
            return s;
        }
        StringBuilder sb = new StringBuilder();
        int a = 2 * (numRows - 1);
        for (int i = 0; i < numRows; i++) {
            int c = i;
            if(i==0||i==numRows-1){
                while (c<s.length()){
                    sb.append(s.charAt(c));
                    c = c + a;
                }
            }else {
                int b = a-2*i;
                while (c < s.length()) {
                    sb.append(s.charAt(c));
                    c = c + b;
                    b = a - b;
                }
            }
        }
        return sb.toString();
    }
}

7.整数反转

难度系数：🚩

🚀 题目
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
 

示例 1：
输入：x = 123
输出：321

示例 2：
输入：x = -123
输出：-321

示例 3：
输入：x = 120
输出：21

示例 4：
输入：x = 0
输出：0

🚀 答案
class Solution {
    public int reverse(int x) {
        long n = 0;
        while(x != 0) {
            n = n*10 + x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }
}

8.字符串转换整数 (atoi)

难度系数：🚩🚩

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

函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
 
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。


示例 2：
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。


示例 3：、
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。


🚀 答案
public class Solution {
    public int myAtoi(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        int idx = 0;
        while (idx < n && chars[idx] == ' ') {
            // 去掉前导空格
            idx++;
        }
        if (idx == n) {
            //去掉前导空格以后到了末尾了
            return 0;
        }
        boolean negative = false;
        if (chars[idx] == '-') {
            //遇到负号
            negative = true;
            idx++;
        } else if (chars[idx] == '+') {
            // 遇到正号
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            // 其他符号
            return 0;
        }
        int ans = 0;
        while (idx < n && Character.isDigit(chars[idx])) {
            int digit = chars[idx] - '0';
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit;
            idx++;
        }
        return negative? -ans : ans;
    }
}

9.正则表达式匹配

难度系数：🚩🚩🚩

🚀 题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

 
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。
因此，字符串 "aa" 可被视为 'a' 重复了一次。


示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 

提示：

1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

🚀 答案

本次使用了动态规划的方法

class Solution {
    public boolean isMatch(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        if(sl != 0 && pl == 0){
            return false;
        }
        //dp[i][j]：s[i...]和p[j...]（从0开始）是否匹配
        boolean[][] dp = new boolean[sl+1][pl+1];
        //base case
        dp[sl][pl] = true;//两个空字符串肯定是匹配的
        //s是空时，p可能也可以匹配空字符串
        for(int i = pl-1; i >= 0; i--){
            if(p.charAt(i) == '*'){
                dp[sl][i] = dp[sl][i + 1];
            }else{
                if(i+1 < pl && p.charAt(i + 1) == '*'){
                    dp[sl][i] = dp[sl][i+1];
                }
            }   
        }

        for(int i = sl-1; i >= 0; i--){
            for(int j = pl-1; j >= 0; j--){
                //1.若p[j]是*
                if(p.charAt(j) == '*'){
                    //1.1若p[j-1]=s[i]或. ，那这个*可能把p[j-1]多匹配几个来，也可能匹配成0个
                    if(p.charAt(j-1) == s.charAt(i) || p.charAt(j-1) == '.'){
                        dp[i][j] = dp[i+1][j] || dp[i][j+1];
                    }else{//1.2 若p[j-1]啥也不是，那*只能把p[j-1]匹配为0个，然后看后面了
                        dp[i][j] = dp[i][j+1];
                    }
                }//2.若p[j]=s[i]或者.
                else if(p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)){
                    if(j+1 < pl && p.charAt(j+1) == '*'){
                    //2.1 p[j+1]为*,又有匹配成0个或多个的情况
                        dp[i][j] = dp[i+1][j] || dp[i][j+1];
                    }else{//2.2 p[j+1]不是*，那就直接都加1了
                        dp[i][j] = dp[i+1][j+1];
                    }
                }//3. 若p[j]既不是*也不是.和s[i]，但是p[j+1]是*，还能做最后的挣扎
                else if(j+1 < pl && p.charAt(j+1) == '*'){
                        dp[i][j] = dp[i][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

10.盛最多水的容器

难度系数：🚩🚩🚩

🚀 题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。


示例 2：
输入：height = [1,1]
输出：1


🚀 答案
双指针 第一次不看题解有思路 看来多刷题真的很有用
class Solution {
    public int maxArea(int[] height) {
        if (null == height) {
            return 0;
        }
        int res = 0;
        // 双指针
        int l = 0, r = height.length - 1;
        while (l < r) {
            // 记住较短的柱子
            int lower = 0;
            if (height[l] < height[r]) {
                // 左边短，左边移动
                lower = height[l++];
            } else {
                // 右边短，右边移动
                lower = height[r--];
            }

            // 用较短的柱子乘上距离得容量
            res = Math.max(res, (r + 1 - l) * lower);
        }

        return res;
    }
}