Merge Sorted Array leetcode

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are mand n respectively.

用倒序的方法从大到小排列，i = m+n-1 注意for循环内都是if语句 时间O(m+n)

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int j = m - 1;
        int k = n - 1;
        for (int i = m + n - 1; i >= 0; i--){
            if (k >= 0 && j >= 0){
                if (A[j] > B[k]){
                    A[i] = A[j];
                    j--;
                } else {
                    A[i] = B[k];
                    k--;
                }
            } else if (k >= 0){
                A[i] = B[k];
                k--;
            } else {// 这个else判定可以没有 因为此时i==j
                A[i] = A[j];
                j--;
            }
        }
        
    }
}

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n -1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[index] = nums1[i];
                i--;
                index--;
            } else {
                nums1[index] = nums2[j];
                j--;
                index--;
            }
        }
        while (j >= 0) {
            nums1[index] = nums2[j];
            j--;
            index--;
        }
    }
}

Remove Duplicates from Sorted Array II leetcode

Follow up for "Remove Duplicates":
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].

依旧是两个指针，并且用一个count来记录重复次数。  遍历一次 时间O(n)空间 O(1)

public class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count >= 3) {
                    continue;
                }
            } else{
                count = 1;
            }
            nums[index++] = nums[i];
        }
        return index;
    }
}

Remove Duplicates from Sorted Array leetcode

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

这道题用两个指针， 一个保留当前有效的长度 一个往后扫 因为是排序过得数组，重复元素一定是相邻的。 复杂度O(n)空集复杂度O(1).

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A == null || 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];
                index ++;
            }
        }
        A = Arrays.copyOf(A, index);
        return index;
    }
}

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

    * Integers in each row are sorted from left to right.

    * Integers in each column are sorted from up to bottom.

    * No duplicate integers in each row or column.

Example

Consider the following matrix:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

Given target = 3, return 2.

Challenge

O(m+n) time and O(1) extra space

对于2d的矩阵 可以从左下角或者右上角沿着对角线找， 

例如从左下角开始找（因为从上到下和从左到右都是递增的）， 如果大于target就网上走一格， 如果小于target就往下走一格

public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param: A number you want to search in the matrix
     * @return: An integer indicate the occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0){
            return 0;
        }
        if (matrix[0] == null || matrix[0].length == 0){
            return 0;
        }
        int row = matrix.length - 1;
        int column = matrix[0].length - 1;
        int m = row;
        int n = 0;
        int count = 0;
        while (m >= 0 && m <= row && n >= 0 && n <= column){
            int cur = matrix[m][n];
            if (cur == target){
                count++;
                m--;
            } else if (cur > target){
                m--;
            } else {
                n++;
            }
        }
        return count;
    }
}

Find Peak element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

这道题也是用二分法，如果num[mid] < num[mid+1] 说明曲线在上升趋势， peak应该在后面 所以把start指针挪到mid+1上

如果num[mid] >num[mid+1], 说明是在下降的趋势， peak在左侧 把end指针指向mid

//O(log(n))
public class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0;
  int end = nums.length - 1;
  int mid;
  while (start + 1 < end) {
   mid = start + (end - start) / 2;
   if (nums[mid] < nums[mid - 1]) {
    end = mid;
   } else if (nums[mid] < nums[mid + 1]) {
       start = mid;
   } 
   else {
    return mid;
   }
  }
  if (nums[start] > nums[end]) {
   return start;
  }
  return end;

    }
}
//O(n)
public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 && nums[i] > nums[i + 1]) {
                return i;
            }
            if (i == nums.length - 1 && nums[i - 1] < nums[i]) {
                return i;
            }
            if ( i > 0 && i < nums.length - 1 && nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return - 1;
    }
}

First Bad Version

The code base version is an integer and start from 1 to n. One day, someone commit a bad version in the code case, so it caused itself and the following versions are all failed in the unit tests.

You can determine whether a version is bad by the following interface: 

Java:    public VersionControl {        boolean isBadVersion(int version);    }
C++:    class VersionControl {    public:        bool isBadVersion(int version);    };
Python:    class VersionControl:        def isBadVersion(version)

Find the first bad version.

Note

You should call isBadVersion as few as possible. 

Please read the annotation in code area to get the correct way to call isBadVersion in different language. For example, Java is VersionControl.isBadVersion.

Example

Given n=5

Call isBadVersion(3), get false

Call isBadVersion(5), get true

Call isBadVersion(4), get true

return 4 is the first bad version

这道题看着很复杂， 其实就是最简单的binary search 

注意调用isBadVersion时候要用VersionControl.isBadVersion

/**
 * public class VersionControl {
 *     public static boolean isBadVersion(int k);
 * }
 * you can use VersionControl.isBadVersion(k) to judge wether 
 * the kth code version is bad or not.
*/
class Solution {
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        if (n < 1){
            return -1;
        }
        int start = 1;
        int end = n;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            if (VersionControl.isBadVersion(mid)){
                end = mid;
            } else {
                start = mid;
            }
        }
        if (VersionControl.isBadVersion(start)){
            return start;
        } else if (VersionControl.isBadVersion(end)){
            return end;
        } else {
            return -1;
        }
    }
}

Search a 2D Matrix leetcode

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

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

Given target = 3, return true.

先对矩阵的行数进行二分法查找， 找到target所在行数 再对此行二分法查找 来判断target时候存在。

这个的算法时间复杂度是O(log(rows)+log(columns))。
做这道题时候犯二了 在第一次二分法的时候先判断matrix[start][0] < target结果死活不对， 后来发现如果这么判定的话当matrix[end][0] < target 时候也会跳到start行。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0){
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0){
            return false;
        }
        int start = 0;
        int end = matrix.length - 1;
        int row;
        while (start + 1 < end){// find the row
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target){
                return true;
            } else if (matrix[mid][0] < target){
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        } else if (matrix[start][0] <= target) {
            row = start;
        } else {
            return false;
        }
        start = 0;
        end = matrix[0].length - 1;
        while (start + 1 < end){// find the column
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target){
                return true;
            } else if (matrix[row][mid] < target){
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[row][start] == target){
            return true;
        } else if (matrix[row][end] == target){
            return true;
        } else {
            return false;
        }
    }
}

第二种方法
把2d矩阵转换成1d 赋值start = 0 end = row * column -1
每个元素都可以用 matrix[position/column][position%column]来表示
然后用2分法解题
时间复杂度 O(log(row * column))

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0){
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0){
            return false;
        }
        int row = matrix.length;
        int column = matrix[0].length;
        int start = 0;
        int end = row * column - 1;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            int num = matrix[mid / column][mid % column];
            if (num == target){
                return true;
            } else if(num < target){
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[start / column][start % column] == target){
            return true;
        } else if (matrix[end / column][end % column] == target){
            return true;
        } else {
            return false;
        }
    }
}

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int total = m * n;
        int start = 0;
        int end = total - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid/n][mid%n] == target) {
                return true;
            }
            else if (matrix[mid/n][mid%n] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}