力扣爆刷第95天之hot100五连刷61-65

力扣爆刷第95天之hot100五连刷61-65

一、131. 分割回文串

题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
思路：本题就是正常的组合题目，只不过需要加上回文子串的判断。

class Solution {List<List<String>> arrayList = new ArrayList<>();List<String> list = new ArrayList<>();public List<List<String>> 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, i+1));backTracking(s, i+1);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/?envType=study-plan-v2&envId=top-100-liked
思路：常规递归，类似于排列，纵向是每一行，横向是每一列，每个位置判断是否合法，合法只需判断上下和45度与135度，无需左右，因为左右是回溯回来的干净的很。

class Solution {List<List<String>> arrayList = new ArrayList();char[][] source;public List<List<String>> 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) {List<String> 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, row+1);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/?envType=study-plan-v2&envId=top-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 = mid+1;}}return left;}
}

四、74. 搜索二维矩阵

题目链接：https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-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/?envType=study-plan-v2&envId=top-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;}}