Leetcode - Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

[Thoughts]:我一开始没仔细看题，target 数组里面一定会有的，我一开始以为不一定会有

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] res = new int[2];
        Arrays.fill(res, -1);
        search(res, A, target, 0, A.length-1);
        return res;
    }
    
    public void search(int[] res, int[] A, int target, int start, int end){
        if(start>end) return;
        int mid = (start+end)/2;
        if(A[mid]==target){
            res[1] = mid>res[1] ? mid : res[1];
            res[0] = (mid<res[0] || res[0]==-1) ? mid : res[0];
            search(res, A, target, start, mid-1);
            search(res, A, target, mid+1, end);
        }else if(target<A[mid]){
            search(res, A, target, start, mid-1);
        }else{
            search(res, A, target, mid+1, end);
        }
        
    }
}

上面的做法，最坏情况还是线性的，此题还有循环的做法：

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] res = {-1, -1};
        int l = 0, r = A.length-1;
        while(l<r){//第一个循环找出最左端
            int mid = (l+r)/2;
            if(A[mid]<target)
                l = mid+1;
            else
                r = mid;
        }
        if(A[l]==target)
            res[0] = l;
        else 
            return res;
            
        l = 0; r = A.length-1;
        while(l<r){//第二个循环找出最右端
            int mid = (l+r)/2;
            if(A[mid]<=target)
                l = mid+1;
            else
                r = mid;
        }
        res[1] = A[l]==target ? l : l-1;
        return res;    
        
    }
}

Leetcode - Search a 2D Matrix

一个 m x n 排好序的矩阵，找一个数。
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

[Thoughts]:把matrix拉成一维，二分

public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = m==0 ? 0 : matrix[0].length;
 
        int start = 0;//Note：模拟一维数组第一个数的index
        int end = m*n-1;//Note：模拟一维数组最后一个数的index
 
        while(start<=end){
            int mid=(start+end)/2;
            int midX=mid/n;//Note: 一维转化成二维的x坐标和y坐标
            int midY=mid%n;
 
            if(matrix[midX][midY]==target) 
                return true;
 
            if(matrix[midX][midY]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
         return false;
    }
}

Leetcode - Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

[Thoughts]:

public class Solution {
    public void sortColors(int[] A) {
        int n = A.length; 
        int i = 0;     //0 pointer
        int j = n - 1; //1 pointer
        int k = n - 1; //2 pointer
        
        while(i <= j){        // i <= j, because all the elements after j are 1 and 2, both greater than 1.
            if(A[i] == 2){
                swap(A, i, k);
                k--;
                if(k < j)//若是blue在white前面了，记得同时更新white
                    j = k;
            }
            else if(A[i] == 1){
                swap(A, i, j);
                j--;
            }else
                i++;
        }
    }
    public void swap(int[] A, int a, int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
}

Leetcode - Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.
Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

public class Solution {
    public int searchInsert(int[] A, int target) {
        for(int i = 0; i < A.length; i++){
            if(A[i]>=target)
                return i;
        }
        return A.length;
    }
}

Remove Duplicates from Sorted Array I && II && Remove Element

I: Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
[Thoughts]: 多指针/滑动窗口扫描，减少循环的次数，此处两个指针是i和index，扫描的终止条件就是i==A.length

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A.length==0) return 0;
        int index = 1;
        for(int i=1; i<A.length; i++){
            if(A[i]!=A[i-1])
                A[index++] = A[i];
        }
        return index;
    }
}

II: What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A==null || A.length==0) 
            return 0;
        int len = 1;
        
        for(int i=1; i<A.length; i++){
            if(A[i]!=A[i-1])
                A[len++]=A[i];
            else{
                A[len++]=A[i];
                while(i+1<A.length && A[i+1]==A[i])
                    i++;
            }
        }
        return len;
    }
}

III: Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

public class Solution {
    public int removeElement(int[] A, int elem) {
        int index = 0;
        for(int i=0;i<A.length; i++){
            if(A[i]!=elem)
                A[index++] = A[i];
        }
        return index;
    }
}

Search in Rotated Sorted Array I && II

I: Suppose a sorted array 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.

[Thoughts]:  二分

public class Solution {//10:22
    public int search(int[] A, int target) {
        if(A==null || A.length==0) return -1;
        int l = 0, r = A.length-1;
        while(l<=r){
            int mid = (l+r)/2;
            
            if(A[mid]==target) return mid;
            
            if((A[l]<A[mid] &&(A[l]<=target && target < A[mid])) || (A[mid]<A[r] && (target<A[mid] || target>A[r])))
                r = mid-1;
            else 
                l = mid+1;
        }
        return -1;
    }
}

II: What if duplicates are allowed?
依然是二分法， 和上面思路类似，但额外处理了一点点地方：
若mid，r，l都是一样的， 那没办法，只能两遍各减一。
若只有一个半边的两头是一样的，那结果一定在另外一边。

public class Solution {
    public boolean search(int[] A, int target) {
        if(A == null || A.length == 0) return false;
        int l = 0, r = A.length-1;
        while(l<=r){
            int mid = (l+r)/2;
            
            if(A[mid]==target) return true;
            
            if(A[mid]==A[l] && A[mid]==A[r]){
                l++;
                r--;
            }else if((A[l]<A[mid] && (A[l]<=target && A[mid]>target)) || (A[mid]<A[r] &&(target<A[mid] || target>A[r])) || A[mid]==A[r])
                r = mid-1;
            else 
                l = mid+1;
        }
        return false;
    }
}

Insertion Sort List

Sort a linked list using insertion sort.

[Note]:
插入排序，就是遍历所有点，每遇到一个点i，i之前是有序的，只需要把i点插在合适的位置即可。 因为linkedlist只能顺序遍历，所以在插入点得时候分三种情况：
1，比newhead要小，那么cur就是new head。
2，比pre要大，cur保持原位置就好，pre和cur各进一步进入下一个点得处理。
3，cur在pre和newhead之间，找到cur应该要在的位置的前一个点，插入即可

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null) return head;
        ListNode newhead = head, pre = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.val >= pre.val){//Note2
                cur = cur.next;
                pre = pre.next;
            }else if(cur.val<newhead.val){//Note1
                pre.next = cur.next;
                cur.next = newhead;
                newhead = cur;
                cur = pre.next;
            }else{//Note3
                ListNode p = newhead;
                while(cur.val > p.next.val)
                    p = p.next;
                ListNode p1 = p.next;
                ListNode p2 = cur.next;
                p.next = cur;
                cur.next = p1;
                pre.next = p2;
                cur = p2;
            }
        }
        return newhead;
    }
}

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

[Note]
nlogn 的时间， 比较容易想到的是quick sort和merge sort， 对linkedlist操作，merge sort更简单。
1，把链表分成两半，用two pointer方法找到中间的点，记住下一个node，把中间点的next设置成null， list就被分成两半啦。 链表找中间点真的很容易被用到啊。

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        //Note1：LinkedList 找中间那个点。 while之后，left就是中间点
        ListNode left = head, right = head;
        while(right.next!=null && right.next.next!=null){
            left = left.next;
            right = right.next.next;
        }
        right = left.next;
        left.next = null;//right是右半部分的开始，要把左右断开。
        left = head;//重置left到head
        
        left = sortList(left);
        right = sortList(right);
        return mergeList(left, right);
        
    }
    
    public ListNode mergeList(ListNode left, ListNode right){
        ListNode dummyhead = new ListNode(-1);
        ListNode pre = dummyhead;
        //题目要求constant space，用一个dummy head记录新head，Linkedlist点不变，变得是指针
        while(left!=null && right!=null){
            if(left.val<=right.val){
                pre.next = left;
                left = left.next;
                pre = pre.next;
            }else{
                pre.next = right;
                right = right.next;
                pre = pre.next;
            }
        }
        pre.next = left==null ? right :left;
        return dummyhead.next;
    }
}