【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： 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 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; } } 153.寻找旋转排序数组中的最小值 二分查找的变种，想这些二分查找变种相关的题目我掌握的实际并不好，需多次练习理解 public int findMin(int[] nums) { int l = 0; int h = nums.length - 1; while (l < h) { int mid = (l + h)/2; if (nums[mid] < nums[h]) { h = mid; }else { l = mid + 1; } } return nums[l]; } 排序 （纯排序题目，这里就不放代码了，之前有） 128. 最长连续序列 题目要求O(n)的时间复杂度，这里先使用Set把元素放入并去重，开始遍历，遍历数为x 如果存在x-1，跳过此次（因为要避免重复计算，要每次从连续数列的第一个开始计算） 存在x+1，继续查找更大的 更新结果 public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } Set<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { set.add(nums[i]); } int res = 0; for (int i = 0; i < nums.length; i++) { int x = nums[i]; if (!set.contains(x-1)) { int cur = 0; while (set.contains(x)) { cur++; x++; } res = Math.max(res, cur); } } return res; } 62.不同路径 经典动规，不多说了 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 i = 0; i < n; i++) { dp[0][i] = 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]; } 136.只出现一次的数字 要求时间O(n)，空间O(1)，则使用异或！ 因为0^a=a，a^a=0，所以一个数字连续两次和0异或之后为0 又因为异或操作满足分配律，所以一个数组里的数字连续异或之后，剩余的结果即为只出现一次的数字！ public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } return res; } 240.搜索二维矩阵 II 从右上角开始，向左下开始寻找 public boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length - 1; while (col >= 0 && row < matrix.length) { if (matrix[row][col] == target) { return true; } if (target < matrix[row][col]) { col--; }else { row++; } } return false; } 221.最大正方形 动规，状态转移方程为dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1，同时更新最优解 public int maximalSquare(char[][] matrix) { int[][] dp = new int[matrix.length][matrix[0].length]; int res = 0; for (int i = 0; i < matrix.length; i++) { dp[i][0] = matrix[i][0] - '0'; res = Math.max(res, dp[i][0]); } for (int i = 0; i < matrix[0].length; i++) { dp[0][i] = matrix[0][i] - '0'; res = Math.max(res, dp[0][i]); } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { if (matrix[i][j] == '0') { continue; } dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1; res = Math.max(res, dp[i][j]); } } return res*res; } 162.寻找峰值 二分变体 public int findPeakElement(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { int mid = (l + r) / 2; if (nums[mid] < nums[mid + 1]) { l = mid + 1; } else { r = mid; } } return l; }
【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： 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 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; } } 155.最小栈 使用 辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中 class MinStack { ArrayDeque<Integer> stack; ArrayDeque<Integer> minStack; public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack.push(val); minStack.push(Math.min(val, minStack.peekFirst())); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peekFirst(); } public int getMin() { return minStack.peekFirst(); } } 41.缺失的第一个正数 缺失的正数一定在[1, nums.length+1]中，由于题目限制空间复杂度为O(1)，我们需要修改原数组，结合数组下标的特性来替代哈希表。 public int firstMissingPositive(int[] nums) { int l = nums.length; //将所有小于等于0的数置为l+1 for (int i = 0; i < l; i++) { if (nums[i] <= 0) { nums[i] = l+1; } } for (int i = 0; i < l; i++) { int temp = Math.abs(nums[i]); if (temp <= l) { nums[temp-1] = -Math.abs(nums[temp-1]); } } //寻找下标对应的第一个正数，返回该下标 for (int i = 0; i < l; i++) { if (nums[i] > 0) { return i+1; } } return l+1; } 718.最长重复子数组 这里要注意是连续子数组，不同于字符串的子序列，所以状态转移方程中不相等的情况下：dp[i][j] = 0; 动规：时间O(MN)，空间O(MN) 滑动窗口： O((N+M)×min(N,M)) ，空间 O(1) public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length+1][nums2.length+1]; int res = 0; for (int i = 1; i <= nums1.length ; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i-1] == nums2[j-1]) { dp[i][j] = 1 + dp[i-1][j-1]; } else { dp[i][j] = 0; } res = Math.max(res, dp[i][j]); } } return res; } 234.回文链表 时间O(n)，空间O(1)，思路还是比较好想的 快慢指针找中点 翻转一半 再遍历比较 class Solution { public boolean isPalindrome(ListNode head) { if (head.next == null) { return true; } ListNode slow = head, fast = head, slowPre = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slowPre = slow; slow = slow.next; } ListNode l2 = slow.next, l1; if (fast.next != null) { slowPre = slow; } slowPre.next = null; l1 = reverseList(head); while (l1 != null && l2 != null) { if (l1.val != l2.val) { return false; } l1 = l1.next; l2 = l2.next; } return true; } public ListNode reverseList(ListNode head) { ListNode prev = null, next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } } 78.子集 记原序列中元素的总数为 n。原序列中的每个数字 ai 的状态可能有两种，即「在子集中」和「不在子集中」。 我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai是否在子集中。 （这里会用到位运算） public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> t = new ArrayList<>(); int n = nums.length; for (int i = 0; i < (1 << n); i++) { t.clear(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { t.add(nums[j]); } } res.add(new ArrayList<>(t)); } return res; } 112.路径总和 递归 class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return sum == root.val; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } } 98.验证二叉搜索树 两个递归思路： 递归，但要判断节点的上下界 递归，中序遍历需递增 class Solution { Long last = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (isValidBST(root.left)) { if (last < root.val) { last = root.val + 0l; return isValidBST(root.right); } } return false; } } 32.最长有效括号 也是一道动态规划，但是动态规划的转移方程比较难想，dp[i]代表以s.charAt(i)结尾时的最长有效括号，由于题目要求为最长且连续，那么： 如果dp[i] == '('，那么在当前位置一定是0 如果dp[i] == ')'，那么需要根据dp[i-1]来找到前一个为被匹配的 '(' 如果存在，则dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2] 这里的dp[i - dp[i-1] - 2]为上一个未被匹配的'('，也就是上一个断连之前的最长连续有效括号值 其中还需要判断数组下标-1的情况 public int longestValidParentheses(String s) { int len = s.length(); if (len <= 1) { return 0; } int res = 0; int[] dp = new int[len]; for (int i = 1; i < len; i++) { if (s.charAt(i) == ')' && i - dp[i-1] > 0 && s.charAt(i - dp[i-1] -1) == '(') { dp[i] += (2 + dp[i-1]); if (i - dp[i-1] > 1) { dp[i] += dp[i - dp[i-1] - 2]; } res = Math.max(res, dp[i]); } } return res; } 101.对称二叉树 两个指针，同步对称移动 class Solution { public boolean isSymmetric(TreeNode root) { return dfs(root, root); } public boolean dfs(TreeNode q, TreeNode p) { if (q == null && p == null) { return true; } if (q == null || p == null) { return false; } return q.val == p.val && dfs(q.left, p.right) && dfs(q.right, p.left); } } 322.零钱兑换 区间dp，dp数组定义不是根据硬币，而是根据金额：dp[i] 代表总金额为 i 时所需的最小硬币个数 状态转移方程也是有些难度的，将数组初始化为无穷大，代表此金额无法使用所给金币凑出，dp[0] = 0 如果当前金额可以被某一种硬币凑出，则：dp[i] = Math.min(dp[i - coin] + 1, dp[i]); public int coinChange(int[] coins, int amount) { if (amount == 0) { return 0; } int[] dp = new int[amount+1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int coin : coins) { for (int i = coin; i <= amount ; i++) { if (dp[i - coin] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i - coin] + 1, dp[i]); } } } return dp[amount] < Integer.MAX_VALUE ? dp[amount] : -1; } 22.括号生成 题目要求给出所有可能，暴力dfs即可 class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { dfs(n, n, ""); return res; } public void dfs(int left, int right, String s) { for (int i = 0; i < 2; i++) { if (left == 0 && right == 0) { res.add(s); break; } if (i == 0 && left > 0) { dfs(left - 1, right, s + "("); }else if (i == 1 && right > left) { dfs(left, right - 1, s + ")"); } } } } 169.多数元素 Boyer-Moore 投票算法，时间O(n)，空间O(1) 算法过程： 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0； 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予candidate，随后我们判断 x： 如果 x 与 candidate 相等，那么计数器 count 的值增加 1； 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。 在遍历完成后，candidate 即为整个数组的众数。 投票算法证明： 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举) 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选 public int majorityElement(int[] nums) { int cand = 0, count = 0; for (int i = 0; i < nums.length; i++) { if (count == 0) { cand = nums[i]; } count += (cand == nums[i] ? 1 : -1); } return cand; } 48.旋转图像 原地旋转：将矩形分为四块，两个for循环一块的量，但是每次swap四个块的坐标 就是四个对应坐标的转换方程有些难推 public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n/2; i++) { for (int j = 0; j < (n+1)/2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = temp; } } } 43.字符串相乘 很恶心的题，费劲又麻烦，没啥特别简洁的套路 public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } int[] res = new int[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { int n1 = num1.charAt(i) - '0'; for (int j = num2.length() - 1; j >= 0; j--) { int n2 = num2.charAt(j) - '0'; int sum = (res[i + j + 1] + n1 * n2); res[i + j + 1] = sum % 10; res[i + j] += sum / 10; } } StringBuilder result = new StringBuilder(); for (int i = 0; i < res.length; i++) { if (i == 0 && res[i] == 0) continue; result.append(res[i]); } return result.toString(); } 64.最小路径和 很简单常规的二维dp，转移方程 dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]) public int minPathSum(int[][] grid) { int row = grid.length; int col = grid[0].length; int[][] dp = new int[row][col]; dp[0][0] = grid[0][0]; for (int i = 1; i < row; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for (int i = 1; i < col; i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]); } } return dp[row-1][col-1]; } 226. 翻转二叉树 典型递归 public TreeNode invertTree(TreeNode root) { if (root != null) { invertTree(root.left); invertTree(root.right); TreeNode tree = root.left; root.left = root.right; root.right = tree; } return root; } 165.比较版本号 String.split分割，但是注意特殊字符前加\\ class Solution { public int compareVersion(String version1, String version2) { String[] s1 = version1.split("\\."); String[] s2 = version2.split("\\."); int len1 = s1.length; int len2 = s2.length; for (int i = 0; i < len1 && i < len2; i++) { if (Integer.valueOf(s1[i]) > Integer.valueOf(s2[i])) { return 1; } if (Integer.valueOf(s1[i]) < Integer.valueOf(s2[i])) { return -1; } } if (len1 > len2 && remain(s1, len2) > 0) { return 1; }else if (len1 < len2 && remain(s2, len1) > 0) { return -1; } return 0; } public int remain(String[] arr, int start) { StringBuilder sb = new StringBuilder(""); for (int i = start; i < arr.length; i++) { sb.append(arr[i]); } return Integer.valueOf(sb.toString()); } } 34.在排序数组中查找元素的第一个和最后一个位置 在使用二分查找第一次查找到目标值之后继续二分查找 那么第一次出现的即为一直二分后最左的位置，最后一次出现即为第一次比target大的数的下标-1 class Solution { public int[] searchRange(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right)/2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid -1; ans = mid; } else { left = mid + 1; } } return ans; } } 83.删除排序链表中的重复元素 链表基操 public ListNode deleteDuplicates(ListNode head) { ListNode node = head; while (node != null) { ListNode cur = node.next; while (cur != null && node.val == cur.val) { cur = cur.next; } node.next = cur; node = node.next; } return head; } 39.组合总和 由于题目要求所有情况，暴力dfs + 剪枝 + 回溯 即可 class Solution { List<List<Integer>> res = new ArrayList<>(); int[] arr; public List<List<Integer>> combinationSum(int[] candidates, int target) { arr = candidates; dfs(new ArrayList<>(), target, 0); return res; } public void dfs(List<Integer> list, int val, int index) { if (val < 0) { return; } if (val == 0) { res.add(new ArrayList<>(list)); } for (int i = index; i < arr.length; i++) { list.add(arr[i]); dfs(list, val - arr[i], i); list.remove(list.size() - 1); } } }
【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： 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 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; } } 8.字符串转换整数 (atoi) 自动机 我的代码就是根据题意一步一步判断的，所以非常臃肿，但是根据官方给的自动机解法暂时还没看懂 public int myAtoi(String s) { int j = 0; for (; j < s.length();) { if (s.charAt(j) == ' ') { j++; }else { break; } } s = s.substring(j); if (s.length() <= 0) { return 0; } boolean isNegative = false; int i = 0, res = 0; if (s.charAt(0) == '-' || s.charAt(0) == '+') { if (s.charAt(0) == '-') { isNegative = true; } i = 1; } for (; i < s.length();) { if (s.charAt(i) == '0') { i++; }else { break; } } StringBuilder sb = new StringBuilder(""); for (; i < s.length(); i++) { if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { sb.append(s.charAt(i)); }else { break; } } String str = sb.toString(); if (str.length() != 0) { if (str.length() > 10) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { long l = Long.valueOf(str); if (l > Integer.MAX_VALUE) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { if (isNegative) { return -1*Integer.valueOf(str); } return Integer.valueOf(str); } } } return res; } 2.两数相加 话说真快被链表题搞懵了呀，这个我也是按照纯模拟加法的思路写的，先去判断哪个链表长，然后哦就把短的依次加到长的上面，还要注意进位问题。 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode cul1 = l1; ListNode cul2 = l2; int l1_len = 0; int l2_len = 0; while (cul1 != null || cul2 != null) { if (cul1 != null) { l1_len++; cul1 = cul1.next; } if (cul2 != null) { l2_len++; cul2 = cul2.next; } } ListNode lon = l1; ListNode shor = l2; if (l2_len > l1_len) { lon = l2; shor = l1; } int yu = 0; while (shor != null) { lon.val += (shor.val+yu); if (lon.val >= 10) { yu = 1; lon.val -=10; }else { yu = 0; } shor = shor.next; if (lon.next == null && yu == 1) { lon.next = new ListNode(0); } lon = lon.next; } while (yu == 1) { lon.val += 1; if (lon.val >= 10) { yu = 1; lon.val -= 10; if (lon.next == null) { lon.next = new ListNode(0); } lon = lon.next; }else { yu = 0; } } if (l2_len > l1_len) { return l2; } return l1; } 82.删除排序链表中的重复元素 II 判断当前节点的下一个节点与下下一个节点的值，相等则不断调整当前节点的next，不相等则向后移动；这里引入头节点方便对首元节点的操作。 public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode fake = new ListNode(); fake.next = head; ListNode cur = fake; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int x = cur.next.val; while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; } }else { cur = cur.next; } } return fake.next; } 144.二叉树的前序遍历 class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs (TreeNode root) { if (root != null) { list.add(root.val); dfs(root.left); dfs(root.right); } } } 148.排序链表 这道题思路是归并，但是有两个归并思路： 递归着归并，先找中点（使用快慢指针），一次分一半，递归，一次分一半，递归....然后两两合并并返回 先设归并长度为1，第一波归并完再把归并长度乘2，再归并，以此类推 （本体采用自顶向下的递归方式） class Solution { public ListNode sortList(ListNode head) { return sort(head, null); } private ListNode sort(ListNode start, ListNode end) { if (start == end) { return start; } ListNode fast = start, slow = start; while (fast != end && fast.next != end) { fast = fast.next.next; slow = slow.next; } ListNode l2 = sort(slow.next, end); slow.next = null; ListNode l1 = sort(start, slow); return mergeTwoLists(l1, l2); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null || l2 == null) { return l1 == null ? l2 : l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } } 31.下一个排列 倒着遍历第一次找到第一个值变小的，记录坐标为i 倒着遍历第二次找到刚好比nums[i]大的坐标j 交换i，j并翻转i+1到结尾的数字 class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i+1]) { i--; } if (i >= 0) { int j = nums.length - 1; while (j > i && nums[j] <= nums[i]) { j--; } swap(nums, i, j); } for (int x = i+1, y = nums.length-1; x < y;) { swap(nums, x, y); x++; y--; } } private void swap (int[] nums, int i, int j) { int swap = nums[i]; nums[i] = nums[j]; nums[j] = swap; } } 76.最小覆盖子串 思路：滑动窗口（左右指针l,r），用两个常量数组判断当前字符串是否包含模式串（'a'~'Z'可以用长度60存下） 不包含，r++；包含，l++，并更新结果 （这道题虽然是困难，但是思路还是比较容易懂的） public String minWindow(String s, String t) { String res = ""; int[] sarr = new int[60]; int[] tarr = new int[60]; for (int i = 0; i < t.length(); i++) { tarr[t.charAt(i) - 'A']++; } int l = 0, r = 0; while (l <= r) { boolean isHave = true; for (int j = 0; j < 60; j++) { if (sarr[j] < tarr[j]) { isHave = false; break; } } if (isHave) { String temp = s.substring(l, r); if (res.length() == 0) { res = temp; }else { res = temp.length() < res.length() ? temp:res; } sarr[s.charAt(l) - 'A']--; l++; }else if (r < s.length()) { sarr[s.charAt(r) - 'A']++; r++; }else { break; } } return res; } 151.翻转字符串里的单词 常规字符串算法题，比较简单，借助java的trim()和split()函数，使用StringBuilder快速追加 public String reverseWords(String s) { StringBuilder sb = new StringBuilder(""); s = s.trim(); String[] arr = s.split(" "); for (int i = arr.length - 1; i > 0; i--) { if (arr[i].length() != 0) { sb.append(arr[i] + " "); } } sb.append(arr[0]); return sb.toString(); } 72. 编辑距离 这里提供了两种方法：自底向上的递归和自顶向下的动规，但是递归会超时，动规就是记录了子问题的结果避免重复计算。 dp[i][j]的意思是word1.subString(0, i)变为word2.subString(0, j)所需的步数 根据题目中给的三种操作我们可以推出核心的动态转移方程为： dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]); 这里由于下标从1开始到length，避免数组越界所以使下一个用当前的值 这是一道经典的动态规划题目，值得反复练习 class Solution { public int minDistance(String word1, String word2) { int l1 = word1.length(); int l2 = word2.length(); int[][] dp = new int[l1 + 1][l2 + 1]; for (int i = 0; i < l1 + 1; i++) { dp[i][0] = i; } for (int i = 0; i < l2 + 1; i++) { dp[0][i] = i; } for (int i = 0; i < l1; i++) { for (int j = 0; j < l2; j++) { if (word1.charAt(i) == word2.charAt(j)) { dp[i+1][j+1] = dp[i][j]; //一样则无需多余操作步数 }else { dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]); } } } return dp[l1][l2]; } //递归（超时） public int minDistance_recursion(String word1, String word2) { if (word1.length() == 0 || word2.length() == 0) { return Math.max(word1.length(), word2.length()); } if (word1.charAt(word1.length()-1) == word2.charAt(word2.length()-1)) { return minDistance_recursion(word1.substring(0, word1.length()-1), word2.substring(0, word2.length()-1)); } return 1 + Math.min(Math.min(minDistance_recursion(word1, word2.substring(0, word2.length()-1)), minDistance_recursion(word1.substring(0, word1.length()-1), word2)), minDistance_recursion(word1.substring(0, word1.length()-1),word2.substring(0, word2.length()-1))); } } 4.寻找两个正序数组的中位数 这道题目有两个思路： 合并两个有序数组，再直接输出中位数，时间复杂度O(m+n)，空间复杂度O(m+n) 划分数组+推导，时间复杂度O(logmin(m,n)))，空间复杂度O(1)，但是这个暂时还没搞懂 class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; int l3 = l1+l2; int[] arr = new int[l3]; for (int i = 0; i < l1; i++) { arr[i] = nums1[i]; } merge(arr, l1, nums2, l2); if (l3 % 2 == 1) { return arr[l3/2]; } return ((float)(arr[l3/2-1]+arr[l3/2]))/2; } public void merge(int[] nums1, int m, int[] nums2, int n) { int n1 = m -1; int n2 = n -1; while (n2 >= 0) { if (n1 >= 0 && nums1[n1] >= nums2[n2]) { nums1[n1+n2+1] = nums1[n1]; n1--; }else { nums1[n1+n2+1] = nums2[n2]; n2--; } } } } 129.求根节点到叶节点数字之和 深度优先搜索，使用StringBuilder记录路径上节点的值，再判断左右孩子为空时，将其转换成Integer。递归返回前去除 StringBuilder的最后一个字符 class Solution { private StringBuilder sb = new StringBuilder(); private int res = 0; public int sumNumbers(TreeNode root) { if (root != null) { sb.append(root.val); if (root.left == null && root.right == null) { res += Integer.valueOf(sb.toString()); }else { sumNumbers(root.left); sumNumbers(root.right); } sb.deleteCharAt(sb.length()-1); } return res; } } 104.二叉树的最大深度 二叉树必需掌握的题，数据结构教材上的原题 public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } } 105.从前序与中序遍历序列构造二叉树 前序遍历和中序遍历的概念这里就不说了，其实推的时候很容易发现是一个递归的过程，有关于递归下标的计算如图： class Solution { private HashMap<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1); } public TreeNode buildTree(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) { if (preLeft > preRight || inLeft > inRight) { return null; } int val = preorder[preLeft]; TreeNode node = new TreeNode(val); int pIndex = map.get(val); node.left = buildTree(preorder, preLeft+1, pIndex - inLeft + preLeft, inLeft, pIndex - 1); node.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, pIndex + 1, inRight); return node; } } 239.滑动窗口最大值 这道题一开始很容易想到使用优先队列来解决，但是写完检测却发现超时了，看题解是使用的单调队列（递增、递减的队列） 定义一个双端队列，存储数组下标，那么队首的值就是nums[queue.peekFirst()]，存下标主要就是为了方便判断队列队首元素是否已经在滑动窗口外：queue.peekFirst() < left，队首元素对应数组值最大，依次递减。 定义右指针right从 0 到nums.length()-1，就很容易计算窗口的左指针left为right - k + 1 如果一个元素入队（入队都是从队尾入），则说明它在窗口内，那么队列内比该值小的则永远不会加入到最终答案res内，直到该元素出窗口，所以我们把队列内比该元素小的值出队。保证队列的一个单调递减。 最后一个right + 1 >= k是因为这时最初的窗口才刚刚形成，满足长度为k，才能添加。 class Solution { //单调队列 public int[] maxSlidingWindow(int[] nums, int k) { int[] res = new int[nums.length-k+1]; ArrayDeque<Integer> queue = new ArrayDeque<>(); for (int right = 0; right < nums.length; right++) { while (queue.size() > 0 && nums[right] > nums[queue.peekLast()]) { queue.pollLast(); } queue.offerLast(right); int left = right - k + 1; if (left > queue.peekFirst()) { queue.pollFirst(); } if (right + 1 >= k) { res[left] = nums[queue.peekFirst()]; } } return res; } //优先队列（超时） public int[] maxSlidingWindow_PriorityQueue(int[] nums, int k) { PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> b-a); int[] res = new int[nums.length-k+1]; for (int i = 0; i < k; i++) { queue.offer(nums[i]); } res[0] = queue.peek(); for (int i = k, j = 0; i < nums.length; i++,j++) { queue.offer(nums[i]); queue.remove(nums[j]); res[j+1] = queue.peek(); } return res; } } 93.复原 IP 地址 一个字符串，分成四部分，我就懒省事直接暴力dfs了，枚举出来所有分割情况再做判断 class Solution { private List<String> res = new ArrayList<>(); private String param; public List<String> restoreIpAddresses(String s) { param = s; dfs("", 0, 1); return res; } public void dfs (String s, int index, int count) { if (count >= 4) { if (judge(index, param.length())) { res.add(s + param.substring(index)); } }else { for (int i = 1; i <= 3; i++) { if ((index + i) <= param.length() && judge(index, index+i)) { dfs(s+param.substring(index, index+i)+".", index+i, count + 1); } } } } public boolean judge (int start, int end) { String temp = param.substring(start, end); if (temp.length() <= 3 && temp.length() != 0) { int val = Integer.valueOf(temp); if (String.valueOf(val).length() == temp.length() && val <= 255) { return true; } } return false; } } 113.路径总和 II 这道题和前面的 129.求根节点到叶节点数字之和 基本一致，都是dfs+回溯即可 class Solution { private List<List<Integer>> res = new ArrayList<>(); private List<Integer> cur = new ArrayList<>(); private int sum = 0; private int target = 0; public List<List<Integer>> pathSum(TreeNode root, int targetSum) { target = targetSum; dfs(root); return res; } public void dfs (TreeNode root) { if (root != null) { sum += root.val; cur.add(root.val); if (root.left == null && root.right == null) { if (sum == target) { List<Integer> temp = new ArrayList<>(); for (int i = 0; i < cur.size(); i++) { temp.add(cur.get(i)); } res.add(temp); } }else { dfs(root.left); dfs(root.right); } sum -= root.val; cur.remove(cur.size()-1); } } } 110.平衡二叉树 平衡二叉树的定义本身就是一个递归的定义：左右子树深度只差的绝对值不超过1，并且左右子树也是平衡的 class Solution { public boolean isBalanced(TreeNode root) { if (root != null) { return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } return true; } public int height (TreeNode root) { if (root == null) { return 0; } else { return Math.max(height(root.left), height(root.right)) + 1; } } } 1143.最长公共子序列 典型的二维动规，dp[i][j]代表text[0...i]和text[0...j]的最长公共子序列，所以可以推导出动态转移方程为： 其实到这里我们可以发现有关于两个字符串之间的动态规划题目，基本都是一个二维数组dp，两个for循环里面一个状态转移方程，更新数组，最后返回数组的最后一个值，这就是动规模板。 class Solution { public int longestCommonSubsequence(String text1, String text2) { 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 (text1.charAt(i-1) == text2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]+1; }else { dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } } return dp[text1.length()][text2.length()]; } } 470.用 Rand7() 实现 Rand10() 古典概型 第一次rand7限定[1,2]，判断奇偶性，概率是1/2，其实first的作用就是生成概率为1/2的奇偶。 （我们还可以通过限定[1,3]，再取模3进行概率为1/3的操作） 第二次rand7限定[1,5]，概率是1/5，加上5为[6,10]，概率也是1/5 二者结合可以得出10种概率相同的结果 借助这个思路我们也可以构造出其他的 /** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */ class Solution extends SolBase { public int rand10() { int first,second; while ((first = rand7()) > 2); while ((second = rand7()) > 5); return first%2 == 0 ? second : second+5; } } 543.二叉树的直径 这道题跟计算二叉树的深度还不太一样，是求任意两个节点的最大路径，可以不过根节点。递归的同时对结果更新要注意： class Solution { private int res = 0; public int diameterOfBinaryTree(TreeNode root) { height(root); return res-1; } public int height (TreeNode root) { if (root != null) { int l = height(root.left); int r = height(root.right); res = Math.max(res, l+r+1); return Math.max(l,r)+1; } return 0; } }
【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： 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 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; } } 92.反转链表II 思路是记录反转部分的前一个节点和后一个节点，将其反转后再连接，思路是这个，但是我在实现上可能麻烦一些： class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode curr = head; ListNode prev = null; ListNode next = curr; int flag = 1; while (flag < right) { if (flag == left - 1) { prev = curr; } curr = curr.next; flag++; } next = curr.next; if (prev == null) { head = reverse(head, left, right); prev = head; }else { prev.next = reverse(prev.next, left, right); } while ( prev.next != null && left <= right) { prev = prev.next; } if (next != null) { if (prev.next != null) { prev.next.next = next; }else { prev.next = next; } } return head; } public ListNode reverse(ListNode head, int left, int right) { if (left == right) { return head; } ListNode prev = null; ListNode curr = head; while (left <= right) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; left++; } return prev; } } 200.岛屿数量 广搜、深搜都可以，这里是深搜+剪枝，不用回溯： class Solution { public int numIslands(char[][] grid) { int res = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { res++; dfs(grid, i, j); } } } return res; } public void dfs(char[][] grid, int x, int y) { grid[x][y] = '0'; if (x < grid.length - 1 && grid[x+1][y] == '1') { dfs(grid, x+1, y); } if (x > 0 && grid[x-1][y] == '1') { dfs(grid, x-1, y); } if (y < grid[0].length - 1 && grid[x][y+1] == '1') { dfs(grid, x, y+1); } if (y > 0 && grid[x][y-1] == '1') { dfs(grid, x, y-1); } } } 33.搜索旋转排序数组 二分（我当时是懒省事直接O(n)遍历了） class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } if (n == 1) { return nums[0] == target ? 0 : -1; } int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid; } if (nums[0] <= nums[mid]) { if (nums[0] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { l = mid + 1; } else { r = mid - 1; } } } return -1; } } 46.全排列 经典算法，使用dfs+交换+回溯，可以当模板套用： class Solution { private List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { dfs(nums, 0, nums.length-1); return list; } public void dfs(int[] array,int start,int end) { if(start==end) { List<Integer> li = new ArrayList<>(); for (int i = 0; i < array.length; i++) { li.add(array[i]); } list.add(li); } else { for (int i = start; i <= end; i++) { swap(array,start,i); dfs(array,start+1,end); swap(array,start,i); } } } public void swap(int[] array,int i,int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } 142.环形链表 II 当快慢指针相遇之后，使用第三个指针从头开始和慢指针一起向后移动（步伐都是一步），当第三个指针与慢指针相遇时，即为环的入口： public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; ListNode res = head; while (fast != null && slow != null) { fast = fast.next; if (fast == null) { break; } fast = fast.next; slow = slow.next; if (slow == fast) { while (slow != res) { slow = slow.next; res = res.next; } return res; } } return null; } 23.合并K个排序链表 结合前面那道合并两个链表，我们只需循环调用该方法即可： class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } ListNode res = lists[0]; for (int i = 0; i < lists.length-1; i++) { res = mergeTwoLists(res, lists[i+1]); } return res; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } } 54.螺旋矩阵 模拟打印顺序： public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<>(); int left = 0 ,up = 0; int right = matrix[0].length - 1; int down = matrix.length - 1; int size = matrix.length * matrix[0].length; while (list.size() < size) { for (int i = left; i <= right; i++) { if (list.size() < size) list.add(matrix[up][i]); } up++; for (int i = up; i <= down; i++) { if (list.size() < size) list.add(matrix[i][right]); } right--; for (int i = right; i >= left; i--) { if (list.size() < size) list.add(matrix[down][i]); } down--; for (int i = down; i >= up; i--) { if (list.size() < size) list.add(matrix[i][left]); } left++; } return list; } 704.二分查找 如题，就是考二分 public int search(int[] nums, int target) { int l = 0, r = nums.length-1, m; while (l <= r) { m = (r + l)/2; if (target == nums[m]) { return m; } if (target > nums[m]) { l = m + 1; }else { r = m - 1; } } return -1; } 232.用栈实现队列 两个栈实现，需要弹出时，将栈s1全部倒入s2，再从s2弹 class MyQueue { private Stack<Integer> s1 = new Stack<>(); private Stack<Integer> s2 = new Stack<>(); private int front; public MyQueue() {} public void push(int x) { if (s1.empty()) { front = x; } s1.push(x); } public int pop() { if (s2.empty()) { while(!s1.empty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if (s2.empty()) { return front; }else { return s2.peek(); } } public boolean empty() { return s1.empty() && s2.empty(); } } 42.接雨水 动规：从左向右，记录最大高度；再从右向左记录最大高度；最后每格的积水为两个数组中较小的那个再减去这个位置的高度： public int trap(int[] height) { int res = 0; int len = height.length; int[] left = new int[len]; int[] right = new int[len]; left[0] = height[0]; for (int i = 1; i < len; i++) { left[i] = Math.max(left[i-1], height[i]); } right[len-1] = height[len-1]; for (int i = len - 2; i >= 0; i--) { right[i] = Math.max(height[i], right[i+1]); } for (int i = 0; i < len; i++) { res += Math.min(left[i], right[i]) - height[i]; } return res; } 94.二叉树的中序遍历 递归 class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs (TreeNode root) { if (root != null) { dfs(root.left); list.add(root.val); dfs(root.right); } } } 300.最长上升子序列 经典动规：（现在看看差不多又忘记怎么做了） public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int res = 1; for (int i = 1; i < nums.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } 143.重排链表 分三步：找中点——>翻转链表——>合并链表 class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode mid = middleList(head); ListNode l2 = reverseList(mid); mergeList(head, l2); } public ListNode middleList(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode prev = null, next; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_t, l2_t; while (l1 != null && l2 != null) { l1_t = l1.next; l1.next = l2; l1 = l1_t; l2_t = l2.next; l2.next = l1; l2 = l2_t; } } } 199.二叉树的右视图 向右深搜，技巧点：树的深度==集合大小，所以记录每层的深度，当depth == res.size()时为第一当这一层的最右节点： class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root, 0); return res; } public void dfs (TreeNode root, int depth) { if (root != null) { if (depth == res.size()) { res.add(root.val); } dfs(root.right, depth+1); dfs(root.left, depth+1); } } } 70.爬楼梯 就是斐波那契数列，滚动数组解决： public int climbStairs(int n) { if (n == 1) { return 1; } int[] dp = new int[3]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[2] = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = dp[2]; } return dp[2]; } 22.链表中倒数第k个节点 两个指针，一个从起点，另一个从正数第k个移动： public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (k-- > 0) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } 124.二叉树中的最大路径和 思路是递归，递归去找左右最大的路径和，个人觉得比较难，需重复做： class Solution { int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return res; } public int dfs(TreeNode node) { if (node == null) { return 0; } int left = Math.max(dfs(node.left), 0); int right = Math.max(dfs(node.right), 0); res = Math.max(res, node.val + left + right); return node.val + Math.max(left, right); } } 69.x 的平方根 二分： public int mySqrt(int x) { int res = -1, l = 0, r = x,m; while (l <= r) { m = l + (r - l)/2; if ((long)m*m <= x) { l = m + 1; res = m; }else { r = m - 1; } } return res; } 56.合并区间 根据左端点排列后开始有序合并： public int[][] merge(int[][] intervals) { List<int[]> res = new ArrayList<>(); if (intervals == null || intervals.length == 0) { return res.toArray(new int[0][]); } if (intervals.length == 1) { return intervals; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 0; i < intervals.length-1;i++) { int left = intervals[i][0]; int right = intervals[i][1]; while (right >= intervals[i+1][1] || right >= intervals[i+1][0]) { if (right < intervals[i+1][1]) { right = intervals[i+1][1]; } i++; if (i == intervals.length - 1) { break; } } int[] temp = new int[]{left, right}; res.add(temp); } if (res.get(res.size() - 1)[1] < intervals[intervals.length -1][1]) { res.add(intervals[intervals.length -1]); } return res.toArray(new int[0][]); } 19.删除链表的倒数第 N 个结点 我的写法可能麻烦些，主要是一些边界值的判断，思路和前面寻找倒数第N个节点思路一样，只不过是找N+1个，再做删除操作即可： class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode prev = findprev(head, n+1); if (prev == null) { if (head.next != null) { return head.next; } return null; } if (prev.next != null) { prev.next = prev.next.next; } return head; } public ListNode findprev (ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (k-- > 0) { if (fast == null) { return null; } fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } }
【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解
之后博主会出一个系列专门记录CodeTop高频算法题的一个详解，一次更新20道，也就是一页的数量。更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： 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 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; } } 206.反转链表 这应该是链表里最基础、最常问的一道算法题了，相比链表简单的插入删除要复杂一些，可以根据代码把图画一遍方便理解，但还是容易忘，记住要点是一个 while 循环里四行ListNode的交换操作： public ListNode reverseList(ListNode head) { ListNode prev = null, next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } 146.LRU缓存机制 这道题在Java里可以通过LinkedHashMap实现，但是面试肯定不能这么说，需要使用 哈希表 + 双向链表 ，可以说又是一道大量链表的操作题，有助于锻炼对链表操作的理解： class LRUCache { //双向链表 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; DLinkedNode() {} DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap<>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { if (size >= capacity) { removeTail(); size--; } addToHead(new DLinkedNode(key, value)); size++; }else { node.value = value; moveToHead(node); } } //加入头部 private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; node.next.prev = node; head.next = node; cache.put(node.key, node); } //移动到头部 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } //移除尾部 private void removeTail() { removeNode(tail.prev); } //删除节点，记者也要更新哈希表 private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; cache.remove(node.key); } } 3.无重复字符的最长子串 这道题的最优解是使用滑动窗口，同时需要用到Set集合，我认为还是比较有难度的 public int lengthOfLongestSubstring(String s) { Set<Character> occ = new HashSet<Character>(); int n = s.length(); int rk = -1, ans = 0; for (int i = 0; i < n; i++) { if (i != 0) { occ.remove(s.charAt(i - 1)); } while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { occ.add(s.charAt(rk + 1)); rk++; } ans = Math.max(ans, rk - i + 1); } return ans; } 215.数组中的第K个最大的数 主要考查排序，大家可以把它当作考堆排的算法题。 25.K个一组翻转链表 在第一道翻转链表的基础上难度又提升了一级，需要使用到递归（这道题我当时做了好久没做出来....） public ListNode reverseKGroup(ListNode head, int k) { // 如果头节点为null或者节点只有一个直接返回 if (head == null || head.next == null) { return head; } //保存每一段反转的头尾指针 ListNode tail = head; //循环k次，找到尾部 for (int i = 0; i < k; i++) { //如果不够k个就结束了，这一段不反转直接返回头部 if (tail == null) { return head; } tail = tail.next; } //反转后记录这一段的头部 ListNode newHead = reverse(head, tail); // [ ) //这里的head其实按这一段的顺序已经是指向尾部了 // 这里的head.next需要指向下一段的头部（就是它反转后的tail） //每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头 head.next = reverseKGroup(tail, k); return newHead; } //根据头尾指针反转，每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头 public ListNode reverse(ListNode head, ListNode tail) { ListNode pre = null, next = null; while (head != tail) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } 补充题4. 手撕快速排序 就是考快排 15.三数之和 最优解：排序+双指针 public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); int lastA = -9999999; for (int i = 0; i < nums.length-2; i++) { if (nums[i] > 0) { return result; } if (nums[i] == lastA) { continue; } lastA = nums[i]; int lastLeft = -9999999; int right = nums.length; for (int j = i+1; j < right - 1; j++) { if (nums[j] == lastLeft) { continue; } for (int k = right - 1; k > j; k--) { if (nums[i] + nums[j] + nums[k] == 0) { List<Integer> temp = new ArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); result.add(temp); right = k; break; } } lastLeft = nums[j]; } } return result; } 53.最大子序和 动态规划，但是空间复杂度是O(1)，每次只保存当前的最优解 public int maxSubArray(int[] nums) { int res = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i-1] > 0) { nums[i]+=nums[i-1]; } res = res > nums[i] ? res:nums[i]; } return res; } 1.两数之和 哈希表，空间换时间，每次存这个数，找哈希表里的另一半target-nums[i] public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target-nums[i])) { return new int[] {i, map.get(target-nums[i])}; } map.put(nums[i], i); } return null; } 141.环形链表 经典链表题：快慢指针，相遇则有环，任意一个为null则无环 public boolean hasCycle(ListNode head) { ListNode fast = head; while (head != null && fast != null) { head = head.next; fast = fast.next; if (fast != null) { fast = fast.next; }else { break; } if (head == fast) { return true; } } return false; } 21.合并两个有序链表 思路：递归 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } 102.二叉树的层序遍历 典型的队列题目 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<>(); int curLevelSize = queue.size(); for (int i = 0; i < curLevelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } res.add(level); } return res; } 160.相交链表 两个指针分别移动，到末尾之后移到对方链表上继续移动，相等时返回 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; while(pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } 121.买卖股票的最佳时机 一次for循环，每次记录最小值，以及更新最大利润 public int maxProfit(int[] prices) { int res = 0; int min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { if (min > prices[i]) { min = prices[i]; }else { res = Math.max(res, prices[i] - min); } } return res; } 88.合并两个有序数组 根据有序和空位这两个特点，我们从nums1末尾开始比较插入 public void merge(int[] nums1, int m, int[] nums2, int n) { int n1 = m -1; int n2 = n -1; while (n2 >= 0) { if (n1 >= 0 && nums1[n1] >= nums2[n2]) { nums1[n1+n2+1] = nums1[n1]; n1--; }else { nums1[n1+n2+1] = nums2[n2]; n2--; } } } 103.二叉树的锯齿形层次遍历 这道题我也是按自己的方法去写的，也是有些麻烦，用了队列和集合倒来倒去 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<Object[]> queue = new ArrayDeque<>(); Object[] arr = new Object[2]; arr[0] = root; arr[1] = 1; queue.offer(arr); int cur = 1; List<Integer> list = new ArrayList<>(); List<Object[]> tempList = new ArrayList<>(); while (queue.size() != 0) { Object[] temp = queue.poll(); TreeNode tn = (TreeNode)temp[0]; Integer floor = (Integer)temp[1]; if (tn != null) { if (floor % 2 == 0) { if (tn.right != null) { tempList.add(new Object[]{tn.right, floor + 1}); } if (tn.left != null) { tempList.add(new Object[]{tn.left, floor + 1}); } }else { if (tn.left != null) { tempList.add(new Object[]{tn.left, floor + 1}); } if (tn.right != null) { tempList.add(new Object[]{tn.right, floor + 1}); } } if (cur == floor) { list.add(tn.val); }else { res.add(list); list = new ArrayList<>(); list.add(tn.val); cur = floor; } } if (queue.size() == 0) { while (tempList.size() > 0) { queue.offer(tempList.get(tempList.size() - 1)); tempList.remove(tempList.size() - 1); } } } res.add(list); return res; } 236.二叉树的最近公共祖先（LCA） 思路是递归，但是难点在于节点的判断： class Solution { private TreeNode ans; public Solution() { this.ans = null; } private boolean dfs(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return false; boolean lson = dfs(root.left, p, q); boolean rson = dfs(root.right, p, q); if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) { ans = root; } return lson || rson || (root.val == p.val || root.val == q.val); } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { this.dfs(root, p, q); return this.ans; } } 10.有效的括号 正常的思路是用栈来做的，但是可以取巧，把括号替换为空字符串来判断： public boolean isValid(String s) { boolean res = false; while (s.contains("()") || s.contains("[]") || s.contains("{}")) { s = s.replace("()", ""); s = s.replace("[]", ""); s = s.replace("{}", ""); } if (s.length() == 0) { res = true; } return res; } 415.字符串相加 模拟加法计算： public String addStrings(String num1, String num2) { if (num2.length() > num1.length()) { String temp = num1; num1 = num2; num2 = temp; } int yu = 0; String s = ""; for (int i = 1; i <= num1.length(); i++) { int sum = 0; int a = Integer.valueOf(num1.charAt(num1.length() - i) + ""); if (i <= num2.length()) { int b = Integer.valueOf(num2.charAt(num2.length() - i) + ""); sum = a+b+yu; }else { sum = a+yu; } if (sum >= 10) { yu = 1; s = (sum-10) + s; }else { yu = 0; s = sum + s; } } if (yu == 1) { s = 1 + s; } return s; } 5. 最长回文子串 经典动态规划，动规思路：判断一个字符串是否回文=头尾相等+中间部分回文，dp数组代表了所有长度子串是否回文： public String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } int len = s.length(); String res = s.charAt(0) + ""; boolean[][] dp = new boolean[len][len]; for (int j = 0; j < len; j++) { for (int i = 0; i <= j; i++) { if (i == j) { dp[i][j] = true; }else { dp[i][j] = ((dp[i + 1][j - 1]) || (j - i < 3)) && (s.charAt(i) == s.charAt(j)); } if (dp[i][j] && j - i > res.length() - 1) { res = s.substring(i, j+1); } } } return res; }
[scode type="share"]2021年06月05日中午1点比赛结束[/scode] 第6战蓝桥杯！这应该是博主大学生涯里的最后一次比赛了，总体感觉这次国赛难度比上一次的简单吧。 [scode type="blue"]填空题[/scode] 填空题一共四道，这次做出来了三道，至少做的三道不难： 第一道是输出最大的8位二进制数的十进制————255。 第二道找纯质数，就是这个数字本身是质数，它的十进制的每一位也是质数，从1~20210605一共多少个，我暴力的结果是1903。 第三道是找完全平方数，例如2012年02月02日是2+0+1+2+2+2=9，9是平方数。那么找出2001年1月1日到2021年12月31日有多少，也是一道逻辑题，注意2月28天，闰年（4的倍数）2月29天，剩下的是30/31，最后好像是977吧我暴力的。 最后一道是日常略过，是一棵树求最小权值，赛后听是一道动态规划。（蒙错了） [scode type="blue"]程序设计题[/scode] 第一题把一行字符串全大写输出，水题。 第二题叫作123，给出一个数列112123123412345....，给出两个端点L，R（L<=R），求这个数列中[L,R]的和，灵活使用累加公式Sn = n*(n+1)/2确定出L和R分别在哪个区间，之后区分下情况再通过累加公式的加减即可求出。 第三题给一个随机数列，求特殊区间的个数，这个特殊区间中的所有数字的乘积等于所有数字之后，一开始我以为是双指针，但是发现不对，有感觉像动规，想了一会干脆直接暴力了，拿一点分也行。 第四题是巧克力，一道贪心题，把巧克力价格从小到大排列之后，先从小的吃，注意过期时间，最后求出最低价格。 第五道是括号题目，给一行字符串是一个括号序列，之后给出n个操作，操作分两种，第一种将区间[L,R]内的括号反转，第二种给出左端点L，找出最大的右端点R使得[L,R]是一个合法的括号序列，我是用的暴力，能过一点是一点吧。 第六题叫作异或三角，给一个数n，找出三个数1 <= a,b,c <= n，这三个数要满足两个条件：1. (a^b^c)==0 2.a、b、c可以组成三角形，可以找出多少组。最后时间不多了就直接写了一个三层for交了，希望对一个就行了。 [scode type="blue"]总结[/scode] 总体感觉题目似乎没有去年的国赛难吧，毕竟上次国赛大题我只写了一道，而且第一道还写错了。。。 不过5月初的集训让我感觉收获颇多，很多新的知识这次也都用到了，例如现在做大题都会先留意数据的范围，该用int还是用long，使用Scanner还是BufferedReader，还有自定义比较器。 其中判断括号序列是否合法的办法还是坤坤教给我的，使用replace把"()"替换为""，如果序列合法最后这个字符串肯定会被替换成空字符串的。 之前的3周的集训确实给我这次带来了不小的提升，希望最后的这次蓝桥杯可以完美收官吧。 [scode type="green"]2021年6月8日[/scode] 下午6点多出成绩了，这次依旧是国二 ::aru:blood:: ，可见这次题目确实简单啊，去年我只写了填空题和半道大题就拿了国二。。。 人数分布是这样，国赛JAVA B组获奖人数一共1213人，一等奖62人，二等255人，三等370人，优秀奖525人。 我处在二等的第121名，算是前50%吧，总数里排在183名，在15%，就这样吧，大学里的最后一次比赛了，收官！
【ACM】第十三届ACM国际大学生程序设计竞赛感想
经过三周的算法训练，5月22日早晨我们从新乡坐高铁来到了郑州，前往位于龙子湖周围的河南农业大学，这次我们一共有六个队伍：法外狂徒、三个人的ACM、大聪明、只会心疼哥哥（我）、不写代码等于爱情、铁娘子（女队）。 观光与签到 早上9点多的郑州地铁不是那么拥挤，还有位置可坐，差不多10点左右到了河南农业大学的校门口开始进行签到，这次的队服是蓝色的，教练的衣服是粉红色的，每个参赛人员还有专门的参赛证： [album] [/album] 在校外简单签到之后就进入学校了，不得不说河农大的校门真的比河科院的高档不少，虽然新科的大门也不错，但是老大门确实比较拉跨。而且在进入校门之后有很长的一条直路，两边都是绿化的树木，看起来十分漂亮，而且学校里面交通便利，可以骑单车，学校的整体建筑风格也是偏古欧美那种的（就是有档次(๑•̀ㅁ•́ฅ)）。 [album] [/album] 校园里的街道上有专门的服务人员指路，我们很快就到了第二个签到地点，同时也是我们的比赛地点（如果说这次比赛有哪些不足，就是比赛场地没包一个室内体育馆，而是校内一个个小的实验室，拉跨了）。我们在里面换上队服，一个队站在一起拍个照片（用于最后颁奖时的屏幕展示），上午的签到工作算是结束了。 [album] [/album] 就餐与开幕式 中午在他们学校的食堂吃饭，食堂总体来说也很不错，还有露天的餐桌，我们每人发了40元的餐票，可以在指定餐厅里消费。中午饱餐一顿之后我和李老师还有光岚在室内找了一个地方休息，我同时把电脑拿出来改bug....下午两点开始举行开幕仪式，40分钟的时间暴晒在太阳下面，是真滴热啊。 [album] [/album] 热身赛 举行完开幕仪式就是模拟赛了，让每位参赛队员提前适应比赛环境。这次的比赛形式和之前我参加的ccpc一样，每次做出一道题目之后会有人员走过来给你插上一支气球，每道题都有对应的气球颜色。这次热身赛一共三道题，应该说都是热身题，但我们做的情况并不理想。 第一题就是给出一组数据，选出4个组成一个矩形，输出面积最大值，不能构成矩形输出-1。很明显是一个贪心的题，当时想也没想直接接收完全部数据后使用Arrays.sort排了个序，然后判断输出，结果超时了。行，那就不排序了，在接收的时候就比出最大的两组值，可能也是我比较紧张的问题，错误频出，第一题让我搞了一个小时，错了6次才过，直接给我心态搞炸了。 第二题是一个数论，问题说了一大堆，结果是输出一个值并对17取模，仔细一想那我可以从0试到16全部输出一遍，最坏情况是错了16遍，我便开始试，最后错了7次算是把答案试出来了。 最终我们算是A了两题。 主要还有一部分压力来自于前后两桌，半个小时后桌已经A完三道题走人了，前面那组没过多久也A完走人了（热身赛是两个小时），看着前后两桌都插满了三个气球，被夹在中间的我们着实尴尬，所以心态上有些崩。 整顿与休息 热身赛结束之后又在学校吃了顿饭就回宾馆休息了，晚上把准备好的ACM宝典打印了一份留到第二天用。晚上我们在宾馆也没怎么学习，我倒是把带的笔记本拿出来打了会游戏，要不然这个死沉死沉的玩意就白带了。 第二天早晨早早起床把房退了之后便去学校了，9点开始比赛，我们仨也只是随便吃了点煎包填填肚子。 正式赛 8点半坐在教室里，看了一下周围的墙壁上一共有13只气球，便知晓了这次比赛有13道题目。 9点钟随着哨响，比赛正式开始，我们三个人开始翻阅题册，很惊讶也很高兴的是这次的题目是全中文，不会因为英文而看不懂题目了。随着少康迅速说出某一道题特别简单之后我们开始集中看这道题。由于昨天的热身赛吃了闭门羹，我们今天的对策是三个人必须一起解题，简单题一定不能马虎，争取一遍过没有罚时。 这道题是讲给出一个坐标系（输入为几行字符串），由'*'组成的行或列代表坐标轴，'#'是目标点，求'#'相对于坐标原点(0,0)的位置，基本上可以确定为一道签到题。我们三个人不慌不忙，为了不出错花了20分钟敲出来这道题，又检查了5分钟，最后一遍过。 之后根据排行开始看做的最多的题是A，这也是一个签到题，接收完输入数据后根据题中给的公式做一些判断即可得出结果，但是我们不慌，也还是一点一点认真的敲出了这道题，最后很幸运也是一遍过，我们队的名次位于第100左右，整队的信心大涨。 接着光岚和少康开始一起看“七便士”题目，我根据排行选出另一个做出的题目最多的是最后一题“输入输出”，第一次读题我感觉这道题还是挺麻烦的，有染色端点，染色区间，最后让求最小花费，仅仅看题目给的条件和思路会感觉这道题很麻烦，但是仔细履一遍样例会发现只需把输入数据相减最后相加即可，当时我们三人还又讨论应该不会这么简单吧，但是看看过这道题的人都是一遍过，题目名字叫作“输入输出”，而且题目给的输入量确实比较大，所以当时就赌了一把，直接按一开始的简单思路写，大不了错了就错了，反正没有头绪。我拿着ACM宝典把快速输入敲上，最后写完全部思路把代码一交，过了！原来这道题就是忽悠人的，题目里给的好多条件就没用。（赛后的题解人也说这道题才是准签到题）此时我们队伍的名次来到了80左右，没有罚时。 之后光岚和少康也一起把“七便士”题目做了出来，也是一遍过，此时我们已经做出4题，由于4道都是一遍过，没有罚时，我们的名次来到了第60名！当时别提我们有多高兴了，只能说认真一点绝对没错。而且用了两个小时，还有三个小时的时间，我们认为我们还可以再冲一道题目，铜也该是没问题了，就要看银了！ 从第五题开始就来到了瓶颈期，当时的时间点做出第五题都是前几，看了一下题目是第J题——“甜甜圈” 闭幕式与颁奖典礼 每队选一位成员去参加了闭幕式 [album] [/album] 滚榜： [vplayer url="https:\/\/file.makeyourchoice.cn\/2021\/05\/30\/acm01.mp4" /] 感想 抖音： [vplayer url="https:\/\/file.makeyourchoice.cn\/2021\/05\/30\/acm02.mp4" /] （未完待续....）
本文用于记录ACM比赛时常用的算法和模板 全排列 public class Main { public static void main(String[] args) { perm(new int[]{1,2,3},0,2); } public static void perm(int[] array,int start,int end) { if(start==end) { System.out.println(Arrays.toString(array)); } else { for (int i = start; i <= end; i++) { //1，2，3的全排列这块相当于将其中一个提了出来，下次递归从start+1开始 swap(array,start,i); perm(array,start+1,end); //这块是复原数组，为了保证下次另外的同级递归使用数组不会出错 //这块可以通过树来理解，每次回退一步操作，交换回去 swap(array,start,i); } } } public static void swap(int[] array,int i,int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } 快速幂 public static long fastPow(long k,long e,long mod) { long ans=1; while(k>=1) { if ((k&1)>=1) { ans*=e%mod; } e*=e%mod; k>>=1; } return ans; } 快速输入输出 //第一种 public class Main { static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { String[] init = br.readLine().split(" "); int n = Integer.valueOf(init[0]); long m = Long.valueOf(init[1]); long q = Long.valueOf(init[2]); long[] x = new long[n+1]; String[] xs = br.readLine().split(" "); for (int i = 0; i < n; i++) { x[i+1] = Long.valueOf(xs[i]); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { String s2[]=br.readLine().split(" "); int k = Integer.parseInt(s2[1]); long length = p * x[k]; if ((length/m)%2 == 1) { sb.append(m - (length%m)); }else { sb.append(length%m); } sb.append('\n'); } bw.write(sb.toString()); bw.flush(); bw.close(); br.close(); } } //第二种 public class FastScanner { public static void main(String[] args) { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); try { st.nextToken(); int n = (int) st.nval; System.out.println(n); } catch (IOException e) { e.printStackTrace(); } } } 格式化输出 public class FormatDemo { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("Hello World"); double x=-10000.0/3.0; double y=5000.0/3.0; System.out.println(x); System.out.printf("%,10.2f\r\n",x); System.out.printf("%-,10.2f\r\n",x); System.out.printf("%+(,10.2f %2$.3f\r\n",x,y); System.out.printf("%+(,10.2f %1$.3f %2$.3f %<f %<.3f\r\n",x,y); } } 并查集 public class DisjointSet { public static int n = 6; public static void main(String[] args) { int[] parent = new int[n]; int[] rank = new int[n]; int[][] edges = {{0,1}, {1,2}, {1,3}, {3,4},{2,5}, {4,5}}; init(parent); for (int i = 0; i < edges.length; i++) { int x = edges[i][0]; int y = edges[i][1]; if (!union_vertices(x, y, parent, rank)) { System.out.println("Cycle detected!"); return; } } System.out.println("No cycles found."); } public static void init(int parent[]) { for (int i = 0; i < n; i++) { parent[i] = -1; } } public static int find_root(int x, int[] parent) { int x_root = x; while (parent[x_root] != -1) { x_root = parent[x_root]; } return x_root; } public static boolean union_vertices(int x, int y, int[] parent, int[] rank) { int x_root = find_root(x, parent); int y_root = find_root(y, parent); if (x_root == y_root) { return false; } if (rank[x_root] > rank[y_root]) { parent[y_root] = x_root; }else if (rank[x_root] < rank[y_root]){ parent[x_root] = y_root; }else { parent[x_root] = y_root; rank[y_root]++; } return true; } } 01背包模板 public class Knapsack { public static void main(String[] args) { int[][] plan = new int[6][21]; int[] w = {0,2,4,8,10,13}; int[] v = {0,3,5,9,12,15}; int v1,v2; for(int id=1;id<6;id++) { for(int C=1;C<21;C++) { if(w[id]>C) plan[id][C]=plan[id-1][C]; else { v1 = plan[id-1][C-w[id]]+v[id]; v2 = plan[id-1][C]; plan[id][C] = v1 >=v2 ?v1:v2; } } } //输出背包 for(int i=0;i<6;i++) { for(int j=0;j<21;j++) { if (j > 9 && i < 3) { System.out.print(plan[i][j]+" "); }else { System.out.print(plan[i][j]+" "); } } System.out.println(); } } } 区间调度dp模板 //根据时间做任务，选任务会占据一定的时间 public class S { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); State[] list = new State[n]; for(int i = 0; i < n; i++) { //开始时间，得分，等待时间 list[i] = new State(sc.nextInt(), sc.nextInt(), sc.nextInt()); } Arrays.sort(list); int[] dp = new int[2000001]; //20000001分钟 int index = 0; for (int i = 0; i < 2000000 ; i++) { while (index < n && list[index].m == i) { dp[i+list[index].w] = Math.max(dp[i+list[index].w], dp[i]+list[index].f); index++; } dp[i+1] = Math.max(dp[i + 1], dp[i]); } System.out.println(dp[2000000]); } static class State implements Comparable<State> { public int m,f,w; public State(int a, int b, int c){ m=a; f=b; w=c; } @Override public int compareTo(State s) { return m - s.m; } } } 二分 当 check(mid) == true 调整的是 l 时：计算 mid 的方式应该为 mid = l + r + 1 >> 1： while (l < r) { long mid = l + r + 1 >> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } 当 check(mid) == true 调整的是 r 时：计算 mid 的方式应该为 mid = l + r >> 1： while (l < r) { long mid = l + r >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } 龟速乘法（处理直接加会爆longlong） 快速乘法，采用了倍增思想： long mul(long a, long k) { long ans = 0; while (k > 0) { if ((k & 1) == 1) ans += a; k >>= 1; a += a; } return ans; } 快速幂 static long mpow(long a, long b) { long res = 1; while (b > 0) { if ((b & 1) == 1) { res *= a; } a *= a; b >>= 1; } return res; } 区间dp for (int l = 1; l <= n; l++) {//枚举长度 for (int i = 1; i + l <= n + 1; i++) {//枚举起点， int j = i + l - 1; for (int k = i; k < j; k++) {//枚举分割点，更新小区间最优解 dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + something); } } } Java快读，快输出 StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); sc.nextToken(); int t = (int)sc.nval; PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); out.println(); out.flush(); 质数筛（埃及筛） int N = (int) 1e7; boolean[] isPrime = new boolean[N + 5]; Arrays.fill(isPrime, true); isPrime[1] = false; for (int i = 2; i <= N; i++) { if (isPrime[i]) { for (int j = 2; j * i <= N; j++) { isPrime[i * j] = false; } } } 阶乘因子个数(m!中含有多少k因子) static long numberOfFactorials(long m, long k) { long ret = 0; while (m > 0) { ret += m / k; m /= k; } return ret; } 快排 public static void quick_sort(int[] nums, int l, int r) { if (l >= r) { return; } int x = nums[l], i = l - 1, j = r + 1; while (i < j) { do i++; while (nums[i] < x); do j--; while (nums[j] > x); if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quick_sort(nums, l, j); quick_sort(nums, j + 1, r); } 弗洛伊德算法--构造两点最短路径（全员） 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][j], dp[i][k] + dp[k][j]); } } } 狄克斯特拉算法 import java.util.Arrays; import java.util.PriorityQueue; public class 最短路径 { static int[] d = new int[2100]; static boolean[] vis = new boolean[2100]; static PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> d[o1] - d[o2]); static int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } static int lcm(int x, int y) { return x * y / gcd(x, y); } static void dijkstra() { Arrays.fill(d, Integer.MAX_VALUE); d[1] = 0; vis[1] = true; for (int i = 2; i <= 22; i++) { d[i] = lcm(1, i); heap.add(i); } while (!heap.isEmpty()) { int v = heap.poll(); if (vis[v]) continue; vis[v] = true; if (v == 2021) break; for (int i = Math.max(1, v - 21); i <= Math.min(2021, v + 21); i++) { if (!vis[i]) { d[i] = Math.min(d[i], d[v] + lcm(v, i)); heap.add(i); } } } System.out.println(d[2021]); } public static void main(String[] args) { dijkstra(); } }
[scode type="blue"]2021年04月18日中午1点比赛结束[/scode] [scode type="yellow"]填空题[/scode] 填空题这次做出来了三道，应该说不难，得是能做出来4道的： 第一道是输出一个英文字母的ASCII值，跳过。 第二道应该是记数吧，有点忘了，也不难，跳过。 第三道是算坐标系内点之间构成的线段个数，这里需要用到数学里的公式算出k和x，再单独加上与坐标轴平行的直线，可恨的是我当时斜率公式记错了，应该是y1-y2/x1-x2，但是代码写成了x1-x2/y1-y2，结果检查了半个多小时才看出了，有点影响心态。 第四道是货物装箱，做法应该是直接暴力出2021041820210418的因子，然后再三层for循环判断组合暴力出结果，当时想着写dfs暴力的，结果没写出来... 第五道日常略过 [scode type="yellow"]程序设计题[/scode] 第一题输出时间格式，逻辑题，跳过 第二题砝码称重我是当时没找到规律，结果尝试使用dfs暴力，可以也没写出来。正确的做法应该是找出规律：1个砝码可以算出1，两个砝码可以算出1~4，三个砝码可以算出 [scode type="blue"]2021年4月28日[/scode] 大概是晚上的时候出的成绩，是省赛一等奖，不出意外应该是3道填空和3道大题都做对了，全省排名第30名，算是成绩最好的一次了，虽然没有上次坤坤全省第一那么nb，也是很满意了，毕竟又是裸考. ::aru:envious::
【九韶杯】河科院程序设计协会第一届程序设计竞赛总结（20210411）
。。。快一个月后才来补这篇文章，已经忘的差不多了.... （在牛客网上进行的比赛，只记得当时做的不太好）