1 兩數(shù)之和

• 題目：給定一個整數(shù)數(shù)組 nums 和一個目標值 target窗声，找出和為目標值的那 兩個 整數(shù)承绸，并返回他們的數(shù)組下標兜蠕。

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

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ù)莱预，下標)
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

2 兩數(shù)相加

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

image-20200712114351646.png

image-20200714183952987.png

public class addTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 相當于頭結(jié)點锁施，返回的是它的next結(jié)點
        ListNode resultNode = new ListNode(0);
        ListNode p = l1, q = l2, current = resultNode;
        // 進位值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;
            // 每一位都開始求和，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;
            }
        }
        // 如果到最后還進位悉抵，就再生成一個進位值的新結(jié)點
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        // 返回結(jié)果值頭結(jié)點的下一個結(jié)點開始的鏈表
        return resultNode.next;
    }
}

class ListNode {
    int val;
    ListNode next;

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

3 最長無重復子串長度

• 滑動窗口法：左指針不變肩狂，右指針枚舉不重復元素存入HashSet中；左指針發(fā)生改變姥饰，移除HashSet中重復上一個元素

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

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

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

/**
 * 給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2谈飒。
 * 請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復雜度為 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就行杭措，標準寫法是！=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;
        // 起始下標
        int index1 = 0;
        int index2 = 0;

        while (true) {
            // 邊界情況
            // 如果數(shù)組長度為0钾恢，返回另一個數(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 最長回文字符串

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

// 暴力法
    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++) {
                // 枚舉所有長度>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;
    }

• 中心擴散法：速度是前三種最快的
  1. 遍歷前步驟和暴力法相同
  2. 編寫expandAroundCenter方法計算出字符串中心回文子串長度泉懦，分為奇偶兩種情況，選最長那個
  3. 當前最>默認最長1疹瘦，就交換最長崩哩，更改起始坐標；否則返回默認最長

image-20200713112020457.png

// 中心擴散法
    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);
            // 選長度大的
            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                // 畫圖發(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;
        // 從每個子串的中心開始判斷
        while (i >= 0 && j < len) {
            if (charArray[i] == charArray[j]) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 跳出循環(huán)時言沐，恰好s.charAt(i)!=s.charAt(j)
        // 回文長度是 j - i +1 -2 = j-i -1 長度不包含本身所以-2
        return j - i - 1;
    }

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

image-20200713112840520.png

image-20200713113136140.png

// 動態(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;
        }
        // 從右上角開始填=先行再列
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (sCharArray[i] != sCharArray[j]) {
                    dp[i][j] = false;
                } else {
                    // 邊界條件滿足：j-i<3 說明中間只能有1個或0個元素邓嘹，就保證肯定是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                    // 中間元素>1個，就參考其他元素 = 狀態(tài)轉(zhuǎn)移
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 如果當前狀態(tài)true呢灶，且當前長度差>上次最長長度
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

• ManaChar算法：速度最快吴超，但是絕大多數(shù)面試、筆試都不會問鸯乃，待學鲸阻；

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

• 題目：給出一個 32 位的有符號整數(shù)，你需要將這個整數(shù)中每位上的數(shù)字進行反轉(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ù)會根據(jù)需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止
  該字符串在有效的整數(shù)部分之后也可能會存在多余的字符奖年，那么這些字符可以被忽略细诸，它們對函數(shù)不應(yīng)該造成影響。
  注意：假如該字符串中的第一個非空格字符不是一個有效整數(shù)字符陋守、字符串為空或字符串僅包含空白字符時震贵，則你的函數(shù)不需要進行轉(zhuǎn)換，即無法進行有效轉(zhuǎn)換水评。在任何情況下猩系，若函數(shù)不能進行有效的轉(zhuǎn)換時，請返回 0 中燥。

 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) {
                // 本來應(yīng)該是 ans * 10 + digit > Integer.MAX_VALUE寇甸，但是前面兩者都有可能越界，所以移項表達
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            // 正常計算
            ans = ans * 10 + digit;
            idx++;
        }
        return negative ? -ans : ans;
    }

10 正則表達式匹配

• 題目：給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配拿霉。

//'.' 匹配任意單個字符
//'*' 匹配零個或多個前面的那一個元素
 public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        // dp表示s的前i個字符和前j個字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 兩個空字符串匹配
        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是最初的開始吟秩，表示空字符串不與一個字符的字符串匹配
        if (i == 0) {
            return false;
        }
        // . 規(guī)定一定能匹配任意字符
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

11 盛水最多的容器

• 題目：給你 n 個非負整數(shù) a1，a2绽淘，...涵防，an，每個數(shù)代表坐標中的一個點 (i, ai) 收恢。在坐標內(nèi)畫 n 條垂直線武学，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)祭往。找出其中的兩條線伦意，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
  說明：你不能傾斜容器硼补，且 n 的值至少為 2驮肉。

image-20200716152404181.png

// 雙指針法
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);
        // 每次都移動下的指針
        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) 的左邊卵渴，來表示 4 和 9。
  X 可以放在 L (50) 和 C (100) 的左邊鲤竹，來表示 40 和 90浪读。
  C 可以放在 D (500) 和 M (1000) 的左邊，來表示 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;
        }
        // 此時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 最長公共前綴

題目：編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴碘橘。如果不存在公共前綴，返回空字符串 ""吱肌。

 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)時痘拆，index = index+1，在substring中右邊就正確
        return s1.substring(0, index);
    }

15 三數(shù)之和

題目：給你一個包含 n 個整數(shù)的數(shù)組 nums氮墨，判斷 nums 中是否存在三個元素 a纺蛆，b，c 规揪，使得 a + b + c = 0 桥氏？請你找出所有滿足條件且不重復的三元組。

 public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 將nums從小到大排序
        Arrays.sort(nums);
        // 一指針從0開始枚舉
        for (int i = 0; i < n; i++) {
            // 和上次枚舉數(shù)不同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 三指針指向數(shù)組最右端
            int k = n - 1;
            // 二指針從一指針后面開始枚舉
            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--;
                }
                // 如果二三指針重合，表示沒有三數(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 電話號碼的字母組合

• 題目：給定一個僅包含數(shù)字 2-9 的字符串祥款，返回所有它能表示的字母組合清笨。給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(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ù)字長度=0抠艾，往ans中加組合結(jié)果
        if (digits.length() == 0) {
            ans.add(comb);
        } else {
            // 獲取數(shù)字串中的第一個數(shù)字
            String digit = digits.substring(0, 1);
            // 通過數(shù)字獲得對應(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開始到末尾
                callBack(comb + letter, digits.substring(1));
            }
        }
    }
}

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

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

public class RemoveNthFromEnd {
    // 兩次遍歷，第一次遍歷找出長度;第二次遍歷刪除倒數(shù)第n個節(jié)點
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // 啞結(jié)點蛙酪，在head的前一個結(jié)點
        ListNode ans = new ListNode(0);
        ans.next = head;
        int length = 0;
        // 遍歷指針,先遍歷head結(jié)點找出長度齐苛；再遍歷啞結(jié)點
        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個節(jié)點
        i.next = i.next.next;
        // 返回ans.next，因為啞結(jié)點的下一個結(jié)點才是head
        return ans.next;

    }

    // 一次遍歷法桂塞，i指針指向第n+1個節(jié)點;j從頭開始遍歷凹蜂；i到達結(jié)尾時，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 有效的括號

題目：給定一個只包括 '('玛痊，')'，'{'狂打，'}'擂煞，'['，']' 的字符串趴乡，判斷字符串是否有效对省。有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合浙宜。
注意空字符串可被認為是有效字符串官辽。

public class IsValid {
    // 存括號集合
    HashMap<Character, Character> mapperings;

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

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

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

21 合并兩個有序鏈表

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

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;
        }
        // 從較小值的那個鏈表開始遞歸
        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é)束后俗批，必有一個指向null，連接不null就行
        pre.next = (l1 == null) ? l2 : l1;
        return preHead.next;
    }
}

23 合成k個排序的鏈表

• 題目：合并 k 個排序鏈表市怎，返回合并后的排序鏈表岁忘。請分析和描述算法的復雜度。
• 待學遞歸和迭代法

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

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

    // 后面待學迭代和遞歸
}

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

• 題目：給定一個排序數(shù)組，你需要在 原地 刪除重復出現(xiàn)的元素麻汰，使得每個元素只出現(xiàn)一次速客，返回移除后數(shù)組的新長度。不要使用額外的數(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]) {
                // 不等于先移動i指針，此時i指向的是相同的數(shù)
                // 如果先移動i位喂，那么i指向的第一個數(shù)就丟失
                i++;
                // 相同的元素才能進行交換
                nums[i] = nums[j];
            }
        }
        // 數(shù)組長度=末尾數(shù)組下標+1
        return i + 1;
    }

28 實現(xiàn)strStr

• 題目：給定一個 haystack 字符串和一個 needle 字符串浪耘，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在塑崖，則返回 -1七冲。

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

    // 雙指針法
    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長度的起始點
        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;
            }
            // 不匹配就回溯下標
            pn = pn - currentLen + 1;
        }
        // 如果循環(huán)沒有返回癞埠，就返回失敗
        return -1;
    }

}