Leetcode array 704 27 189 121 380 238 134 13

review:

704. Binary Search

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;
 
    }
};

二分搜索：

判断条件是left 和 right

这里就要注意区间开闭的问题

27. Remove Element

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

189. Rotate Array

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin()+k%n);
        reverse(nums.begin()+k%n, nums.end());
    }
};

121. Best Time to Buy and Sell Stock

class Solution {
public:
    int maxProfit(vector<int>& prices) {
 
        vectorint>> dp(prices.size(), vector<int>(2));
 
        //0表示未持有， 1表示持有
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        int maxVal = 0;
        for(int i=1; isize(); i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }
 
        return dp[prices.size()-1][0];
    }
};

New:

380. Insert Delete GetRandom O(1)

class RandomizedSet {
private:
    vector<int> nums;
    unordered_map<int, int> valToIndex;//nums中每个元素在nums的下表
public:
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if(valToIndex.find(val) != valToIndex.end()){
            return false;
        }
        valToIndex[val] = nums.size();
        nums.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        if(valToIndex.find(val) == valToIndex.end()) return false;
 
        int lastNum = nums.back();
        int index = valToIndex[val];
        valToIndex[lastNum] = index;
        swap(nums[index], nums.back());
        nums.pop_back();
        valToIndex.erase(val);
        return true;
    }
    
    int getRandom() {
        if(nums.size() == 0) return false;
        return nums[rand() % nums.size()];
    }
};

因为需要运行时间时O（1），所以要加上map

删除的时候要把需要删除的变到最后，再直接pop掉

rand用法：

1.rand()

2. nums[rand() % nums.size()];

3. left+rand() % (right-left)

238. Product of Array Except Self

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> presuf(n, nums[0]);
        for(int i=1; isize(); i++){
            presuf[i] = presuf[i-1] * nums[i];
        }
        vector<int> postsuf(n, nums[n-1]);
        for(int i=n-2; i>=0; i--){
            postsuf[i] = postsuf[i+1] * nums[i];
        }
 
        vector<int> res(n);
        res[0] = postsuf[1];
        res[n-1] = presuf[n-2];
        for(int i=1; i-1; i++){
            res[i] = presuf[i-1] * postsuf[i+1];
        }
        return res;
    }
};

134. Gas Station

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0, minSum = 0;
        int start = 0;
        for(int i=0; isize(); i++){
            sum += gas[i] - cost[i];
            if(sum < minSum){
                minSum = sum;
                start = i+1;
            }
        }
 
        if(sum < 0) return -1;
        return start == gas.size() ? 0 : start;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0;
        int start = 0;
        for(int i=0; isize(); i++){
            sum += gas[i] - cost[i];
        }
 
        if(sum < 0) return -1;
        int tank = 0;
        for(int i=0; isize(); i++){
            tank += gas[i] - cost[i];
            if(tank < 0){
                start = i+1;
                tank = 0;
            } 
        }
        return start == gas.size() ? 0 : start; 
    }
};

13. Roman to Integer

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> map;
        map['I'] = 1;
        map['V'] = 5;
        map['X'] = 10;
        map['L'] = 50;
        map['C'] = 100;
        map['D'] = 500;
        map['M'] = 1000; 
        int sum = 0;
        for(int i = 0; isize(); i++){
            int x = map[s[i+1]];
            if(map[s[i]] < map[s[i+1]]){
                sum -= map[s[i]];
            }else{
                sum += map[s[i]];
            }
        }
 
        return sum;
    }
};