Search a 2D Matrix

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.

Solution:  binary search

Because of the matrix's special features, the matrix can be considered as a sorted array. Your goal is to find one element in this sorted array by using binary search. 

midValue 的位置： 行数是position/columns，而列数是position%columns.

Run time complexity is O(logn), constant space.

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

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.
Solution1:  这写的是神马！！！请看solution2

public class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        int i = 0, j =len - 1;
        int left = height[0], right = height[len - 1];
        int area = 0, temp = 0;
        
        while(i < j) {
            temp = Math.min(left, right) * (j - i);
            area = Math.max(temp, area);
           
            if(left < right) {
                while(i < j && height[i] <= left) {
                    i++;
                }
                if(i < j && height[i] > left)
                    left = height[i];
            }else {
                while(i < j && height[j] <= right) {
                    j--;
                }
                if(i < j && height[j] > right)
                    right = height[j];
            }
        }
        return area;
    }
}

Solution2: run time complexity is O(n), constant space. 
两个指针，从两边往中间扫。夹逼法。

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int left = 0; 
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = (right - left) * h;
            max = Math.max(max, area);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return max;
    }
}

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution: 按照上右下左的顺序放，这道题是直接给出1到n^2， 每个元素只访问一次，时间复杂度是O(n^2), space complexity is O(n^2)。

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        
        if(n == 0)
            return result;
        
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int k = 1;
        
        while(top < bottom && left < right) {
            for(int i = left; i < right; i++) {
                result[top][i] = k++;
            }
            for(int i = top; i < bottom; i++) {
                result[i][right] = k++;
            }
            for(int i = right; i > left; i--) {
                result[bottom][i] = k++;
            }
            for(int i = bottom; i > top; i--) {
                result[i][left] = k++;
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        
        if(n % 2 != 0) {    //如果是奇数行，中心点要单独加
            result[n / 2][n / 2] = k;
        }
        
        return result;
    }
}

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Solution: 基本思路是把图片分为行数/2层，然后一层层进行旋转，每一层有上下左右四个列，然后目标就是把上列放到右列，右列放到下列，下列放到左列，左列放回上列，中间保存一个临时变量即可。因为每个元素搬运的次数不会超过一次，时间复杂度是O(n^2)，空间复杂度是O(1)。

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null)
            return;
        
        int len = matrix.length;
        int layer = len / 2;
        
        for(int i = 0; i < layer; i++) {
            for(int j = i; j < len-i-1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len-1-j][i];
                matrix[len-1-j][i] = matrix[len-1-i][len-1-j];
                matrix[len-1-i][len-1-j] = matrix[j][len-1-i];
                matrix[j][len-1-i] = temp;
            }
        }
    }
}

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution: 这道题跟Unique Path系列是思路一样的。2维DP

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid == null)
            return 0;
        
        int row = grid.length;
        int col = grid[0].length;
        
        int[][] sum = new int[row][col];
        sum[0][0] = grid[0][0];
        
        //for column
        for(int i = 1; i < row; i++) {
            sum[i][0] = sum[i - 1][0] + grid[i][0];
        }
        
        //for row
        for(int i = 1; i < col; i++) {
            sum[0][i] = sum[0][i - 1] + grid[0][i];
        }
        
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                sum[i][j] = grid[i][j] + Math.min(sum[i - 1][j], sum[i][j - 1]);
            }
        }
        
        return sum[row - 1][col - 1];
    }
}

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution1: run time complexity is O(nlogn), constant space.

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        if (nums[0] != 0) {
            return 0; 
        }
        
        int i = 0;
        for (; i < nums.length - 1; i++) {
            if (nums[i + 1] - nums[i] != 1) {
                return nums[i] + 1;
            } 
        }
        
        return nums[i] + 1;
    }
}

Solution2: run time complexity is O(n), constant space.

The formula to calculate this sum:

 is  

Compute the sum of the given elements in the array. Use this sum to minus each element in the array, the difference will be the missing number.

public class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int sum = len * (len + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            sum -= nums[i];
        }
        return sum;
    }
}

Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution: 

I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;

其中每两个阶段的之间有一个减法的表示，比如900=CM， C写在M前面表示M-C。

所以有：I = 1; IV = 4; V = 5; IX = 9; X = 10; XL = 40; L = 50; XC = 90; C = 100; CD = 400; D = 500; CM = 900; M = 1000;

public class Solution {
    public String intToRoman(int num) {
        String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] integer = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < integer.length; i++) {
            while(num >= integer[i]) {
                result.append(roman[i]);
                num = num - integer[i];
            }
        }
        return result.toString();
    }
}