php网站开发实例视频,商业网站开发入门选课,上海网站建设技术托管,医院网站建设公司价格低力扣爆刷第117天之CodeTop100五连刷71-75 文章目录 力扣爆刷第117天之CodeTop100五连刷71-75一、48. 旋转图像二、39. 组合总和三、113. 路径总和 II四、34. 在排序数组中查找元素的第一个和最后一个位置五、394. 字符串解码 一、48. 旋转图像
题目链接#xff1a;https://le…力扣爆刷第117天之CodeTop100五连刷71-75 文章目录 力扣爆刷第117天之CodeTop100五连刷71-75一、48. 旋转图像二、39. 组合总和三、113. 路径总和 II四、34. 在排序数组中查找元素的第一个和最后一个位置五、394. 字符串解码 一、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;ListInteger list new ArrayList();ListListInteger resList new ArrayList();public ListListInteger 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;ListInteger list new ArrayList();ListListInteger resList new ArrayList();public ListListInteger 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;LinkedListInteger stk1 new LinkedList();LinkedListString 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();}}
