【CodeTop】每日练习 2025.7.29

栈的常见应用，定义好运算优先级，遇到当前运算优先级高于符号栈顶符号的情况进行计算，并保存结果。

class Solution {Map<Character, Integer> map = new HashMap<>() {{put('+', 1);put('-', 1);put('*', 2);put('/', 2);}};public int calculate(String s) {s = s.replaceAll(" ", "");char[] chS = s.toCharArray();int n = chS.length;Deque<Integer> nums = new ArrayDeque<>();Deque<Character> ops = new ArrayDeque<>();for (int i = 0; i < n; i++) {char cur = chS[i];if (cur == '(') {ops.addLast(cur);} else if (cur == ')') {while (!ops.isEmpty()) {if (ops.peekLast() != '(') {cal(nums, ops);} else {ops.pollLast();break;}}} else {if (Character.isDigit(cur)) {int num = 0;int j = i;while (j < n && Character.isDigit(chS[j])) {num = num * 10 + chS[j++] - '0';}nums.addLast(num);i = j - 1;} else {if (i > 0 && (chS[i - 1] == '(' || chS[i - 1] == '+' || chS[i - 1] == '-')) {nums.addLast(0);}while (!ops.isEmpty() && ops.peekLast() != '(') {char pre = ops.peekLast();if (map.get(pre) >= map.get(cur)) {cal(nums, ops);} else {break;}}ops.addLast(cur);}}}while (!ops.isEmpty()) {cal(nums, ops);}return nums.peekLast();}private void cal(Deque<Integer> nums, Deque<Character> ops) {if (nums.isEmpty() || nums.size() < 2) {return;}if (ops.isEmpty()) {return;}int b = nums.pollLast(), a = nums.pollLast();char op = ops.pollLast();int res = 0;if (op == '+') {res = a + b;} else if (op == '-') {res = a - b;} else if (op == '*') {res = a * b;} else if (op == '/') {res = a / b;}nums.addLast(res);}
}

摩尔投票，针对众数出现超过元素总数一半次数的集合，依次枚举可能的结果，遇到当前枚举的元素增加分数，否则减少分数，当分数为零时重新枚举下一个元素，最后一个被枚举的元素就是众数。

class Solution {public int majorityElement(int[] nums) {int res = 0, count = 0;for (int num : nums) {if (count == 0) {res = num;}count += num == res ? 1 : -1;}return res;}
}

递归地在每个节点处交换左右子树，最终返回原根节点即可。

/*** 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 TreeNode invertTree(TreeNode root) {if (root == null) {return root;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}

滑窗模板题，理解的基础上记住。

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

类似于最长公共子序列，动态规划解决。

class Solution {public int findLength(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;int res = 0;int[][] dp = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (nums1[i] == nums2[j]) {dp[i + 1][j + 1] = dp[i][j] + 1;res = Math.max(res, dp[i + 1][j + 1]);}}}return res;}
}