Skip to content

Latest commit

 

History

History
411 lines (395 loc) · 13.2 KB

3.16.2017(Q31-Q45).md

File metadata and controls

411 lines (395 loc) · 13.2 KB
Raw

Questions 31 ~ 45

31, Next Permutation

Question: Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory.
Idea: Back tracking:
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return;
        int j = n-1, k = n-1;
        while(j && nums[j-1]>=nums[j]) --j;
        if(j){
              while(nums[k] <= nums[j-1]) --k;
              swap(nums[k],nums[j-1]);
        }
        reverse(nums.begin()+j,nums.end());
    }
};

32, Longest Valid Parentheses

Question: Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2.
Idea: Using dp and for every step, there are several possibilities: dp[i] is the longest length of valid paranthese that ends at i:
1, s[i] == '(' then dp[i] = 0;
2, s[i] == ')' then the configuration should be (....)(...), and we try to find where the intermediate '(' and ')' are and dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if(n<=1) return 0;
        vector<int> dp(n,0);
        dp[1] = s[0]=='(' && s[1]==')'? 2:0;
        int mL = dp[1];
        for(int i=2;i<n;++i){
            if(s[i]=='(') continue;
            if(s[i-1]=='(') dp[i] = dp[i-2] + 2;
            else {
                if(!(i-dp[i-1])) dp[i] = 0;
                else if(s[i-dp[i-1]-1]=='('){
                    dp[i] = dp[i-1]+2;
                    if(i-dp[i-1]-2>=0) dp[i] += dp[i-dp[i-1]-2];
                }
            }
            mL = max(mL,dp[i]);
        }
        return mL;
    }
};

33, Search in Rotated Sorted Array

Question: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.
Idea: find the pivat first, and then find the value. Both steps use binary search.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int n = nums.size();
        int p = 0;
        if(nums[0]>nums[n-1]){
            int l = 0;
            p = n-1;
            while(l<p-1){
                int c = (l+p)/2;
                if(nums[c]>nums[0]) l = c;
                else p = c;
            }
        }
        if(target < nums[p]) return -1;
        int l = 0, r = n;
        while(l<r-1){
            int c = (l+r)/2;
            if(nums[(p+c)%n] > target) r = c;
            else l = c;
        }
        return nums[(l+p)%n]==target? (l+p)%n:-1;
    }
};

34, Search for a Range

Question: Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
Idea: Simple binary search
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty() || nums[nums.size()-1]<target) return vector<int>{-1,-1};
        int i = -1, l = nums.size()-1;
        while(i<l-1){
            int c = (i+l)/2;
            if(nums[c]<target) i = c;
            else l = c;
        }
        if(nums[l] != target) return vector<int>{-1,-1};
        int r = l;
        i = nums.size();
        while(r<i-1){
            int c = (i+r)/2;
            if(nums[c]==target) r = c;
            else i = c;
        }
        return vector<int>{l,r};
    }
};

35, Search Insert Position

Question: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.
Idea: Simple binary search.
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty() || nums[nums.size()-1]<target) return nums.size();
        int l = -1, r = nums.size()-1;
        while(l<r-1){
            int c = (l+r)/2;
            if(nums[c]<target) l = c;
            else r = c;
        }
        return r;
    }
};

36, Valid Sudoku

Question: Determine if a Sudoku is valid
Idea: carefully check all the conditions:
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<int>> cnt(27,vector<int>(9,0));
        for(int i=0;i<9;++i) for(int j=0;j<9;++j) if(board[i][j]!='.'){
            int k = (int)board[i][j] - (int)'1';
            cnt[i][k]++;
            if(cnt[i][k]>1) return false;
            cnt[9+j][k]++;
            if(cnt[9+j][k]>1) return false;
            cnt[18+(i/3)*3+(j/3)][k]++;
            if(cnt[18+(i/3)*3+(j/3)][k]>1) return false;
        }
        return true;
    }
};

37, Sudoku Solver

Question: Write a program to solve a Sudoku puzzle by filling the empty cells.
Idea: using dfs
typedef vector<int> vi;
typedef pair<int,int> ii;
class Solution {
    vector<ii> vacancy;
    int nv;
    vector<vi> cnt;
    bool validPath(vector<vector<char>>& board, int k){
        if(k==nv) return true;
        int i = vacancy[k].first, j = vacancy[k].second;
        for(int m=0;m<9;++m) if(cnt[i][m]==0 && cnt[9+j][m]==0 && cnt[18+(i/3)*3+j/3][m]==0){
            cnt[i][m]++;
            cnt[9+j][m]++;
            cnt[18+(i/3)*3+j/3][m]++;
            board[i][j] = (char)(m+(int)'1');
            if(validPath(board,k+1)) return true;
            cnt[i][m]--;
            cnt[9+j][m]--;
            cnt[18+(i/3)*3+j/3][m]--;
            board[i][j] = '.';
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        cnt = vector<vi>(27,vi(9,0));
        for(int i=0;i<9;++i) for(int j=0;j<9;++j){
            if(board[i][j] == '.') vacancy.push_back(ii(i,j));
            else{
                int m = (int)board[i][j] - (int)'1';
                cnt[i][m]++;
                cnt[9+j][m]++;
                cnt[18+(i/3)*3+j/3][m]++;
            }
        }
        nv = vacancy.size();
        validPath(board,0);
    }
};

38, Count and Say

Question: The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Idea: Easy recursive
class Solution {
public:
    string countAndSay(int n) {
        if(n==1) return "1";
        string str = countAndSay(n-1), ans;
        for(int i=0,cnt=1;i<str.size();++i){
            if(i<str.size()-1 && str[i]==str[i+1]) cnt++;
            else {
                ans += to_string(cnt) + str[i];
                cnt =1;   ///好粗心
            }
        }
        return ans;
    }
};

39, Combination Sum

Question: Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Idea: simple dfs
typedef vector<int> vi;
class Solution {
    void dfs(vector<vi> &ans,vi cur,vi &A,int k,int tar){
        if(!tar){
            ans.push_back(cur);
            return;
        }
        if(k==A.size()) return;
        for(int i=0;i<=tar/A[k];++i){
            dfs(ans,cur,A,k+1,tar-i*A[k]); //Stop making stupid mistakes plz
            cur.push_back(A[k]);
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vi> ans;
        dfs(ans,vi(),candidates,0,target);
        return ans;
    }
};

40, Combination Sum II

Question: Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination.
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Idea: Still using simple dfs:
typedef vector<int> vi;
class Solution {
    void dfs(vector<vi> &ans,vi cur, vi &A,int k,int tar){
        if(!tar){
            ans.push_back(cur);
            return;
        }
        for(int j=k;j<A.size() && A[j]<=tar;++j) if(j==k || A[j]!=A[j-1]){
            cur.push_back(A[j]);
            dfs(ans,cur,A,j+1,tar-A[j]);
            cur.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vi> ans;
        dfs(ans,vi(),candidates,0,target);
        return ans;
    }
};

41, First Missing Positive

Question: Given an unsorted integer array, find the first missing positive integer. For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Idea: transform
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;){
            if(nums[i]<=0 || nums[i]>n || nums[i]==i+1 || nums[nums[i]-1]==nums[i]) ++i;
            else swap(nums[nums[i]-1],nums[i]);
        }
        for(int i=0;i<n;++i) if(nums[i]!=i+1) return i+1;
        return n+1;
    }
};

42, Trapping Rain Water

Question: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Idea: Bury approach: (We can also use the maximum until i to determine the water level.)
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        int i = 0, j = height.size()-1, ans = 0;
        for(int l = height[i],r = height[j];i<j-1;){
            if(l<r){
                ++i;
                if(l>height[i]) ans += l-height[i];
                else l = height[i];
            }
            else{
                --j;
                if(r>height[j]) ans += r-height[j];
                else r = height[j];
            }
        }
        return ans;
    }
};

43, Multiply Strings

Question: Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2
Idea: Just do it: Consider the carrier of each digit
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        string ans;
        for(int i=0,cur=0;i<num1.size()+num2.size()-1||cur;i++){
            for(int j=max(i+1-(int)num2.size(),0);j<=min(i,(int)num1.size()-1);++j) cur += int(num1[j]-'0')*int(num2[i-j]-'0');
            ans += (char)(cur%10 + (int)'0');
            cur /= 10;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

44, Wildcard Matching

Question: Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
Idea: the same dp[i][j] as the previous one: (400 ms, needs optimization!)
typedef vector<bool> vb;
class Solution {
public:
    bool isMatch(string s, string p) {
        int ns = s.size(), np = p.size();
        if(!np) return !ns;
        vector<vb> dp(ns+1,vb(np+1,false));
        dp[ns][np] = true;
        for(int j=np-1;j>=0&&p[j]=='*';--j) dp[ns][j] = true;
        for(int i=ns-1;i>=0;--i) for(int j=np-1;j>=0;--j){
            if(p[j]=='*') for(int l=i;l<=ns;++l) dp[i][j] = dp[i][j]||dp[l][j+1];
            else dp[i][j] = dp[i+1][j+1]&&(p[j]=='?'||p[j]==s[i]);
        }
        return dp[0][0];
    }
};

45, Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.
Idea: Easy Greedy!
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return 0;
        int ans = 1;
        for(int i=0,p=nums[0];p<n-1;ans++){
            int tmp = p;
            for(;i<=p;++i) tmp = max(tmp,i+nums[i]);
            p = tmp;
        }
        return ans;
    }
};