Day 34, 59, 61,63 Spiral Matrix II, Rotate List, Unique Paths II

Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n² 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 straightforward, follow spiral's track, O(n)

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret(n);
        if (n == 0) return ret;
        if (n == 1) {
            vector<int> v(1);
            v[0] = 1;
            ret[0] = v;
            return ret;
        }
        for (int i=0;i<n;i++) {
            vector<int> row(n);
            for (int j=0;j<n;j++) {
                row[j] = 0;
            }
            ret[i] = row;
        }
        int row=0,col=0,index=1;  
        while (ret[row][col] == 0) {
            // right
            while (col < n && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                col++;
            }
            col--;
            row++;
            // down
            while (row < n && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                row++;
            }
            row--;
            col--;
            // left
            while (col >= 0 && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                col--;
            }
            col++;
            row--;
            // up
            while (row >= 0 && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                row--;
            }
            row++;
            col++;
        }
        return ret;
    }
};

Update on Sep-13-2014
Solution #2
Go google it


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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || k == 0) return head;
        ListNode *cur=head, *end=head;
        int count=1;
        while (end->next != NULL) {
            count++;
            end = end->next;
        }
        k = k % count;
        if (k == 0) return head;
        for (int i=0;i<count-k-1;i++) {
            cur = cur->next;
        }
        ListNode *ret = cur->next;
        end->next = head;
        cur->next = NULL;
        return ret;
    }
};

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.
-----------------------------------
DP, based on unique path I

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int matrix[101][101] = {0};
        int m = obstacleGrid.size() - 1;
        int n = obstacleGrid[0].size() - 1;
        matrix[m+1][n] = 1;
        for (int i=m;i>=0;i--) {
            for (int j=n;j>=0;j--) {
                if (obstacleGrid[i][j] == 0) {
                    matrix[i][j] = matrix[i+1][j] + matrix[i][j+1];
                }
            }
        }
        return matrix[0][0];
    }
};

Update on Sep-14-2014
Consider the case when matrix[m + 1][n] or matrix[m][n + 1] has an obstacle

O(n) space

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n + 1,0);
        if (obstacleGrid[m - 1][n - 1] == 1) return 0;
        dp[n - 1] = 1;
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                }else {
                    dp[j] += dp[j + 1];
                }
            }
        }
        return dp[0];
    }
};