wed网站开发是什么,西安百度搜索排名,哈尔滨企业建站模板,wordpress安装memcached力扣爆刷第95天之hot100五连刷61-65 文章目录 力扣爆刷第95天之hot100五连刷61-65一、131. 分割回文串二、51. N 皇后三、35. 搜索插入位置四、74. 搜索二维矩阵五、34. 在排序数组中查找元素的第一个和最后一个位置 一、131. 分割回文串
题目链接#xff1a;https://leetcod…力扣爆刷第95天之hot100五连刷61-65 文章目录 力扣爆刷第95天之hot100五连刷61-65一、131. 分割回文串二、51. N 皇后三、35. 搜索插入位置四、74. 搜索二维矩阵五、34. 在排序数组中查找元素的第一个和最后一个位置 一、131. 分割回文串
题目链接https://leetcode.cn/problems/palindrome-partitioning/description/?envTypestudy-plan-v2envIdtop-100-liked 思路本题就是正常的组合题目只不过需要加上回文子串的判断。
class Solution {ListListString arrayList new ArrayList();ListString list new ArrayList();public ListListString partition(String s) {backTracking(s, 0);return arrayList;}void backTracking(String s, int index) {if(index s.length()) {arrayList.add(new ArrayList(list));return;}for(int i index; i s.length(); i) {if(isTrue(s, index, i)) {list.add(s.substring(index, i1));backTracking(s, i1);list.remove(list.size()-1);}}}boolean isTrue(String s, int left, int right) {while(left right) {if(s.charAt(left) ! s.charAt(right)) {return false;}left;right--;}return true;}
}二、51. N 皇后
题目链接https://leetcode.cn/problems/n-queens/description/?envTypestudy-plan-v2envIdtop-100-liked 思路常规递归类似于排列纵向是每一行横向是每一列每个位置判断是否合法合法只需判断上下和45度与135度无需左右因为左右是回溯回来的干净的很。
class Solution {ListListString arrayList new ArrayList();char[][] source;public ListListString solveNQueens(int n) {source new char[n][n];for(int i 0; i n; i) {Arrays.fill(source[i], .);} backTracking(n, 0);return arrayList;}void backTracking(int n, int row) {if(row n) {ListString list new ArrayList();for(char[] c : source) {list.add(new String(c));}arrayList.add(list);return;}char[] cList source[row];for(int i 0; i n; i) {if(isTrue(n, row, i)) {cList[i] Q;backTracking(n, row1);cList[i] .;}}}boolean isTrue(int n, int x, int y) {for(int i 0; i n; i) {if(source[i][y] Q) return false;}for(int i x, j y; i 0 j 0; i--, j--) {if(source[i][j] Q) return false;}for(int i x, j y; i 0 j n; i--, j) {if(source[i][j] Q) return false;}return true;}
}三、35. 搜索插入位置
题目链接https://leetcode.cn/problems/search-insert-position/description/?envTypestudy-plan-v2envIdtop-100-liked 思路二分查找。
class Solution {public int searchInsert(int[] nums, int target) {int left 0, right nums.length-1;while(left right) {int mid left (right-left)/2;if(nums[mid] target) {return mid;}else if(nums[mid] target) {right mid-1;}else {left mid1;}}return left;}
}四、74. 搜索二维矩阵
题目链接https://leetcode.cn/problems/search-a-2d-matrix/description/?envTypestudy-plan-v2envIdtop-100-liked 思路先定位到是哪一行然后再在该行内进行二分查找。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int row -1, n matrix.length, m matrix[0].length;for(int i 0; i n; i) {if(target matrix[i][0] target matrix[i][m-1]) {row i;break;}}if(row -1) return false;int left 0, right m-1;while(left right) {int mid left (right - left) / 2;if(matrix[row][mid] target) {return true;}else if(matrix[row][mid] target) {right mid - 1;}else {left mid 1;}}return false;}
}五、34. 在排序数组中查找元素的第一个和最后一个位置
题目链接https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envTypestudy-plan-v2envIdtop-100-liked 思路分别搜索左边界和右边界
class Solution {public int[] searchRange(int[] nums, int target) {int i findLeft(nums, target);int j findRight(nums, target);return new int[]{i, j};}int findLeft(int[] nums, int target) {int left 0, right nums.length-1;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 target) {int left 0, right nums.length-1;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;}}
