2016-07-18-动态规划&贪心&模拟

[wolfogre]

64. Minimum Path Sum 55. Jump Game 59. Spiral Matrix II

[wolfogre]

递归效率忒低……

//64. Minimum Path Sum
class Solution {
#define MAX_INPUT_SIZE 1000
public:
    int minPathSum(vector<vector<int>>& grid) {
        for(int i = 0; i < grid.size(); ++i)
            for(int j = 0; j < grid.back().size(); ++j)
                record[i][j] = -1;
        return minPathSumFrom(0, 0, grid);
    }
private:
    int record[MAX_INPUT_SIZE][MAX_INPUT_SIZE];
    int minPathSumFrom(int x, int y, const vector<vector<int>>& grid){
        if(record[x][y] != -1)
            return record[x][y];

        if(x == grid.size() - 1 && y == grid.back().size() - 1)
            return grid[x][y];
        int min = INT32_MAX;
        if(x < grid.size() - 1)
            min = minPathSumFrom(x + 1, y, grid);
        if(y < grid.back().size() - 1){
            int temp = minPathSumFrom(x, y + 1, grid);
            if(temp < min)
                min = temp;
        }
        record[x][y] = min + grid[x][y];
        return record[x][y];
    }
};

[dayang]

/**
 * [AC] LeetCode 64 Minimum Path Sum
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    var m = grid.length,n = grid[0].length;
    for(var i = 0; i < m; i++){
        for(var j = 0; j < n; j++){
            if(j === 0 && i > 0){
                grid[i][j] = grid[i-1][j] + grid[i][j];
            }else if(j > 0 && i === 0){
                grid[i][j] = grid[i][j-1] + grid[i][j];
            }else if(j > 0 && i > 0){
                grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
            }
        }
    }
    return grid[m-1][n-1];
};

[wolfogre]

//55. Jump Game
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    var max = 0;
    for(var i = 0; i < nums.length && i <= max; ++i){
        if(i + nums[i] > max)
            max = i + nums[i];
        if(max >= nums.length - 1)
            return true;
    }
    return false;
};

[wolfogre]

// 59. Spiral Matrix II
/**
 * @param {number} n
 * @return {number[][]}
 */

var generateMatrix = function(n) {

    var result = new Array(n);
    for(var i = 0; i < n; ++i)
        result[i] = new Array(n);

    for(var i = 0; i < n; ++i)
        for(var j= 0; j < n; ++j)
            result[i][j] = 0;

    var value = 1;
    var direction = "right";
    var x = 0, y = 0;

    while(value <= n * n){
        if(result[x][y] === 0)
            result[x][y] = value++;
        switch(direction){
        case "up":
            if(x - 1 < 0 || result[x - 1][y] !== 0)
                direction = "right";
            else
                --x;
            break;
        case "down":
            if(x + 1 >= n || result[x + 1][y] !== 0)
                direction = "left";
            else
                ++x;
            break;
        case "left":
            if(y - 1 < 0 || result[x][y - 1] !== 0)
                direction = "up";
            else
                --y;
            break;
        case "right":
            if(y + 1 >= n || result[x][y + 1] !== 0)
                direction = "down";
            else
                ++y;
            break;
        }
    }
    return result;
};

[zhaokuohaha]

LeetCode-64-C

public class Solution {
    public int MinPathSum(int[,] grid) {
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);
        for(int i = 0; i < m; i++){
            for(int j=0; j < n; j++){
                if(i==0&&j==0) continue;
                else if(j==0){
                    grid[i,j] += grid[i-1,j];
                }
                else if(i == 0){
                    grid[i,j] += grid[i,j-1];
                }
                else{
                    grid[i,j] += Math.Min(grid[i,j-1],grid[i-1,j]);
                }
            }
        }
        return grid[m-1,n-1];
    }
}

[SnackMen]

/*
[AC] LeetCode 64 Minimum Path Sum
*/
public class Solution {  
    public int minPathSum(int[][] grid) {  
       int len1=grid.length;
       int len2=grid[0].length;
       int min=0;
       for(int i=len1-1;i>=0;i--){
           for(int j=len2-1;j>=0;j--){
               int belowValue=Integer.MAX_VALUE;
               int rightValue=Integer.MAX_VALUE;
               if(i<len1-1)
                    belowValue=grid[i+1][j];
                if(j<len2-1)
                    rightValue=grid[i][j+1];
                min=Math.min(belowValue,rightValue);
                if(min!=Integer.MAX_VALUE)
                    grid[i][j]+=min;
           }
        } 
        return grid[0][0];
    }
} 

[zhaokuohaha]

LeetCodt-55-C

public class Solution {
    public bool CanJump(int[] nums) {
        if(nums.Length <= 1)return true;
        int max = nums[0];
        for(int i=0; i<nums.Length; i++){
            max = Math.Max(max, i+nums[i]);
            if(nums[i]==0 && max == i)
                return false;
            if(max >= nums.Length-1)
                return true;
        }
        return false;
    }
}

[zhaokuohaha]

LeetCode-59-C

public class Solution {
    public int[,] GenerateMatrix(int n) {
        int[,] res = new int[n,n];
        if(n==0) return res;
        int x=0,y=1;
        int i=0,j=0;
        res[0,0] = 1;
        for(int count=1; count<n*n; count++){
            if(i+x >= n || j+y >= n || i+x < 0 || y+j < 0 || res[i+x,j+y] != 0){
                if(x == 0){
                    x =  y　== 1 ? 1 : -1;//如果之前向右, 则向下, 反之向上
                    y = 0;
                }
                else{
                    y = x == 1 ? -1 : 1;//如果之前向下, 则向左, 反之向右
                    x = 0;
                }
            }
            i+=x;
            j+=y;
            res[i,j] = count+1;
        }
        return res;
    }
}

[dayang]

/**
 * [AC] LeetCode 55 Jump Game
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length === 1)
        return true;
    var maxpos = nums.length - 1;
    var max = nums[0];
    for(var i = 1; i<= maxpos; i++){
        if(i > max)
            return false
        if(max >= maxpos)
            return true;
        if(max < i + nums[i])
            max = i + nums[i];
    }
};

[SnackMen]

/*
[AC] LeetCode 55 Jump Game
*/
public class Solution {
 public boolean canJump(int[] nums) {
        int max=nums[0];
        for(int i=0;i<nums.length&&i<=max;i++){
            int num=nums[i]+i;
            if(max<num)
                max=num;
            if(max>=nums.length-1)
                return true;
        }
        return false;
    }
}

[SnackMen]

/*
[AC]59. Spiral Matrix II
*/
public class Solution {  
    public int[][] generateMatrix(int n) {  
        int nums[][] = new int[n][n];
        int k=1;
        int i=0;
        int j=0;
        int leftToBelow=0;
        int rightToUp=n;
        int max=n*n;
        while(k<=max){
            while(k<=max && j<rightToUp){
                nums[i][j++]=k++;
            }
            j--;
            i++;
            while (k<=max && i<rightToUp){
                nums[i++][j]=k++;
            }
            i--;
            j--;
            while (k<=max && j>=leftToBelow){
                nums[i][j--]=k++;
            }
            j++;
            i--;
            while (k<=max&&i>leftToBelow){
                nums[i--][j]=k++;
            }
            i++;
            j++;
            rightToUp--;
            leftToBelow++;
        }
        return nums;
    }
}  

[dayang]

/**
 * [AC]  LeetCode 59 Spiral Matrix II
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    var ans = [];
    var temp;
    for(var i = 0; i < n; i++){
        temp = [];
        for(var j = 0; j < n; j++){
            temp.push(0);
        }
        ans.push(temp);
    }

    var cur = 1;
    i = 0; j = 0;
    while(cur <= n*n){
        while(j < n && ans[i][j] === 0) ans[i][j++] = cur++; j--;i++;
        while(i < n && ans[i][j] === 0) ans[i++][j] = cur++; i--;j--;
        while(j >=0 && ans[i][j] === 0) ans[i][j--] = cur++; j++;i--;
        while(i >= 0 && ans[i][j] === 0) ans[i--][j] = cur++; i++;j++;
    }

    return ans;
};