Skip to content

Latest commit

 

History

History
264 lines (241 loc) · 6.41 KB

9.8.2017(Q166-Q180).md

File metadata and controls

264 lines (241 loc) · 6.41 KB
Raw

Questions 166 ~ 180

166. Fraction to Recurring Decimal

1 Treat a/b and a%b separately; 2 Care about overflow; 3 Care about negative numbers; 4 Use a map to determine the position of the recusion start point.
typedef long long LL;
class Solution {
    string afterDecimal(LL a,LL b){
        string ans;
        unordered_map<LL,int> index;
        for(int i=0;a && !index.count(a);++i){
            index[a] = i;
            a *= 10;
            ans += to_string(a/b);
            a %= b;
        }
        if(a==0) return ans;
        return ans.substr(0,index[a]) + "(" + ans.substr(index[a]) +")";
    }
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(!numerator) return "0";
        LL A = (LL)numerator, B = (LL)denominator, sA = 1, sB = 1;
        if(A<0) sA = -1;
        if(B<0) sB = -1;
        A*=sA;
        B*=sB;
        return (sA==sB?"":"-") + to_string(A/B) + (A%B? ("."+afterDecimal(A%B,B)):"");
    }
};

167. Two Sum II - Input array is sorted

I don't know why this question comes up again. It is so easy.
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = (int)numbers.size()-1, sum;
        while(i<j && (sum = numbers[i]+numbers[j])!=target){
            if(sum>target) --j;
            else ++i;
        }
        return i==j?vector<int>{0,0}:vector<int>{i+1,j+1};
    }
};

168. Excel Sheet Column Title

Be careful during the iteration, since the number is 1 based:
class Solution {
public:
    string convertToTitle(int n) {
        string ans;
        while(n){
            ans += char((n-1)%26 + 'A');
            n = (n-1)/26;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

169. Majority Element

Method#1: Using sort, or pick kth number, since nums[nums.size()/2] must be the majority number:
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        return nums[nums.size() / 2];
    }
};
Method#2: By selective voting:
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0], cnt = 1;
        for(int i=1;i<(int)nums.size();++i){
            if(!cnt){
                ans = nums[i];
                cnt = 1;
            }
            else cnt += nums[i]==ans? 1:-1;
        }
        return ans;
    }
};
Method#3: Bit-manipulation:
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = 0, n = (int)nums.size();
        for(int j=0;j<32;++j){
            int cnt = 0;
            for(auto k:nums) cnt += 1&(k>>j);
            if(cnt>n/2) ans |= 1<<j;
        }
        return ans;
    }
};

170. Two Sum III - Data structure design

Do not think too much, it is super super easy:
class TwoSum {
public:
    /** Initialize your data structure here. */
    unordered_map<int,int> cnt;
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        cnt[number]++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for(auto p:cnt) if(cnt.count(value-p.first)){
            if(value == p.first + p.first && p.second<=1) continue;
            return true;
        }
        return false;
    }
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * bool param_2 = obj.find(value);
 */

171. Excel Sheet Column Number

Very easy:
class Solution {
public:
    int titleToNumber(string s) {
        int ans = 0;
        for(auto c:s){
            ans = ans*26 + int(c-'A'+1);
        }
        return ans;
    }
};

172. Factorial Trailing Zeroes

Super easy: just counting how many 5-factors appear during the factorial
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while(n){
            ans += n/5;
            n/=5;
        }
        return ans;
    }
};

173. Binary Search Tree Iterator

Using stack: the complexity is averaged to be O(1), not exactly O(1): similar as the preorder-traversal
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
    stack<TreeNode *> stk;
public:
    BSTIterator(TreeNode *root) {
        while(root){
            stk.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !stk.empty();
    }

    /** @return the next smallest number */
    int next() {
        int ans = stk.top()->val;
        auto root = stk.top()->right;
        stk.pop();
        while(root){
            stk.push(root);
            root = root->left;
        }
        return ans;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

174. Dungeon Game

Using a min-Max update: max(0, min(path#1, path#2))
typedef vector<int> vi;
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        if(dungeon.empty() || dungeon[0].empty()) return 0;
        int n = (int)dungeon.size(), m = (int)dungeon[0].size(), ans = 0;
        vi dp(m,0);
        for(int i=m-2,sum = 0;i>=0;--i){
            dp[i] = max(dp[i+1]-dungeon[n-1][i+1],0);
        }
        for(int i=n-2;i>=0;--i){
            dp[m-1] = max(0,dp[m-1]-dungeon[i+1][m-1]);
            for(int j=m-2;j>=0;--j) dp[j] = max(0,min(dp[j]-dungeon[i+1][j],dp[j+1]-dungeon[i][j+1]));
        }
        return max(0,dp[0] - dungeon[0][0])+1;
    }
};

179. Largest Number

Define a comparing mechanism: [](int a,int b){return to_string(a)+to_string(b)>to_string(b)+to_string(a);}, and use this new compare function to sort.
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),[](int a,int b){return to_string(a)+to_string(b)>to_string(b)+to_string(a);});
        string ans;
        for(auto n:nums) ans += to_string(n);
        if(ans.empty() || ans[0]=='0') return "0";
        return ans;
    }
};

175, 176, 177, 178, 180 are SQL questions, which we will cover later.