[LeetCode] 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Subscribe to see which companies asked this question

public class Solution {
    public int climbStairs(int n) {
        // 1d dp
        
        if(0 == n)
            return 0;
        if(1 == n)
            return 1;
        
        int[] dp = new int[3];
        
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; ++i){
            dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
        }
        
        return dp[n%3];
    }
}

[LeetCode] 64. 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.

Subscribe to see which companies asked this question

public class Solution {
    public int minPathSum(int[][] grid) {
        
        int m = grid.length;
        if(0 == m)
            return 0;
        int n = grid[0].length;
        if(0 == n)
            return 0;
            
        int dp[] = new int[m];
        
        dp[0] = grid[0][0];
        for(int i = 1; i < m; ++i){
            dp[i] = dp[i-1] + grid[i][0];
        }
        
        for(int j = 1; j < n; ++j){
            for(int i = 0; i < m; ++i){
                if(0 == i){
                    dp[i] += grid[0][j];
                }
                else{
                    dp[i] = Math.min(dp[i-1], dp[i])+grid[i][j];
                }
            }
        }
        
        return dp[m-1];
        
    }
}

[LeetCode] 63. Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        
        if(0 == m)
            return 0;
            
        int n = obstacleGrid[0].length;
        
        if(0 == n)
            return 0;
            
        int[] dp = new int[m];
        
        if( 1 == obstacleGrid[0][0])
            return 0;
        
        dp[0] = 1;
        
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(1 == obstacleGrid[j][i]){
                    dp[j] = 0;
                }else{
                    if(0 == j){
                        dp[j] = dp[j];
                    }else{
                        dp[j] += dp[j-1];
                    }
                }
            }
        }
        
        return dp[m-1];
    }
}

[LeetCode] 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

public class Solution {
    public int uniquePaths(int m, int n) {
        if(0 == m || 0 == n)
            return 0;
            
        int[] dp = new int[m];
        
        for(int i = 0; i < m; ++i){
            dp[i] = 1;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 1; j < m; ++j){
                dp[j] += dp[j-1];
            }
        }
        
        return dp[m-1];
    }
}

[LeetCode] 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
    
        if(null == head)
            return null;
        
        if(0 == k)
            return head;
        
        int len = 1;
        
        ListNode tail = head;
        while(null != tail.next){
            tail = tail.next;
            ++len;
        }
        
        tail.next = head;
        
        ListNode c = tail;
        
        k %= len;
        k = len - k;
        
        while(k-- > 0){
            c = c.next;
        }
        
       ListNode ret = c.next;
        c.next = null;
        
        return ret;
        
    }
}

[LeetCode] 60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

public class Solution {
    public String getPermutation(int n, int k) {
        
        String ret = new String();
        
        if(0 == n)
            return ret;
            
        StringBuilder sb = new StringBuilder();
            
        ArrayList eArr = new ArrayList();
        
        for(int i = 1; i < n+1; ++i){
            eArr.add(i);
        }
        
        int[] pArr = new int[n+1];
        
        pArr[1] = 1;
        
        for(int i = 2; i < n+1; ++i){
            pArr[i] = pArr[i-1]*i;
        }
        
        // Error: i>=0. pArr[0] stored 0. division by 0 error.
        for(int i = n - 1 ; i>=1; --i){
            int pos = (k - 1) / pArr[i];
            sb.append(eArr.get(pos));
            eArr.remove(pos);
            k -= (pos) * pArr[i];
        }
        
        sb.append(eArr.get(0));
        
        return sb.toString();
        
    }
}

[LeetCode] 59. 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 ]
]

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        
        int i = 0;
        int j = 0;
        
        int c = 1;
        
        while(n > 1){
            for(int k = 0; k < n-1; ++k){
                ret[i][j++] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i++][j] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i][j--] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i--][j] = c++;
            }
            i++;
            j++;
            n -= 2;
        }
        
        if(1 == n){
            ret[i][j] = c;
        }
        
        return ret;
        
    }
}