【面试】Leetcode2022秋招算法

leetcode 2022年 秋招算法题

1 数组

1.1 两数之和

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

// 【哈希表】
// 优点：消耗内存，节省时间，一次循环解决
// 将数据存入Map中，记录num和index，寻找target-nums[i]值
public static int[] twoSum2(int[] nums, int target) {
    Map<Integer, Integer> subTarget = new HashMap<>();
    for (int i=0; i<nums.length; i++) {
        if (subTarget.containsKey(target - nums[i])) {
            return new int[]{subTarget.get(target - nums[i]), i};
        }
        subTarget.put(nums[i], i);
    }
    return new int[0];
}

---

1.2 三数之和

• 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

// 【排序 + 双指针】
// 当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法
public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    // 排序，方便去重
    Arrays.sort(nums);
    for (int first=0; first<nums.length-2; first++) {
        // 有序数组，first元素>0，结束循环
        if (nums[first] > 0) {
            break;
        }
        // first去重
        if (first > 0 && nums[first] == nums[first-1]) {
            continue;
        }
        int third = nums.length - 1;
        for (int second=first+1; second<nums.length-1; second++) {
            // second去重
            if (second > first+1 && nums[second] == nums[second-1]) {
                continue;
            }
            // 保证second 在 third 左边，并移动 third 直至和<=0
            while (second < third && nums[first]+nums[second]+nums[third] > 0) {
                third --;
            }
            // 双指针重合时，往后的三者之和数必定>0，结束second循环
            if (second == third) {
                break;
            }
            if (nums[first]+nums[second]+nums[third] == 0) {
                result.add(new ArrayList<>(Arrays.asList(nums[first], nums[second], nums[third])));
            }
        }
    }
    return result;
}

---

1.3 合并两个有序数组

• 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

// 正常思路为双指针，新开一个数组，双指针比较，小的放入新数组，指针后移
// 【逆双指针】
// 示例nums1后面数组为空，可以直接覆盖，不用新开数组，从后往前比较大小
public void merge2(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    int index = m + n - 1;
    while (j >= 0) {
        if (i == -1 || nums1[i] < nums2[j]) {
            nums1[index] = nums2[j];
            j--;
        } else {
            nums1[index] = nums1[i];
            i--;
        }
        index--;
    }
    System.out.println(Arrays.toString(nums1));
}

---

1.4 螺旋矩阵

• 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

// 【按层模拟】
// 类似同心圆，从外层到里层，转一圈为一个循环
public static int[][] generateMatrix(int n) {
    // 初始化
    int[][] matrix = new int[n][n];
    int left = 0;
    int top = 0;
    int right = n - 1;
    int bottom = n - 1;
    int num = 1;
    // 按层循环
    while (left <= right && top <= bottom) {
        // 向右移动 →
        for (int column = left; column <= right; column ++) {
            matrix[top][column] = num;
            num ++;
        }
        // 向下移动 ↓
        for (int row = top + 1; row <= bottom; row ++) {
            matrix[row][right] = num;
            num ++;
        }
        // 向左移动 ←
        for (int column = right - 1; column >= left; column --) {
            matrix[bottom][column] = num;
            num ++;
        }
        // 向上移动 ↑
        for (int row = bottom -1; row >= top + 1; row --) {
            matrix[row][left] = num;
            num ++;
        }
        left ++;
        right --;
        top ++;
        bottom --;
    }
    return matrix;
}

---

2 字符串

2.1 有效的括号

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
• 有效字符串需满足：
  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

// 【栈】
// （规律）当遇到第一个右括号时，栈顶必定为对应的左括号；匹配后栈顶出栈，依次循环
public static boolean isValid(String s) {
    // 合法性判断，奇数一定不合法
    if (s.length() % 2 != 0) {
        return false;
    }
    // Map存储对应关系，方便处理
    Map<Character, Character> charMap = new HashMap<>();
    charMap.put(')', '(');
    charMap.put(']', '[');
    charMap.put('}', '{');
    // 栈处理
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        // 匹配到右括号，判断栈顶左括号
        if (charMap.containsKey(c)) {
            if (stack.empty() || !stack.peek().equals(charMap.get(c))) {
                return false;
            }
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

---

2.2 字符串相加

• 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

输入：num1 = "11", num2 = "123"
输出："134"

// 【模拟竖直相加】
// 从个位往前相加，进位=和/10，相加后的位数=和%10
public static String addStrings(String num1, String num2) {
    int m = num1.length() - 1;
    int n = num2.length() - 1;
    int carry = 0;
    StringBuilder result = new StringBuilder();
    while (m >=0 || n >= 0 || carry != 0) {
        if (m > -1) {
            carry += num1.charAt(m) - '0';
        }
        if (n > -1) {
            carry += num2.charAt(n) - '0';
        }
        result.insert(0, carry % 10);
        carry /= 10;
        m --;
        n --;
    }
    return result.toString();
}

---

2.3 最长回文子串

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

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

// 【中心拓展法】
// 将字符串每个下标作为中心，向左右拓展，枚举出最长的回文，记录初始结束点
// 回文有奇数回文，和偶数回文
public static String longestPalindrome(String s) {
    int len1;
    int len2;
    int maxLen;
    int start = 0;
    int end = 0;
    String result = "";
    for (int i=0; i<s.length(); i++) {
        // 奇数回文串
        len1 = getMaxLen(s, i, i);
        // 偶数回文串
        len2 = getMaxLen(s, i, i + 1);
        maxLen = Math.max(len1, len2);
        if (maxLen > end - start) {
            start = i - (maxLen-1)/2;
            end = i + maxLen/2;
        }
    }
    return s.substring(start, end + 1);
}

public static int getMaxLen(String s, int left, int right) {
    while (left > -1
            && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        left --;
        right ++;
    }
    return right - left - 1;
}

---

3 单链表

3.1 合并两个单链表

• 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

// 【单链表数据结构】
public class ListNode {
    int val;
    ListNode next;

    ListNode() {}

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

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

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

// 【迭代循环】
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode headNode = new ListNode(-1);
    ListNode currentNode = headNode;
    while (list1 != null && list2 != null) {
        if (list1.val > list2.val) {
            currentNode.next = list2;
            list2 = list2.next;
        } else {
            currentNode.next = list1;
            list1 = list1.next;
        }
        currentNode = currentNode.next;
    }
    currentNode.next = list1 == null ? list2 : list1;
    return headNode.next;
}

---

3.2 单链表反转

• 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

// 【迭代循环】
// 遍历下一个节点时，下一个节点.next=前一个节点
public static ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode next;
    ListNode curr = head;
    while (curr != null) {
        next = curr.next;
        // 位置互换
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

---

3.3 两链表相加

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
• 请你将两个数相加，并以相同形式返回一个表示和的链表。
• 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

// 【循环迭代】
// 思路类似字符串相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode headNode = new ListNode(-1);
	ListNode sum = headNode;
	int carry = 0;
	while (l1 != null || l2 != null || carry != 0) {
		if (l1 != null) {
			carry += l1.val;
			l1 = l1.next;
		}
		if (l2 != null) {
			carry += l2.val;
			l2 = l2.next;
		}
		sum.next = new ListNode(carry % 10);
		sum = sum.next;
		carry = carry / 10;
	}
	return headNode.next;
}

---

3.4 重排链表

• 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
  • L0 → L1 → … → Ln - 1 → Ln
• 请将其重新排列后变为：
  • L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
• 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

// 【寻找链表中点 + 链表逆序 + 合并链表】
// 找出中间点，分左右两部分（中间点包含在左），右边部分反转，然后交叉插入
public void reorderList(ListNode head) {
	ListNode midNode = midNode(head);
	ListNode reverseList = reverseList(midNode.next);
	midNode.next = null;
	mergeList(head, reverseList);
}

// 链表中点
// fast是slow的两倍移速，当fast到达末尾时，slow在中间
public ListNode midNode(ListNode head) {
	ListNode fast = head;
	ListNode slow = head;
	while (fast.next != null && fast.next.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}
	return slow;
}

// 链表反转
public ListNode reverseList(ListNode head) {
	ListNode pre = null;
	ListNode next;
	ListNode current = head;
	while (current != null) {
		next = current.next;
		current.next = pre;
		pre = current;
		current = next;
	}
	return pre;
}

// 链表交叉合并
public void mergeList(ListNode l1, ListNode l2) {
	ListNode l1Temp;
	ListNode l2Temp;
	while (l1 != null && l2!= null) {
		l1Temp = l1.next;
		l2Temp = l2.next;
		// 交叉合并
		l1.next = l2;
		l2.next = l1Temp;
		// 重新赋值
		l1 = l1Temp;
		l2 = l2Temp;
	}
}

---

4 双链表

4.1 LRU算法

---

5 双指针

5.1 数组

5.1.1 移除元素

• 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
• 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
• 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

// 【双指针向中间遍历】
public int removeElement(int[] nums, int val) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        if (nums[left] == val) {
            // 左指针元素相同，左指针元素=右指针元素（判断右指针元素，写法简化了if条件），向前移动
            nums[left] = nums[right];
            right --;
        } else {
            // 左指针元素不同，向后移动
            left ++;
        }
    }
    return left;
}

---

5.1.2 有序数组的平方

• 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

// 【双指针向中间遍历】
public static int[] sortedSquares(int[] nums) {
    int[] result = new int[nums.length];
    // 负数平方后最左边最大，正数平方后最右边最大，双指针设置在左右进行遍历
    int left = 0;
    int right = nums.length - 1;
    int i = right;
    while (left <= right) {
        if (nums[left]*nums[left] < nums[right]*nums[right]) {
            result[i] = nums[right] * nums[right];
            right --;
        } else {
            result[i] = nums[left] * nums[left];
            left ++;
        }
        i --;
    }
    return result;
}

---

5.1.3 长度最小的子数组

• 给定一个含有 n 个正整数的数组和一个正整数 target 。
• 找出该数组中满足其和≥target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

// 【滑动窗口（双指针）】
public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int right = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    // 右指针一直往右移动，移动到sum>=target时，记录长度，并开始移动左指针，直到sum<taget时，再移动右指针
    while (right < nums.length) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left ++;
        }
        right ++;
    }
    if (minLen == Integer.MAX_VALUE) {
        return 0;
    }
    return minLen;
}

---

5.2 字符串

5.2.1 反转字符串

• 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
• 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

// 【双指针（中间靠拢）】
public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;
    char temp;
    // 首尾指针元素互换，向中间移动
    while (left < right) {
        temp  = s[left];
        s[left] = s[right];
        s[right] = temp;
        left ++;
        right --;
    }
}

---

5.2.2 无重复字符的最长字串

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

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

// 【滑动窗口（双指针）】
public static int lengthOfLongestSubstring(String s) {
    int left = 0;
    int right = 0;
    int maxLen = 0;
    Set<Character> chars = new HashSet<>();
    // right指针右移，直至出现重复字符；移动left指针，并移除left指针对应的字符，直至不与right指针字符重复
    while (right < s.length()) {
        while (chars.contains(s.charAt(right))) {
            chars.remove(s.charAt(left));
            left ++;
        }
        chars.add(s.charAt(right));
        right ++;
        maxLen = Math.max(maxLen, right-left);
    }
    return maxLen;
}

---

5.2.3 字符串的排列

• 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
• 换句话说，s1 的排列之一是 s2 的 子串 。

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

// 【双指针】
// s1的排列，可以用统计字符出现次数来判断，长度相同，字符出现相同，则时s2的排列字串之一
public static boolean checkInclusion(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();
    if (n > m) {
        return false;
    }
    // 统计s1 26字母字符次数
    int[] cnt = new int[26];
    for (int i = 0; i < n; ++i) {
        cnt[s1.charAt(i) - 'a'] ++;
    }
    int left = 0;
    for (int right = 0; right < m; ++right) {
        int x = s2.charAt(right) - 'a';
        cnt[x] --;
        // s2当前字符-1，若<0，表示非s1中的字符，移动左指针把字符加回去
        while (cnt[x] < 0) {
            cnt[s2.charAt(left) - 'a'] ++;
            left ++;
        }
        // 移动右指针中，未出现字符<0，且长度right-left=n，则命中
        if (right - left + 1 == n) {
            return true;
        }
    }
    return false;
}

---

5.3 链表

5.3.1 环形链表

• 给你一个链表的头节点 head ，判断链表中是否有环。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
(pos表示尾节点与哪个节点相连， 不作为参数进行传递 。仅仅是为了标识链表的实际情况)

// 【快慢指针】
// 慢指针移动1，快指针=2*慢指针，如果出现环形，总会出现快指针=慢指针
// 若无循环，快指针=null时结束
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

---

5.3.2 删除链表的倒数第N个结点

• 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

// 【双指针】
// 创建两指针，first和second，first比second向后移动了n格，当first到达尾节点时，second就到达了n点
// 因为时单链表删除，需要到n前一个进行删除，所以first和second相距n+1格
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = head;
    ListNode second = dummy;
    // first向后移动n格，不考虑n>指针长度出现null报错
    for (int i = 0; i < n; ++i) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    // 删除链表
    second.next = second.next.next;
    return dummy.next;
}

---

5.3.3 链表的中间结点

• 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
• 如果有两个中间结点，则返回第二个中间结点。

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

// 双指针
// 快慢指针，快指针 = 慢指针 * 2，快指针到末尾时，慢指针到中间结点
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

---

5.3.4 环形链表Ⅱ

• 给定一个链表的头节点 head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

// 【双指针】
// 快慢指针，快指针=2*慢指针
// 根据公式推到，当快指针与慢指针相遇时，慢指针跑完环的距离 = 头节点到环的距离，头节点和慢指针相遇就是入环点
// 推导地址：https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，新指针指向头节点，与慢指针同速移动
        if (fast == slow) {
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            // 与慢指针相遇的点为入环点
            return ptr;
        }
    }
    return null;
}

---

6 哈希表

6.1 有效的字母异位词

• 给定两个字符串s和t ，编写一个函数来判断t是否是s的字母异位词。

输入: s = "anagram", t = "nagaram"
输出: true

// 【哈希表】
// 26位数组表示26字母，记录次数；遍历相减，若出现负数，就不是异位词
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    // 记录s字符串中字母次数
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    // 减去t中字符字母出现次数
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

---

6.2 存在重复元素

• 给你一个整数数组nums。如果任一值在数组中出现至少两次 ，返回true ；如果数组中每个元素互不相同，返回false 。

输入：nums = [1,2,3,1]
输出：true

// 【Set】
// Set不能存储重复元素，若重复返回false
public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    for (int x : nums) {
        if (!set.add(x)) {
            return true;
        }
    }
    return false;
}

---

6.3 两个数组的交集

• 给定两个数组nums1和nums2，返回它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

// 【Set】
// Set去重然后比较
public int[] intersection(int[] nums1, int[] nums2) {
    // 通过Set去重其中一个数组
    Set<Integer> set = new HashSet<>();
    for (int num : nums1) {
        set.add(num);
    }
    // 跟另一个数组进行比较，重复加入到Set（去重）
    Set<Integer> resultSet = new HashSet<>();
    for (int num : nums2) {
        if (set.contains(num)) {
            resultSet.add(num);
        }
    }
    // 转成数组
    int[] arr = new int[resultSet.size()];
    int i = 0;
    for (Integer num : resultSet) {
        arr[i] = num;
        i ++;
    }
    return arr;
}

---

6.4 四数相加Ⅱ

• 给你四个整数数组 nums1、nums2、nums3和nums4 ，数组长度都是n，请你计算有多少个元组(i, j, k, l) 能满足：
  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

// 【分组 + 哈希表】
// 将ABCD分为两组，AB一组，CD一组，记录AB之间所有相加的可能数字，并记录次数。同理CD也是，最后比较相加等于0的次数
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    // 双for记录AB相加的数字，以及次数
    Map<Integer, Integer> countAB = new HashMap<>();
    for (int i : A) {
        for (int j : B) {
            countAB.put(i+j, countAB.getOrDefault(i+j, 0)+1);
        }
    }
    // 双for比较C+D中的数字的负数，是否A+B中出现；出现即相加等于0
    int count = 0;
    for (int i : C) {
        for (int j : D) {
            if (countAB.containsKey(-(i+j))) {
                count += countAB.get(-(i+j));
            }
        }
    }
    return count;
}

---

7 队列

7.1 用队列实现栈

• 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

public class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    // 将新元素入列到queue2，再从queue出列并入列到queue2，queue1 = queue2（最后数据都存在queue1中）
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        queue1 = queue2;
        queue2 = new LinkedList<>();
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

---

7.2 前K个高频元素

• 给你一个整数数组nums和一个整数 k ，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

// 【优先队列】
public int[] topKFrequent(int[] nums, int k) {
    // map统计数字次数
    Map<Integer, Integer> numCount = new HashMap<Integer, Integer>();
    for (int num : nums) {
        numCount.put(num, numCount.getOrDefault(num, 0) + 1);
    }
    // 创建优先队列（根据比较器自动进行排序【根据次数进行降序】），存储长度为2的数组，[0]存储数字，[1]存储出现次数
    PriorityQueue<int[]> queue = new PriorityQueue<>((m, n) -> n[1] - m[1]);
    for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
        queue.offer(new int[]{entry.getKey(), entry.getValue()});
    }
    // 取出前k个
    int[] result = new int[k];
    for (int i = 0; i < k; ++i) {
        result[i] = queue.poll()[0];
    }
    return result;
}

---

7.3 滑动窗口最大值

• 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
• 返回滑动窗口中的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

// 【单调队列】
// 营造出单调递减队列，队首永远时最大值，只要队首的下标在窗口范围内，就是当前窗口最大值；不在则出队，下一个值为窗口最大值
public static int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    Deque<Integer> deque = new LinkedList<>();
    // 预处理前k条数据（后数>前数，前数出队列，直至队列为empty或后数<前数），保证队首的值最大【记录的是数组下标】
    for (int i = 0; i < k; ++i) {
        while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }
        deque.offerLast(i);
    }
    int[] ans = new int[n - k + 1];
    ans[0] = nums[deque.peekFirst()];
    // 窗口向右移动（从k开始）
    for (int i = k; i < n; ++i) {
        // 上面逻辑同理
        while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        // 当队首的最大不在窗口范围内，则进行移除（保证当前队首时有效最大值）
        while (deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        ans[i - k + 1] = nums[deque.peekFirst()];
    }
    return ans;
}

---

8 栈

8.1 用栈实现队列

• 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

public class MyQueue {
    private Stack<Integer> stack1; // 入队列用
    private Stack<Integer> stack2; // 出队列用
    int front; // 队首

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // 记录队首，并元素放入stack1
    public void push(int x) {
        if (stack1.isEmpty()) {
            front = x;
        }
        stack1.push(x);
    }

    // 出队列时，将stack1入栈到stack2，此时stack2栈顶就是队首
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            return front;
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

---

8.2 . 逆波兰表达式求值

• 根据逆波兰表示法（后缀表达式），求表达式的值。
• 有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>(); // 存数字
    // 遇到操作符，将入栈的数字出栈参与计算，将计算结果重新入栈
    for (String token : tokens) {
        if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
            stack.push(cul(stack.pop(), stack.pop(), token));
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.peek();
}

// 计算
public int cul(Integer num1, Integer num2, String operate) {
    switch (operate) {
        case "+":
            return num2 + num1;
        case "-":
            return num2 - num1;
        case "*":
            return num2 * num1;
        case "/":
            return num2 / num1;
        default:
            return -1;
    }
}

---

8.3 接雨水

• 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

//【单调栈】
public static int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int top;
    int left;
    int width;
    int result = 0;
    // 遍历数据，栈记录下标（方便计算面积），当当前元素高度>栈顶元素高度，可能会形成包围
    // 栈顶元素出栈，作为'底'，高度计算 = min(新栈顶元素高度，当前元素高度) - ‘底’
    for (int i=0; i<height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            top = stack.pop();
            if (stack.isEmpty()) {
                break;
            }
            left = stack.peek();
            width = i - left - 1;
            result += width * (Math.min(height[i], height[left]) - height[top]);
        }
        stack.push(i);
    }
    return result;
}

---

9 二叉树

9.1 二叉树遍历

9.1.1 二叉树中序遍历

• 给定一个二叉树的根节点 root ，返回它的中序遍历 。

// 【二叉树结构】
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    TreeNode() {}

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

    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inOrder(root, result);
    return result;
}

public void inOrder(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    // 遍历左子树
    inOrder(node.left, result);
    result.add(node.val);
    // 遍历右子树
    inOrder(node.right, result);
}

---

9.1.2 二叉树的层序遍历

• 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]

// 【广度优先搜索】
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 记录每层节点数，遍历对应的节点数，list封装为一层，重新计算新的一层的个数，依次往复
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        while (levelSize > 0) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            levelSize --;
        }
        result.add(level);
    }
    return result;
}

---

9.1.3 二叉树的锯齿层序遍历

• 给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

// 【广度优先搜索】
// 跟层序遍历基本一直，稍作变形
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean isLeftOrder = true;
    while (!queue.isEmpty()) {
        // 记录每层节点数，遍历对应的节点数，list封装为一层，重新计算新的一层的个数，一次往复
        int levelSize = queue.size();
        Deque<Integer> level = new LinkedList<>();
        while (levelSize > 0) {
            TreeNode node = queue.poll();
            // 双向队列存储数据，奇数层从后往前存，偶数层从前往后存
            if (isLeftOrder) {
                level.offerLast(node.val);
            } else {
                level.offerFirst(node.val);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            levelSize --;
        }
        result.add(new ArrayList<>(level));
        isLeftOrder = !isLeftOrder;
    }
    return result;
}

---

9.2 二叉树的属性

9.2.1 二叉树的最大深度

• 给定一个二叉树，找出其最大深度。

给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

// 【递归】【深度优先】
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

---

9.2.2 二叉树的直径

• 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

// 【递归】【深度优先搜索】
int maxlength = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return maxlength;
}

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    // 记录最长路径（左子树深度 + 右子树深度）
    maxlength = Math.max(maxlength, leftHeight + rightHeight);
    return Math.max(leftHeight, rightHeight) + 1;
}

---

9.2.3 二叉树中的最大路径和

• 给你一个二叉树的根节点 root ，返回其最大路径和 。

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

// 【递归】【深度优先搜索】
int maxSum;

public int maxPathSum(TreeNode root) {
    maxSum = Integer.MIN_VALUE;
    getMaxSum(root);
    return maxSum;
}

public int getMaxSum(TreeNode node) {
    if (node == null) {
        return 0;
    }
    // 最大总数 > 0 才采用此子树的节点
    int leftPathSum = Math.max(getMaxSum(node.left), 0);
    int rightPathSum = Math.max(getMaxSum(node.right), 0);
    maxSum = Math.max(maxSum, leftPathSum + rightPathSum + node.val);
    return node.val + Math.max(leftPathSum, rightPathSum);
}

---

9.3 二叉树的构造

9.3.1 从中序与后序遍历序列构造二叉树

• 给定两个整数数组inorder和postorder ，其中inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

// 【递归】
int[] postorder;
int postIdx;
Map<Integer, Integer> inorderMap;

public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.postorder = postorder;
    postIdx = postorder.length - 1;
    // 记录inorderMap（key是元素，value是下标）
    inorderMap = new HashMap<>(inorder.length);
    for (int i=0; i<inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    // 构建树
    return buildTreeByInIdx(0, inorder.length-1);
}

// 通过inorder下标边界构建树
public TreeNode buildTreeByInIdx(int in_left, int in_right) {
    if (in_left > in_right) {
        return null;
    }
    TreeNode root = new TreeNode(postorder[postIdx]);
    int inIdx = inorderMap.get(postorder[postIdx]);
    // 后序遍历，从后往前访问; 变成先处理右子树，再处理左子树
    postIdx --;
    root.right = buildTreeByInIdx(inIdx+1, in_right);
    root.left = buildTreeByInIdx(in_left, inIdx-1);
    return root;
}

---

10 贪心算法

10.1 基础常见问题

10.1.1 分发饼干

• 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
• 对每个孩子 i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸s[j]。如果s[j]>= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

// 【贪心算法】
public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    // 因为每个孩子只有一个饼干，将大于胃口值的饼干分发下去
    int count = 0;
    for (int i=0, j=0; i<g.length && j<s.length; i++, j++) {
        while (j < s.length && g[i] > s[j]) {
            j++;
        }
        if (j < s.length) {
            count ++;
        }
    }
    return count;
}

---

10.2 区间问题

10.2.1 跳跃游戏

• 给定一个非负整数数组 nums ，你最初位于数组的第一个下标。
• 数组中的每个元素代表你在该位置可以跳跃的最大长度。
• 判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

// 【贪心算法】
// 遍历数组，并记录当前位置最大能跳距离，如果最大能跳距离 < 当前index，则return false;
public boolean canJump(int[] nums) {
    int maxJump = 0;
    for(int i=0; i<nums.length; i++) {
        if (maxJump < i) {
            return false;
        }
        maxJump = Math.max(maxJump, i+nums[i]);
    }
    return true;
}

---

10.2.2 跳跃游戏Ⅱ

• 给你一个非负整数数组nums，你最初位于数组的第一个位置。
• 数组中的每个元素代表你在该位置可以跳跃的最大长度。
• 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
• 假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

// 【贪心算法】（局部最优）
// 在一跳的过程中，记录每个点的最远距离，选出最远距离的该点作为下一跳点，step+1
// 每遍历一个跳点，更新一次最远距离。当遍历到跳跃的边界时，将最远距离作为新的边界，相当于在其中选择了跳得最远的点，作为下一个跳点
public int jump(int[] nums) {
    int maxJump = 0;
    int end = 0;
    int step = 0;
    for (int i=0; i<nums.length-1; i++) {
        maxJump = Math.max(maxJump, nums[i] + i);
        if (i == end) {
            end = maxJump;
            step ++;
        }
    }
    return step;
}

---

10.2.3 划分字母区间

• 字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

// 【贪心算法】
public List<Integer> partitionLabels(String s) {
    List<Integer> result = new ArrayList<>();
    // 26字母，记录每个字母组后出现位置
    int[] lastPos = new int[26];
    for (int i=0; i<s.length(); i++) {
        lastPos[s.charAt(i)-'a'] = i;
    }
    // 遍历字符串，比较遍历的每个字符串最后出现的位置end，取其中最大值
    // 若i == end，表示里面的所有字母都包含在此字段，切分字段
    int start = 0;
    int end = 0;
    for (int i=0; i<s.length(); i++) {
        end = Math.max(end, lastPos[s.charAt(i)-'a']);
        if (i == end) {
            result.add(end-start+1);
            start = end + 1;
        }
    }
    return result;
}

---

10.3 两个维度权衡问题

10.3.1 根据身高重建队列

• 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki]表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
• 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj]是队列中第 j 个人的属性（queue[0]是排在队列前面的人）。

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

public int[][] reconstructQueue(int[][] people) {
    // 先按身高降序，同身高按个数升序
    Arrays.sort(people, (o1, o2) -> o2[0]-o1[0]==0 ? o1[1]-o2[1] : o2[0]-o1[0]);
    // 按照个数进行插空
    List<int[]> res = new LinkedList<>();
    for (int[] person : people) {
        res.add(person[1], person);
    }
    return res.toArray(people);
}

---

10.3.2 分发糖果

• n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
• 你需要按照以下要求，给这些孩子分发糖果：
  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。
• 请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

// 【规律得出】
// 自增时，糖果数 = 前糖果数 + 1 ; 
// 相同时，糖果数 = 1 ; 
// 递减时，糖果数 = 1，且每递减一次，前面递减序列的糖果都+1
public int candy(int[] ratings) {
    int incrSize = 0; // 递增长度
    int decrSize = 0; // 递减长度
    int candyCount = 1; // 当前糖果数
    int result = 1; // 总糖果数
    for (int i=1; i<ratings.length; i++) {
        if (ratings[i] >= ratings[i-1]) {
            decrSize = 0;
            if (ratings[i] == ratings[i-1]) {
                candyCount = 1;
            } else {
                candyCount ++;
            }
            incrSize = candyCount;
            result += candyCount;
        } else {
            decrSize ++;
            // 递增大小 == 递减大小时，将递增最后一个纳入递减中
            if (decrSize == incrSize) {
                decrSize ++;
            }
            result += decrSize;
            candyCount = 1;
        }
    }
    return result;
}

---

11 动态规划

11.1 基础

11.1.1 爬楼梯

• 假设你正在爬楼梯。需要n阶你才能到达楼顶。
• 每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

// 【动态规划】
// 得出规律 f(x) = f(x-1) + f(x-2)，最终可能走一步，也可能走两步
// 下一步的总方法个数 = 前两个总方法个数之和
public int climbStairs(int n) {
    if (n < 3) {
        return n;
    }
    // 初始化 a = f(1)，b = f(2)
    int a = 1;
    int b = 2;
    int sum = 0;
    for (int i=3; i<=n; i++) {
        sum = a + b;
        // a，b数值更新，a相当于f(x-2)，b相当于f(x-1)
        a = b;
        b = sum;
    }
    return sum;
}

---

11.1.2 杨辉三角

• 给定一个非负整数 numRows，生成「杨辉三角」的前numRows行。
• 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

// 【动态规划】
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    if (numRows == 0) {
        return result;
    }
    // 初始化（第一行只有1个1）
    List<Integer> row = new ArrayList<>();
    row.add(1);
    result.add(row);
    for (int i=1; i<numRows; i++) {
        List<Integer> preRow = result.get(i-1);
        row = new ArrayList<>();
        for (int j=0; j<=i; j++) {
            // 计算上一行左上方、右上方个数，超出列数设置为0
            int left = j==0 ? 0 : preRow.get(j-1);
            int right = j==i ? 0 : preRow.get(j);
            row.add(left+right);
        }
        result.add(row);
    }
    return result;
}

---

11.1.3 不同路径

• 一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
• 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
• 问总共有多少条不同的路径？

输入：m = 3, n = 7
输出：28

// 【动态规划】
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // 初始化（因为只会向右和下移动，所以边界只有1种可抵达方法）
    for (int i=0; i<m; i++) {
        dp[i][0] = 1;
    }
    for (int i=0; i<n; i++) {
        dp[0][i] = 1;
    }
    // 根据递推公式，填充dp数组 （dp[i][j] = dp[i-1][j] + dp[i][j-1]）（跟爬台阶类似）
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

---

11.2 线性问题

11.2.1 打家劫舍

• 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
• 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

// 【动态规划】
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    if (nums.length == 1) {
        return nums[0];
    }
    // dp数组初始化（下标：能抢劫的户数-1；数值：能抢劫户数下的最大金额）
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    // 根据公式填充dp数组，dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    for (int i=2; i<nums.length; i++) {
        dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
    }
    return dp[nums.length-1];
}

---

11.2.2 打家劫舍Ⅲ

• 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
• 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
• 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

// 【动态规划】
public int rob(TreeNode root) {
    int[] result = robArr(root);
    return Math.max(result[0], result[1]);
}

// 下标(0:不偷能获取的最大金额，1：偷能获取的最大金额)
// 递推公式：0:不偷 = max(左偷, 左不偷) + max(右偷, 右不偷)； 1：偷 = node.val + 左不偷 + 右不偷
private int[] robArr(TreeNode root) {
    if (root == null) {
        return new int[2];
    }
    // 递归获取子树偷ro不偷数组
    int[] leftArr = robArr(root.left);
    int[] rightArr = robArr(root.right);
    // 计算当前节点偷or不偷的最大金额
    int[] result = new int[2];
    result[0] = Math.max(leftArr[0], leftArr[1]) + Math.max(rightArr[0], rightArr[1]);
    result[1] = root.val + leftArr[0] + rightArr[0];
    return result;
}

---

11.2.3 买卖股票最佳时机

• 给定一个数组 prices ，它的第i个元素prices[i]表示一支给定股票第i天的价格。
• 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
• 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

//【动态规划】
public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    // 状态转移；循环比较最小购入金额，以及最大利润
    for (int i=0; i<prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = Math.max(prices[i]-minPrice, maxProfit);
        }
    }
    return maxProfit;
}

---

11.2.4 买卖股票的最佳时机Ⅱ

• 给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。
• 在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。
• 返回你能获得的最大利润。

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

// 【动态规划】
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    // 初始化（第一天数据填入），have表示手中有股表，nothave表示手中无股票，值表示利润
    int have = -prices[0];
    int notHave = 0;
    // 依次与昨天比较，进行状态转移
    // 无股票：（1）昨天也无股票，（2）昨天有股票，但卖出了，加上昨天股票价钱
    // 有股票：（1）昨天也有股票，（2）昨天无股票，但花钱购买了，减上昨天股票价钱
    for (int i=1; i<prices.length; i++) {
        have = Math.max(have, notHave - prices[i]);
        notHave = Math.max(notHave, have + prices[i]);
    }
    return notHave;
}

---

11.2.5 最大子数组和

• 给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

// 【动态规划】
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    // 状态推移 
    // pre = max(pre+nums[i], nums[i])
    // result = max(pre, result)
    int pre = nums[0];
    int result = nums[0];
    for (int i=1; i<nums.length; i++) {
        pre = Math.max(nums[i]+pre, nums[i]);
        result = Math.max(result, pre);
    }
    return result;
}

---

11.2.6 最长递增子序列

• 给你一个整数数组nums，找到其中最长严格递增子序列的长度。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

/ 【动态规划】
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    // dp数组：index=当前数字下标；value=最长递增序列个数（即：当前数字最长递增序列个数）
    // 默认最长递增序列为1（即自身）
    int[] dp = new int[nums.length];
    int result = 1;
    for (int i=0; i<nums.length; i++) {
        dp[i] = 1;
        // i 跟 i之前的数字比较大小；nums[i] > nums[j]，dp[i] = max(dp[i], dp[j]+1)
        for (int j=0; j<i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        result = Math.max(result, dp[i]);
    }
    return result;
}

---

11.2.7 编辑距离

• 给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

// 【动态规划】
public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    int m = word1.length();
    int n = word2.length();
    // 出现空串，操作次数 = 非空串长度
    if (m * n == 0) {
        return m + n;
    }
    // dp数组：i表示word1前i个字符，j表示word2前j个字符，dp[i][j] = word1前i个字符和word2前j个字符，互相转换的最小次数
    // 额外多出1个空间，表示空字符串，位于0号位
    int[][] dp = new int[m+1][n+1];
    // 初始化边界
    for (int i=0; i<m+1; i++) {
        dp[i][0] = i;
    }
    for (int j=0; j<n+1; j++) {
        dp[0][j] = j;
    }
    // 递推公式：dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1], dp[i-1][j-1]+1)
    for (int i=1; i<m+1; i++) {
        for (int j=1; j<n+1; j++) {
            int left = dp[i-1][j] + 1;
            int down = dp[i][j-1] + 1;
            int left_down = dp[i-1][j-1];
            // left_down表示替换，字符一样无需替换
            if (word1.charAt(i-1) != word2.charAt(j-1)) {
                left_down ++;
            }
            dp[i][j] = Math.min(left, Math.min(down, left_down));
        }
    }
    return dp[m][n];
}

---

11.3 背包问题

11.3.1 单词拆分

• 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
• 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

// 【动态规划】
public boolean wordBreak(String s, List<String> wordDict) {
    // 拆分字段去重
    Set<String> wordDictSet = new HashSet<>(wordDict);
    // dp[j]==true（表示上个单词拆分的边界）
    // 若此时string.sub(j, i) == wordDict中的词，j边界到i之间又有一个拆分的词，dp[i] = true
    // 当dp[n] == true，表示整个字符串都能被单词拆分
    boolean[] dp = new boolean[s.length()+1];
    // 初始化（0号位表示空串，用来设置边界）
    dp[0] = true;
    for (int i=1; i<s.length()+1; i++) {
        for (int j=0; j<i; j++) {
            if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

---

11.2.2 零钱兑换

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
• 计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
• 你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

// 【动态规划】
public int coinChange(int[] coins, int amount) {
    // dp数组，i表示金额，dp[i]表示达到i所需最小硬币数
    int[] dp = new int[amount + 1];
    // 初始化：填充amount+1，用于判断数组末尾是否有硬币能组合，硬币组合不了值一定等于amount+1
    Arrays.fill(dp, amount+1);
    dp[0] = 0;
    // 状态转移公式：dp[i] = Math.min(dp[i], dp[i-coins[j]+1])
    for(int i=1; i<amount+1; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

---

11.2.3 完全平方数

• 给你一个整数 n ，返回0和为n的完全平方数的最少数量

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

// 动态规划
public int numSquares(int n) {
    // dp数组：i为数字，dp[i]为组成该数字所需的最小平方数和
    int[] dp = new int[n+1];
    for (int i = 1; i <= n; i++) {
        // 默认为i，即该数全由1组成
        int min = i;
        // 从1到i找出最小的平方数和
        for (int j = 1; j * j <= i; j++) {
            min = Math.min(min, dp[i-j*j]+1);
        }
        dp[i] = min;
    }
    return dp[n];
}

---

11.3 区间问题

11.3.1 最长回文子序列

• 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
  • 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

// 动态规划
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    // i, j为字符i到j组成的字符串，dp[i][j]为ij字符串的最长回文序列
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        // 默认1，即一个字符
        dp[i][i] = 1;
        // i从后往前推移，j从前往后推移，保证数据存在
        // 假如i字符==j字符，往字符内部推移，即dp[i+1][j-1]+2
        // 假如i字符!=j字符，取i or j 往内推移的最大值，max(dp[i+1][j], dp[i][j-1])
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n - 1];
}

---