算法题目汇总
数组
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;
(nums[mid] > target) right = mid;
{ left = mid + ; rightBorder = mid; }
}
rightBorder;
}
{
, right = nums.length;
-;
(left < right) {
left + ((right - left) / );
(nums[mid] < target) left = mid + ;
(nums[mid] > target) right = mid;
{ right = mid; leftBorder = right; }
}
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 = ;
( ; i < horizontal.length; i++) {
horisum += horizontal[i];
result = Math.min(result, Math.abs((sum - horisum) - horisum));
}
;
( ; 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( val) {
(val);
prehead;
(cur.next != ) cur = cur.next;
cur.next = newtail; size++;
}
{
(index < || index > size) ;
(val), cur = prehead;
( ; i <= index - ; i++) cur = cur.next;
newnode.next = cur.next; cur.next = newnode; size++;
}
{
(index < || index >= size) ;
prehead;
( ; 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]));
(left < right && nums[right] == nums[right - ]) right--;
(left < right && nums[left] == nums[left + ]) left++;
right--; left++;
}
}
}
}
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 {
, end = ;
(start < sb.length()) {
(end < sb.length() && sb.charAt(end) != ) end++;
reverseString(sb, start, end - );
start = end + ; end = start + ;
}
}
}
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++) {
map.get(digits.charAt(i));
( c : letters.toCharArray()) {
sb.append(c);
backTracking(digits, i + );
sb.deleteCharAt(sb.length() - );
}
}
}
}
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] = ;
;
([] dir : direction) {
i + dir[], nextJ = j + dir[];
(nextI >= && nextI < height && nextJ >= && nextJ < len && !used[nextI][nextJ]) {
(backTracking(board, nextI, nextJ, word, index + , used)) { res = ; ; }
}
}
used[i][j] = ;
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;
( row - , j = col + ; i >= && j < n; i--, j--) (board[i][j] == ) ;
( row - , j = col - ; i >= && j >= ; i--, j--) (board[i][j] == ) ;
;
}
List<String> {
List<String> ans = <>();
([] ch : board) ans.add( (ch));
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[].length - ];
}
}
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 + ; start = i; }
}
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);
}
}
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 {
(x == n) { result.add( <>(path)); ; }
( ; i <= n; i++) {
(graph[x][i] == ) { path.add(i); dfs(graph, i, n); path.remove(path.size() - ); }
}
}
}
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 {
(x == n) { result.add( <>(path)); ; }
( i : graph.get(x)) { path.add(i); dfs(graph, i, n); path.remove(path.size() - ); }
}
}
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++) (!visit[i][j] && map[i][j] == ) { ans++; bfs(map, visit, i, j); }
System.out.println(ans);
}
{
Deque<[]> queue = <>();
queue.add( []{x, y});
visit[x][y] = ;
(!queue.isEmpty()) {
[] cur = queue.pop();
( ; i < ; i++) {
cur[] + dir[i][], nextY = cur[] + dir[i][];
(nextX < || nextX >= map.length || nextY < || nextY >= map[].length) ;
(map[nextX][nextY] == && !visit[nextX][nextY]) { queue.push( []{nextX, nextY}); visit[nextX][nextY] = ; }
}
}
}
}
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++) (!visit[i][j] && grid[i][j] == ) { ans++; visit[i][j] = ; dfs(grid, visit, i, j); }
System.out.println(ans);
}
{
( ; i < ; i++) {
x + dir[i][], nextY = y + dir[i][];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) ;
(!visit[nextX][nextY] && grid[nextX][nextY] == ) { visit[nextX][nextY] = ; 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 < M; j++) (!visit[i][j] && grid[i][j] == ) { count = ; dfs(grid, visit, i, j); result = Math.max(result, count); }
System.out.println(result);
}
{
(visit[x][y] || grid[x][y] == ) ;
count++; visit[x][y] = ;
( ; i < ; i++) {
x + dir[i][], nextY = y + dir[i][];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) ;
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 < M; j++) (!visit[i][j] && grid[i][j] == ) { count = ; bfs(grid, visit, i, j); result = Math.max(result, count); }
System.out.println(result);
}
{
Deque<[]> deque = <>();
deque.push( []{x, y});
count++; visit[x][y] = ;
(!deque.isEmpty()) {
[] cur = deque.pop();
( ; i < ; i++) {
cur[] + dir[i][], nextY = cur[] + dir[i][];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) ;
(!visit[nextX][nextY] && grid[nextX][nextY] == ) { deque.push( []{nextX, nextY}); visit[nextX][nextY] = ; 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 ; i < N; i++) ( ; j < M; j++) (!visit[i][j] && grid[i][j] == ) { isEdge = ; s = ; dfs(grid, visit, i, j); (!isEdge) result += s; }
System.out.println(result);
}
{
(visit[x][y] || grid[x][y] == ) ;
s++; visit[x][y] = ;
( ; i < ; i++) {
x + dir[i][], nextY = y + dir[i][];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) { isEdge = ; ; }
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 ; i < M; i++) { (grid[][i] == ) dfs(grid, , i); (grid[N - ][i] == ) dfs(grid, N - , i); }
( ; i < N; i++) ( ; j < M; j++) { (grid[i][j] == ) grid[i][j] = ; (grid[i][j] == ) grid[i][j] = ; }
( ; i < N; i++) { ( ; j < M; j++) System.out.print(grid[i][j] + ); System.out.println(); }
}
{
(grid[x][y] == || grid[x][y] == ) ;
grid[x][y] = ;
( ; i < ; i++) {
x + dir[i][], nextY = y + dir[i][];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) ;
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 < m; i++) { dfs(height, first, , i, Integer.MIN_VALUE); dfs(height, second, n - , i, Integer.MIN_VALUE); }
List<List<Integer>> result = <>();
( ; i < n; i++) ( ; j < m; j++) (first[i][j] && second[i][j]) result.add(Arrays.asList(i, j));
(List<Integer> list : result) { ( ; i < list.size(); i++) System.out.print(list.get(i) + (i == list.size() - ? : )); System.out.println(); }
}
{
(x < || x >= height.length || y < || y >= height[].length) ;
(height[x][y] < preHeight || visit[x][y]) ;
visit[x][y] = ;
( ; i < ; i++) dfs(height, visit, x + dir[i][], y + dir[i][], 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 ; i < n; i++) ( ; j < m; j++) {
(grid[i][j] == ) isAllIsland = ;
(grid[i][j] == ) { count = ; dfs(grid, visit, i, j); size.put(mark, count); mark++; }
}
isAllIsland ? m * n : ;
Set<Integer> set = <>();
( ; i < n; i++) ( ; j < m; j++) (grid[i][j] == ) {
set.clear(); ;
([] dir : dirs) {
i + dir[], curY = j + dir[];
(curX < || curX >= n || curY < || curY >= m) ;
grid[curX][curY];
(set.contains(curMark) || !size.containsKey(curMark)) ;
curSize += size.get(curMark); set.add(curMark);
}
result = Math.max(curSize, result);
}
System.out.println(result);
}
{
count++; visit[x][y] = ; grid[x][y] = mark;
([] dir : dirs) {
x + dir[], nextY = y + dir[];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length) ;
(grid[nextX][nextY] == || visit[nextX][nextY]) ;
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] == ) { count = ; sum(grid, i, j); result += count; }
System.out.println(result);
}
{
([] di : dir) {
x + di[], nextY = y + di[];
(nextX < || nextX >= grid.length || nextY < || nextY >= grid[].length || grid[nextX][nextY] == ) 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 == ) {
(!queue.isEmpty()) { len++; queue.offer(); } ;
}
[] chararray = node.toCharArray();
( ; i < chararray.length; i++) {
chararray[i];
( ; j <= ; j++) {
chararray[i] = j;
(chararray);
(wordSet.contains(newWord) && !visit.contains(newWord)) {
queue.offer(newWord); visit.add(newWord);
(newWord.equals(endStr)) len + ;
}
}
chararray[i] = old;
}
}
;
}
}
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) {
(visit[x]) ;
visit[x] = ;
( 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])); }
{ n = find(n); m = find(m); (n == m) ; father[m] = n; }
{ 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) { n == father[n] ? n : (father[n] = find(father[n])); }
{ n = find(n); m = find(m); (n == m) ; father[m] = n; }
{ 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); }
}
{
(System.in);
scan.nextInt();
List<Edge> edges = <>();
Node[] nodeMap = [n + ];
( ; i <= n; i++) nodeMap[i] = ();
;
( ; i < n; i++) {
scan.nextInt(), t = scan.nextInt();
nodeMap[t].in++;
(nodeMap[t].in >= ) doubleIn = t;
edges.add( (s, t));
}
;
(doubleIn != ) {
List<Edge> doubleInEdges = <>();
(Edge edge : edges) { (edge.t == doubleIn) doubleInEdges.add(edge); (doubleInEdges.size() == ) ; }
doubleInEdges.get();
(isTree(edges, edge, nodeMap)) result = edge;
result = doubleInEdges.get();
} result = findResultEdge(edges, nodeMap);
System.out.println(result.s + + result.t);
}
{
(nodeMap.length + );
(Edge edge : edges) { (edge == resultEdge) ; (disjoint.isSame(edge.s, edge.t)) ; disjoint.join(edge.s, edge.t); }
;
}
Edge {
(nodeMap.length + );
(Edge edge : edges) { (disjoint.isSame(edge.s, edge.t)) edge; disjoint.join(edge.s, edge.t); }
;
}
}
最小生成树之 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 = -, mindist = Integer.MAX_VALUE;
( ; j <= v; j++) (!isInTree[j] && minDist[j] < mindist) { cur = j; mindist = minDist[j]; }
isInTree[cur] = ;
( ; j <= v; j++) (!isInTree[j] && grid[cur][j] < minDist[j]) minDist[j] = grid[cur][j];
}
;
( ; 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 {
(System.in);
scan.nextInt(), E = scan.nextInt();
List<Edge> edges = <>();
(E-- > ) edges.add( (scan.nextInt(), scan.nextInt(), scan.nextInt()));
;
edges.sort(Comparator.comparingInt(e -> e.val));
();
(Edge edge : edges) {
(!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);
( file : map.get(cur)) { inDegree[file]--; (inDegree[file] == ) deque.offer(file); }
}
(result.size() == n) { ( ; i < result.size(); i++) System.out.print(result.get(i) + (i < result.size() - ? : )); }
System.out.println(-);
}
}
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 <= n; j++) (!visit[j] && minDist[j] < min) { min = minDist[j]; cur = j; }
visit[cur] = ;
( ; j <= n; j++) (!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 ? - : 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 + ];
Arrays.fill(minDist, Integer.MAX_VALUE);
[] visit = [n + ];
PriorityQueue<Pair<Integer, Integer>> pq = <>((p1, p2) -> p1.second - p2.second);
pq.add( <>(, ));
minDist[] = ;
(!pq.isEmpty()) {
Pair<Integer, Integer> cur = pq.poll();
(visit[cur.first]) ;
visit[cur.first] = ;
(Edge edge : grid.get(cur.first)) (!visit[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { minDist[edge.to] = minDist[cur.first] + edge.val; pq.add( <>(edge.to, minDist[edge.to])); }
}
System.out.println(minDist[n] == Integer.MAX_VALUE ? - : 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 ? : 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[] = ;
Deque<Integer> deque = <>();
deque.offer();
[] visit = [n + ];
(!deque.isEmpty()) {
deque.poll(); visit[curNode] = ;
(Edge edge : grid.get(curNode)) (minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.end]) {
minDist[edge.end] = minDist[edge.from] + edge.val;
(!visit[edge.end]) { deque.offer(edge.end); visit[edge.end] = ; }
}
}
System.out.println(minDist[n] == Integer.MAX_VALUE ? : 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[] = ;
Deque<Integer> deque = <>();
deque.offer();
[] visit = [n + ];
[] count = [n + ];
count[]++;
;
(!deque.isEmpty()) {
deque.poll(); visit[curNode] = ;
(Edge edge : grid.get(curNode)) (minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.end]) {
minDist[edge.end] = minDist[edge.from] + edge.val;
(!visit[edge.end]) { deque.offer(edge.end); visit[edge.end] = ; count[edge.end]++; }
(count[edge.end] == n) { flag = ; (!deque.isEmpty()) deque.poll(); ; }
}
}
(flag) System.out.println();
(minDist[n] == Integer.MAX_VALUE) System.out.println();
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 + ; i++) {
[] minDistCopy = Arrays.copyOf(minDist, n + );
(Edge edge : grid) (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 ? : 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 ( ; i <= n; i++) ( ; j <= n; j++) dp[i][j][k] = Math.min(dp[i][k][k - ] + dp[k][j][k - ], dp[i][j][k - ]);
scan.nextInt();
( ; i < q; i++) { scan.nextInt(), end = scan.nextInt(); System.out.println(dp[start][end][n] == ? - : 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 = ; j <= n; j++) dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
scan.nextInt();
( ; i < q; i++) { scan.nextInt(), end = scan.nextInt(); System.out.println(dp[start][end] == ? - : 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 ();
start.x = scan.nextInt(); start.y = scan.nextInt();
endX = scan.nextInt(); endY = scan.nextInt();
start.g = ; start.h = distance(start); start.f = start.g + start.h;
aStar(start);
System.out.println(steps[endX][endY]);
queue.clear();
}
}
{
queue.add(node);
(!queue.isEmpty()) {
queue.poll();
(cur.x == endX && cur.y == endY) ;
([] move : moves) {
cur.x + move[], nextY = cur.y + move[];
(nextX < || nextX >= || nextY < || nextY >= ) ;
(steps[nextX][nextY] == ) {
steps[nextX][nextY] = steps[cur.x][cur.y] + ;
();
next.x = nextX; next.y = nextY;
next.g = cur.g + ; next.h = distance(next); next.f = next.g + next.h;
queue.add(next);
}
}
}
}
{ (node.x - endX) * (node.x - endX) + (node.y - endY) * (node.y - endY); }
}
{ x, y, f, g, h; }
