LeetCode(90) -- 81,

P81. Search in Rotated Sorted Array II (Medium)

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

The Best Solution

int first = 0, last = nums.length - 1;
        
        while(first <= last){
            int mid = (first + last)/2;
            
            if(nums[mid] == target)
                return true;
            else if(nums[first] == nums[last]){
                if(nums[first] == target || nums[last] == target)
                    return true;
                first++;
                last--;
            }
            else if(nums[mid] >= nums[first]){
                if(target < nums[mid] && target >= nums[first])
                    last = mid - 1;
                else
                    first = mid + 1;
            }
            else{
                if(target > nums[mid] && target <= nums[last])
                    first = mid + 1;
                else
                    last = mid -1;
            }
        }
        return false;

这个题是难点是，第一个数和最后一个数有可能是一样的，这样就没办法判断到底在左边还是右边。但如果通过检验，把边上不是的都扔掉，就跟非重复的那道题完全一样了。

P86. Partition List (Medium)

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

My Solution

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode less = new ListNode(0);
        ListNode greater = new ListNode(0);
        if (head == null) {
            return null;
        }
        ListNode lessCurr = less;
        ListNode greaterCurr = greater;
        while (head != null) {
            if (head.val < x) {
                lessCurr.next = head;
                lessCurr = lessCurr.next;
            } else {
                greaterCurr.next = head;
                greaterCurr = greaterCurr.next;
            }
            head = head.next;
        }
        greaterCurr.next = null;
        lessCurr.next = greater.next;
        return less.next;
    }
}

100%

P90. Subsets II (Medium)

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

My Solution

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums, new ArrayList<>(), 0);
        return ans;
    }

    private void backtrack(int[] nums, List<Integer> tempList, int start) {
        ans.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            if(i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            tempList.add(nums[i]);
            backtrack(nums, tempList, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

98%