总结了 Java 语言在常见算法题型中的解题思路与代码实现，涵盖数组操作、链表处理、哈希表应用、字符串处理、栈与队列、二叉树遍历、回溯法、贪心策略、动态规划、单调栈及图论算法（最短路径、最小生成树等）。内容包含双指针、二分查找、滑动窗口、递归、迭代等多种技巧的代码示例。
class Solution {
public int removeDuplicates(int[] nums) {
(nums.length == ) ;
;
( ; fastIndex < nums.length; fastIndex++) {
(nums[fastIndex] != nums[fastIndex - ]) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
slowIndex;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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);
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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]);
}
}
}
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);
}
}
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;
}
}
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--;
}
}
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);
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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());
}
}
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;
}
}
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();
}
}
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();
}
}
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;
}
}
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];
}
}
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;
}
}
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;
}
}
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;
}
}
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--;
}
}
}
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);
}
}
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;
}
}
}
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;
}
}
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;
}
}
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()); }
}
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(); }
}
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();
}
}
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;
}
}
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();
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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);
}
}
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);
}
}
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;
}
}
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;
}
}
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;
}
}
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);
}
}
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;
}
}
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;
}
}
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;
}
}
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);
}
}
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);
}
}
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();
}
}
}
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();
}
}
}
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);
}
}
}
}
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();
}
}
}
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();
}
}
}
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;
}
}
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();
}
}
}
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();
}
}
}
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;
}
}
}
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;
}
}
}
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);
}
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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();
}
}
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;
}
}
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];
}
}
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];
}
}
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];
}
}
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];
}
}
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];
}
}
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];
}
}
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];
}
}
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;
}
}
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];
}
}
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;
}
}
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];
}
}
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;
}
}
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];
}
}
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];
}
}
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()];
}
}
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];
}
}
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;
}
}
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();
}
}
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];
}
}
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];
}
}
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();
}
}
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];
}
}
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);
}
}
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()];
}
}
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()];
}
}
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;
}
}
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];
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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); }
}
}
}
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); }
}
}
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; }
}
}
}
}
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); }
}
}
}
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);
}
}
}
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++; }
}
}
}
}
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);
}
}
}
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);
}
}
}
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]);
}
}
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);
}
}
}
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++;
}
}
}
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;
}
}
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);
}
}
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); }
}
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); }
}
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;
}
}
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);
}
}
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);
}
}
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]);
}
}
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]);
}
}
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]);
}
}
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]);
}
}
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]);
}
}
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]);
}
}
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]); }
}
}
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]); }
}
}
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; }
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online