1 兩數(shù)之和

• 題目：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。

• 分析：暴力法、一遍哈希

public class TwoNum {
    // 暴力法
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[i] + nums[j]) == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // 一遍hashMap
    public int[] twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            //map中存(數(shù)，下標(biāo))
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

2 兩數(shù)相加

• 題目：給出兩個(gè)非空的鏈表表示兩個(gè)非負(fù)的整數(shù)。 生成一個(gè)各自位數(shù)上和的新鏈表，按照逆序讀出

image-20200712114351646.png

image-20200714183952987.png

public class addTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 相當(dāng)于頭結(jié)點(diǎn)，返回的是它的next結(jié)點(diǎn)
        ListNode resultNode = new ListNode(0);
        ListNode p = l1, q = l2, current = resultNode;
        // 進(jìn)位值carry
        int carry = 0;
        // p、q遍歷到末尾
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            // 每一位都開(kāi)始求和，carry每次都加上
            int sum = x + y + carry;
            // sum/10取高位值
            carry = sum / 10;
            // sum%10取末尾
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        // 如果到最后還進(jìn)位，就再生成一個(gè)進(jìn)位值的新結(jié)點(diǎn)
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        // 返回結(jié)果值頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開(kāi)始的鏈表
        return resultNode.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

3 最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度

• 滑動(dòng)窗口法：左指針不變，右指針枚舉不重復(fù)元素存入HashSet中；左指針發(fā)生改變，移除HashSet中重復(fù)上一個(gè)元素

/**
 * 求出一個(gè)字符串中的無(wú)重復(fù)子串的長(zhǎng)度
 */
public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        // 哈希Set不能存放重復(fù)元素
        HashSet<Character> set = new HashSet<>();
        int n = s.length();
        // 右指針：right 最長(zhǎng)無(wú)重復(fù)長(zhǎng)度：ans
        int right = -1, ans = 0;
        // 左指針：i
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                // 左指針向右移一個(gè)單位，set中移除所有左指針指向的元素
                set.remove(s.charAt(i - 1));
            }
            // 左指針i=0的時(shí)候，右指針不斷枚舉不含重復(fù)元素的值加入set
            while (right + 1 < n && !set.contains(s.charAt(right + 1))) {
                set.add(s.charAt(right + 1));
                right++;
            }
            // 每次長(zhǎng)度差都發(fā)生變化，取和上次長(zhǎng)度差的較大值賦給ans
            ans = Math.max(ans, right - i + 1);
        }
        return ans;
    }
}

4 兩個(gè)數(shù)組的中位數(shù)

• 題目：要求在兩個(gè)數(shù)組中找出中位數(shù)，時(shí)間復(fù)雜度O(log(m+n))
• 分析：出現(xiàn)log就是二分查找

/**
 * 給定兩個(gè)大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。
 * 請(qǐng)你找出這兩個(gè)正序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。
 */
public class FindMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;
        // 正序數(shù)組判斷奇數(shù)==1就行，標(biāo)準(zhǔn)寫(xiě)法是！=0
        // 總數(shù)是奇數(shù)
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1;
            int midIndex2 = totalLength / 2 ;
            int totalNum = getKElement(nums1, nums2, midIndex1 + 1) + getKElement(nums1, nums2, midIndex2 + 1);
            double median = totalNum / 2.0;
            return median;
        }
    }

    private int getKElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        // 起始下標(biāo)
        int index1 = 0;
        int index2 = 0;

        while (true) {
            // 邊界情況
            // 如果數(shù)組長(zhǎng)度為0，返回另一個(gè)數(shù)組k值
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            } else if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            // 以下是正常情況
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

}

5 最長(zhǎng)回文字符串

• 題目：找出一個(gè)字符串的最長(zhǎng)回文子串（回文串：正反讀都一樣）
• 暴力法：速度最慢
  1. 子串長(zhǎng)度<2，本身就是最大回文串
  2. 將字符串轉(zhuǎn)換成字符數(shù)組，防止下標(biāo)越界
  3. 兩次遍歷判斷出最長(zhǎng)回文長(zhǎng)度，返回子串

// 暴力法
    public String longestPalindrome1(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        char[] sCharArray = s.toCharArray();
        int strLen = 1;
        int index = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 枚舉所有長(zhǎng)度>2的子串
                if (j - i + 1 > strLen && isPalindrome(sCharArray, i, j)) {
                    strLen = j - i + 1;
                    index =i;
                }
            }
        }
        return s.substring(index,index+strLen);
    }

    private boolean isPalindrome(char[] charArray, int i, int j) {
        while (i < j) {
            if (charArray[i] != charArray[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

• 中心擴(kuò)散法：速度是前三種最快的
  1. 遍歷前步驟和暴力法相同
  2. 編寫(xiě)expandAroundCenter方法計(jì)算出字符串中心回文子串長(zhǎng)度，分為奇偶兩種情況，選最長(zhǎng)那個(gè)
  3. 當(dāng)前最>默認(rèn)最長(zhǎng)1，就交換最長(zhǎng)，更改起始坐標(biāo)；否則返回默認(rèn)最長(zhǎng)

image-20200713112020457.png

// 中心擴(kuò)散法
    public String longestPalindrome2(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        char[] sCharArray = s.toCharArray();
        int maxLen = 1;
        int begin = 0;
        for (int i = 0; i < n - 1; i++) {
            // 奇數(shù)
            int oddLen = expandAroundCenter(sCharArray, i, i);
            // 偶數(shù)
            int evenLen = expandAroundCenter(sCharArray, i, i + 1);
            // 選長(zhǎng)度大的
            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                // 畫(huà)圖發(fā)現(xiàn)規(guī)律
                begin = i - (maxLen - 1) / 2;
            }
        }
        return s.substring(begin, begin + maxLen);


    }

    private int expandAroundCenter(char[] charArray, int left, int right) {
        int len = charArray.length;
        int i = left;
        int j = right;
        // 從每個(gè)子串的中心開(kāi)始判斷
        while (i >= 0 && j < len) {
            if (charArray[i] == charArray[j]) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 跳出循環(huán)時(shí)，恰好s.charAt(i)!=s.charAt(j)
        // 回文長(zhǎng)度是 j - i +1 -2 = j-i -1 長(zhǎng)度不包含本身所以-2
        return j - i - 1;
    }

• 動(dòng)態(tài)規(guī)劃法：利用去掉兩頭還是回文串性質(zhì)

image-20200713112840520.png

image-20200713113136140.png

// 動(dòng)態(tài)規(guī)劃法
    public String longestPalindrome3(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        char[] sCharArray = s.toCharArray();
        int maxLen = 1;
        int begin = 0;
        // 初始化dp二維數(shù)組
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 從右上角開(kāi)始填=先行再列
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (sCharArray[i] != sCharArray[j]) {
                    dp[i][j] = false;
                } else {
                    // 邊界條件滿(mǎn)足：j-i<3 說(shuō)明中間只能有1個(gè)或0個(gè)元素，就保證肯定是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                    // 中間元素>1個(gè)，就參考其他元素 = 狀態(tài)轉(zhuǎn)移
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 如果當(dāng)前狀態(tài)true，且當(dāng)前長(zhǎng)度差>上次最長(zhǎng)長(zhǎng)度
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

• ManaChar算法：速度最快，但是絕大多數(shù)面試、筆試都不會(huì)問(wèn)，待學(xué)；

7 整數(shù)反轉(zhuǎn)

• 題目：給出一個(gè) 32 位的有符號(hào)整數(shù)，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。

public class Reverse {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x = x / 10;
            if (rev > (Integer.MAX_VALUE / 10) || ((rev == Integer.MAX_VALUE / 10) && pop > 7)) {
                return 0;
            } else if (rev < (Integer.MIN_VALUE / 10) || ((rev == Integer.MIN_VALUE / 10) && pop < (-8))) {
                return 0;
            }
            rev = rev * 10 + pop;
        }
        return rev;
    }

}

8 字符串轉(zhuǎn)換成整數(shù)

• 題目：使其能將字符串轉(zhuǎn)換成整數(shù)。該函數(shù)會(huì)根據(jù)需要丟棄無(wú)用的開(kāi)頭空格字符，直到尋找到第一個(gè)非空格的字符為止
  該字符串在有效的整數(shù)部分之后也可能會(huì)存在多余的字符，那么這些字符可以被忽略，它們對(duì)函數(shù)不應(yīng)該造成影響。
  注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符、字符串為空或字符串僅包含空白字符時(shí)，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換，即無(wú)法進(jìn)行有效轉(zhuǎn)換。在任何情況下，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)，請(qǐng)返回 0 。

 public int myAtoi(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        int idx = 0;
        // 去掉前導(dǎo)空格
        while (idx < n && chars[idx] == ' ') {
            idx++;
        }
        // 去掉空格以后到末尾
        if (idx == n) {
            return 0;
        }
        // 判斷是否存在負(fù)號(hào)
        boolean negative = false;
        if (chars[idx] == '-') {
            //遇到負(fù)號(hào)
            negative = true;
            idx++;
        } else if (chars[idx] == '+') {
            // 遇到正號(hào)
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            // 其他符號(hào)
            return 0;
        }
        int ans = 0;
        while (idx < n && Character.isDigit(chars[idx])) {
            int digit = chars[idx] - '0';
            // 越界 返回最大或最小
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本來(lái)應(yīng)該是 ans * 10 + digit > Integer.MAX_VALUE，但是前面兩者都有可能越界，所以移項(xiàng)表達(dá)
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            // 正常計(jì)算
            ans = ans * 10 + digit;
            idx++;
        }
        return negative ? -ans : ans;
    }

10 正則表達(dá)式匹配

• 題目：給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配。

//'.' 匹配任意單個(gè)字符
//'*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
 public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        // dp表示s的前i個(gè)字符和前j個(gè)字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 兩個(gè)空字符串匹配
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (match(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    if (match(s, p, i, j)) {
                        dp[i][j] =dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }
    // 判端兩字中間字符是否相同
    private boolean match(String s, String p, int i, int j) {
        // i=0,j=1是最初的開(kāi)始，表示空字符串不與一個(gè)字符的字符串匹配
        if (i == 0) {
            return false;
        }
        // . 規(guī)定一定能匹配任意字符
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

11 盛水最多的容器

• 題目：給你 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫(huà) n 條垂直線(xiàn)，垂直線(xiàn) i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線(xiàn)，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
  說(shuō)明：你不能傾斜容器，且 n 的值至少為 2。

image-20200716152404181.png

// 雙指針?lè)?public int maxArea(int[] height) {
    int i = 0;
    int j = height.length - 1;
    int ans = 0;
    while (i < j) {
        int area = Math.min(height[i], height[j]) * (j - i);
        ans = Math.max(area, ans);
        // 每次都移動(dòng)下的指針
        if (height[i] <= height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return ans;
}

// 暴力破解
public int maxArea1(int[] height) {
    int ans = 0;
    int NowValue;
    for (int i = 0; i < height.length; i++) {
        for (int j = i; j < height.length; j++) {
            NowValue = Math.min(height[i], height[j]) * (j - i);
            ans = Math.max(NowValue,ans);
        }
    }
    return ans;
}

13 羅馬數(shù)字轉(zhuǎn)換

• 題目：羅馬數(shù)字包含以下七種字符: I， V， X， L，C，D 和 M

• I 可以放在 V (5) 和 X (10) 的左邊，來(lái)表示 4 和 9。
  X 可以放在 L (50) 和 C (100) 的左邊，來(lái)表示 40 和 90。
  C 可以放在 D (500) 和 M (1000) 的左邊，來(lái)表示 400 和 900

字符          數(shù)值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

public int romanToInt(String s) {
        int sum = 0;
        // 獲取第一位的值
        int preNum = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int nextNow = getValue(s.charAt(i));
            if (preNum < nextNow) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = nextNow;
        }
        // 此時(shí)preNum 就是最后一位的值，得加上
        sum += preNum;
        return sum;
    }

    private int getValue(char c) {
        switch (c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

14 最長(zhǎng)公共前綴

題目：編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。如果不存在公共前綴，返回空字符串 ""。

 public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs == null){
            return "";
        }
        String s1 = strs[0];
        for (int i = 1; i < strs.length; i++) {
            s1 = selectLongesCommonStr(s1, strs[i]);
            if (s1.length() == 0) {
                break;
            }
        }
        return s1;
    }

    private String selectLongesCommonStr(String s1, String s2) {
        int length = Math.min(s1.length(), s2.length());
        int index = 0;
        while (index < length && s1.charAt(index) == s2.charAt(index)) {
            index++;
        }
        // 跳出循環(huán)時(shí)，index = index+1，在substring中右邊就正確
        return s1.substring(0, index);
    }

15 三數(shù)之和

題目：給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有滿(mǎn)足條件且不重復(fù)的三元組。

 public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 將nums從小到大排序
        Arrays.sort(nums);
        // 一指針從0開(kāi)始枚舉
        for (int i = 0; i < n; i++) {
            // 和上次枚舉數(shù)不同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 三指針指向數(shù)組最右端
            int k = n - 1;
            // 二指針從一指針后面開(kāi)始枚舉
            for (int j = i + 1; j < n; j++) {
                // 上次枚舉數(shù)不同
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 二指針保證在三支針左邊，并且三者加的數(shù)大于0，就三指針左移
                while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                }
                // 如果二三指針重合，表示沒(méi)有三數(shù)之和為0，跳出循環(huán)
                if (j == k) {
                    break;
                }
                if (nums[i] + nums[j] + nums[k] == 0) {
                    // 結(jié)果集是鏈表套鏈表
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

17 電話(huà)號(hào)碼的字母組合

• 題目：給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。給出數(shù)字到字母的映射如下（與電話(huà)按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

public class LetterCom {
    List<String> ans = new ArrayList<>();

    Map<String, String> nums = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0) {
            callBack("", digits);
        }
        return ans;
    }

    /**
     * @param comb   組合結(jié)果
     * @param digits 數(shù)字
     */
    private void callBack(String comb, String digits) {
        // 遞歸結(jié)束提交時(shí)當(dāng)前數(shù)字長(zhǎng)度=0，往ans中加組合結(jié)果
        if (digits.length() == 0) {
            ans.add(comb);
        } else {
            // 獲取數(shù)字串中的第一個(gè)數(shù)字
            String digit = digits.substring(0, 1);
            // 通過(guò)數(shù)字獲得對(duì)應(yīng)的全部字母
            String letters = nums.get(digit);
            // 全部字母遞歸
            for (int i = 0; i < letters.length(); i++) {
                String letter = nums.get(digit).substring(i, i + 1);
                // substring(1)從1開(kāi)始到末尾
                callBack(comb + letter, digits.substring(1));
            }
        }
    }
}

19 刪除倒數(shù)第n個(gè)節(jié)點(diǎn)的鏈表

• 題目：給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

public class RemoveNthFromEnd {
    // 兩次遍歷，第一次遍歷找出長(zhǎng)度;第二次遍歷刪除倒數(shù)第n個(gè)節(jié)點(diǎn)
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // 啞結(jié)點(diǎn)，在head的前一個(gè)結(jié)點(diǎn)
        ListNode ans = new ListNode(0);
        ans.next = head;
        int length = 0;
        // 遍歷指針,先遍歷head結(jié)點(diǎn)找出長(zhǎng)度；再遍歷啞結(jié)點(diǎn)
        ListNode i = head;
        // 注意別是i.next
        while (i != null) {
            length++;
            i = i.next;
        }
        length -= n;
        i = ans;
        // i遍歷到length - 的位置
        while (length > 0) {
            length--;
            i = i.next;
        }
        // 刪除倒數(shù)第n個(gè)節(jié)點(diǎn)
        i.next = i.next.next;
        // 返回ans.next，因?yàn)閱〗Y(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)才是head
        return ans.next;

    }

    // 一次遍歷法，i指針指向第n+1個(gè)節(jié)點(diǎn);j從頭開(kāi)始遍歷；i到達(dá)結(jié)尾時(shí)，i到j(luò)距離就是n
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode ans = new ListNode(0);
        ans.next = head;
        // i、j的
        ListNode i = ans;
        ListNode j = ans;
        for (int k = 1; k <= n + 1; k++) {
            i = i.next;
        }
        while (i != null) {
            i = i.next;
            j = j.next;
        }
        j.next = j.next.next;
        return ans.next;
    }
}

20 有效的括號(hào)

題目：給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿(mǎn)足：

左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。

public class IsValid {
    // 存括號(hào)集合
    HashMap<Character, Character> mapperings;

    // 初始化括號(hào)存進(jìn)map
    public IsValid() {
        mapperings = new HashMap<>();
        mapperings.put(')', '(');
        mapperings.put('}', '{');
        mapperings.put(']', '[');
    }

    public boolean isValid(String s) {
        // 初始化棧保存括號(hào)
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (mapperings.containsKey(c)) {
                // 匹配到閉括號(hào)，就出棧頂元素
                char topEle = stack.empty() ? '#' : stack.pop();
                // 如果棧頂元素不對(duì)因當(dāng)前字符對(duì)應(yīng)的開(kāi)括號(hào)，就失敗
                if (topEle != mapperings.get(c)) {
                    return false;
                }
            } else {
                // 沒(méi)有匹配到閉括號(hào)，就進(jìn)棧
                stack.push(c);
            }
        }
        // 返回棧是否為空的狀態(tài)
        return stack.isEmpty();
    }
}

21 合并兩個(gè)有序鏈表

• 題目：將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

class ListNode1 {
    int val;
    ListNode1 next;

    ListNode1() {
    }

    ListNode1(int val) {
        this.val = val;
    }

    ListNode1(int val, ListNode1 next) {
        this.val = val;
        this.next = next;
    }
}

public class MergeTwoLists {
    // 遞歸法
    public ListNode1 mergeTwoLists1(ListNode1 l1, ListNode1 l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        // 從較小值的那個(gè)鏈表開(kāi)始遞歸
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists1(l1, l2.next);
            return l2;
        }
    }

    //迭代法
    public ListNode1 mergeTwoLists2(ListNode1 l1, ListNode1 l2) {
        ListNode1 preHead = new ListNode1(-1);
        ListNode1 pre = preHead;
        while (l1 != null && l2 != null) {
            // 每次選擇值下的指向
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        //循環(huán)結(jié)束后，必有一個(gè)指向null，連接不null就行
        pre.next = (l1 == null) ? l2 : l1;
        return preHead.next;
    }
}

23 合成k個(gè)排序的鏈表

• 題目：合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。
• 待學(xué)遞歸和迭代法

public class MergeKLists {
    // 方法一：每次比較出minNode來(lái)合并鏈表
    public ListNode mergeKLists1(ListNode[] lists) {
        int n = lists.length;
        // 啞結(jié)點(diǎn)
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (true) {
            // 創(chuàng)建最小值結(jié)點(diǎn)存最小值，最小值指針指向鏈表最小值下標(biāo)
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < n; i++) {
                // 本次循環(huán)跳出
                if (lists[i] == null) {
                    continue;
                }
                // 遍歷找出最小值結(jié)點(diǎn)和下標(biāo)
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;
                }
            }
            // 如果最小值下標(biāo)是-1，結(jié)束循環(huán)
            if (minPointer == -1) {
                break;
            }
            // tail指針指向最小值結(jié)點(diǎn)
            tail.next = minNode;
            tail = tail.next;
            // 最小值結(jié)點(diǎn)指針后移重新比較
            lists[minPointer] = lists[minPointer].next;
        }
        return dummy.next;
    }

    // 方法一：使用pq小根堆優(yōu)化方法二
    public ListNode mergeKLists2(ListNode[] lists) {
        // 使用優(yōu)先級(jí)隊(duì)列存小根堆,參數(shù)是選擇結(jié)點(diǎn)值從小
        PriorityQueue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        // 將數(shù)組各個(gè)首結(jié)點(diǎn)，放入小根堆
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        // 創(chuàng)建啞結(jié)點(diǎn)
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        // 遍歷輸出
        while (!pq.isEmpty()) {
            // 最小值結(jié)點(diǎn)指向根頂元素
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            // 將首節(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)放入根堆
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }
        return dummy.next;
    }

    // 后面待學(xué)迭代和遞歸
}

26 刪除數(shù)組中重復(fù)的元素

• 題目：給定一個(gè)排序數(shù)組，你需要在 原地 刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。

public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                // 不等于先移動(dòng)i指針，此時(shí)i指向的是相同的數(shù)
                // 如果先移動(dòng)i，那么i指向的第一個(gè)數(shù)就丟失
                i++;
                // 相同的元素才能進(jìn)行交換
                nums[i] = nums[j];
            }
        }
        // 數(shù)組長(zhǎng)度=末尾數(shù)組下標(biāo)+1
        return i + 1;
    }

28 實(shí)現(xiàn)strStr

• 題目：給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開(kāi)始)。如果不存在，則返回 -1。

public class StrStr {
    // 滑動(dòng)窗口法
    public int strStr1(String haystack, String needle) {
        if (needle.isEmpty() || needle.equals("")) {
            return 0;
        }
        int n = haystack.length();
        int l = needle.length();
        // 暴力，每一個(gè)長(zhǎng)度的都比較，所以時(shí)間復(fù)雜度比較高
        for (int i = 0; i < n - l + 1; i++) {
            // 選擇hay中的長(zhǎng)度為l的子串與needle比較
            if (haystack.substring(i, i + l).equals(needle)) {
                return i;
            }
        }
        return -1;
    }

    // 雙指針?lè)?    public int strStr2(String haystack, String needle) {
        int n = haystack.length();
        int l = needle.length();
        if (l == 0) {
            return 0;
        }
        // 右指針遍歷hay
        int pn = 0;
        // pn最末只能在hay中最后l長(zhǎng)度的起始點(diǎn)
        while (pn < n - l + 1) {
            if (pn < n - l + 1 && haystack.charAt(pn) != needle.charAt(0)) {
                pn++;
            }
            int currentLen = 0;
            // 左指針遍歷needle
            int pl = 0;
            while (pl < l && pn < n && haystack.charAt(pn) == needle.charAt(pl)) {
                pl++;
                pn++;
                currentLen++;
            }
            //如果needle匹配到
            if (currentLen == l) {
                return pn - l;
            }
            // 不匹配就回溯下標(biāo)
            pn = pn - currentLen + 1;
        }
        // 如果循環(huán)沒(méi)有返回，就返回失敗
        return -1;
    }

}