【CodeTop】每日练习 2025.7.17

状态机 DP，把可能的情况拆解清楚就比较好写了。

class Solution {private int[] prices;private int[][] memo;public int maxProfit(int[] prices) {this.prices = prices;int n = prices.length;memo = new int[n][2];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(n - 1, 0);}private int dfs(int i, int state) {if (i < 0) {return state == 1 ? Integer.MIN_VALUE : 0;}if (memo[i][state] != -1) {return memo[i][state];}if (state == 1) {return memo[i][state] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);}return memo[i][state] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);}
}

利用矩阵双向递增的性质，每轮循环排除掉一行或者一列。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target) {return true;} else if (matrix[i][j] < target) {i++;} else {j--;}}return false;}
}

核心思路是验证二叉树中的每个节点是否在符合要求的范围内，先中后三种顺序的遍历都可以解决。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode node, long left, long right) {if (node == null) {return true;}long cur = node.val;return left < cur && cur < right && isValidBST(node.left, left, cur) && isValidBST(node.right, cur, right);}
}

利用快慢指针找出链表中点，再将它从中间反转，依次比较每个节点值是否相等。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ListNode middle = middle(head);middle = reverse(middle);ListNode list1 = head, list2 = middle;while (list2 != null) {if (list1.val != list2.val) {return false;}list1 = list1.next;list2 = list2.next;}middle = reverse(middle);return true;}private ListNode middle(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private ListNode reverse(ListNode head) {ListNode pre = null, cur = head, next;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

取第一个字符串作为标准，依次比较后续所有字符串每个位置上字符是否一致即可。

class Solution {public String longestCommonPrefix(String[] strs) {String first = strs[0];for (int col = 0; col < first.length(); col++) {char cur = first.charAt(col);for (String str : strs) {if (col == str.length() || str.charAt(col) != cur) {return first.substring(0, col);}}}return first;}
}