227. Basic Calculator II M

 Q:

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 231 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

A:

走3遍， 第一遍， 都分割， 成为list 形式的string

第二遍。  做 / * 运算

第三遍， 做 + - 运算

class Solution {
public:
    int calculate(string s) {
        // first convert s to list of symbols
        vector<string> V;
        int start = 0;
        while(start < s.length()){
            if(s[start]==' '){
                start++;
            }else if(s[start]=='/' || s[start]=='+' || s[start]=='-' || s[start]=='*'){
                V.push_back(s.substr(start,1));
                start++;
            }else{
                int end = start+1;
                while(end < s.length() && isdigit(s[end])){
                    end++;
                }
                V.push_back(s.substr(start,end-start)); //substr (expect the 2nd as length)
                start = end;
            }
        }
        vector<string> V2;
        // calcualte / * first
        for(int i =0; i<V.size(); ++i){
            if(V[i] == "*" || V[i] == "/" ){
                int tmp = 0;
                if(V[i] == "*"){
                    tmp = stoi(V2.back()) * stoi( V[i+1]);
                }else{
                    tmp = stoi(V2.back()) / stoi( V[i+1]);
                }
                V2.pop_back();
                ++i;
                V2.push_back(to_string(tmp));
            }else{
                V2.push_back(V[i]);
            }
        }

        for(int i =0; i<V2.size(); ++i){
            cout << i<< ":" << V2[i] <<endl;
        }
        int res = stoi(V2[0]);
        // calcualte + - 
        for(int i =1; i<V2.size(); ++i){
            if(V2[i] == "+" || V2[i] == "-" ){
                if (V2[i] == "+" ){
                    res += stoi(V2[i+1]);
                }else{
                    res -= stoi(V2[i+1]);
                }
                ++i;
            }
        }
        return res;
    }
};

283. Move Zeroes E

 Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

 

Follow up: Could you minimize the total number of operations done?

A:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        while(j<n && nums[j]==0){ // first none zero remaining;
            j++;
        }
        int i =0;
        for(;i<n;++i){
            if(j>=n){
                nums[i]=0;
            }else{
                swap(nums[i],nums[j]);
                j++;
                while(j<n && nums[j]==0){ // first none zero remaining;
                    j++;
                }
            }
        }
    }
};

384. Shuffle an Array M

  Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

• Solution(int[] nums) Initializes the object with the integer array nums.
• int[] reset() Resets the array to its original configuration and returns it.
• int[] shuffle() Returns a random shuffling of the array.

 

Example 1:

Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

 

Constraints:

• 1 <= nums.length <= 50
• -106 <= nums[i] <= 106
• All the elements of nums are unique.
• At most 104 calls in total will be made to reset and shuffle.

A:

Fisher–Yates shuffle

class Solution {
public:
    vector<int> v;
    Solution(vector<int>& nums) {
        v=nums;
    }
    
    vector<int> reset() {
        return v;
    }
    
    vector<int> shuffle() {
        vector<int> res = v;	    
	    int random = rand();
        for(int i =v.size()-1;i > 0;--i){
            int newIdx = rand() % (i+1);
            
            if(newIdx != i){// swap if needed
                int tmp = res[i];
                res[i] = res[newIdx];
                res[newIdx] = tmp;
            }
        }
        return res;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

454. 4Sum II M

 Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

 

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

 

Constraints:

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

A:

两两做map， 然后看其对应大负值是否存在。

class Solution {      // beat 5%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        auto map1=helper(nums1,nums2);
        auto map2=helper(nums3,nums4);
        int res =0;
        for(const auto & p:map1){
            int key = p.first;
            int c1= p.second;
            auto it = map2.find(-key);
            res += (it != map2.end()? it->second * c1 : 0);
        }
        return res;
    }
private:
    map<int,int> helper(vector<int> & v1, vector<int>& v2){
        map<int,int> m;
        for(auto v : v1){
            for(auto k : v2){
                auto it = m.find(v+k);
                int value = it != m.end()? it->second : 0;
                m[v+k] = value +1;
            }
        }
        return m;
    }
};

注意到： C++ 里， map是ordered的，因此选择unordered_map. 

class Solution {      // beat 23%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        auto map1=helper(nums1,nums2);
        auto map2=helper(nums3,nums4);
        int res =0;
        for(const auto & p:map1){
            int key = p.first;
            int c1= p.second;
            auto it = map2.find(-key);
            res += (it != map2.end()? it->second * c1 : 0);
        }
        return res;
    }
private:
    unordered_map<int,int> helper(vector<int> & v1, vector<int>& v2){
        unordered_map<int,int> m;
        for(auto v : v1){
            for(auto k : v2){
                auto it = m.find(v+k);
                int value = it != m.end()? it->second : 0;
                m[v+k] = value +1;
            }
        }
        return m;
    }
};

再次注意到，第二个map其实不需要保存，只需要build on the fly。 精简后的code

class Solution {  //beat 97%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> m;
        for(auto v : nums1)
            for(auto k : nums2)
                ++m[v+k];
        
        int res = 0;
        for(auto a: nums3){
            for(auto b: nums4){
                auto it=m.find(0-a-b);
                if(it!= m.end()){
                    res += it->second;
                }
            }
        }
        return res;
    }
};

甚至， 利用语法糖， 不用去检查是否存在，直接利用不存在，检索为0的特性

it is actually safe to assume that the values inside Foo are always initialized to zero because of the behaviour of operator[]

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> m;
        for(auto v : nums1)
            for(auto k : nums2)
                ++m[v+k];
        
        int res = 0;
        for(auto a: nums3)
            for(auto b: nums4)
                res += m[0-a-b];
        return res;
    }
};