leetcode刷题

categories: leetcode

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

code

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }
    public void backtrack(List<String>ans, String cur, int open, int close, int max) {
        if(cur.length() == max * 2) {
            ans.add(cur);
            return;
        }
        if(open < max) {
            backtrack(ans, cur+"(", open+1, close, max);
        }
        if(close < open) {
            backtrack(ans, cur+")", open, close+1, max);
        }
    }
}

summary

通过以(开头，可以递归遍历所有括号匹配情况。左括号不可能在大于n的下标，右括号要与左括号匹配。每次只可能添加( or )，所以两个if条件足够，当不满足条件则向上回溯。回溯（也就是递归）的边界条件是 open < max 和close < open。

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Comparator<ListNode> cmp;
        cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        };
        Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
        for(ListNode l : lists) {
            if(l != null) {
                q.add(l);
            }
        }
        ListNode head = new ListNode(0);
        ListNode point = head;
        while(!q.isEmpty()) {
            point.next = q.poll();
            point = point.next;
            ListNode next = point.next;
            if(next != null) {
                q.add(next);
            }
        }
       return head.next;
    }
}

summary

用优先队列，还是要熟悉优先队列，两两合并的方法比较坑，[[2],[],[-1]] 这样的情况还需要多进行一层判断。参考 https://leetcode.wang/leetCode-23-Merge-k-Sorted-Lists.html

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

code

class Solution {
    public void nextPermutation(int[] nums) {
          int i = nums.length - 2;
        while (i >= 0 && nums[i+1] <= nums[i]) {//少了等号会发生越界
            i--;
        }
        if( i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
    }
        reverse(nums, i + 1);
    }
    private void reverse(int [] nums, int start) {//不需要调用系统，必然有序，所以两两对调 
        int i = start, j = nums.length - 1;
        while(i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    private void swap(int[] nums, int i, int j) {
       int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

summary

官网总结的很精致，可以参考普通思路一点点来。无论数字怎么排列，找 next permutation 分成三步，1)从右往左找到第一个非递增的数字，2)将非递增的数字左边第一个数字与其右侧，从右往左第一个大于他的数字对调，3)将非递增数字右侧数字进行升序排序。这种计算机思考方式真的奇怪，它是对的，但你总感觉别扭，想去验证。只能说，计算机思维和从小养成的按部就班、投机取巧的数学思维习惯很不同吧。计算机思维讲究有逻辑的高度正确、简洁，我应试教育的数学思维还是习惯提心吊胆地推演。。。。可能一直学的都不是正确的方法？还是说要自己认识到并改正，这好像也让我感受到庸人和天才的云泥之别。

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: “)()())“
Output: 4
Explanation: The longest valid parentheses substring is "()()"

code

//栈索引法
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i =0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else{
                stack.pop();
                if(stack.empty()) {
                    stack.push(i);//确保边界情况时，i - stack.peek()为0
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}
//Without extra space
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLength = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if(left == right) {
                maxLength = Math.max(maxLength, 2 * right);
            } else if(right > left){
                left = right = 0;
            }
        }
        left = right = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if(left == right) {
                maxLength = Math.max(maxLength, 2 * right);
            } else if(right < left){
                left = right = 0;
            }
        }
        return maxLength;
    }
}
//Using Dynamic Programming
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int dp[] = new int[s.length()];
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == ')') {
                if(s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) +2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

summary

栈可以避免一种括号多的情况。Without extra space 必须两侧都遍历，因为只一侧可能出现永远不相等的情况。前面感觉在划水，尤其是 Without extra space 方法。动态规划才是硬解法，不过是真的好难……..This problem can be solved by using Dynamic Programming.（手动狗头）

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

code

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, mid = 0, right = nums.length - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] < nums[right]) {
                if(nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else right = mid -1;
            }
            else {
                if(nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
}

summary

虽然有旋转，但是和旋转点没任何关系。旋转是为了打乱顺序，然后从中找到需要的点。所以二分法是很容易想到的。因为边界值可能出现想要的结果，所以要做等于的判断。可以参考我的参考。

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

code

//我的
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] a = {-1, -1};
        int left = 0, mid = 0, right = nums.length - 1;
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                a = sorted(mid, a, nums,left, right);
                return a;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return a;
    }
    private int[] sorted(int mid, int[] a, int[] nums, int left, int right) {
        for(int i = left; i <= right; i++) {
            if(nums[i] == nums[mid]) {
                a[0] = i;
                break;
            }
        }
        for(int j = right; j >= a[0]; j--) {
            if(nums[j] == nums[mid]) {
                a[1] = j;
                break;
            }
        }
        return a;
    }
}
//官网
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};
        int leftIdx = extremeInsertionIndex(nums, target, true);
        if(leftIdx == nums.length || nums[leftIdx] != target) {
            return targetRange;
        }
        targetRange[0] = leftIdx;
        targetRange[1] = extremeInsertionIndex(nums, target, false) - 1;
        return targetRange;
    }
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if(nums[mid] > target || (left && target == nums[mid])) {
                hi = mid;//缩短右端距离,防止出现最左侧无效的情况
            }
            else {
                lo = mid + 1;//缩短左端距离
            }
        }
        return lo;
    }
}

summary

先用二分查找，再用遍历，数学不好，不知道我那个复杂度是多少，应该离 O(logn) 不远，当距离缩短，遍历可能更快速。官网的巧妙在用boolean来控制，显而易见，其复杂度是 O(logn) 。

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [2,3,6,7],target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5],target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

code

//recursive
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        getResult(result, new ArrayList<Integer>(), candidates, target, 0);
        return result;
    }
    private void getResult(List<List<Integer>> result, List<Integer> cur, int[] candidates, int target, int start) {
        if(target > 0) {
            for(int i = start; i < candidates.length && target >= candidates[i]; i++) {
                cur.add(candidates[i]);
                getResult(result, cur, candidates, target - candidates[i], i);
                cur.remove(cur.size() - 1);//排除错误情况，移除后推进
            }
        }
        else if(target == 0) {
            result.add(new ArrayList<Integer>(cur));//确保有正确则立即保存
        }
    }
}
//DP solution
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // sort candidates to try them in asc order
        Arrays.sort(candidates); 
        // dp[t] stores all combinations that add up to t
        List<List<Integer>>[] dp = new ArrayList[target+1];
        // build up dp
        for(int t=0; t<=target; t++) {
            // initialize
            dp[t] = new ArrayList();
            // initialize
            List<List<Integer>> combList = new ArrayList();
            // for each t, find possible combinations
            for(int j=0; j<candidates.length && candidates[j] <= t; j++) {
                if(candidates[j] == t) {
                    combList.add(Arrays.asList(candidates[j])); // itself can form a list
                } else {
                    for(List<Integer> prevlist: dp[t-candidates[j]]) { // here use our dp definition
                        // i thought it makes more sense to compare with the last element
                        // only add to list when the candidates[j] >= the last element
                        // so the list remains ascending order, can prevent duplicate (ex. has [2 3 3], no [3 2 3])
                        // equal is needed since we can choose the same element many times   
                        if(candidates[j] >= prevlist.get(prevlist.size()-1)){
                            List temp = new ArrayList(prevlist); // temp is needed since 
                            temp.add(candidates[j]); // cannot edit prevlist inside 4eeach looop
                            combList.add(temp);
                        }
                    }
                }
            }
            dp[t] = combList;
        }
        return dp[target];
    }

summary

从 Discuss 里面找了递归和动规两个解法，递归里面，List>[]是指数组的链表的链表，即三层