数组

704 Binary Search

class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while(left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return -1;
    }
}

35 Search Insert Position

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return left;
    }
}

34 Find First and Last Position of Element in Sorted Array

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int isFound = binarySearch(nums, target);
        if (isFound == -1) return result;
        else {
            int left = isFound;
            int right = isFound;
            while (left >= 0 && nums[left] == nums[isFound]) left--;
            while (right < nums.length && nums[right] == nums[isFound]) right++;
            result[0] = left + 1;
            result[1] = right - 1;
        }
        return result;
    }

    private int binarySearch(int[] nums, int target){
        
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;
        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return -1;
    }
}

69 Sqrt(x)

注意要用long表示整数型

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1; 
        int left = 0;
        int right = x;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            long midS = (long) mid * mid;

            if (midS == (long) x) return mid;
            else if (midS < x) left = mid + 1;
            else right = mid;
        }

        return left - 1;
        
    }
}

367 Valid Perfect Square

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 0|| num == 1) return true;

        int left = 0;
        int right = num;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            long midS = (long) mid * mid;
            if (midS == (long) num) return true;
            else if (midS < num) left = mid + 1;
            else right = mid;
        }

        return false;
    }
}

27 Remove Element

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) return 0;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            if (nums[left] == val) nums[left] = nums[right--];
            else left++;
        }

        return left;
    }
}

26 Remove Duplicates from Sorted Array


class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length){
            if (nums[fastIndex] == nums[slowIndex]) fastIndex++;
            else {
                slowIndex++;
                nums[slowIndex] = nums[fastIndex++];
            }
        }

        return slowIndex + 1;
    }
}

283 Move Zeroes

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int slowIndex = 0;
        int fastIndex = 0;

        while (fastIndex < nums.length){
            if (nums[fastIndex] != 0){
                nums[slowIndex++] = nums[fastIndex];
            }

            fastIndex++;
        }


        while (slowIndex < nums.length){
            nums[slowIndex++] = 0;
        }
        
    }
}

844 Backspace String Compare

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspaceHelper(s).equals(backspaceHelper(t));
    }

    private String backspaceHelper(String s){
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c != '#') sb.append(c);
            else {
                if (sb.length() >= 1) sb.deleteCharAt(sb.length() - 1);
            }
        }

        return sb.toString();
    }
}

977 Squares of a Sorted Array



class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];

        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while (left <= right){
            int leftS = nums[left] * nums[left];
            int rightS = nums[right] * nums[right];

            if (leftS >= rightS){
                result[index--] = leftS;
                left++;
            } else {
                result[index--] = rightS;
                right--;
            }
        }
        return result;
    }
}

209 Minimum Size Subarray Sum

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minSize = Integer.MAX_VALUE; 

        while (right < nums.length){
            sum += nums[right++];
            while (sum >= target){
                minSize = Math.min(minSize, right - left);
                sum -= nums[left++];
            }
        }

        return minSize == Integer.MAX_VALUE ? 0 : minSize;
    }
}

904 Fruit Into Baskets

class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int right = 0;
        int maxNum = Integer.MIN_VALUE;

        Map<Integer, Integer> map = new HashMap<>();

        while (right < fruits.length){
            map.put(fruits[right], map.getOrDefault(fruits[right++], 0) + 1);
            while (map.size() > 2) {
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            maxNum = Math.max(maxNum, right - left);
        }

        return maxNum;
    }
}

59 Spiral Matrix II


class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int offset = 1;
        int start = 0;
        int i = 0, j = 0;
        int loop = n / 2;
        int count = 1;

        while (loop-- > 0){
            for (j = start; j < n - offset; j++){
                result[start][j] = count++; 
            }
            for (i = start; i < n - offset; i++){
                result[i][j] = count++;
            }

            for (;j > start; j--){
                result[i][j] = count++;
            }

            for (;i > start; i--){
                result[i][j] = count++;
            }

            offset++;
            start++;
        }

        if (n % 2 == 1){
            result[start][start] = count;
        }

        return result;
        
    }
}

80 Remove Duplicates from Sorted Array II

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) return nums.length;

        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length){
            nums[slowIndex++] = nums[fastIndex++];
            if (fastIndex < nums.length && nums[fastIndex] == nums[slowIndex - 1])
            nums[slowIndex++] = nums[fastIndex++];

            while (fastIndex< nums.length && nums[fastIndex] == nums[slowIndex - 1]) fastIndex++;
        }

        return slowIndex;

    }
}

Linked List

203 Remove Linked List Elements

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null){
            if (cur.val == val) pre.next = cur.next;
            else pre = cur;
            cur = cur.next;
        }

        return dummy.next;
    }
}

707 Design Linked List

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val, ListNode next){
        this.val = val; 
        this.next = next;
    }
}

class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index > size - 1) return -1;
        ListNode cur = head;
        for (int i = 0; i<= index; i++){
            cur = cur.next;
        }   
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;

        size++;
        ListNode pre = head;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) return;
        size--;
        ListNode pre = head;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }

        pre.next = pre.next.next;
    }
}

206 Reverse Linked List

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode cur = head;
        ListNode temp;
        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        
        return pre;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode pre){
        if (cur == null) return pre;

        ListNode temp = cur.next;
        cur.next = pre;

        return reverse(temp, cur);
    }
}

24 Swap Nodes in Pairs

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;
        
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        
        while (pre.next != null && pre.next.next != null){
            ListNode temp = pre.next.next.next;
            ListNode first = pre.next;
            ListNode second = pre.next.next;

            pre.next = second;
            second.next = first;
            first.next = temp;

            pre = first;
        }

        return dummy.next;
        
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;

        ListNode next = head.next;
        ListNode newNode = swapPairs(head.next.next);

        next.next = head;
        head.next = newNode;

        return next;

    }
}

19 Remove Nth Node From End of List

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
		
		ListNode slowIndex = dummy;
		ListNode fastIndex = dummy;
		
		for (int i = 0; i <= n; i++) fastIndex = fastIndex.next;

		while(fastIndex != null){
			fastIndex = fastIndex.next;
			slowIndex = slowIndex.next;
		}
		
		slowIndex.next = slowIndex.next.next;
		
		return dummy.next;
    }
}

160 Intersection of Two Linked Lists

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenHeadA = 0;
        int lenHeadB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != null){
            lenHeadA++;
            curA = curA.next;
        }

        while (curB != null){
            lenHeadB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if (lenHeadA > lenHeadB){
            for (int i = 0; i < lenHeadA - lenHeadB; i++){
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < lenHeadB - lenHeadA; i++){
                curB = curB.next;
            }
        }

        while (curA != null){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }
}

142 Linked List Cycle II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                ListNode node1 = head;
                ListNode node2 = slow;

                while (node1 != node2){
                    node1 = node1.next;
                    node2 = node2.next;
                }

                return node1;
            }
        }

        return null;
    }
}

哈希表

242 Valid Anagram

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] chars = new int[26];
        for (int i = 0; i < s.length(); i++){
            chars[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < t.length(); i++){
            chars[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < chars.length; i++){
            if (chars[i] != 0) return false;
        }

        return true;
    }
}

383 Ransom Note

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] chars = new int[26];

        for (int i = 0; i < magazine.length(); i++){
            chars[magazine.charAt(i) - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++){
            chars[ransomNote.charAt(i) - 'a']--;
        }

        for (int i = 0; i < chars.length; i++){
            if (chars[i] < 0) return false;
        }

        return true;
    }
}

复习

贪心算法没有套路只有思路，从局部最优解找到全局最优解

455 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int indexC = 0;
        int indexG = 0;
        int count = 0;
        while (indexC < s.length){
            if (s[indexC] >= g[indexG]){
                count++;
                indexC++;
                indexG++;
            } else {
                indexC++;
            }
            if (count == g.length) return count;
        }
        return count;
    }
}

376 摆动序列

在更新preDiff的时候需要注意时机，只有在更新count的时候才更新prediff 即在摆动时更新，就不会在单调区间时出问题

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 1) return 0;

        int count = 1;
        int index = 1;
        int curDiff = 0;
        int preDiff = 0;
        for (index = 1; index < nums.length; index++){
            curDiff = nums[index] - nums[index - 1];
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)){
                count++;
                preDiff = curDiff;
            }
            
        }

        return count;
    }
}

53 最大子序和

具体逻辑，就是不停累加数组里面的数，遇到负数，就清空sum，即舍弃前面所有的总和

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) sum = 0;
        }

        return maxSum;
    }
}

122 买卖股票的最佳时机II

此题即将所有两个值的区间为正值的数加在一起，负值舍弃，在贪心算法中，每一天如果买进，第二天卖出则所有正值就是最大值
最终利润可以分解，所以可以用贪心算出每一天的收益

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 1) return 0;
        int sum = 0;
        for (int i = 1; i < prices.length; i++){
            int curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0) sum += curDiff;
        }

        return sum;
    }
}

55 跳跃游戏

这道题本质是累加nums[i]之后的数字，找到是不是>=数组长度

此题的难点是在于for loop 之中的判断条件是累加的，是变化的


class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;

        int coverage = 0;

        for (int i = 0; i <= coverage; i++){
            coverage = Math.max(coverage, i + nums[i]);
            if (coverage >= nums.length - 1){
                return true;
            }
        }

        return false;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;

        int maxDistance = 0;

        for (int i = 0; i < nums.length; i++){
            maxDistance = Math.max(maxDistance, i+ nums[i]);
            if (maxDistance >= nums.length - 1) return true;
            if (maxDistance == i && nums[i] == 0) return false;
        }

        return true;
        
    }
}

45 跳跃游戏II

思路：
解题要从覆盖范围出发，不管怎么跳，覆盖范围一定可以跳到，最小步数增加覆盖范围，一旦覆盖了终点就是最小步数
利用current distance 记录走的步数，如果i == curdistance，就相当于走到了现在的max的最终，需要count++；

也就是如果i走到超过当前可覆盖的最大范围，则count就需要加一了，这之后覆盖记录的这一count之中最大范围值

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1 || nums == null) return 0;
        
        int count = 0;
        int curDistance = 0;
        int maxDistance = 0;

        for (int i = 0; i < nums.length; i++){
            maxDistance = Math.max(maxDistance, i + nums[i]);
            if (maxDistance >= nums.length - 1){
                count++;
                break;
            }

            if (i == curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count++;
    }
}

解法需要温习

class Solution {
    public int jump(int[] nums) {
        int result = 0;
        int end = 0;
        int temp = 0;
        for (int i = 0; i <= end && end < nums.length - 1; i++){
            temp = Math.max(temp, i + nums[i]);
            if (i == end) {
                end = temp;
                result++;
            }
        }

        return result;
    }
}

回溯总结

77 组合

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }

    private void backTracking(int n, int k, int start){
        if (k == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - k + 1; i++){
            k--;
            path.add(i);
            backTracking(n, k, i + 1);
            k++;
            path.removeLast();
        }
    }
}

17 电话号码的字母组合

class Solution {
    String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }
    private void backTracking(String digits, int start){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start) - '0'];
        for (int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

216 组合总和III

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }

    private void backTracking(int k, int n, int start){
        if (n < 0) return;
        if (k == 0 && n == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= 9 - k + 1; i++){
            k--;
            n -= i;
            path.add(i);
            backTracking(k, n, i + 1);
            path.removeLast();
            n += i;
            k++;
        }
    }
}

39 组合总和

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            target -= candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i);
            path.removeLast();
            target += candidates[i];
        }

        
    }
}

40 组合总和II

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i + 1);
            target += candidates[i];
            path.removeLast();
            used[i] = false;
        }
    }
}

131 分割回文串

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) return result;
        backTracking(s, 0);

        return result;
    }

    private void backTracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                path.add(s.substring(start, i + 1));
                backTracking(s, i + 1);
                path.removeLast();
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end){
        while (start <= end){
            if (s.charAt(start++) != s.charAt(end--)) return false;
        }

        return true;
    }
}

93 复原ip地址

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0 || s.length() > 12) return result;
        backTracking(s, 0, 0);
        return result;
    }

    private void backTracking(String s, int start, int pointsNum){
        if (pointsNum == 3) {
            if (isValid(s, start, s.length() - 1)){
                result.add(s);
                return;
            }
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                s = s.substring(0, i + 1) + '.' + s.substring(i + 1); 
                pointsNum++;
                backTracking(s, i + 2, pointsNum);
                pointsNum--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            }
        }
    }
    private boolean isValid(String s, int start, int end){
        if (start > end) return false;

        if (s.charAt(start) - '0' == 0 && start != end) return false;

        int num = 0;
        for (int i = start; i <= end; i++){
            if (s.charAt(i) - '0' < 0 || s.charAt(i) - '0' > 9) return false;
            
            num = num * 10 + s.charAt(i) - '0';

            if (num > 255) return false;
        }

        return true;
    }
}

78 子集

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList<>(path));

        for (int i = start; i< nums.length; i++){
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

90 子集II

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        Arrays.sort(nums);
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList(path));

        for (int i = start; i < nums.length; i++){
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

491 递增子序列

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        if (path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++){
            if (set.contains(nums[i]) || !path.isEmpty() && nums[i] < path.get(path.size() - 1)) continue;
            set.add(nums[i]);
            path.add(nums[i]);

            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46 全排列

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return result;
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
        }
    }
}

47 全排列II

需要判断指定元素是否在枝上

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) return result;
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;    
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;
            if (used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
            
        }
    }
}

332 重新安排行程

class Solution {
    List<String> result = new LinkedList<>();
    Map<String, Map<String, Integer>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets){
            Map<String, Integer> temp;
            if (map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }

            map.put(t.get(0), temp);
        }

        result.add("JFK");
        backTracking(tickets.size());
        return new ArrayList<>(result);
    }

    private boolean backTracking(int ticketSize){
        if (result.size() == ticketSize + 1){
            return true;
        }

        String last = result.getLast();
        if (map.containsKey(last)){
            for (Map.Entry<String, Integer> entry : map.get(last).entrySet()){
                int count = entry.getValue();
                if (count > 0){
                    result.add(entry.getKey());
                    entry.setValue(count - 1);
                    if (backTracking(ticketSize)) return true;
                    result.removeLast();
                    entry.setValue(count);
                }
                
            }
        }
        return false;

    }
}

也可利用priority queue，做排序

51 N皇后

class Solution {
    List<List<String>> result = new ArrayList<>();
    char[][] board;
    public List<List<String>> solveNQueens(int n) {
        board = new char[n][n];
        for (char[] i : board){
            Arrays.fill(i, '.');
        }
        backTracking(n, 0);
        return result;
    }

    private void backTracking(int n, int row){
        if (row == n){
            result.add(board2List(board));
            return;
        }
        for (int i = 0; i < n; i++){
            if (isValid(n, row, i)){
                board[row][i] = 'Q';
                backTracking(n, row + 1);
                board[row][i] = '.';
            }
        }
    }

    private List<String> board2List(char[][] board){
        List<String> result = new ArrayList<>();
        for (char[] i : board){
            result.add(String.copyValueOf(i));
        }

        return result;
    }


    private boolean isValid(int n, int row, int col){
        for (int i = row - 1; i >= 0; i--){
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (board[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }
}

37 解数独


class Solution {
    public void solveSudoku(char[][] board) {
        solver(board);
    }

    private boolean solver(char[][] board){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++){
                    if (isValid(board, i, j, k)){
                        board[i][j] = k;
                        if (solver(board)) return true;
                        board[i][j] = '.';
                    }
                }

                return false;
            }
        }

        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char k){
        for (int i = 0; i < 9; i++){
            if (board[i][col] == k) return false; 
        }
        for (int i = 0; i < 9; i++){
            if (board[row][i] == k) return false;
        }

        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;

        for (int i = startRow; i < startRow + 3 ; i++){
            for (int j = startCol; j< startCol + 3; j++){
                if (board[i][j] == k) return false;
            }
        }

        return true;
    }
}

贪心算法

理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优
贪心没有套路
最好的策略就是反例，举不了反例就是用贪心，有反例考虑动态规划

贪心算法分四步

问题分解成若干子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

455 分发饼干

小饼干喂小胃口
或者大饼干先满足大胃口


class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int index = 0;
        int count = 0;
        for (int i : g){
            while (index < s.length && i > s[index]) index++;
            if (index == s.length) break;
            count++;
            index++;
        }

        return count;
    }
}

376 摆动序列

局部最优是删除单调坡度上的点
整体就是求整个序列有几个局部峰值

不用删除，只需要就长度，即统计峰值数量

考虑情况：

上下坡中有中坡，这里可以删除左边的或者右边的
数组首位两端，可以写死，或者添加dummy在数组中
单调坡度上有平坡

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 1){
            return nums.length;
        }

        int curDiff = 0;
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                count++;
                preDiff = curDiff;
            }

        }

        return count;

        
    }
}

53 最大子序和

局部：如果连续和为负数时，放弃，从下一个计算连续和
全局：最大连续和

如果 count 小于0，把coun归位
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1) return nums[0];

    int sum = Integer.MIN_VALUE;
    int count = 0;

    for (int i = 0; i < nums.length; i++){
        count += nums[i];
        sum = Math.max(count, sum);
        if (count <= 0){
            count = 0;
        }
    }

    return sum;

}

}

复习

77 组合

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int start){
        if (k == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - k + 1; i++){
            path.add(i);
            k--;
            backtracking(n, k, i + 1);
            k++;
            path.removeLast();
        }
    }
}

17 电话号码的字母组合

class Solution {
    String[] numString = {"", "", "abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backtracking(digits, 0);
        return result;        
    }

    private void backtracking(String digits, int start){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start) - '0'];
        for (int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backtracking(digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

216 组合总和III

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }

    private void backtracking(int k, int n, int start){
        if (n < 0) return;
        if (k == 0 && n == 0){
            result.add(new ArrayList(path));
            return;
        }

        for (int i = start; i <= 9 - k + 1; i++){
            k--;
            n-=i;
            path.add(i);
            backtracking(k, n, i + 1);
            k++;
            n += i;
            path.removeLast();
        }
    }
}

39 组合总和

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        backtracking(candidates, target, 0);
        return result;
    }

    private void backtracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            target -= candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, i);
            path.removeLast();
            target += candidates[i];
        }
    }
}

40 组合总和II

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        used = new boolean[candidates.length];
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return result;
    }

    private void backtracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            target -= candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, i + 1);
            used[i] = false;
            path.removeLast();
            target += candidates[i];

        }
    }
}

131 分割回文串

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s.length() == 0 || s == null) return result;
        backtracking(s, 0);
        return result;
    }

    private void backtracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                path.add(s.substring(start, i + 1));
                backtracking(s, i + 1);
                path.removeLast();
            }
        }
    }
    private boolean isPalindrome(String s, int start, int end){
        while (start<=end){
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }

        return true;
    }
}

93 复原ip地址

class Solution {
    List<String> result=  new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() == 0 || s == null || s.length() > 12) return result;

        backtracking(s, 0, 0);
        return result;
    }

    private void backtracking(String s, int start, int points){
        if (points == 3){
            if (isValid(s, start, s.length() - 1)){
                result.add(new String(s));
                return;
            }
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                points++;
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                backtracking(s, i + 2, points);
                points--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            }
        }
    }

    private boolean isValid(String s, int start, int end){
        if (start > end) return false;
        if (s.charAt(start) - '0' == 0 && start != end) return false;
        int num = 0;

        for (int i = start; i <= end; i++){
            if (s.charAt(i) - '0' > 9 || s.charAt(i) - '0' < 0) return false;
            num = num * 10 + s.charAt(i) - '0';
            if (num > 255) return false;
        }

        return true;
    }
}

78 子集

注意result添加地方

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return result;
    }

    private void backtracking(int[] nums, int start){
        result.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

90 子集II

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            backTracking(nums, i + 1);
            used[i] = false;
            path.removeLast();
        }
    }
}

491 递增子序列

这里在result结果输出时不返回
利用set判断结果
判断path里面的重复数组

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backtracking(nums, 0);
        return result;
    }

    private void backtracking(int[] nums, int start){
        if (path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++){
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || set.contains(nums[i])) continue;
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46 全排列

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backtracking(nums);
        return result;
    }

    private void backtracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            backtracking(nums);
            path.removeLast();
        }
    }
}

47 全排列II

里面除了包含了同层去重，还包含了同枝下是否使用过该元素的去重

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (nums.length == path.size()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            if (used[i] == false){
                path.add(nums[i]);
                used[i] = true;
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
        }
    } 
}

332 重新安排行程

难点：

一个行程可能有圆
有多种解法时，字母排序问题
回溯法的终止条件
搜索过程中遍历机场对应的所有机场

建立Map<String, Map<String, Integer>> 记录每个飞机场对应的下一个飞机场的map

注意因为有字母排序问题，生成map<String,Integer>时要用Treemap直接进行排序

class Solution {
    LinkedList<String> result = new LinkedList<>();
    Map<String, Map<String, Integer>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets){
            Map<String, Integer> temp; 
            if (map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }

            map.put(t.get(0), temp);
        }

        result.add("JFK");
        backtracking(tickets.size());
        return new ArrayList(result);
    }

    private boolean backtracking(int ticketSize){
        if (result.size() == ticketSize + 1){
            return true;
        }
        
        String last = result.getLast();
        if (map.containsKey(last)){
            for(Map.Entry<String, Integer> entry: map.get(last).entrySet()){
                int count = entry.getValue();
                if (count > 0){
                    result.add(entry.getKey());
                    entry.setValue(count - 1);
                    if (backtracking(ticketSize)) return true;
                    result.removeLast();
                    entry.setValue(count);
                }
            }
        }

        return false;
    }
}

优化就是把Map<String, Integer> 调整成为链表的形式
添加节点不需要利用treemap

class Solution {
    Map<String, LinkedList<String>> ticketMap = new HashMap<>();
    LinkedList<String> result = new LinkedList<>();
    int total;

    public List<String> findItinerary(List<List<String>> tickets) {
        total = tickets.size() + 1;
        for (List<String> ticket : tickets) {
            addNew(ticket.get(0), ticket.get(1));
        }
        result.add("JFK");
        deal();
        return result;
    }

    boolean deal() {
        if (result.size() == total) {
            return true;
        }

        String last = result.getLast();
        if (ticketMap.containsKey(last)){
            String cur;
            LinkedList<String> list = ticketMap.get(last);
            for (int i = 0; i < list.size(); i++){
                cur = list.get(i);
                list.remove(i);
                result.add(cur);
                if (deal()) return true;
                result.removeLast();
                list.add(i, cur);
            }
        }
        return false;
    }

    void addNew(String start, String end) {
        LinkedList<String> startAllEnd = ticketMap.getOrDefault(start, new LinkedList<>());
        if (!startAllEnd.isEmpty()) {
            for (int i = 0; i < startAllEnd.size(); i++) {
                if (end.compareTo(startAllEnd.get(i)) < 0) {
                    startAllEnd.add(i, end);
                    return;
                }
            }
            startAllEnd.add(startAllEnd.size(), end);
        } else {
            startAllEnd.add(end);
            ticketMap.put(start, startAllEnd);
        }
    }
}

51 N皇后

本题难点就是怎样找到valid的格子，也就是Q的位置
要检查列，45度角，135度；

将此问题抽象成树形式

class Solution {
    List<List<String>> result = new ArrayList<>();
    char[][] chessboard;
    public List<List<String>> solveNQueens(int n) {
        chessboard = new char[n][n];
        for (char[] i : chessboard){
            Arrays.fill(i, '.');
        }

        backtracking(n, 0);
        return result;
    }

    private void backtracking(int n, int row){
        if (row == n){
            result.add(Board2List());
            return;
        }

        for (int i = 0; i < n; i++){
            if (isValid(n, row, i)){
                chessboard[row][i] = 'Q';
                backtracking(n, row + 1);
                chessboard[row][i] = '.';
            }
        }
    }

    private List<String> Board2List(){
        List<String> list = new ArrayList<>();

        for (char[] i : chessboard){
            list.add(String.copyValueOf(i));
        }

        return list;
    }

    private boolean isValid(int n, int row, int col){
        for (int i = row - 1; i >= 0; i--){
            if (chessboard[i][col] == 'Q') return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (chessboard[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++){
            if (chessboard[i][j] == 'Q') return false;
        }

        return true;
    }
}

37 解数独

二维递归
思路类似n皇后
只是比n皇后多一层循环

class Solution {
    public void solveSudoku(char[][] board) {
        sudoSolver(board);
    }

    private boolean sudoSolver(char[][] board){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] != '.') continue;

                for (char k = '1'; k <= '9'; k++){
                    if (isValid(i, j, k, board)){
                        board[i][j] = k;
                        if (sudoSolver(board)) return true;
                        board[i][j] = '.'; 
                    }
                }

                return false;
            }
        }

        return true;
    }

    private boolean isValid(int row, int col, char val, char[][] board){
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val) return false;
        }
        for (int i = 0; i < 9; i++){
            if (board[i][col] == val) return false;
        } 

        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;

        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val) return false;
            }
        }

        return true;
    }
}

复习

77 组合


class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k ,1);
        return result;
    }

    private void backTracking(int n, int k, int start){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = start; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            backTracking(n , k, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

17 电话号码的字母组合

class Solution {
    String[] numString = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }

    private void backTracking(String digits, int start){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start) - '0'];
        for (int i = 0; i< str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

216 组合总和III

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k , n, 1);
        return result;
    }

    private void backTracking(int k, int n , int start){
        if (n < 0) return;
        if (n == 0 && path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);
            n -= i;
            backTracking(k, n, i + 1);
            n += i;
            path.remove(path.size() - 1);
        }
    }
}

39 组合总和

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i);
            target += candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

40 组合总和II

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.sort(candidates);
        Arrays.fill(used, false);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (target < 0) break;
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            path.add(candidates[i]);
            used[i] = true;
            target -= candidates[i];
            backTracking(candidates, target, i + 1);
            target += candidates[i];
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

131 分割回文串

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) return result;

        backTracking(s, 0);
        return result;
    }

    private void backTracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                path.add(s.substring(start, i + 1));
                backTracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end){
        while (start <= end){
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

93 复原ip地址

注意：
判断数字问题
判断最后一段符合逻辑
注意对s的操作

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() == 0 || s.length() > 12) return result;
        backTracking(s, 0, 0);
        return result;
    }

    private void backTracking(String s, int start, int points){
        if (points == 3){
            if (isValid(s, start, s.length() - 1)){
                result.add(s);
            }

            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                points++;
                backTracking(s, i + 2, points);
                points--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            } else break;
        }
    }

    private boolean isValid(String s, int start, int end){
        if (start > end) return false;
        if (s.charAt(start) == '0' && start != end) return false;
        int num = 0;
        for (int i = start; i <= end; i++){
            if (s.charAt(i) - '0' > 9 || s.charAt(i) - '0' < 0) return false;
            num = num * 10 + s.charAt(i) - '0';
            if (num > 255) return false;
        }
        return true;
    }
}

78 子集

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++){
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

90 子集II

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> path = new ArrayList<>();

    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            backTracking(nums, i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

491 递增子序列

利用在回溯函数里面的hashset或者int[] 记录本层通过的点
利用if语句判断是否递增，或者是否是重复的值

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        if (path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        int[] used = new int[201];
        for (int i = start; i < nums.length; i++){
            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || used[nums[i] + 100] == 1  ) continue;
            path.add(nums[i]);
            used[nums[i] + 100] = 1;
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private boolean isNonDecreasing(List<Integer> nums){
        for (int i = 1; i < nums.size(); i++){
            if (nums.get(i) < nums.get(i - 1)){
                return false;
            }
        }

        return true;
    }
}


class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    private void backTracking(int[] nums, int start){
        if (path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++){
            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || set.contains(nums[i])) continue;
            set.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    } 
}

46 全排列

第一种利用used记录path里面有没有nums[i]


class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums);
            used[i] = false;
            path.removeLast();
        }
    }
}

第二种直接通过检查path里面有没有nums[i] 元素判断
List 有个 removeLast 方法

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
        }
    }
}

47 全排列II

去重代码中
!used[i - 1] 是树层去重
used[i - 1] 是树枝去重
要确定used[i] 是否为false，因为i一直是从0开始的

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            if (used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                path.removeLast();
                used[i] = false;
            }
        }
    } 
}

复习

77 组合

注意剪枝操作，以及for loop的判断条件


class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        getPath(n , k, 1);
        return result;
    }

    private void getPath(int n, int k, int start){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            getPath(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

17 电话号码的字母组合

注意for loop之前的值

class Solution {
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }

    private void backTracking(String digits, int start){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }

        String str = numString[digits.charAt(start) - '0'];
        for (int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

39 组合总和

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length == 0) return result;
        backTracking(candidates, target, 0);
        return result;    
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0){
            return;
        }
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            target -= candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i);
            path.remove(path.size() - 1);
            target += candidates[i];
        }
    }
}

40 组合总和II

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);  
        return result;  
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (target < 0) break;
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i-1]) continue;

            target -= candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backTracking(candidates, target, i + 1);
            path.remove(path.size() - 1);
            target += candidates[i];
            used[i] = false;
        }
    }
}

216 组合总和III

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }

    private void backTracking(int k, int n, int start){
        if (n < 0) return;
        if (n == 0 && path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= 9 - (k - path.size()) + 1; i++){
            n -= i;
            path.add(i);
            backTracking(k, n, i + 1);
            path.remove(path.size() - 1);
            n += i;
        }
    }
}

131 分割回文串

分割过程的for loop
先是切割出一个字符判断，如果是，就切割第二个，是切割第三个，完成后
第二个循环开始，直接切割两个，是移动，不是就继续第三个循环

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return result;
    }

    private void backTracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                path.add(s.substring(start, i+1));
                backTracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String s, int left, int right){
        while (left <= right){
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }

        return true;
    }
}

93 复原IP 地址

分割问题和分割回文串类似
几个重点，

代码随想录利用了一个pointnum记录逗号数量，判断
我没有用pointnum
我用Integer.parseInt()转化了string

在实际问题中，判断数字是否valid也很重要

数字起始不能有0

数字要在0 到 255中间

class Solution {
    List<String> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backTracking(s, 0);
        return result;
    }

    private void backTracking(String s, int start){
        if (path.size() == 4){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++){
                sb.append(path.get(i)).append(".");
            }
            sb.append(path.get(path.size() - 1));
            if (sb.length() == s.length() + 3){
                result.add(sb.toString());
            }
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                path.add(Integer.parseInt(s.substring(start, i + 1)));
                backTracking(s, i + 1);
                path.remove(path.size() - 1);
            } else {
                break;
            }
            
        }
    }

    private boolean isValid(String s, int start, int end){
        if (start > end){
            return false;
        }
        if (s.charAt(start) == '0' && end != start) return false;

        int num = 0;
        for (int i = start; i <= end; i++){
            if (s.charAt(i) > '9' || s.charAt(i) < '0'){
                return false;
            }

            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255){
                return false;
            }
        }

        return true;
    }
}

78 子集

与组合和分割都不一样，
如果把子集问题抽象成树，就要把所有结点都记录下来

终止条件，就是start到了nums length的时候

result一直添加path

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList<>(path));
        if (start >= nums.length) return;

        for (int i = start; i < nums.length; i++){
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

90 子集II

利用组合中的去重原理

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        Arrays.fill(used, false);
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList<>(path));
        if (start > nums.length){
            return;
        }

        for (int i = start; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums, i +1);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

拓展 645 setmismatch

思路
利用loop循环查找，不等于同位置的结点，将该节点放到对应的位置上，进行排序，然后再利用for loop查找不等于该位置上的值输出result

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int i = 0;
        while (i < nums.length){
            if (nums[nums[i] - 1] != nums[i]){
                swap(nums, nums[i] - 1, i);
            } else {
                i++;
            }
        }

        for (i = 0; i < nums.length; i++){
            if (nums[i] != i + 1){
                result[0] = nums[i];
                result[1] = i + 1;
            }
        }

        return result;
    }

    private void swap(int[] nums, int index1, int index2){
        nums[index1] ^= nums[index2];
        nums[index2] ^= nums[index1];
        nums[index1] ^= nums[index2];
    }
}

代码随想录第二十七天

Posted on 2024-01-21 Edited on 2024-01-22 In 代码随想录

复习

回溯结构



private void backtracking(...){
if (终止条件){
	保存结果;
	return;
}
	
for (选择： 本层集合中的元素（树中节点孩子的数量就是集合的大小）){

	处理节点
	backTracking(路径，选择列表)；//递归
	回溯,撤销处理结果
}

}

77 组合

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        getPath(n, k, 1);

        return result;
    }

    private void getPath(int n, int k, int start){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            getPath(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

216 组合总和III

判断n时，如果n< 0 则直接返回
还有for loop 中的判断条件

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }

    private void backTracking(int k, int n, int start){
        if (n < 0) return;
        if (n == 0 && path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);
            n -= i;
            backTracking(k, n, i + 1);
            n += i;
            path.remove(path.size() - 1);
        }
    }
}

17 电话号码的字母组合

class Solution {
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }

    private void backTracking(String digits, int index){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }

        String str = numString[digits.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        
    }
}

39 组合总和

本体没有数量要求，可以无限重复，但总和有限制，需要的就是解决答案重复问题

此时利用start，将函数锁定，只能向后或当前元素选取即可


class Solution {
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
        }

        for (int i = start; i < candidates.length; i++){
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i);
            target += candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

剪枝优化
把candidates sort一下，这样可以减少操作，可以把对n的判断放到循环内部减少时间


class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++){
            if (target < 0) break;
            target -= candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i);
            target += candidates[i];
            path.remove(path.size() - 1);

        }
    }
}

40 组合总和II

组合问题的去重

难点在于candidates里面有重复元素但是不能有重复组合

从树的结构上，同一个树层上不能重复选取相同的值，这样会重复读取

在同一层上要记录选取过的元素

基本结构不变，利用used boolean数组

首先sort candidates数组记录used数组全部false

比较candidates的这一位和前一位是不是同一个数，如果是，如果前一位已经被用了，就跳过此次循环

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

添加回溯used数组

 class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        if (candidates == null || candidates.length == 0) return result;
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (target < 0) break;
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue; 
            used[i] = true;
            target -= candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
            target += candidates[i];
        }

    }
}

131 分割回文串

此题为分割问题

第一要分割，第二要判断回文

每段依次分割
需要切割线 startIndex
还需要判断回文函数

具体实现
利用分割点，判断该子字符串是否为回文，是的话，回溯函数，不是就是continue

string的子字符串取法：
s.substring(string, start, end);

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return result;
    }

    private void backTracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList(path));
            return;
        }
        for(int i = start; i < s.length(); ++i) {
            if(isPalindrome(s, start, i)) {
                path.add(s.substring(start, i+1));
                backTracking(s, i+1);
                path.remove(path.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s, int left, int right){
        while (left <= right){
            if (s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}

代码随想录解法

逻辑一致，注意回溯时s的设置问题

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return result;
        backTracking(s, 0, 0);
        return result;
    }

    private void backTracking(String s, int start, int points){
        if (points == 3){
            if (isValid(s,start,s.length()-1)) {
                result.add(s);
            }
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                points++;
                backTracking(s, i + 2, points);
                points--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            } else {
                break;
            }
        }
    }
    private boolean isValid(String s, int left, int right){
        if (left > right) return false;
        if (s.charAt(left) == '0' && left != right) return false;

        int num = 0;
        for (int i = left; i <= right; i++){
            if (s.charAt(i) > '9' || s.charAt(i) < '0') return false;
            num = num * 10 + (s.charAt(i) - '0');

            if (num > 255) return false;
        }

        return true;
    }
}

Interview150

Posted on 2024-01-20 Edited on 2024-01-26 In 复习

数组和字符串

88 合并两个有序数组

思路中，正序考虑的东西很多，可以倒序插入

因为nums1在后面的数组为空

具体思路：

设定nums1 的index 为 m-1即数组一中最大值
设定nums2 的index为n-1即数组二中最大值
设定一个总的index为了插入数字

循环开始
因为要合并到nums1中，
就要确定nums2是否全部放入nums1中
比较nums1 和nums2的值的大小，谁大谁就在最后
在放nums1值时要确定index1是否大于0


class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;

        int index = nums1.length - 1;

        while(index2 >= 0){
            if (index1 >= 0 && nums1[index1] > nums2[index2]){
                nums1[index--] = nums1[index1--];
            } else {
                nums1[index--] = nums2[index2--];
            }
        }
    }
}

27 移除元素

左右指针，不需要确定右指针是不是val，或者利用while loop确定右指针指到第一个不是val的值

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            if (nums[left] == val){
                nums[left] = nums[right--];
            } else {
                left++;
            }
        }

        return left;
    }
}

26 删除有序数组中的重复项

注意快慢指针的变化

class Solution {
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        int fastIndex = 0;

        while (fastIndex < nums.length){
            if (nums[fastIndex] != nums[slowIndex]){
                nums[++slowIndex] = nums[fastIndex];
            }
            fastIndex++;
        }

        return slowIndex + 1;
    }
}

80. 删除有序数组中的重复项 II

利用快慢指针

在快指针还没有到终点时
快指针和慢指针一起走，一起经历一个if循环，查看当前快指针，和前一个慢指针的点是否一致，一致则通过该点，此时快指针应移到不等于慢指针的前一个节点的点上

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) return nums.length;

        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length){
            nums[slowIndex++] = nums[fastIndex++];
            if (fastIndex < nums.length && nums[fastIndex] == nums[slowIndex - 1])
            nums[slowIndex++] = nums[fastIndex++];

            while (fastIndex< nums.length && nums[fastIndex] == nums[slowIndex - 1]) fastIndex++;
        }

        return slowIndex;

    }
}

169 多数元素

此题主要熟悉map的用法
利用map统计元素出现次数

利用for loop查看所有元素的次数

for(Map.Entry<Integer, Integer> entry : map.entrySet()){
}

entry.getValue()
entry.getKey();

具体代码：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > nums.length / 2) {
                return entry.getKey();
            }
        }

        return 0;
    }
}

189 旋转数组

此题和反转字符串是一个思路，
首先整体反转
之后再局部反转
如果K=3，前三个翻转，后面的翻转

唯一需要注意的是k值的转化，k值可能大于数组长度，所以需要去k%num.length的余数

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverseArray(nums, 0, nums.length - 1);
        reverseArray(nums, 0, k - 1);
        reverseArray(nums, k, nums.length - 1);
    }
    private void reverseArray(int[] nums, int start, int end){
        while (start <= end){
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

121 购入股票最好时机

此题贪心算法，累加到是负值，清空重新计算，中间记录最大值

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++){
            sum += prices[i] - prices[i - 1];
            if (sum < 0){
                sum = 0;
            } else {
                max = Math.max(max, sum);
            }
        }

        return max == Integer.MIN_VALUE ? 0 : max;
    }
}

122 购入股票的最好时机II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;

        for (int i = 1; i< prices.length; i++){
            if (prices[i] - prices[i - 1] > 0){
                sum += prices[i] - prices[i - 1];
            }
        }

        return sum;
    }
}

55 跳跃游戏

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;

        for (int i = 1; i< prices.length; i++){
            if (prices[i] - prices[i - 1] > 0){
                sum += prices[i] - prices[i - 1];
            }
        }

        return sum;
    }
}

45 跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        int count = 0;
        int maxLen = 0;
        int curLen = 0;
        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return ++count;

            if (i == curLen){
                curLen = maxLen;
                count++;
            }
        }

        return count;
    }
}

274 H-index

利用binary search，所有数值，数出每一组mid的count值，进行比较，多了，就取右边，少了就取左边，最后输出一个值

不能用位运算

class Solution {
    public int hIndex(int[] c) {
        int low=0 , high = c.length;
        while(low < high){
            int mid = (low+high+1)/2;
            int cnt=0;
            for(int i=0 ; i<c.length ; i++) if(c[i] >= mid) cnt++;
            if(cnt >= mid) low = mid;
            else high = high=mid-1;
        }
        return low;
    }
}

代码随想录第二十五天

Posted on 2024-01-19 In 代码随想录

复习

回溯结构



private void backtracking(...){
if (终止条件){
	保存结果;
	return;
}
	
for (选择： 本层集合中的元素（树中节点孩子的数量就是集合的大小）){

	处理节点
	backTracking(路径，选择列表)；//递归
	回溯,撤销处理结果
}

}

77 组合

加剪枝优化

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int start){
        if (path.size() == k){
            result.add(new ArrayList<>(path));

            return;
        }

        for (int i = start; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            backtracking(n, k , i + 1);
            path.remove(path.size() - 1);
        }
    }
}

216 组合总和III

自己写的

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }

    private void backtracking(int k, int n, int start){
	
		if (n < 0){
			return;
		}
		
        if (path.size() == k){
            if (n == 0){
                result.add(new ArrayList<>(path));
                return;
            }
        }

        for (int i = start; i <= 9 - (k - path.size()) + 1; i++){
            n -= i;
            path.add(i);
            backtracking(k, n, i + 1);
            n += i;
            path.remove(path.size() - 1);
        }
    }
}

此时剪枝操作有两个:

确定n是否为负，如果是负直接返回
确保for loop 循环之中不过度（与组合一样）

在回溯时，要n值也要回溯到之前的即加上i

17 电话号码的字母组合

自己写的

class Solution {
    StringBuilder path = new StringBuilder();
    List<String> result = new ArrayList<>();
    String[] numString = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        
        backtracking(digits, 0, 0);
        return result;
    }

    private void backtracking(String digits, int start, int n){
        if (path.length() == digits.length()){
            result.add(path.toString());
            return;
        }

        for (int i = start; i < numString[digits.charAt(n) - '0'].length(); i++){
            path.append(numString[digits.charAt(n) - '0'].charAt(i));
            backtracking(digits, start, n + 1);
            path.deleteCharAt(path.length() - 1);
        }

    }
}

此题有几个注意点

映射
要把数字和字母映射起来利用numString[]
利用StringBuilder
注意这里的start是计算digits中的值
把digits的值拿出来之后，要减掉‘0’ 这样才能是对应的int 值
注意回溯函数的引用

代码随想录第二十四天

Posted on 2024-01-18 In 代码随想录

回溯算法理论基础

回溯法也叫回溯搜索法是一种搜索方式

只要有递归就有回溯
回溯的本质是穷举，穷举所有可能，选出想要的答案，使他变高效可以剪枝

回溯可以解决的问题

组合问题：N个数里面按一定规则找出K个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合有多少符合条件的集合
排列问题：N个数按一定规则排列，有几种排列方式
棋盘问题：N皇后，解数独

组合是不强调顺序的，排列是强调顺序的

理解回溯

回溯解决的问题都可以抽象成树形结构

解决的都是在集合中递归查找子集，集合的大小就构成树的宽度，递归的深度就是树的深度

递归有终止条件，必然是一颗高度有限的树（N叉树）

回溯法模版

对应递归三部曲

回溯函数模版返回值以及参数

函数起名：backtracking
函数返回：void

参数不确定，一般是需要什么参数，再后填参数

伪代码为

1	private void backtracking(参数)

回溯函数终止条件

对应遍历树形结构需要终止条件
在回溯中，一般遍历到叶子结点，即满足条件，保存结果并返回

伪代码为

if (终止条件){
	保存结果;
	return;
}

回溯搜索的遍历过程

利用for循环进行横向遍历，利用递归进行纵向遍历

伪代码为

for (选择： 本层集合中的元素（树中节点孩子的数量就是集合的大小）){

	处理节点
	backTracking(路径，选择列表)；//递归
	回溯,撤销处理结果
}

77 组合

给定n, k，找出所有【1，n】集合中k个数的组合

利用回溯模版

首先确定result 和 path数组
利用path进行回溯

模拟回溯过程，见图

需要一个startIndex确定

以 n = 4，k = 2为例
回溯的终止条件，是path里面有两个值

利用for loop 遍历 1234，在遍历过程中嵌套一个递归函数，就会有第二个for loop，此时第二个for loop 需要从i + 1开始
所以回溯此时就是多嵌套几次for loop

具体实现

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int start){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n; i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.remove(path.size() - 1);
        }
    }
}

在此基础上进行剪枝操作，优化当前逻辑
以n = 4 k = 4举例

在1234中选择后
下一层只可能从234中选择，34,4都是可以减掉的
同理再下一层只可能从34中选择，4可以减掉

剪枝部分就是每一层中for loop 所选择的起始位置

for loop中不需要遍历到n 需要调整i遍历到哪里停止

思考逻辑：
已经选取的元素个数是path.size()
所以所需元素个数为 k - path.size()
所以此时i的最大值为 n - (k - path.size()) + 1，之后的都可以不用遍历

具体代码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);

        return result;
    }

    private void backtracking(int n, int k, int start){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - k + path.size() + 1; i++){
            path.add(i);
            backtracking(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

将回溯过程抽象成树结构进行思考