力扣爆刷第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;
    }
   
}