Java 算法刷题总结：数组、链表、树与动态规划

算法题目汇总

数组

26. 删除有序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int slowIndex = 1;
        for (int fastIndex = 1; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != nums[fastIndex - 1]) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

27. 移除元素（双指针，快慢指针）

class Solution {
    // 快慢指针法
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftBorder = searchLeftBorder(nums, target);
        int rightBorder = searchRightBorder(nums, target);
        if (leftBorder == -1 || rightBorder == -1) return new int[]{-1, -1};
        else if (rightBorder - leftBorder >= 0) return new int[]{leftBorder, rightBorder};
        else return new int[]{-1, -1};
    }

    public int searchRightBorder(int[] nums, int target) {
        int left = 0, right = nums.length;
        int rightBorder = -1;
        while (left < right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid;
            else { left = mid + 1; rightBorder = mid; }
        }
        return rightBorder;
    }

    public int searchLeftBorder(int[] nums, int target) {
        int left = 0, right = nums.length;
        int leftBorder = -1;
        while (left < right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid;
            else { right = mid; leftBorder = right; }
        }
        return leftBorder;
    }
}

35. 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        int middle = left + ((right - left) / 2);
        while (left < right) {
            if (nums[middle] == target) return middle;
            else if (nums[middle] < target) left = middle + 1;
            else right = middle;
        }
        return left;
    }
}

69. x 的平方根

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int ans = -1;
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if ((long) mid * mid == x) return mid;
            else if ((long) mid * mid < x) { ans = mid; left = mid + 1; }
            else right = mid - 1;
        }
        return ans;
    }
}

283. 移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int slowIdx = 0;
        for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
            if (nums[fastIdx] != 0) {
                nums[slowIdx] = nums[fastIdx];
                slowIdx++;
            }
        }
        int rest = nums.length - slowIdx;
        for (int i = 0; i < rest; i++) nums[nums.length - 1 - i] = 0;
    }
}

367. 有效的完全平方数

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if ((long) mid * mid < num) left = mid + 1;
            else if ((long) mid * mid == num) return true;
            else right = mid - 1;
        }
        return false;
    }
}

704. 二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] < target) left = middle + 1;
            else if (nums[middle] > target) right = middle;
            else return middle;
        }
        return -1;
    }
}

844. 比较含退格的字符串

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        return removeString(cs).equals(removeString(ct));
    }

    public String removeString(char[] cs) {
        int slow = 0;
        for (int fast = 0; fast < cs.length; fast++) {
            if (cs[fast] != '#') {
                cs[slow] = cs[fast];
                slow++;
            } else {
                if (slow > 0) slow--;
            }
        }
        return new String(cs).substring(0, slow);
    }
}

977. 有序数组的平方

class Solution {
    public int[] sortedSquares(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        int left = 0, right = length - 1, pos = length - 1;
        while (right >= left) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[pos] = nums[left] * nums[left];
                pos--; left++;
            } else {
                res[pos] = nums[right] * nums[right];
                pos--; right--;
            }
        }
        return res;
    }
}

209. 长度最小的子数组（滑动窗口问题）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

904. 水果成篮

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> mp = new HashMap<>();
        int n = fruits.length, left = 0, ans = 0;
        for (int right = 0; right < n; right++) {
            mp.put(fruits[right], mp.getOrDefault(fruits[right], 0) + 1);
            while (mp.size() > 2) {
                mp.put(fruits[left], mp.get(fruits[left]) - 1);
                if (mp.get(fruits[left]) == 0) mp.remove(fruits[left]);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

59. 螺旋矩阵 II

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int startx = 0, starty = 0, offset = 1, count = 1, loop = 1;
        int x = 0, y = 0;
        while (loop <= n / 2) {
            for (y = starty; y < n - offset; y++) ans[startx][y] = count++;
            for (x = startx; x < n - offset; x++) ans[x][y] = count++;
            for (; y > starty; y--) ans[x][y] = count++;
            for (; x > startx; x--) ans[x][y] = count++;
            loop++; offset++; startx++; starty++;
        }
        if (n % 2 == 1) ans[startx][starty] = count;
        return ans;
    }
}

54. 螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int hang = matrix.length, lie = matrix[0].length;
        int left = 0, right = lie - 1, top = 0, bottom = hang - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) ans.add(matrix[top][i]); top++;
            for (int i = top; i <= bottom; i++) ans.add(matrix[i][right]); right--;
            if (top <= bottom) for (int i = right; i >= left; i--) ans.add(matrix[bottom][i]); bottom--;
            if (left <= right) for (int i = bottom; i >= top; i--) ans.add(matrix[i][left]); left++;
        }
        return ans;
    }
}

58. 区间和（前缀和）

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        int[] presum = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
            presum[i] = (i == 0) ? arr[i] : presum[i - 1] + arr[i];
        }
        while (scan.hasNext()) {
            int a1 = scan.nextInt(), a2 = scan.nextInt();
            System.out.println(a1 == 0 ? presum[a2] : presum[a2] - presum[a1 - 1]);
        }
    }
}

44. 开发商购买土地

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] arr = new int[n][m];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = scan.nextInt();
                sum += arr[i][j];
            }
        }
        int[] horizontal = new int[n];
        int[] vertical = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                horizontal[i] += arr[i][j];
                vertical[j] += arr[i][j];
            }
        }
        int result = Integer.MAX_VALUE, horisum = 0;
        for (int i = 0; i < horizontal.length; i++) {
            horisum += horizontal[i];
            result = Math.min(result, Math.abs((sum - horisum) - horisum));
        }
        int vertisum = 0;
        for (int i = 0; i < vertical.length; i++) {
            vertisum += vertical[i];
            result = Math.min(result, Math.abs((sum - vertisum) - vertisum));
        }
        System.out.println(result);
    }
}

链表

203. 移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) head = head.next;
        ListNode node = head;
        while (node != null && node.next != null) {
            if (node.next.val == val) node.next = node.next.next;
            else node = node.next;
        }
        return head;
    }
}

707. 设计链表

class MyLinkedList {
    class listNode { int val; listNode next; public listNode(int val) { this.val = val; } }
    private listNode prehead; private int size;
    public MyLinkedList() { this.prehead = new listNode(0); this.size = 0; }
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        listNode cur = prehead.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }
    public void addAtHead(int val) {
        listNode newhead = new listNode(val);
        newhead.next = prehead.next; prehead.next = newhead; size++;
    }
    public void addAtTail(int val) {
        listNode newtail = new listNode(val);
        listNode cur = prehead;
        while (cur.next != null) cur = cur.next;
        cur.next = newtail; size++;
    }
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        listNode newnode = new listNode(val), cur = prehead;
        for (int i = 0; i <= index - 1; i++) cur = cur.next;
        newnode.next = cur.next; cur.next = newnode; size++;
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        listNode cur = prehead;
        for (int i = 0; i < index; i++) cur = cur.next;
        cur.next = cur.next.next; size--;
    }
}

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }
    private ListNode reverse(ListNode pre, ListNode cur) {
        if (cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur, temp);
    }
}

24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode prehead = new ListNode(-1); prehead.next = head;
        ListNode cur = prehead;
        while (cur.next != null && cur.next.next != null) {
            ListNode firstNode = cur.next, secondNode = cur.next.next;
            cur.next = secondNode;
            secondNode.next = firstNode;
            firstNode.next = cur.next.next;
            cur = firstNode;
        }
        return prehead.next;
    }
}

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode prehead = new ListNode(-1); prehead.next = head;
        ListNode fast = prehead, slow = prehead;
        for (int i = 0; i < n; i++) fast = fast.next;
        while (fast.next != null) { fast = fast.next; slow = slow.next; }
        slow.next = slow.next.next;
        return prehead.next;
    }
}

160. 相交链表

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengtha = 0, lengthb = 0;
        ListNode cura = headA, curb = headB;
        while (cura != null) { lengtha++; cura = cura.next; }
        while (curb != null) { lengthb++; curb = curb.next; }
        cura = headA; curb = headB;
        int interval = Math.abs(lengtha - lengthb);
        if (lengtha > lengthb) for (int i = 0; i < interval; i++) cura = cura.next;
        else for (int i = 0; i < interval; i++) curb = curb.next;
        while (cura != null) {
            if (cura == curb) return cura;
            cura = cura.next; curb = curb.next;
        }
        return null;
    }
}

142. 环形链表 II

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) {
                ListNode joint = slow, begin = head;
                while (joint != begin) { joint = joint.next; begin = begin.next; }
                return joint;
            }
        }
        return null;
    }
}

哈希表

242. 有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] rec = new int[26];
        for (char ch : s.toCharArray()) rec[ch - 'a']++;
        for (char ch : t.toCharArray()) rec[ch - 'a']--;
        for (int i : rec) if (i != 0) return false;
        return true;
    }
}

383. 赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] record = new int[26];
        for (char c : magazine.toCharArray()) record[c - 'a']++;
        for (char c : ransomNote.toCharArray()) record[c - 'a']--;
        for (int i : record) if (i < 0) return false;
        return true;
    }
}

49. 字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] rec = new int[26];
            for (char c : str.toCharArray()) rec[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) if (rec[i] != 0) { key.append((char)(i + 'a')).append(rec[i]); }
            String k = key.toString();
            map.computeIfAbsent(k, x -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int slen = s.length(), plen = p.length();
        List<Integer> ans = new ArrayList<>();
        if (slen < plen) return ans;
        int[] scount = new int[26], pcount = new int[26];
        for (int i = 0; i < plen; i++) { scount[s.charAt(i) - 'a']++; pcount[p.charAt(i) - 'a']++; }
        if (Arrays.equals(scount, pcount)) ans.add(0);
        for (int i = 0; i < slen - plen; i++) {
            scount[s.charAt(i) - 'a']--;
            scount[s.charAt(i + plen) - 'a']++;
            if (Arrays.equals(scount, pcount)) ans.add(i + 1);
        }
        return ans;
    }
}

349. 两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> ans = new HashSet<>();
        for (int i : nums1) set1.add(i);
        for (int i : nums2) if (set1.contains(i)) ans.add(i);
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

350. 两个数组的交集 II

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return intersect(nums2, nums1);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) map.put(i, map.getOrDefault(i, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int i : nums2) {
            int count = map.getOrDefault(i, 0);
            if (count > 0) { ans.add(i); count--; if (count > 0) map.put(i, count); else map.remove(i); }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

202. 快乐数

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) { set.add(n); n = getNext(n); }
        return n == 1;
    }
    private int getNext(int n) {
        int ans = 0;
        while (n > 0) { ans += (n % 10) * (n % 10); n /= 10; }
        return ans;
    }
}

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp)) return new int[]{map.get(temp), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) for (int j : nums2) map.put(i + j, map.getOrDefault(i + j, 0) + 1);
        int res = 0;
        for (int i : nums3) for (int j : nums4) res += map.getOrDefault(0 - i - j, 0);
        return res;
    }
}

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) right--;
                else if (sum < 0) left++;
                else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++; right--;
                }
            }
        }
        return result;
    }
}

18. 四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int a = 0; a < nums.length; a++) {
            if (nums[a] > target && nums[a] >= 0) break;
            if (a > 0 && nums[a] == nums[a - 1]) continue;
            for (int b = a + 1; b < nums.length; b++) {
                if (nums[a] + nums[b] > target && nums[a] + nums[b] >= 0) break;
                if (b > a + 1 && nums[b] == nums[b - 1]) continue;
                int left = b + 1, right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[a] + nums[b] + nums[left] + nums[right];
                    if (sum > target) right--;
                    else if (sum < target) left++;
                    else {
                        res.add(Arrays.asList(nums[a], nums[b], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        right--; left++;
                    }
                }
            }
        }
        return res;
    }
}

字符串

344. 反转字符串

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left]; s[left] = s[right]; s[right] = temp;
            left++; right--;
        }
    }
}

541. 反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i += 2 * k) {
            int start = i, end = Math.min(ch.length - 1, start + k - 1);
            while (start < end) { char temp = ch[start]; ch[start] = ch[end]; ch[end] = temp; start++; end--; }
        }
        return new String(ch);
    }
}

151. 反转字符串中的单词

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeExtraSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();
    }
    private StringBuilder removeExtraSpace(String s) {
        int start = 0, end = s.length() - 1;
        while (start <= end && s.charAt(start) == ' ') start++;
        while (end >= start && s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char ch = s.charAt(start++);
            if (ch != ' ' || sb.charAt(sb.length() - 1) != ' ') sb.append(ch);
        }
        return sb;
    }
    private void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start++, sb.charAt(end)); sb.setCharAt(end--, temp); }
    }
    private void reverseEachWord(StringBuilder sb) {
        int start = 0, end = 0;
        while (start < sb.length()) {
            while (end < sb.length() && sb.charAt(end) != ' ') end++;
            reverseString(sb, start, end - 1);
            start = end + 1; end = start + 1;
        }
    }
}

28. 找出字符串中第一个匹配项的下标（KMP 算法）

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = getNext(needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            if (j == needle.length()) return i - j + 1;
        }
        return -1;
    }
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];
            if (s.charAt(i) == s.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }
}

459. 重复的子字符串（KMP 算法）

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() == 1) return false;
        int[] next = getNext(s);
        if (next[s.length() - 1] != 0 && s.length() % (s.length() - next[s.length() - 1]) == 0) return true;
        return false;
    }
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];
            if (s.charAt(i) == s.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }
}

栈与队列

232. 用栈实现队列

class MyQueue {
    Stack<Integer> stackIn, stackOut;
    public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); }
    public void push(int x) { stackIn.push(x); }
    public int pop() { transfer(); return stackOut.pop(); }
    public int peek() { transfer(); return stackOut.peek(); }
    public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); }
    private void transfer() { if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()) stackOut.push(stackIn.pop()); }
}

225. 用队列实现栈

class MyStack {
    Queue<Integer> queue;
    public MyStack() { queue = new LinkedList<>(); }
    public void push(int x) {
        queue.offer(x);
        int len = queue.size();
        while (len > 1) { queue.offer(queue.poll()); len--; }
    }
    public int pop() { return queue.poll(); }
    public int top() { return queue.peek(); }
    public boolean empty() { return queue.isEmpty(); }
}

20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || c != stack.peek()) return false;
            else stack.pop();
        }
        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!deque.isEmpty() && deque.peek() == c) deque.pop();
            else deque.push(c);
        }
        String str = "";
        while (!deque.isEmpty()) str = deque.pop() + str;
        return str;
    }
}

150. 逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (String s : tokens) {
            if (s.equals("+")) { int a = deque.pop(), b = deque.pop(); deque.push(b + a); }
            else if (s.equals("-")) { int a = deque.pop(), b = deque.pop(); deque.push(b - a); }
            else if (s.equals("*")) { int a = deque.pop(), b = deque.pop(); deque.push(b * a); }
            else if (s.equals("/")) { int a = deque.pop(), b = deque.pop(); deque.push(b / a); }
            else deque.push(Integer.parseInt(s));
        }
        return deque.pop();
    }
}

239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int len = nums.length, index = 0;
        int[] res = new int[len - k + 1];
        for (int i = 0; i < len; i++) {
            while (!deque.isEmpty() && deque.peek() < i - k + 1) deque.poll();
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.offer(i);
            if (i >= k - 1) res[index++] = nums[deque.peek()];
        }
        return res;
    }
}

347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) pq.add(new int[]{entry.getKey(), entry.getValue()});
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = pq.poll()[0];
        return res;
    }
}

二叉树

144. 二叉树的前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop();
                if (node.right != null) deque.push(node.right);
                if (node.left != null) deque.push(node.left);
                deque.push(node); deque.push(null);
            } else {
                deque.pop(); node = deque.peek(); deque.pop(); res.add(node.val);
            }
        }
        return res;
    }
}

94. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop();
                if (node.right != null) deque.push(node.right);
                deque.push(node); deque.push(null);
                if (node.left != null) deque.push(node.left);
            } else {
                deque.pop(); res.add(deque.pop().val);
            }
        }
        return res;
    }
}

145. 二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop();
                deque.push(node); deque.push(null);
                if (node.right != null) deque.push(node.right);
                if (node.left != null) deque.push(node.left);
            } else {
                deque.pop(); res.add(deque.pop().val);
            }
        }
        return res;
    }
}

102. 二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        if (root == null) return resList;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            while (len > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                len--;
            }
            resList.add(list);
        }
        return resList;
    }
}

107. 二叉树的层序遍历 II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        Deque<List<Integer>> stack = new LinkedList<>();
        if (root == null) return resList;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = deque.size();
            while (len > 0) {
                TreeNode temp = deque.poll();
                list.add(temp.val);
                if (temp.left != null) deque.offer(temp.left);
                if (temp.right != null) deque.offer(temp.right);
                len--;
            }
            stack.push(list);
        }
        while (!stack.isEmpty()) resList.add(stack.pop());
        return resList;
    }
}

199. 二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode cur = deque.poll();
                if (len == 1) res.add(cur.val);
                if (cur.left != null) deque.offer(cur.left);
                if (cur.right != null) deque.offer(cur.right);
                len--;
            }
        }
        return res;
    }
}

429. N 叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> resList = new ArrayList<>();
        if (root == null) return resList;
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                Node temp = deque.poll();
                list.add(temp.val);
                if (temp.children != null) for (Node child : temp.children) if (child != null) deque.offer(child);
            }
            resList.add(list);
        }
        return resList;
    }
}

104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null) return depth;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode temp = deque.poll();
                if (len == 1) depth++;
                if (temp.left != null) deque.offer(temp.left);
                if (temp.right != null) deque.offer(temp.right);
                len--;
            }
        }
        return depth;
    }
}

111. 二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if (root == null) return depth;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode temp = deque.poll();
                if (temp.left == null && temp.right == null) { depth++; return depth; }
                if (len == 1) depth++;
                if (temp.left != null) deque.offer(temp.left);
                if (temp.right != null) deque.offer(temp.right);
                len--;
            }
        }
        return depth;
    }
}

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left; root.left = root.right; root.right = temp;
        invertTree(root.left); invertTree(root.right);
        return root;
    }
}

101. 对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSame(root.left, root.right);
    }
    private boolean isSame(TreeNode left, TreeNode right) {
        if (left == null && right != null) return false;
        if (left != null && right == null) return false;
        if (left == null && right == null) return true;
        if (left.val != right.val) return false;
        return isSame(left.left, right.right) && isSame(left.right, right.left);
    }
}

572. 另一棵树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode temp = deque.poll();
                if (temp.val == subRoot.val && isSame(temp, subRoot)) return true;
                if (temp.left != null) deque.offer(temp.left);
                if (temp.right != null) deque.offer(temp.right);
                len--;
            }
        }
        return false;
    }
    private boolean isSame(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSame(left.left, right.left) && isSame(left.right, right.right);
    }
}

222. 完全二叉树的节点个数

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left, right = root.right;
        int leftDep = 1, rightDep = 1;
        while (left != null) { left = left.left; leftDep++; }
        while (right != null) { right = right.right; rightDep++; }
        if (leftDep == rightDep) return (int) Math.pow(2, rightDep) - 1;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110. 平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
        int leftHeight = getHeight(node.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

700. 二叉搜索树中的搜索

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val > val) root = root.left;
            else if (root.val < val) root = root.right;
            else return root;
        }
        return null;
    }
}

98. 验证二叉搜索树

class Solution {
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= prev) return false;
        prev = root.val;
        return isValidBST(root.right);
    }
}

236. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null) return null;
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}

543. 二叉树的直径

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left), right = depth(node.right);
        ans = Math.max(ans, left + right + 1);
        return Math.max(left, right) + 1;
    }
}

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedBST(nums, 0, nums.length - 1);
    }
    private TreeNode sortedBST(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedBST(nums, left, mid - 1);
        root.right = sortedBST(nums, mid + 1, right);
        return root;
    }
}

230. 二叉搜索树中第 K 小的元素

class Solution {
    int count = 0, ans;
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return ans;
    }
    private void inOrder(TreeNode node, int k) {
        if (node == null) return;
        inOrder(node.left, k);
        if (++count == k) ans = node.val;
        inOrder(node.right, k);
    }
}

114. 二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        preTraversal(root, deque);
        while (!deque.isEmpty()) {
            TreeNode cur = deque.poll();
            cur.left = null;
            cur.right = deque.peek();
        }
    }
    private void preTraversal(TreeNode root, Deque<TreeNode> deque) {
        if (root == null) return;
        deque.offer(root);
        preTraversal(root.left, deque);
        preTraversal(root.right, deque);
    }
}

回溯

77. 组合

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return res;
    }
    private void backTracking(int n, int k, int startIndex) {
        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backTracking(n, k, i + 1);
            path.removeLast();
        }
    }
}

216. 组合总和 III

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return res;
    }
    private void backTracking(int k, int n, int startIndex) {
        if (path.size() == k && n == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = startIndex; i <= 9; i++) {
            if (n - i < 0) break;
            path.add(i);
            backTracking(k, n - i, i + 1);
            path.removeLast();
        }
    }
}

17. 电话号码的字母组合

class Solution {
    private static final Map<Character, String> map = new HashMap<>();
    private List<String> res = new ArrayList<>();
    private StringBuilder sb = new StringBuilder();
    static { map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); }
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return res;
        backTracking(digits, 0);
        return res;
    }
    private void backTracking(String digits, int startIndex) {
        if (sb.length() == digits.length()) { res.add(new String(sb)); return; }
        for (int i = startIndex; i < digits.length(); i++) {
            String letters = map.get(digits.charAt(i));
            for (char c : letters.toCharArray()) {
                sb.append(c);
                backTracking(digits, i + 1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}

39. 组合总和

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return res;
    }
    private void backTracking(int[] candidates, int target, int startIndex) {
        if (target == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            path.add(candidates[i]);
            backTracking(candidates, target - candidates[i], i);
            path.removeLast();
        }
    }
}

40. 组合总和 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return res;
    }
    private void backTracking(int[] candidates, int target, int startIndex) {
        if (target == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            if (i > startIndex && candidates[i] == candidates[i - 1]) continue;
            path.add(candidates[i]);
            backTracking(candidates, target - candidates[i], i + 1);
            path.removeLast();
        }
    }
}

131. 分割回文串

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, 0, new StringBuilder());
        return res;
    }
    private void backTracking(String s, int startIndex, StringBuilder sb) {
        if (startIndex == s.length()) { res.add(new ArrayList<>(path)); return; }
        for (int i = startIndex; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (check(sb)) { path.add(sb.toString()); backTracking(s, i + 1, new StringBuilder()); path.removeLast(); }
        }
    }
    private boolean check(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) return false;
        return true;
    }
}

78. 子集

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums, 0);
        return res;
    }
    private void backTracking(int[] nums, int startIndex) {
        res.add(new LinkedList<>(path));
        if (startIndex == nums.length) return;
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

90. 子集 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums, 0);
        return res;
    }
    private void backTracking(int[] nums, int startIndex) {
        res.add(new LinkedList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46. 全排列

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return res;
    }
    private void backTracking(int[] nums) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.add(nums[i]);
            backTracking(nums);
            path.removeLast(); used[i] = false;
        }
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums, used);
        return res;
    }
    private void backTracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true; path.add(nums[i]);
            backTracking(nums, used);
            path.removeLast(); used[i] = false;
        }
    }
}

22. 括号生成

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n <= 0) return res;
        generateParenthesis(new StringBuilder(), n, n);
        return res;
    }
    private void generateParenthesis(StringBuilder path, int left, int right) {
        if (left == 0 && right == 0) { res.add(path.toString()); return; }
        if (left == right) { path.append('('); generateParenthesis(path, left - 1, right); path.deleteCharAt(path.length() - 1); }
        else if (left < right) {
            if (left > 0) { path.append('('); generateParenthesis(path, left - 1, right); path.deleteCharAt(path.length() - 1); }
            path.append(')'); generateParenthesis(path, left, right - 1); path.deleteCharAt(path.length() - 1);
        }
    }
}

79. 单词搜索

class Solution {
    int len, height;
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public boolean exist(char[][] board, String word) {
        height = board.length; len = board[0].length;
        boolean[][] used = new boolean[height][len];
        for (int i = 0; i < height; i++) for (int j = 0; j < len; j++) if (backTracking(board, i, j, word, 0, used)) return true;
        return false;
    }
    private boolean backTracking(char[][] board, int i, int j, String word, int index, boolean[][] used) {
        if (board[i][j] != word.charAt(index)) return false;
        else if (index == word.length() - 1) return true;
        used[i][j] = true;
        boolean res = false;
        for (int[] dir : direction) {
            int nextI = i + dir[0], nextJ = j + dir[1];
            if (nextI >= 0 && nextI < height && nextJ >= 0 && nextJ < len && !used[nextI][nextJ]) {
                if (backTracking(board, nextI, nextJ, word, index + 1, used)) { res = true; break; }
            }
        }
        used[i][j] = false;
        return res;
    }
}

51. N 皇后

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] ch : board) Arrays.fill(ch, '.');
        backTracking(board, 0, n);
        return res;
    }
    private void backTracking(char[][] board, int row, int n) {
        if (row == n) { res.add(construct(board)); return; }
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';
                backTracking(board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }
    private boolean isValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j--) if (board[i][j] == 'Q') return false;
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false;
        return true;
    }
    private List<String> construct(char[][] board) {
        List<String> ans = new ArrayList<>();
        for (char[] ch : board) ans.add(new String(ch));
        return ans;
    }
}

贪心算法

455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g); Arrays.sort(s);
        int num = s.length - 1, count = 0;
        for (int i = g.length - 1; i >= 0; i--) {
            if (num >= 0 && s[num] >= g[i]) { num--; count++; }
        }
        return count;
    }
}

121. 买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) minPrice = price;
            else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
        }
        return maxProfit;
    }
}

55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= right) {
                right = Math.max(right, i + nums[i]);
                if (right >= nums.length - 1) return true;
            }
        }
        return false;
    }
}

45. 跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) return 0;
        int ans = 0, cur = 0, next = 0;
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(next, i + nums[i]);
            if (next >= nums.length - 1) { ans++; break; }
            if (i == cur) { ans++; cur = next; }
        }
        return ans;
    }
}

1005. K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) { nums[i] = -nums[i]; k--; }
        }
        if (k % 2 == 1) { Arrays.sort(nums); nums[0] = -nums[0]; }
        return Arrays.stream(nums).sum();
    }
}

763. 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int[] last = new int[26];
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) last[ch[i] - 'a'] = i;
        int start = -1, end = 0;
        for (int i = 0; i < ch.length; i++) {
            end = Math.max(end, last[ch[i] - 'a']);
            if (end == i) { res.add(end - start); start = i; }
        }
        return res;
    }
}

动态规划

509. 斐波那契数

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
}

70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 0 || cost.length == 1) return 0;
        int[] dp = new int[cost.length + 1];
        dp[0] = 0; dp[1] = 0;
        for (int i = 2; i <= cost.length; i++) dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[cost.length];
    }
}

62. 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][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];
    }
}

63. 不同路径 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
}

343. 整数拆分

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) for (int j = 1; j <= i - j; j++) dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        return dp[n];
    }
}

96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
}

416. 分割等和子集（01 背包问题）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        int maxWeight = sum / 2;
        int[] dp = new int[maxWeight + 1];
        for (int i = 0; i < nums.length; i++) for (int j = maxWeight; j >= nums[i]; j--) dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        return dp[maxWeight] == maxWeight;
    }
}

198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[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];
    }
}

118. 杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) if (j == 0 || j == i) list.add(1);
            else list.add(dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j));
            dp.add(list);
        }
        return dp;
    }
}

213. 打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(commonRob(nums, 0, nums.length - 2), commonRob(nums, 1, nums.length - 1));
    }
    private int commonRob(int[] nums, int start, int end) {
        if (start == end) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start]; dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        return dp[end];
    }
}

337. 打家劫舍 III

class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        return Math.max(dfs(root)[0], dfs(root)[1]);
    }
    private int[] dfs(TreeNode node) {
        int[] dp = new int[2];
        if (node == null) return dp;
        int[] left = dfs(node.left), right = dfs(node.right);
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = node.val + left[0] + right[0];
        return dp;
    }
}

322. 零钱兑换（完全背包）

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[] dp = new int[amount + 1];
        int Max = Integer.MAX_VALUE;
        Arrays.fill(dp, Max); dp[0] = 0;
        for (int coin : coins) for (int j = coin; j <= amount; j++) if (dp[j - coin] != Max) dp[j] = Math.min(dp[j - coin] + 1, dp[j]);
        return dp[amount] == Max ? -1 : dp[amount];
    }
}

279. 完全平方数

class Solution {
    public int numSquares(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;
        for (int i = 1; i <= n; i++) for (int j = 1; j * j <= i; j++) dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        return dp[n];
    }
}

139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) for (int j = 0; j < i; j++) if (wordDict.contains(s.substring(j, i)) && dp[j]) { dp[i] = true; break; }
        return dp[s.length()];
    }
}

121. 买卖股票的最佳时机（只能买卖一次）

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0; dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) for (int j = 0; j < i; j++) if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        for (int i : dp) if (i > max) max = i;
        return max;
    }
}

152. 乘积最大子数组

class Solution {
    public int maxProduct(int[] nums) {
        int[] dpMax = new int[nums.length], dpMin = new int[nums.length];
        dpMax[0] = dpMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
        }
        return Arrays.stream(dpMax).max().getAsInt();
    }
}

122. 买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0; dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

123. 买卖股票的最佳时机 III

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][5];
        dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0; dp[0][3] = -prices[0]; dp[0][4] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.length - 1][4];
    }
}

674. 最长连续递增序列

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
        return Arrays.stream(dp).max().getAsInt();
    }
}

64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < grid[0].length; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < grid.length; i++) for (int j = 1; j < grid[0].length; j++) dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i++) dp[i][i] = true;
        int start = 0, maxLen = 1;
        for (int L = 2; L <= len; L++) for (int i = 0; i < len; i++) {
            int j = i + L - 1;
            if (j >= len) break;
            if (chars[i] != chars[j]) dp[i][j] = false;
            else if (j - i < 3) dp[i][j] = true;
            else dp[i][j] = dp[i + 1][j - 1];
            if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; }
        }
        return s.substring(start, start + maxLen);
    }
}

1143. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] ch1 = text1.toCharArray(), ch2 = text2.toCharArray();
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i <= text1.length(); i++) for (int j = 1; j <= text2.length(); j++) {
            if (ch1[i - 1] == ch2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
        return dp[text1.length()][text2.length()];
    }
}

72. 编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0 || word2.length() == 0) return Math.max(word1.length(), word2.length());
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); i++) dp[i][0] = i;
        for (int j = 1; j <= word2.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= word1.length(); i++) for (int j = 1; j <= word2.length(); j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
        }
        return dp[word1.length()][word2.length()];
    }
}

647. 回文子串

class Solution {
    public int countSubstrings(String s) {
        char[] ch = s.toCharArray();
        int len = ch.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) for (int j = i; j < len; j++) {
            if (ch[i] == ch[j]) {
                if (j - i <= 1) { result++; dp[i][j] = true; }
                else if (dp[i + 1][j - 1]) { result++; dp[i][j] = true; }
            }
        }
        return result;
    }
}

516. 最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] ch = s.toCharArray();
        int len = ch.length;
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if (ch[i] == ch[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j - 1], dp[i][j]));
            }
        }
        return dp[0][len - 1];
    }
}

单调栈

739. 每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < len; i++) {
            if (temperatures[i] <= temperatures[stack.peek()]) stack.push(i);
            else {
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}

496. 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) map.put(nums1[i], i);
        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[stack.peek()]) stack.push(i);
            else {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                    if (map.containsKey(nums2[stack.peek()])) res[map.get(nums2[stack.peek()])] = nums2[i];
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}

503. 下一个更大元素 II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if (nums.length <= 1) return new int[]{-1};
        int len = nums.length;
        int[] res = new int[len];
        Deque<Integer> stack = new LinkedList<>();
        Arrays.fill(res, -1);
        for (int i = 0; i < 2 * len; i++) {
            while (!stack.isEmpty() && nums[i % len] > nums[stack.peek()]) {
                res[stack.peek()] = nums[i % len];
                stack.pop();
            }
            stack.push(i % len);
        }
        return res;
    }
}

42. 接雨水

class Solution {
    public int trap(int[] height) {
        int size = height.length;
        if (size <= 2) return 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int sum = 0;
        for (int i = 1; i < size; i++) {
            int top = stack.peek();
            if (height[i] < height[top]) stack.push(i);
            else if (height[i] == height[top]) { stack.pop(); stack.push(i); }
            else {
                while (!stack.isEmpty() && height[i] > height[top]) {
                    int mid = height[stack.pop()];
                    if (!stack.isEmpty()) {
                        int h = Math.min(height[i], height[stack.peek()]) - mid;
                        int w = i - stack.peek() - 1;
                        sum += h * w;
                        top = stack.peek();
                    }
                }
                stack.push(i);
            }
        }
        return sum;
    }
}

84. 柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] height = new int[heights.length + 2];
        height[0] = 0; height[height.length - 1] = 0;
        for (int i = 0; i < heights.length; i++) height[i + 1] = heights[i];
        Deque<Integer> stack = new LinkedList<>();
        int area = 0;
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            if (height[i] > height[stack.peek()]) stack.push(i);
            else if (height[i] == height[stack.peek()]) { stack.pop(); stack.push(i); }
            else {
                while (!stack.isEmpty() && height[i] < height[stack.peek()]) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int h = height[mid];
                        int w = i - stack.peek() - 1;
                        area = Math.max(h * w, area);
                    }
                }
                stack.push(i);
            }
        }
        return area;
    }
}

图论

98. 所有可达路径（图的 DFS 经典题目）【邻接矩阵存储图】

import java.util.*;
public class Main {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) graph[scan.nextInt()][scan.nextInt()] = 1;
        path.add(1);
        dfs(graph, 1, n);
        if (result.size() == 0) System.out.println(-1);
        for (List<Integer> temp : result) {
            for (int i = 0; i < temp.size() - 1; i++) System.out.print(temp.get(i) + " ");
            System.out.println(temp.get(temp.size() - 1));
        }
    }
    public static void dfs(int[][] graph, int x, int n) {
        if (x == n) { result.add(new ArrayList<>(path)); return; }
        for (int i = 1; i <= n; i++) {
            if (graph[x][i] == 1) { path.add(i); dfs(graph, i, n); path.remove(path.size() - 1); }
        }
    }
}

98. 所有可达路径（图的 DFS 经典题目）【邻接表存储图】

import java.util.*;
public class Main {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<LinkedList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new LinkedList<>());
        while (m-- > 0) graph.get(scan.nextInt()).add(scan.nextInt());
        path.add(1);
        dfs(graph, 1, n);
        if (result.isEmpty()) System.out.println(-1);
        for (List<Integer> temp : result) {
            for (int i = 0; i < temp.size() - 1; i++) System.out.print(temp.get(i) + " ");
            System.out.println(temp.get(temp.size() - 1));
        }
    }
    public static void dfs(List<LinkedList<Integer>> graph, int x, int n) {
        if (x == n) { result.add(new ArrayList<>(path)); return; }
        for (int i : graph.get(x)) { path.add(i); dfs(graph, i, n); path.remove(path.size() - 1); }
    }
}

99. 岛屿数量（广搜方法）

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) map[i][j] = scan.nextInt();
        boolean[][] visit = new boolean[n][m];
        int ans = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!visit[i][j] && map[i][j] == 1) { ans++; bfs(map, visit, i, j); }
        System.out.println(ans);
    }
    public static void bfs(int[][] map, boolean[][] visit, int x, int y) {
        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visit[x][y] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.pop();
            for (int i = 0; i < 4; i++) {
                int nextX = cur[0] + dir[i][0], nextY = cur[1] + dir[i][1];
                if (nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[0].length) continue;
                if (map[nextX][nextY] == 1 && !visit[nextX][nextY]) { queue.push(new int[]{nextX, nextY}); visit[nextX][nextY] = true; }
            }
        }
    }
}

99. 岛屿数量（深搜方法）

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(), M = scan.nextInt();
        int[][] grid = new int[N][M];
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) grid[i][j] = scan.nextInt();
        int ans = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (!visit[i][j] && grid[i][j] == 1) { ans++; visit[i][j] = true; dfs(grid, visit, i, j); }
        System.out.println(ans);
    }
    private static void dfs(int[][] grid, boolean[][] visit, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (!visit[nextX][nextY] && grid[nextX][nextY] == 1) { visit[nextX][nextY] = true; dfs(grid, visit, nextX, nextY); }
        }
    }
}

100. 最大岛屿的面积（深搜方法）

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int result = 0, count = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(), M = scan.nextInt();
        int[][] grid = new int[N][M];
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) grid[i][j] = scan.nextInt();
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (!visit[i][j] && grid[i][j] == 1) { count = 0; dfs(grid, visit, i, j); result = Math.max(result, count); }
        System.out.println(result);
    }
    private static void dfs(int[][] grid, boolean[][] visit, int x, int y) {
        if (visit[x][y] || grid[x][y] == 0) return;
        count++; visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            dfs(grid, visit, nextX, nextY);
        }
    }
}

100. 最大岛屿的面积（广搜方法）

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int result = 0, count = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(), M = scan.nextInt();
        int[][] grid = new int[N][M];
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) grid[i][j] = scan.nextInt();
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (!visit[i][j] && grid[i][j] == 1) { count = 0; bfs(grid, visit, i, j); result = Math.max(result, count); }
        System.out.println(result);
    }
    private static void bfs(int[][] grid, boolean[][] visit, int x, int y) {
        Deque<int[]> deque = new LinkedList<>();
        deque.push(new int[]{x, y});
        count++; visit[x][y] = true;
        while (!deque.isEmpty()) {
            int[] cur = deque.pop();
            for (int i = 0; i < 4; i++) {
                int nextX = cur[0] + dir[i][0], nextY = cur[1] + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (!visit[nextX][nextY] && grid[nextX][nextY] == 1) { deque.push(new int[]{nextX, nextY}); visit[nextX][nextY] = true; count++; }
            }
        }
    }
}

101. 孤岛的总面积

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static boolean isEdge = false, s = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(), M = scan.nextInt();
        int[][] grid = new int[N][M];
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) grid[i][j] = scan.nextInt();
        int result = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (!visit[i][j] && grid[i][j] == 1) { isEdge = false; s = 0; dfs(grid, visit, i, j); if (!isEdge) result += s; }
        System.out.println(result);
    }
    private static void dfs(int[][] grid, boolean[][] visit, int x, int y) {
        if (visit[x][y] || grid[x][y] == 0) return;
        s++; visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) { isEdge = true; continue; }
            dfs(grid, visit, nextX, nextY);
        }
    }
}

102. 沉没孤岛

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(), M = scan.nextInt();
        int[][] grid = new int[N][M];
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) grid[i][j] = scan.nextInt();
        for (int i = 0; i < N; i++) { if (grid[i][0] == 1) dfs(grid, i, 0); if (grid[i][M - 1] == 1) dfs(grid, i, M - 1); }
        for (int i = 0; i < M; i++) { if (grid[0][i] == 1) dfs(grid, 0, i); if (grid[N - 1][i] == 1) dfs(grid, N - 1, i); }
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (grid[i][j] == 1) grid[i][j] = 0; if (grid[i][j] == 2) grid[i][j] = 1; }
        for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) System.out.print(grid[i][j] + " "); System.out.println(); }
    }
    private static void dfs(int[][] grid, int x, int y) {
        if (grid[x][y] == 2 || grid[x][y] == 0) return;
        grid[x][y] = 2;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            dfs(grid, nextX, nextY);
        }
    }
}

103. 水流问题

import java.util.*;
public class Main {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] height = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) height[i][j] = scan.nextInt();
        boolean[][] first = new boolean[n][m], second = new boolean[n][m];
        for (int i = 0; i < n; i++) { dfs(height, first, i, 0, Integer.MIN_VALUE); dfs(height, second, i, m - 1, Integer.MIN_VALUE); }
        for (int i = 0; i < m; i++) { dfs(height, first, 0, i, Integer.MIN_VALUE); dfs(height, second, n - 1, i, Integer.MIN_VALUE); }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (first[i][j] && second[i][j]) result.add(Arrays.asList(i, j));
        for (List<Integer> list : result) { for (int i = 0; i < list.size(); i++) System.out.print(list.get(i) + (i == list.size() - 1 ? "" : " ")); System.out.println(); }
    }
    public static void dfs(int[][] height, boolean[][] visit, int x, int y, int preHeight) {
        if (x < 0 || x >= height.length || y < 0 || y >= height[0].length) return;
        if (height[x][y] < preHeight || visit[x][y]) return;
        visit[x][y] = true;
        for (int i = 0; i < 4; i++) dfs(height, visit, x + dir[i][0], y + dir[i][1], height[x][y]);
    }
}

104. 建造最大岛屿

import java.util.*;
public class Main {
    static int mark, count;
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] visit = new boolean[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid[i][j] = scan.nextInt();
        mark = 2;
        Map<Integer, Integer> size = new HashMap<>();
        boolean isAllIsland = true;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (grid[i][j] == 0) isAllIsland = false;
            if (grid[i][j] == 1) { count = 0; dfs(grid, visit, i, j); size.put(mark, count); mark++; }
        }
        int result = isAllIsland ? m * n : 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j] == 0) {
            set.clear(); int curSize = 1;
            for (int[] dir : dirs) {
                int curX = i + dir[0], curY = j + dir[1];
                if (curX < 0 || curX >= n || curY < 0 || curY >= m) continue;
                int curMark = grid[curX][curY];
                if (set.contains(curMark) || !size.containsKey(curMark)) continue;
                curSize += size.get(curMark); set.add(curMark);
            }
            result = Math.max(curSize, result);
        }
        System.out.println(result);
    }
    public static void dfs(int[][] grid, boolean[][] visit, int x, int y) {
        count++; visit[x][y] = true; grid[x][y] = mark;
        for (int[] dir : dirs) {
            int nextX = x + dir[0], nextY = y + dir[1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (grid[nextX][nextY] == 0 || visit[nextX][nextY]) continue;
            dfs(grid, visit, nextX, nextY);
        }
    }
}

106. 岛屿的周长

import java.util.*;
public class Main {
    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int count;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid[i][j] = scan.nextInt();
        int result = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j] == 1) { count = 0; sum(grid, i, j); result += count; }
        System.out.println(result);
    }
    public static void sum(int[][] grid, int x, int y) {
        for (int[] di : dir) {
            int nextX = x + di[0], nextY = y + di[1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] == 0) count++;
        }
    }
}

110. 字符串接龙

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String beginStr = scan.next(), endStr = scan.next();
        scan.nextLine();
        List<String> strList = new ArrayList<>();
        strList.add(beginStr); strList.add(endStr);
        for (int i = 0; i < n; i++) strList.add(scan.nextLine());
        System.out.println(bfs(strList, beginStr, endStr));
    }
    public static int bfs(List<String> strList, String beginStr, String endStr) {
        int len = 1;
        Set<String> wordSet = new HashSet<>(strList);
        Set<String> visit = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginStr); visit.add(beginStr);
        queue.offer(null);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            if (node == null) {
                if (!queue.isEmpty()) { len++; queue.offer(null); } continue;
            }
            char[] chararray = node.toCharArray();
            for (int i = 0; i < chararray.length; i++) {
                char old = chararray[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    chararray[i] = j;
                    String newWord = new String(chararray);
                    if (wordSet.contains(newWord) && !visit.contains(newWord)) {
                        queue.offer(newWord); visit.add(newWord);
                        if (newWord.equals(endStr)) return len + 1;
                    }
                }
                chararray[i] = old;
            }
        }
        return 0;
    }
}

105. 有向图的完全联通

import java.util.*;
public class Main {
    static List<List<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), k = scan.nextInt();
        for (int i = 0; i < n; i++) graph.add(new LinkedList<>());
        for (int i = 0; i < k; i++) graph.get(scan.nextInt() - 1).add(scan.nextInt() - 1);
        boolean[] visit = new boolean[n];
        dfs(visit, 0);
        for (int i = 0; i < n; i++) if (!visit[i]) { System.out.println(-1); return; }
        System.out.println(1);
    }
    public static void dfs(boolean[] visit, int x) {
        if (visit[x]) return;
        visit[x] = true;
        for (int nextKey : graph.get(x)) dfs(visit, nextKey);
    }
}

107. 寻找存在的路径

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        DisJoint disjoint = new DisJoint(n + 1);
        for (int i = 0; i < m; i++) disjoint.join(scan.nextInt(), scan.nextInt());
        boolean flag = disjoint.isSame(scan.nextInt(), scan.nextInt());
        System.out.println(flag ? 1 : 0);
    }
}
class DisJoint {
    private int[] father;
    public DisJoint(int N) { father = new int[N]; for (int i = 0; i < N; i++) father[i] = i; }
    public int find(int n) { return n == father[n] ? n : (father[n] = find(father[n])); }
    public void join(int n, int m) { n = find(n); m = find(m); if (n == m) return; father[m] = n; }
    public boolean isSame(int n, int m) { return find(n) == find(m); }
}

108. 冗余连接

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        DisJoint disjoint = new DisJoint(n + 1);
        for (int i = 0; i < n; i++) {
            int s = scan.nextInt(), t = scan.nextInt();
            if (disjoint.isSame(s, t)) { System.out.println(s + " " + t); return; }
            else disjoint.join(s, t);
        }
    }
}
class DisJoint {
    private int[] father;
    public DisJoint(int N) { father = new int[N]; for (int i = 0; i < N; i++) father[i] = i; }
    public int find(int n) { return n == father[n] ? n : (father[n] = find(father[n])); }
    public void join(int n, int m) { n = find(n); m = find(m); if (n == m) return; father[m] = n; }
    public boolean isSame(int n, int m) { return find(n) == find(m); }
}

109. 冗余连接 II

import java.util.*;
public class Main {
    static class Edge { int s, t; public Edge(int s, int t) { this.s = s; this.t = t; } }
    static class Node { int id, in, out; }
    static class Disjoint {
        private int[] father;
        public Disjoint(int n) { father = new int[n]; for (int i = 0; i < n; i++) father[i] = i; }
        public int find(int n) { return father[n] == n ? n : (father[n] = find(father[n])); }
        public void join(int s, int v) { s = find(s); v = find(v); if (s == v) return; father[s] = v; }
        public boolean isSame(int m, int n) { return find(m) == find(n); }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<Edge> edges = new ArrayList<>();
        Node[] nodeMap = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodeMap[i] = new Node();
        int doubleIn = 0;
        for (int i = 0; i < n; i++) {
            int s = scan.nextInt(), t = scan.nextInt();
            nodeMap[t].in++;
            if (nodeMap[t].in >= 2) doubleIn = t;
            edges.add(new Edge(s, t));
        }
        Edge result = null;
        if (doubleIn != 0) {
            List<Edge> doubleInEdges = new ArrayList<>();
            for (Edge edge : edges) { if (edge.t == doubleIn) doubleInEdges.add(edge); if (doubleInEdges.size() == 2) break; }
            Edge edge = doubleInEdges.get(1);
            if (isTree(edges, edge, nodeMap)) result = edge;
            else result = doubleInEdges.get(0);
        } else result = findResultEdge(edges, nodeMap);
        System.out.println(result.s + " " + result.t);
    }
    public static boolean isTree(List<Edge> edges, Edge resultEdge, Node[] nodeMap) {
        Disjoint disjoint = new Disjoint(nodeMap.length + 1);
        for (Edge edge : edges) { if (edge == resultEdge) continue; if (disjoint.isSame(edge.s, edge.t)) return false; disjoint.join(edge.s, edge.t); }
        return true;
    }
    public static Edge findResultEdge(List<Edge> edges, Node[] nodeMap) {
        Disjoint disjoint = new Disjoint(nodeMap.length + 1);
        for (Edge edge : edges) { if (disjoint.isSame(edge.s, edge.t)) return edge; disjoint.join(edge.s, edge.t); }
        return null;
    }
}

最小生成树之 Prim 算法

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int v = scan.nextInt(), e = scan.nextInt();
        int[][] grid = new int[v + 1][v + 1];
        for (int i = 0; i <= v; i++) Arrays.fill(grid[i], 10001);
        for (int i = 0; i < e; i++) {
            int v1 = scan.nextInt(), v2 = scan.nextInt(), val = scan.nextInt();
            grid[v1][v2] = val; grid[v2][v1] = val;
        }
        int[] minDist = new int[v + 1];
        Arrays.fill(minDist, 10001);
        boolean[] isInTree = new boolean[v + 1];
        for (int i = 1; i < v; i++) {
            int cur = -1, mindist = Integer.MAX_VALUE;
            for (int j = 1; j <= v; j++) if (!isInTree[j] && minDist[j] < mindist) { cur = j; mindist = minDist[j]; }
            isInTree[cur] = true;
            for (int j = 1; j <= v; j++) if (!isInTree[j] && grid[cur][j] < minDist[j]) minDist[j] = grid[cur][j];
        }
        int result = 0;
        for (int i = 2; i <= v; i++) result += minDist[i];
        System.out.println(result);
    }
}

最小生成树之 Kruskal 算法

import java.util.*;
public class Main {
    static class Edge { int v1, v2, val; public Edge(int v1, int v2, int val) { this.v1 = v1; this.v2 = v2; this.val = val; } }
    static class Disjoint {
        private int[] father;
        public Disjoint(int n) { father = new int[n]; for (int i = 0; i < n; i++) father[i] = i; }
        public int find(int n) { return father[n] == n ? n : (father[n] = find(father[n])); }
        public void join(int s, int v) { s = find(s); v = find(v); if (s == v) return; father[s] = v; }
        public boolean isSame(int s, int v) { return find(s) == find(v); }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int V = scan.nextInt(), E = scan.nextInt();
        List<Edge> edges = new ArrayList<>();
        while (E-- > 0) edges.add(new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt()));
        int result = 0;
        edges.sort(Comparator.comparingInt(e -> e.val));
        Disjoint disjoint = new Disjoint(10001);
        for (Edge edge : edges) {
            if (!disjoint.isSame(edge.v1, edge.v2)) { disjoint.join(edge.v1, edge.v2); result += edge.val; }
        }
        System.out.println(result);
    }
}

拓扑排序

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<List<Integer>> map = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) map.add(new ArrayList<>());
        for (int i = 0; i < m; i++) { int s = scan.nextInt(), t = scan.nextInt(); map.get(s).add(t); inDegree[t]++; }
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) if (inDegree[i] == 0) deque.offer(i);
        List<Integer> result = new LinkedList<>();
        while (!deque.isEmpty()) {
            int cur = deque.poll(); result.add(cur);
            for (int file : map.get(cur)) { inDegree[file]--; if (inDegree[file] == 0) deque.offer(file); }
        }
        if (result.size() == n) { for (int i = 0; i < result.size(); i++) System.out.print(result.get(i) + (i < result.size() - 1 ? " " : "")); }
        else System.out.println(-1);
    }
}

Dijkstra（朴素版）精讲

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] grid = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) Arrays.fill(grid[i], Integer.MAX_VALUE);
        int temp = 0;
        while (temp++ < m) grid[scan.nextInt()][scan.nextInt()] = scan.nextInt();
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        boolean[] visit = new boolean[n + 1];
        minDist[1] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE, cur = 0;
            for (int j = 1; j <= n; j++) if (!visit[j] && minDist[j] < min) { min = minDist[j]; cur = j; }
            visit[cur] = true;
            for (int j = 1; j <= n; j++) if (!visit[j] && grid[cur][j] != Integer.MAX_VALUE && minDist[cur] + grid[cur][j] < minDist[j]) minDist[j] = minDist[cur] + grid[cur][j];
        }
        System.out.println(minDist[n] == Integer.MAX_VALUE ? -1 : minDist[n]);
    }
}

Dijkstra（堆优化版）精讲

import java.util.*;
class Edge { int to, val; public Edge(int to, int val) { this.to = to; this.val = val; } }
class Pair<U, V> { U first; V second; public Pair(U first, V second) { this.first = first; this.second = second; } }
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i <= n; i++) grid.add(new ArrayList<>());
        int temp = 0;
        while (temp++ < m) grid.get(scan.nextInt()).add(new Edge(scan.nextInt(), scan.nextInt()));
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        boolean[] visit = new boolean[n + 1];
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((p1, p2) -> p1.second - p2.second);
        pq.add(new Pair<>(1, 0));
        minDist[1] = 0;
        while (!pq.isEmpty()) {
            Pair<Integer, Integer> cur = pq.poll();
            if (visit[cur.first]) continue;
            visit[cur.first] = true;
            for (Edge edge : grid.get(cur.first)) if (!visit[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { minDist[edge.to] = minDist[cur.first] + edge.val; pq.add(new Pair<>(edge.to, minDist[edge.to])); }
        }
        System.out.println(minDist[n] == Integer.MAX_VALUE ? -1 : minDist[n]);
    }
}

Bellman-Ford 算法精讲

import java.util.*;
public class Main {
    static class Edge { int from, end, val; public Edge(int from, int end, int val) { this.from = from; this.end = end; this.val = val; } }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<Edge> grid = new LinkedList<>();
        int temp = 0;
        while (temp++ < m) grid.add(new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt()));
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        for (int i = 0; i < n; i++) for (Edge edge : grid) if (minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.end]) minDist[edge.end] = minDist[edge.from] + edge.val;
        System.out.println(minDist[n] == Integer.MAX_VALUE ? "unconnected" : minDist[n]);
    }
}

Bellman-Ford 队列优化算法（SPFA）

import java.util.*;
public class Main {
    static class Edge { int from, end, val; public Edge(int from, int end, int val) { this.from = from; this.end = end; this.val = val; } }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<List<Edge>> grid = new LinkedList<>();
        for (int i = 0; i <= n; i++) grid.add(new LinkedList<>());
        int temp = 0;
        while (temp++ < m) { int from = scan.nextInt(), end = scan.nextInt(), val = scan.nextInt(); grid.get(from).add(new Edge(from, end, val)); }
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(1);
        boolean[] visit = new boolean[n + 1];
        while (!deque.isEmpty()) {
            int curNode = deque.poll(); visit[curNode] = false;
            for (Edge edge : grid.get(curNode)) if (minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.end]) {
                minDist[edge.end] = minDist[edge.from] + edge.val;
                if (!visit[edge.end]) { deque.offer(edge.end); visit[edge.end] = true; }
            }
        }
        System.out.println(minDist[n] == Integer.MAX_VALUE ? "unconnected" : minDist[n]);
    }
}

Bellman-Ford 之判断负权回路

import java.util.*;
public class Main {
    static class Edge { int from, end, val; public Edge(int from, int end, int val) { this.from = from; this.end = end; this.val = val; } }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<List<Edge>> grid = new LinkedList<>();
        for (int i = 0; i <= n; i++) grid.add(new LinkedList<>());
        int temp = 0;
        while (temp++ < m) { int from = scan.nextInt(), end = scan.nextInt(), val = scan.nextInt(); grid.get(from).add(new Edge(from, end, val)); }
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(1);
        boolean[] visit = new boolean[n + 1];
        int[] count = new int[n + 1];
        count[1]++;
        boolean flag = false;
        while (!deque.isEmpty()) {
            int curNode = deque.poll(); visit[curNode] = false;
            for (Edge edge : grid.get(curNode)) if (minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.end]) {
                minDist[edge.end] = minDist[edge.from] + edge.val;
                if (!visit[edge.end]) { deque.offer(edge.end); visit[edge.end] = true; count[edge.end]++; }
                if (count[edge.end] == n) { flag = true; while (!deque.isEmpty()) deque.poll(); break; }
            }
        }
        if (flag) System.out.println("circle");
        else if (minDist[n] == Integer.MAX_VALUE) System.out.println("unconnected");
        else System.out.println(minDist[n]);
    }
}

Bellman-Ford 之单源有限最短路

import java.util.*;
public class Main {
    static class Edge { int from, end, val; public Edge(int from, int end, int val) { this.from = from; this.end = end; this.val = val; } }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        List<Edge> grid = new LinkedList<>();
        int temp = 0;
        while (temp++ < m) grid.add(new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt()));
        int start = scan.nextInt(), end = scan.nextInt(), k = scan.nextInt();
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;
        for (int i = 0; i < k + 1; i++) {
            int[] minDistCopy = Arrays.copyOf(minDist, n + 1);
            for (Edge edge : grid) if (minDistCopy[edge.from] != Integer.MAX_VALUE && minDistCopy[edge.from] + edge.val < minDist[edge.end]) minDist[edge.end] = minDistCopy[edge.from] + edge.val;
        }
        System.out.println(minDist[end] == Integer.MAX_VALUE ? "unreachable" : minDist[end]);
    }
}

Floyd 算法精讲（多源最短路径问题）

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][][] dp = new int[n + 1][n + 1][n + 1];
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 0; k <= n; k++) dp[i][j][k] = 10001;
        for (int i = 0; i < m; i++) { int from = scan.nextInt(), end = scan.nextInt(), val = scan.nextInt(); dp[from][end][0] = dp[end][from][0] = val; }
        for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j][k] = Math.min(dp[i][k][k - 1] + dp[k][j][k - 1], dp[i][j][k - 1]);
        int q = scan.nextInt();
        for (int i = 0; i < q; i++) { int start = scan.nextInt(), end = scan.nextInt(); System.out.println(dp[start][end][n] == 10001 ? -1 : dp[start][end][n]); }
    }
}

Floyd 算法的二维数组简化方法

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = 10001;
        for (int i = 0; i < m; i++) { int from = scan.nextInt(), end = scan.nextInt(), val = scan.nextInt(); dp[from][end] = dp[end][from] = val; }
        for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
        int q = scan.nextInt();
        for (int i = 0; i < q; i++) { int start = scan.nextInt(), end = scan.nextInt(); System.out.println(dp[start][end] == 10001 ? -1 : dp[start][end]); }
    }
}

A* 算法精讲

import java.util.*;
public class Main {
    static int[][] moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
    static int endX, endY;
    static PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.f - n2.f);
    static int[][] steps = new int[1001][1001];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for (int i = 0; i < n; i++) {
            for (int[] step : steps) Arrays.fill(step, 0);
            Node start = new Node();
            start.x = scan.nextInt(); start.y = scan.nextInt();
            endX = scan.nextInt(); endY = scan.nextInt();
            start.g = 0; start.h = distance(start); start.f = start.g + start.h;
            aStar(start);
            System.out.println(steps[endX][endY]);
            queue.clear();
        }
    }
    public static void aStar(Node node) {
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.x == endX && cur.y == endY) return;
            for (int[] move : moves) {
                int nextX = cur.x + move[0], nextY = cur.y + move[1];
                if (nextX < 1 || nextX >= 1001 || nextY < 1 || nextY >= 1001) continue;
                if (steps[nextX][nextY] == 0) {
                    steps[nextX][nextY] = steps[cur.x][cur.y] + 1;
                    Node next = new Node();
                    next.x = nextX; next.y = nextY;
                    next.g = cur.g + 5; next.h = distance(next); next.f = next.g + next.h;
                    queue.add(next);
                }
            }
        }
    }
    public static int distance(Node node) { return (node.x - endX) * (node.x - endX) + (node.y - endY) * (node.y - endY); }
}
class Node { int x, y, f, g, h; }