Skip to content

Latest commit

 

History

History
443 lines (429 loc) · 13.4 KB

3.18.2017(Q61-Q75).md

File metadata and controls

443 lines (429 loc) · 13.4 KB
Raw

Questions 61 ~ 75

Full score: 3 X 100 = 300
Actual score: 78 + 71 + 95 = 244

61,

Question: 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.
Idea: Count and manipulate:
/**
 * 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) {
        if(!head || !head->next) return head;
        int n = 1;
        for(auto p = head->next; p; p=p->next,++n);
        k %= n;
        if(!k) return head;
        auto p = head;
        for(int i=1;i<n-k;++i) p = p->next;
        auto p1 = p->next;
        p->next = NULL;
        p = p1;
        while(p1->next) p1=p1->next;
        p1->next = head;
        return p;
    }
};

62, Unique Paths

Question: 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?
Idea: Mathematics? dp?
Method #1: Mathematics:
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<=1 || n <=1) return 1;
        if(n>m) swap(n,m);
        int N = m+n-2, M = n-1, ans = 1, i = 2;
        for(int j=0;j<M;++j){
            ans *= (N-j);
            while(i<=M && !(ans%i)) ans /= i++;
        }
        return ans;
    }
};
Method #2: DP:
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n,1);
        for(int i=1;i<m;++i) for(int j=1;j<n;++j) dp[j] += dp[j-1];
        return dp[n-1];
    }
};

63, Unique Paths II

Question: 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.
Idea: dp
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.empty() || obstacleGrid[0].empty()) return 1;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0;
        vector<int> dp(n,1);
        bool ok = false;
        for(int j=0;j<n;++j){
            if(obstacleGrid[0][j]) ok = true;
            if(ok) dp[j] = 0;
        }
        for(int i=1;i<m;++i){
            ok = true;
            for(int j=0;j<n;++j){
                if(!j) dp[j] *= 1-obstacleGrid[i][j];
                else dp[j] = (1-obstacleGrid[i][j])*(dp[j-1] + dp[j]);
                if(dp[j]) ok = false;
            }
            if(ok) return 0;
        }
        return dp[n-1];
    }
};

64, Minimum Path Sum

Question: 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.
Idea: dp:
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n,grid[0][0]);
        for(int j=1;j<n;++j) dp[j] = dp[j-1] + grid[0][j];
        for(int i=1;i<m;++i) for(int j=0;j<n;++j){
            if(!j) dp[j] += grid[i][j];
            else dp[j] = grid[i][j] + min(dp[j],dp[j-1]);
        }
        return dp[n-1];
    }
};

65, Valid Number

Question: Validate if a given string is numeric.
Idea: state transformation:
Step 1, Creating state:
0: start
1: +
2: 9
3: .
4: .3
5: 3.
6: 3.4E
7: 3.4E-
8: 3.4E-2
9: end
Step 2, Possible transitions:
0: 0-9
1: .
2: +/-
3: e/E
4: Other
Step 3, Create Transition Table
class Solution {
    int state(char c){
        if(c>='0' && c<='9') return 0;
        if(c=='.') return 1;
        if(c=='-' || c=='+') return 2;
        if(c=='e' || c=='E') return 3;
        return 4;
    }
    int T[9][5]={{2, 3, 1, -1, -1},
                 {2, 3, -1, -1, -1},
                 {2, 5, -1, 6, 9},
                 {4, -1, -1, -1, -1},
                 {4, -1, -1, 6, 9},
                 {4, -1, -1, 6, 9},
                 {8, -1, 7, -1, -1},
                 {8, -1, -1, -1, -1},
                 {8, -1, -1, -1, 9}};
public:
    bool isNumber(string s) {
        auto i = s.find_first_not_of(" "), j = s.find_last_not_of(" ");
        if(i == string::npos) return false;
        s = s.substr(i,j-i+1);
        if(s.find_first_not_of("0123456789.eE+-") != string::npos) return false;
        int st = 0;
        for(auto c:s){
            st = T[st][state(c)];
            if(st == -1) return false;
        }
        return T[st][4]>=0;
    }
};

66, Plus One

Question: Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.
Idea: Just Do It:
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        reverse(digits.begin(),digits.end());
        int d = 1;
        for(int i=0;i<digits.size() && d;++i){
            int x = digits[i]+d;
            digits[i] = x%10;
            d = x/10;
        }
        if(d) digits.push_back(d);
        reverse(digits.begin(),digits.end());
        return digits;
    }
};

67, Add Binary

Question: Given two binary strings, return their sum (also a binary string).
Idea: Just Do It:
class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        string ans;
        int i = 0, j = 0, n = a.size(), m = b.size(), d = 0;
        while(i<n || j<m || d){
            int x = (i<n && a[i++]=='1') + (j<m && b[j++]=='1') +d;
            ans += x%2?'1':'0';
            d = x/2;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

68, Text Justification

Question: Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words. For example, words: ["This", "is", "an", "example", "of", "text", "justification."] and L: 16.
Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.
Idea: Be Careful:
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        for(int i=1, L=words[0].size(), b=0;i<=words.size();++i){
            if(i<words.size() && L+words[i].size()<maxWidth) L += words[i].size()+1;
            else if(i<words.size()){
                int n = i - b - 1, m = maxWidth-L;
                string tmp = words[b];
                if(!n) tmp += string(m,' ');
                else{
                    for(int j=1;j<=m%n;++j) tmp += string(m/n+2,' ') + words[b+j];
                    for(int j=m%n+1;j<=n;++j) tmp += string(m/n+1,' ') + words[b+j];
                }
                ans.push_back(tmp);
                b = i;
                L = words[i].size();
            }
            else{
                string tmp = words[b];
                for(int j = b+1;j<words.size();++j) tmp += ' '+words[j];
                tmp += string(maxWidth-tmp.size(),' ');
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};

69, Sqrt(x)

Question: Implement int sqrt(int x).
Idea: Bisection Search:
class Solution {
public:
    int mySqrt(int x) {
        if(x<=1) return x;
        long xx = x, l = 0, r = x;
        while(l<r-1){
            long c = (l+r)/2;
            if(c*c<=xx) l = c;
            else r = c;
        }
        return (int)l;
    }
};

70, Climbing Stairs

Question: 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?
Idea: Fibonacci
class Solution {
public:
    int climbStairs(int n) {
        if(n<=1) return 1;
        int v = 1, v0 = 1;
        for(int i=1;i<n;++i){
            v += v0;
            v0 = v - v0;
        }
        return v;
    }
};

71, Simplify Path

Question: Given an absolute path for a file (Unix-style), simplify it. For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Idea: Using stack
class Solution {
public:
    string simplifyPath(string path) {
        auto i = path.find_first_not_of("/");
        if(i == string::npos) return "/";
        stack<string> P,R;
        while(i!=string::npos){
            auto j = path.find_first_of("/",i);
            if(j == string::npos) j = path.size();
            string tmp = path.substr(i,j-i);
            i = path.find_first_not_of("/",j);
            if(tmp == ".") continue;
            else if(tmp == ".."){
                if(!P.empty()) P.pop();
            }
            else P.push(tmp);
        }
        if(P.empty()) return "/";
        while(!P.empty()){
            R.push(P.top());
            P.pop();
        }
        string ans;
        while(!R.empty()){
            ans += '/' + R.top();
            R.pop();
        }
        return ans;
    }
};

72, Edit Distance

Question: Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Idea: DP: (这种题其实都是可以只用一维dp的，因为都是逐级递归)
typedef vector<int> vi;
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        if(!n1) return n2;
        if(!n2) return n1;
        vector<vi> dp(n1+1,vi(n2+1,0));
        for(int j=0;j<n2;++j) dp[n1][j] = n2-j;
        for(int i=0;i<n1;++i) dp[i][n2] = n1-i;
        for(int i=n1-1;i>=0;i--) for(int j=n2-1;j>=0;j--){
            dp[i][j] = min(1 + min(dp[i][j+1],dp[i+1][j]),(word1[i]!=word2[j])+dp[i+1][j+1]);
        }
        return dp[0][0];
    }
};

73, Set Matrix Zeroes:

Question: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Idea: In place: using the first row to record
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size(), ok = 1, ok1 = 1;
        for(int j=0;j<n&&ok;++j) if(!matrix[0][j]) ok = 0;
        for(int i=1;i<m;++i,ok1 = 1){
            for(int j=0;j<n;++j) if(!matrix[i][j]) ok1 = matrix[0][j] = 0;
            if(!ok1) matrix[i].assign(n,0);
        }
        for(int j=0;j<n;++j) if(!matrix[0][j]) for(int i=1;i<m;++i) matrix[i][j] = 0;
        if(!ok) matrix[0].assign(n,0);
    }
};

74, Search a 2D Matrix

Question: 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.
Idea: Binary Search:
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        if(target > matrix[m-1][n-1] || target < matrix[0][0]) return false;
        int l=-1,r=m*n;
        while(l<r-1){
            int c = (l+r)/2;
            if(matrix[c/n][c%n]>target) r = c;
            else l = c;
        }
        return matrix[l/n][l%n]==target;
    }
};

75, Sort Colors

Question: Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. (One Pass)
Idea: Appropriately use swap;
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0, m = 0, r = nums.size()-1;
        while(r>=0 && nums[r]==2) --r;
        while(m<=r){
            if(nums[m] == 1){
                ++m;
            }
            else if(nums[m] == 2){
                swap(nums[m],nums[r]);
                while(r>=0 && nums[r]==2) --r;
            }
            else{
                swap(nums[m],nums[l]);
                ++m;
                ++l;
            }
        }
    }
};