leetcode 面试经典150题

记录leetcode网站面试经典150题的思路和心得。

150题网页链接

1-10

88.合并两个有序数组

归并排序合并过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    vector<int> b;
    b.clear();
    int i = 0, j = 0;
    for( ; i < m || j < n;) {
        if((j == n) || ( i < m && nums1[i] <= nums2[j])) {
            b.push_back(nums1[i++]);
        }
        else b.push_back(nums2[j++]);
    }
    
    for(i = 0; i < n+m; i++) nums1[i] = b[i];
}

27.移除元素

双指针扫描互换即可。

26.删除有序数组中的重复项

按照条件筛选元素，条件为不与前驱相同的元素。

用覆盖的思路处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i-1]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};

80.删除有序数组中的重复项 II

在上一题基础上加一个前驱的前驱即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int k = 2;
        for(int i = 2; i < nums.size(); i++) {
            if(nums[i] != nums[k-1] || nums[i] != nums[k-2]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};

169.多数元素

求众数方法。计数，相同则加，不同则减，减到0更换预选数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0];
        int k = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(ans == nums[i]) k++;
            else k--;
            if(!k) {
                k = 1;
                ans = nums[i];
            }
        }
        return ans;
    }
};

189.轮转数组

前后调换，三次逆转即可。

121.买卖股票的最佳时机

维护一个前缀最小值，动态更新答案。

122.买卖股票的最佳时机 II

贪心。记录折现转折点，在最低点买入最高点卖出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n <= 1) return 0;
        int l = prices[0], r = prices[0], ans = 0;
        for(int i = 1; i < n; i++) {
            if(prices[i] >= prices[i-1]) {
                r = prices[i];
            }
            else {
                ans += r-l;
                l = r = prices[i];
            }
        }
        ans += r-l;
        return ans;
    }
};

55.跳跃游戏

维护一个能跳到的最大范围即可。

45.跳跃游戏 II

正向DP，用当前值更新后面的值即可。

11-20

274.H 指数

枚举即可。 显然答案具有单调性，可以用二分进一步优化。

380.O(1) 时间插入、删除和获取随机元素

数组+哈希表双向绑定。删除时尾部交换删除来做到O(1)删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class RandomizedSet {
public:
    vector<vector<int> > vec;
    vector<int> value;
    RandomizedSet() {
        value.clear();
        for(int i = 0; i <= 10007; i++) {
            vector<int> u;
            u.clear();
            vec.push_back(u);
        }
    }
    
    int hash(int val) {
        return abs(val)%10007;
    }

    int indexOfVal(int val) {
        int H = hash(val);
        if(vec[H].empty() || value.empty()) return -1;
        for(int i = 0; i < vec[H].size(); i++) {
            int index = vec[H][i];
            if(index == -1) continue;
            if(value[index] == val) return index;
        }
        return -1;
    }

    bool insert(int val) {
        if(indexOfVal(val) != -1) 
            return false;
        value.push_back(val);
        int index = value.size()-1;
        int H = hash(val);
        vec[H].push_back(index);
        return true;
    }
    
    bool remove(int val) {
        int index = indexOfVal(val);
        if(index == -1) return false;
        int n = value.size();
        int last = value[n-1];

        int H = hash(last);
        for(int i = 0; i < vec[H].size(); i++) {
            if(vec[H][i] == n-1) vec[H][i] = index;
        }

        H = hash(val);
        for(int i = 0; i < vec[H].size(); i++) {
            if(vec[H][i] == index) vec[H][i] = -1;
        }

        swap(value[n-1], value[index]);
        if(n > 1) value.resize(n-1);
        else value.clear();

        return true;
    }
    
    int getRandom() {
        int n = value.size();
        int r = rand()%n;
        return value[r];
    }
};

238.除自身以外数组的乘积

求前缀乘和后缀乘即可。

134.加油站

尝试走完全程即可，失败则从失败点继续尝试。

42.接雨水

单调栈。维护一个凸形即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<pair<int, int> >st;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            int h = height[i];
            if(st.empty() || h < st.top().first) {
                st.push(make_pair(h, i));
            }
            else if(h == st.top().first) {
                st.top().second = i;
            }
            else {
                while(st.size() > 1 && h > st.top().first) {
                    int th = st.top().first, j = st.top().second;
                    st.pop();
                    if(th >= st.top().first) break;
                    sum += (i-st.top().second-1) * (min(st.top().first, h)-th);
                }
                if(h == st.top().first) st.top().second = i;
                else st.push(make_pair(h, i));
            }
        }
        
        return sum;
    }
};