Array-Medium

2020-04-27
Abstract：leetcode 线性表相关 Medium 难度 题解合集

16. 3Sum Closest

image-20200427215132211

解法一：暴力法

遍历所有可能的3组数，求最接近的sum

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int min = INT32_MAX, res = min;
        for(int i = 0; i<nums.size(); i++){
            for(int j = i + 1; j<nums.size(); j++){
                for(int k = j + 1; k<nums.size(); k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    int val = std::abs(sum - target);
                    if(val == 0) return sum;
                    if(val < min){
                        min = val;
                        res = sum;
                    }
                }
            }
        }
        return res;
    }
};

解法二：排序+双指针

还记得两数之和那题是靠双指针做的，这题也可以，但是要固定一个数，而且这个数必须从小到大变化，所以先排序，然后就转换成两数之和了

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int min = INT32_MAX, res = min;
        std::sort(nums.begin(), nums.end());
        for(int i = 0; i<nums.size(); i++){
            int lo = i + 1, hi = nums.size() - 1;
            while(lo < hi){
                int sum = nums[i] + nums[lo] + nums[hi];
                int val = std::abs(sum - target);
                if (val < min) {
                    res = sum;
                    min = val;
                }
                if(sum < target) lo++;
                else if(sum > target) hi--;
                else return res;
            }
        }
        return res;
    }
};

15. 3Sum

image-20200429140647649

解法一：排序 + 双指针

同上题，暴力解就不写了，这题的坑点在去重，因为要求unique triplets

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		std::vector<vector<int>> res;
		if (nums.size() < 3) return res;
		std::sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size() - 2; i++) {
			if (nums[i] > 0) return res;
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			int lo = i + 1, hi = nums.size() - 1;
			while (lo < hi) {
				int sum = nums[i] + nums[lo] + nums[hi];
				if (sum == 0) {
					res.push_back({ nums[i], nums[lo], nums[hi] });
					while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
					while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
					lo++;
					hi--;
				}
				else if (sum > 0)
					hi--;
				else
					lo++;
			}
		}
		return res;
	}
};

18. 4Sum

image-20200429143922947

解法一：同上

同上，好像只能套一层双指针的样子，复杂度依然有n^3

另外由于target可以为负数，所以nums[i] > target & nums[i] + nums[j] > target 就 return 的好性质就没了

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		vector<vector<int>> res;
		if (nums.size() < 4) return res;
		std::sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size() - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			for (int j = i + 1; j < nums.size() - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;
				int lo = j + 1, hi = nums.size() - 1;
				while (lo < hi) {
					int sum = nums[i] + nums[j] + nums[lo] + nums[hi];
					if (sum == target) {
						res.push_back({ nums[i],nums[j],nums[lo],nums[hi] });
						while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
						while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
						lo++;
						hi--;
					}
					else if (sum > target) hi--;
					else if (sum < target) lo++;
				}
			}
		}
		return res;
	}
};

48. Rotate Image

image-20200430144224282

image-20200430144236162

解法一：先转置再求反

一开始以为是转置，结果发现刚好反过来，那就再求一次reverse就好了，但是直觉上就知道这样有点先降温再烧水的意味

  • 注意交换的时候只交换上三角
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = i + 1; j < col; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        for (vector<int>& v : matrix) {
            std::reverse(v.begin(), v.end());
        }
    }
};

解法二：旋转变换

反正我是没想出来，抄答案的

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < (n + 1) / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
                matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
    }
};

36. Valid Sudoku

image-20200430171033116

image-20200430171047297

image-20200430171056746

解法一：暴力法（三次遍历）

依次按行遍历，按列遍历，按九宫格遍历，用unordered_map记录出现的数字的次数，每轮超过一次算错

class Solution {
public:
	bool isValidSudoku(vector<vector<char>>& board) {
		unordered_map<char, int> map;
		for (int i = 0; i < board.size(); i++) {
			map.clear();
			for (int j = 0; j < board[0].size(); j++) {
				int count = map[board[i][j]]++;
				if (isdigit(board[i][j]) && count > 0)
					return false;
			}
		}

		for (int i = 0; i < board.size(); i++) {
			map.clear();
			for (int j = 0; j < board[0].size(); j++) {
				int count = map[board[j][i]]++;
				if (isdigit(board[j][i]) && count > 0)
					return false;
			}
		}

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				map.clear();
				for (int m = i * 3; m < i * 3 + 3; m++) {
					for (int n = j * 3; n < j * 3 + 3; n++) {
						int count = map[board[m][n]]++;
						if (isdigit(board[m][n]) && count > 0)
							return false;
					}
				}
			}
		}

		return true;
	}
};

解法二：一次遍历

其实可以一次遍历，前提是要知道在哪行哪列哪个box

因为只有9个数，哈希容器也可以换成bool数组

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row[9][9] = { false }, col[9][9] = { false }, box[9][9] = { false };
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int box_idx = (i / 3) * 3 + j / 3;
                int val = board[i][j] - '1';
                if (row[i][val] || col[j][val] || box[box_idx][val])
                    return false;
                row[i][val] = col[j][val] = box[box_idx][val] = true;
            }
        }
        return true;
    }
};

54. Spiral Matrix

image-20200430235816762

解法一：标记访问点

按顺序向右，向下，向左，向上，直到”撞墙“，需要“预判”，当下一个被访问过或要越界的时候就转向

这里有点投机取巧，用INT32_MAX作标记，而且直接修改了原数组脏了数据

替代方案是开另一个等大的数组来记录是否被访问过，但我懒得改了（ 就这样吧（

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};
        int row = matrix.size(), col = matrix[0].size();
        vector<int> sp = vector<int>(row * col);
        int num = 0, tot = row * col, x, y;
        sp[0] = matrix[y = 0][x = 0];
        matrix[0][0] = INT32_MAX;
        while (num < tot - 1) {
            while (x < col - 1 && INT32_MAX != matrix[y][x + 1]) { sp[++num] = matrix[y][++x]; matrix[y][x] = INT32_MAX; }
            while (y < row - 1 && INT32_MAX != matrix[y + 1][x]) { sp[++num] = matrix[++y][x]; matrix[y][x] = INT32_MAX; }
            while (x > 0 && INT32_MAX != matrix[y][x - 1]) { sp[++num] = matrix[y][--x]; matrix[y][x] = INT32_MAX; }
            while (y > 0 && INT32_MAX != matrix[y - 1][x]) { sp[++num] = matrix[--y][x]; matrix[y][x] = INT32_MAX; }
        }
        return sp;
    }
};

59. Spiral Matrix II

image-20200501001955053

解法一：紫书原题好吧

做法同54题 Spiral Matrix，比起Ⅰ甚至不需要标记访问点了，更简单了

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        if(n == 0) return {};
        int size = n * n, tot = 1, x, y;
        vector<vector<int>> map = vector<vector<int>>(n);
        for(vector<int>& v : map) v = vector<int>(n);
        map[x = 0][y = 0] = 1;
        while(tot < size){
            while(x + 1 < n && !map[y][x+1]) map[y][++x] = ++tot;
            while(y + 1 < n && !map[y+1][x]) map[++y][x] = ++tot;
            while(x > 0 && !map[y][x-1]) map[y][--x] = ++tot;
            while(y > 0 && !map[y-1][x]) map[--y][x] = ++tot;
        }
        return map;
    }
};

73. Set Matrix Zeroes

image-20200501003723728

解法一：暴力法

先遍历一次记下所有0元素的行数和列数，然后重新遍历一次把对应的行和列置零，空间复杂度O(m + n)

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> row, col;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(matrix[i][j] == 0){
                    row.emplace(i);
                    col.emplace(j);
                }
            }
        }

        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(row.find(i) != row.end() || col.find(j) != col.end())
                    matrix[i][j] = 0;
            }
        }
    }
};

解法二：

1424. Diagonal Traverse II

image-20200501120709959

image-20200501120721893

image-20200501120732859

解法一：顺序遍历

学过初中数学都知道，直线上 x + y = c (c为常数)，依照这个性质就可以用正常的遍历顺序取到每一层反向的结果，最后再反向存入一个新的res数组就行了

  • 顺带一提，由于i,j的规模达到10^9，暴力法是不可行的，会超时，即使是顺序遍历也要500ms上下
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<vector<int>> map;
        for(int i = 0;i < nums.size(); i++){
            for(int j = 0; j < nums[i].size(); j++){
                int idx = i + j;
                if(idx >= map.size()) map.push_back({});
                map[idx].push_back(nums[i][j]);
            }
        }
        vector<int> res;
        for(int i = 0;i<map.size();i++){
            for(int j = map[i].size() - 1; j>-1;j--){
                res.push_back(map[i][j]);
            }
        }
        return res;
    }
};

56. Merge Intervals

image-20200501140513629

解法一：先排序

按左端点排序，那么判断重合就好办了

  • 只要下一个区间的左端点小于等于这个区间的右端点，就修改这个区间的左右端点
  • 如果不重合，就直接push下一个区间，同时指向下一个区间
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() <= 1) return intervals;
        std::sort(intervals.begin(),intervals.end(),[](vector<int> a, vector<int> b){
            return a[0] < b[0];
        });
        vector<vector<int>> res;
        int i = 0, j = 1;
        res.push_back(intervals[0]);
        while(j < intervals.size()) {
            if(intervals[j][0] <= res[i][1]){
                res[i][0] = std::min(res[i][0], intervals[j][0]);
                res[i][1] = std::max(res[i][1], intervals[j][1]);
                j++;
            }
            else{
                res.push_back(intervals[j]);
                i++;
            }   
        }
        return res;
    }
};

原来vector可以默认按第一位排序。。删掉lambda比较函数后，快了不少。。

std::sort(intervals.begin(),intervals.end());

228. Summary Ranges

image-20200506185521306

解法一：一次性遍历

就这？

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        if(nums.empty()) return {};
        vector<string> res;
        int start = 0, end = 0;
        for(int i = 0; i < nums.size() - 1; i++) {
            if(nums[i] != nums[i + 1] - 1) {
                end = i;
                if(start == end) 
                    res.push_back(to_string(nums[end]));
                else
                    res.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
                start = end + 1;
            } 
        }
        end = nums.size() - 1;
        if(start == end) 
            res.push_back(to_string(nums[end]));
        else
            res.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
        return res;
    }
};

1277. Count Square Submatrices with All Ones

image-20200506191826850

解法一：DP

同上题

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size()));
        int res = 0;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) 
                        res += dp[i][j] = 1;
                    else
                        res += dp[i][j] = std::min(dp[i - 1][j], std::min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return res;
    }
};

215. Kth Largest Element in an Array

image-20200506210330951

解法一：排序

可以，但是没必要

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

解法二：小根堆

但是需要辅助空间，而且只求前k时也不是效率最高的，因为本质上还是排了前k的序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q;
        for(int i = 0; i < nums.size(); i++) {
        	q.push(nums[i]);
            if(q.size() > k) q.pop();
        }
        return q.top();
    }
};

解法三：快速选择

相当于一个阉割版的快排，为了去掉一些快排中在这个问题下的冗余操作

  • 快排中每轮排序都能取得一个数在排序数组中的最终位置
  • 题目要求的是第k大的数，也就是最终位置为 size - k + 1，索引为size - k的元素
  • 如果一轮排序找到的索引大于size - k，那就只向下继续排，否则向上排，直到刚好等于size - k
  • 时间复杂度来到O(n)
class Solution {
public:
    int partition(vector<int> &nums, int left, int right) {
        swap(nums[left], nums[rand() % (right - left + 1) + left]); // 
        int pivot = nums[left];
        int hi = left;
        for (int lo = left + 1; lo <= right; lo++) {
            if (nums[lo] < pivot) {
                swap(nums[lo], nums[++hi]);
            }
        }
        swap(nums[left], nums[hi]);
        return hi;
    }

    int findKthLargest(vector<int> &nums, int k) {
        int target = nums.size() - k;
        int lo = 0, hi = nums.size() - 1;
        while (lo <= hi) {
            int res = partition(nums, lo, hi);
            if(res == target) return nums[res];
            else if(res < target) lo = res + 1;
            else hi = res - 1;
        }
        return -1;
    }
};

229. Majority Element II

image-20200508012701656

解法一：排序 & 哈希

排序可以一次统计同一个数字，哈希可以直接统计每个数字

但是前者时间复杂度O(nlogn)，后者空间复杂度O(n)，都不满足要求，也很简单就不贴了

解法二：摩尔投票法

摩尔投票法的图形化理解请参考从柱状图角度理解

  • 对于出现超过 n / m 次的众数，最多有 m - 1 个，本题显然最多只能有两个存在
  • 用摩尔投票法考虑两个候选人，这两个就是出现次数最多的两个
  • 但是出现次数最多不代表超过 n / 3 ，所以求得候选数之后还要遍历一次来验证是否正确
  • 另外侯选数可能重复，记得去重
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return {};
        int cand1 = nums[0], cand2 = nums[0];
        int cnt1 = 0, cnt2 = 0;
        for(int i : nums) {
            if(i == cand1) cnt1++;
            else if(i == cand2) cnt2++;
            else if(cnt1 == 0) {
                cnt1 = 1;
                cand1 = i;
            }
            else if(cnt2 == 0) {
                cnt2 = 1;
                cand2 = i;
            }
            else {
                cnt1--; cnt2--;
            }
        }
        cnt1 = 0, cnt2 = 0;
        for(int i : nums) {
            if(i == cand1) cnt1++;
            if(i == cand2) cnt2++;
        }
        vector<int> res;
        if(cnt1 > nums.size() / 3) res.push_back(cand1);
        if(cand2 != cand1 && cnt2 > nums.size() / 3) res.push_back(cand2);
        return res;

    }
};

220. Contains Duplicate III

image-20200508014707098

解法一：暴力法

超时，但是如果面向测试用例编程倒是可以 😅

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        // if (k == 10000) return false; 加上这句可以暴力法通过99.9%
        int max_t = -1, max_k = -1;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if (abs((long)nums[i] - (long)nums[j]) <= t && abs(i - j) <= k)
                    return true;
            }
        }
        return false;
    }
};

解法二：排序

显然如果有序的话，就能在线性时间内解决，但是排序会丢掉索引

274. H-Index

image-20200511143753045

解法一：直接排序

题意是对于所有n来说求不小于num[i]的个数的最大值，那么排序是个很显然的思路

class Solution {
public:
    int hIndex(vector<int>& citations) {
        std::sort(citations.begin(), citations.end(), greater<int>());
        int res = 0;
        for(int i = 0; i < citations.size(); i++) {
            if(citations[i] >= i + 1) res = std::max(res, i + 1);
        }
        return res;
    }
};

解法二：计数排序

300. Longest Increasing Subsequence

image-20200511213352059

解法一：DP

  • 构造一个前缀最大长度数组DP

  • 转移方程显然是

    dp[i] = max(dp[j] + 1, dp[i]); // j < i 且 nums[j] < nums[i]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> dp(nums.size(), 1);
        int max = 1;
        for(int i = 1; i < nums.size(); i++) {
            for(int j = 0; j < i;j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = std::max(dp[j] + 1, dp[i]);
                }
            }
            max = std::max(max, dp[i]);
        }
        return max;
    }
};

解法二：贪心

238. Product of Array Except Self

image-20200513144756662

解法一：前缀积 & 后缀积

这题本来求出总的积再分别除数组的各位就可以解决（而且是线性时间 + 常数空间），但是题目要求不能使用除法，第一时间想到的就是这个

也就是除自己以外的乘积等价于左边的乘积 * 右边的乘积，那用数组把对应的前缀积和后缀积记下来再相乘填入就行了

但是题目还要求常数空间，而现在用了8n个额外字节，下一步应该是把两个数组优化成两个变量

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> prefix(len, 1), suffix(len, 1);
        prefix[0] = nums[0], suffix[len - 1] = nums[len - 1];
        for(int i = 1; i < len; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
            suffix[len - i - 1] = suffix[len - i] * nums[len - i - 1];
        }

        vector<int> res(len);
        for(int i = 1; i < len - 1; i++) {
            res[i] = suffix[i + 1] * prefix[i - 1];
        }
        res[0] = suffix[1], res[len - 1] = prefix[len - 2];
        return res;
    }
};

优化辅助空间

  • 先从左往右遍历，让各位乘以对应的前缀积
  • 再从右往左遍历，各位乘以后缀积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len, 1);
        int prefix = 1, suffix = 1;
        for(int i = 1; i < len; i++) {
            prefix *= nums[i - 1];
            res[i] *= prefix;
        }

        for(int i = len - 2; i > -1; i--) {
            suffix *= nums[i + 1];
            res[i] *= suffix;
        }
        res[0] = suffix, res[len - 1] = prefix;

        return res;
    }
};

实际上只需要一次遍历

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len, 1);
        int prefix = 1, suffix = 1;
        for(int i = 0; i < len; i++) {
            res[i] *= prefix;
            res[len - i - 1] *= suffix;
            prefix *= nums[i];
            suffix *= nums[len - i - 1];
        }
        return res;
    }
};

216. Combination Sum III

image-20200513155456262

解法一：回溯法

注意只能取 0 ~ 9

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1, vector<int>());
        return res;
    }

    void dfs(int k, int n, int start, vector<int> v) {
        if(k == 0 && n == 0) {
            res.push_back(v);
            return;
        }
        for(int i = start; i <= 9; i++) {
            if(i <= n) {
                v.push_back(i);
                dfs(k - 1, n - i, i + 1, v);
                v.pop_back();
            }
        }
    }
};

还可以再剪枝

560. Subarray Sum Equals K

image-20200515145518511

解法一：暴力【超时】

两重循环枚举所有可能的sum

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(nums.size() == 1) return nums[0] == k;
        int res = 0;
        for(int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for(int j = i; j < nums.size(); j++) {
                sum += nums[j];
                if(sum == k) res++;
            }
        } 
        return res;
    }
};

解法二：前缀和

参考523题

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int sum = 0, res = 0;
        for(int& i : nums) {
            sum += i;
            int val = sum - k;
            res += map[val];
            map[sum]++;
        }
        return res;
    }
};

60. Permutation Sequence

image-20200516003023049

解法一：回溯法【超时】

按顺序枚举所有可能性，用 vector<bool>来记录已经加入的数字

class Solution {
public:
    int cnt;
    string ans;
    string getPermutation(int n, int k) {
        cnt = k;
        genPermutation(n, vector<bool>(10, true), "");
        return ans;
    }

    void genPermutation(int n, vector<bool> set, string res) {
        if(res.length() == n) {
            cnt--;
            if(cnt == 0) ans = res;
        }
        for(int i = 1; i <= n; i++) {
            if(set[i] == true) {
                set[i] = false;
                res += to_string(i);
                genPermutation(n, set, res);
                res.pop_back();
                set[i] = true;
            }
        }
    }

};

解法二：

78. Subsets

image-20200516142035809

解法一：回溯法

因为没有限制条件，所以没法剪枝，也就是必须搜完所有状态

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        dfs(nums, 0, res, vector<int>());
        return res;
    }

    void dfs(vector<int>& nums, int start, vector<vector<int>>& res, vector<int> curr) {
        res.push_back(curr);
        for(int i = start; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            dfs(nums, i + 1, res, curr);
            curr.pop_back();
        }
    }
};

解法二：二进制计数

77. Combinations

image-20200516142130938

解法一：暴力回溯【超时】

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        combineN(n, k, 1, vector<int>(), res);
        return res;
    }

    void combineN(int n, int k, int start, vector<int> curr, vector<vector<int>>& res){
        if(curr.size() == k) {
            res.push_back(curr);
            return;
        }
        for(int i = start; i <= n; i++) {
            curr.push_back(i);
            combineN(n, k, i + 1, curr, res);
            curr.pop_back();
        }
    }
};

优化剪枝【通过】

  • 由于是 n 选 k，当所以每次只需要搜到 n - (k - curr.size()) + 1处就足够了

  • 循环条件改为

for(int i = start; i <= n - (k - curr.size()) + 1; i++) {
    // ...
}

解法二：二进制计数

457. Circular Array Loop

image-20200517164411900

解法一：递归法

错了最多次的一道题，吐了

class Solution {
public:
    const int INF = 1e8;
    bool circularArrayLoop(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) {
            bool dir = nums[i] > 0 ? true : false;
            if(detectCycle(nums, i, dir, nums.size()))
                return true;
        }
        return false;
    }

    bool detectCycle(vector<int>& nums, int idx, bool dir, int size) {
        if(nums[idx] == 0) return false;
        if(nums[idx] == INF) return true;
        bool tdir = nums[idx] > 0 ? true : false;
        if(tdir == dir) {
            int next = (size + (idx + nums[idx]) % size) % size;
            nums[idx] = INF;
            if(idx != next && detectCycle(nums, next, dir, size))
                return true;
            else {
                nums[idx] = 0;
                return false;
            }
        }
        return false;
    }
};

209. Minimum Size Subarray Sum

image-20200517171944389

解法一：滑动窗口

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int start = 0, end = 0, len = nums.size(), min = INT32_MAX;
        vector<int> sum(len + 1);
        for(int i = 0; i < len; i++)
            sum[i + 1] += nums[i] + sum[i];
		
        while(start <= len && end <= len) {
            int val = sum[end] - sum[start];
            if(val >= s) {
                while(sum[end] - sum[start] >= s)
                    min = std::min(min, end - start++);
            }
            else end++;
        }
        return min == INT32_MAX ? 0 : min;
    }
};

解法二：二分查找

  • 复杂度不如解法一
  • 思路是对暴力法的优化，由于前缀和数组是递增的，所以把二重循环的第二层循环改成二分查找
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size(), min = INT32_MAX;
        vector<int> sum(len + 1, 0);
        for(int i = 0; i < len; i++)
            sum[i + 1] += nums[i] + sum[i];
        for (int i = 1; i <= len; i++) {
            int to_find = s + sum[i - 1];
            // 暴力for-loop 改成 lower_bound(s + sum[i - 1])
            auto bound = lower_bound(sum.begin(), sum.end(), to_find);
            if (bound != sum.end()) {
                min = std::min(min, static_cast<int>(bound - (sum.begin() + i - 1)));
            }
        }
        return min == INT32_MAX ? 0 : min;
    }
};

390. Elimination Game

image-20200517181325801

解法一：找规律

  • 想象一个等差数列，初始首项为1，公差为1，每删一轮，数列长度减半，公差翻倍

  • 如果从左往右删 或 数组的长度为奇数，首项都会被删掉，其他情况则不会

  • 利用这个规律，如果是上一条中的情况，则start = start + diff，否则不变

class Solution {
public:
    int lastRemaining(int n) {
        return lastRemain(1, 1, n, true);
    }

    int lastRemain(int start, int diff, int len, bool left) {
        if(len <= 1) return start;
        if(left || len % 2 != 0) start += diff; 
        return lastRemain(start, diff * 2, len / 2, !left);
    }
};

152. Maximum Product Subarray

image-20200518011930210

解法一：DP

又是子数组的题，这回的trick是

  • 维护两个变量，代表n为后缀的最大乘积和最小乘积
  • 如果nums[i]为正，我们自然需要最大乘积，否则需要最小乘积
  • 最大乘积如何更新？
    • 取 nums[i]，max * nums[i]，min * nums[i] 中的最大者
  • 最小乘积同理
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int Max = nums[0], Min = nums[0], res = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            int max = Max, min = Min;
            Max = std::max(max * nums[i], std::max(nums[i], min * nums[i]));
            Min = std::min(min * nums[i], std::min(nums[i], max * nums[i]));
            res  = std::max(Max, res);
        }
        return res;
    }
};

442. Find All Duplicates in an Array

image-20200523141928644

解法一：哈希

不用说了

解法二

  • 因为数值的范围在 1 - size 之间，所以需要找到一种方法在不影响值的情况下标记出已经出现的数字

  • 又因为全是正整数，所以为什么不用负号标记呢

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++) {
            int val = abs(nums[i]);
            if (nums[val - 1] > 0)
                nums[val - 1] *= -1;
            else
                res.push_back(val);
        }
        return res;
    }
};

解法三：置换法

把值为 i 的数放在 i 位置，第一个值和位置不匹配的点的即为重复数，空间复杂度O(1)

621. Task Scheduler

image-20200926224724214

image-20200926224734229

Solution

  • First count the number of occurrences of each element.
  • Let the max frequency seen be M for element E
  • We can schedule the first M-1 occurrences of E, each E will be followed by at least N CPU cycles in between successive schedules of E
  • Total CPU cycles after scheduling M-1 occurrences of E = (M-1) * (N + 1) // 1 comes for the CPU cycle for E itself
  • Now schedule the final round of tasks. We will need at least 1 CPU cycle of the last occurrence of E. If there are multiple tasks with frequency M, they will all need 1 more cycle.
  • Run through the frequency dictionary and for every element which has frequency == M, add 1 cycle to result.
  • If we have more number of tasks than the max slots we need as computed above we will return the length of the tasks array as we need at least those many CPU cycles.
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<int, int> mp;
        int cnt = 0, res = 0, val;
        for(const char& c : tasks) {
            val = ++mp[c];
            cnt = std::max(cnt, val);
        }
        res = (cnt - 1) * (n + 1);
        for(const auto& i : mp)
            if(i.second == cnt) ++res;
        return std::max((int)tasks.size(), res);
    }   
};
© 2020 Overyam - Powered by Hexo - Theme Chan