力扣爆刷第117天之CodeTop100五连刷71-75

力扣爆刷第117天之CodeTop100五连刷71-75

一、48. 旋转图像

题目链接：https://leetcode.cn/problems/rotate-image/description/
思路：向右旋转90度可以由两个操作来达成，即先沿着nums[0][0]和nums[n][n]对角线进行对折，然后再左右对折。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for(int i = 0; i < n; i++) {for(int j = i; j < n; j++) {int t = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = t;}}for(int i = 0; i < n; i++) {for(int j = 0; j < n/2; j++) {int t = matrix[i][j];matrix[i][j] = matrix[i][n-j-1];matrix[i][n-j-1] = t;}}}
}

二、39. 组合总和

题目链接：https://leetcode.cn/problems/combination-sum/description/
思路：组合成一个数，元素无重可复用，开始索引位置不需要加1，然后利用排序，可以早停，其他的就是递归模板。

class Solution {int sum = 0;List<Integer> list = new ArrayList<>();List<List<Integer>> resList = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backTracking(candidates, target, 0);return resList;}void backTracking(int[] candidates, int target, int start) {if(sum == target) {resList.add(new ArrayList(list));return;} for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {sum += candidates[i];list.add(candidates[i]);backTracking(candidates, target, i);sum -= candidates[i];list.remove(list.size()-1);}}
}

三、113. 路径总和 II

题目链接：https://leetcode.cn/problems/path-sum-ii/description/
思路：对二叉树进行递归，路径指的是从根节点到叶子节点，故而前序遍历，在进入左右子树之前搜集结果，当前节点的左右子树递归结束时，要向上一级返回，需要进行回溯的返回操作。

class Solution {int sum = 0, pro = 0;List<Integer> list = new ArrayList<>();List<List<Integer>> resList = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {backTracking(root, targetSum);return resList;}void backTracking(TreeNode root, int targetSum) {if(root == null) return;sum += root.val;list.add(root.val);if(root.left == null && root.right == null && sum == targetSum) {   resList.add(new ArrayList(list));}backTracking(root.left, targetSum);backTracking(root.right, targetSum);sum -= root.val;list.remove(list.size()-1);}
}

四、34. 在排序数组中查找元素的第一个和最后一个位置

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
思路：采用二分查找，分别查找左边界和右边界，注意边界条件，越界和不符合的返回-1；

class Solution {public int[] searchRange(int[] nums, int target) {int left = findList(nums, 0, nums.length-1, target);int right = findRight(nums, 0, nums.length-1, target);return new int[]{left, right};}int findList(int[] nums, int left, int right, int target) {while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] >= target) {right = mid - 1;}else{left = mid + 1;}}if(left < 0 || left >= nums.length) return -1;return nums[left] == target ? left : -1;} int findRight(int[] nums, int left, int right, int target) {while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] <= target) {left = mid + 1;}else{right = mid - 1;}}if(right < 0 || right >= nums.length) return -1;return nums[right] == target ? right : -1;}
}

五、394. 字符串解码

题目链接：https://leetcode.cn/problems/decode-string/description/
思路：字符串的编码符合栈的规律，故使用两个栈，一个栈记录数字，一个栈记录前面已经拼接好的片段，一个字符串作为全局变量接收字符，遇到左括号时记录数字和已经拼好的片段，然后计数和字符串重置，用来记录括号内部的字符，遇到右括号，用之前栈里记录的数字循环拼接这一段字符串，最后再和栈里保存的括号左边的片段进行拼接。

class Solution {public String decodeString(String s) {int num = 0;LinkedList<Integer> stk1 = new LinkedList<>();LinkedList<String> stk2 = new LinkedList<>();StringBuilder res = new StringBuilder();for(char c : s.toCharArray()) {if(c >= '0' && c <= '9') {num = num * 10 + Integer.parseInt(c + "");}else if(c == '[') {stk1.push(num);stk2.push(res.toString());num = 0;res = new StringBuilder();}else if(c == ']') {StringBuilder t = new StringBuilder();int count = stk1.pop();for(int i = 0; i < count; i++) {t.append(res);}res = new StringBuilder(stk2.pop() + t);}else{res.append(c);}}return res.toString();}}