devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode：数组刷题（17道经典题目）_leetcode题库

作者：你好赵伟 | 2024-05-27 17:12:27

赞

踩

leetcode题库

LeetCode 数组刷题（17道经典题目）

本文带来的是以数组为主题的经典题目，主要实现是C++，部分题目也用Python实现了。

首先，需要明确：

  • 数组是存放在连续内存空间上的相同类型数据的集合。
  • 数组可以方便的通过下标索引的方式获取到下标下对应的数据。
  • 由于数组的在内存空间的地址是连续的，我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

所以数组的元素是不能删的，只能覆盖。

此外，需要知道，C++中二维数组在地址空间上是连续的。

二分法要求数组排序，并且数组中没有重复的元素。

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。（假设 nums 中的所有元素是不重复的。）

  • 这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的
  • 写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)
class Solution {
public:
	int search(vector<int>& nums, int target) {  // 左闭右开
		int left = 0;
		int right = nums.size();
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			}
			else if (nums[mid] > target) {
				right = mid;
			}
			else {
				return mid;
			}
		}
		return -1;
	}

	int search2(vector<int> &nums, int target) {  // 左闭右闭
		int left = 0;
		int right = nums.size() - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			}
			else if (nums[mid] > target) {
				right = mid - 1;
			}
			else {
				return mid;
			}
		}
		return -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

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法

暴力解题(不一定时间消耗就非常高，关键看实现的方式)。时间复杂度为O(n)

class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {  // 二分法
		int left = 0;
		int right = nums.size();
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			}
			else if (nums[mid] > target) {
				right = mid;
			}
			else {
				return mid;
			}
		}
		return left;  // 如果目标值不存在于数组中，返回它将会被按顺序插入的位置
	}

	int searchInsert2(vector<int>& nums, int target) { // 暴力解
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] >= target) {
				return i;
			}
		}
		// 目标值在数组所有元素之后的情况
		return nums.size();  // 如果target是最大的，或者 nums为空，则返回nums的长度
	}
};

  • 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

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

暴力解法，两个循环，时间复杂度为O(n)

class Solution {
public:
	vector<int> searchRange1(vector<int>& nums, int target) {  // 暴力求解
		int left = -1, right = -1;
		for (int i = 0; i < nums.size(); i++) {  // 找到左边界
			if (nums[i] == target) {
				left = i;
				break;
			}
		}
		for (int j = nums.size() - 1; j >= 0; j--) {  // 找到右边界
			if (nums[j] == target) {
				right = j;
				break;
			}
		}
		return{ left, right };
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

二分法，左右滑动指针，来找到符合题意的区间

class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		int index = binarySearch(nums, target);
		if (index == -1) {
			return{ -1, -1 };
		}
		int left = index, right = index;  // nums 中存在 target，则左右滑动指针，来找到符合题意的区间
		while (left - 1 >= 0 && nums[left - 1] == target) {
			left -= 1;
		}
		while (right + 1 < nums.size() && nums[right + 1] == target) {
			right += 1;
		}
		return{ left,right };
	}

private:
	int binarySearch(vector<int> &nums, int target) {
		int left = 0;
		int right = nums.size();
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] > target) {
				right = mid;
			}
			else if (nums[mid] < target) {
				left = mid + 1;
			}
			else {
				return mid;
			}
		}
		return -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

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的平方根。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

袖珍计算器算法:用指数函数和对数函数代替平方根函数的方法

由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。因此在得到结果的整数部分ans后，我们应当找出与ans+1中哪一个是真正的答案。

class Solution {
public:
	int mySqrt2(int x) {   // 二分法
		int left = 0;
		int right = x;
		int ans = 0;
		while (left <= right) {
			long long mid = left + (right - left) / 2;
			if (mid * mid > x) {   // mid 必须是long long，不然会溢出
				right = mid - 1;
			}
			else {
				ans = mid;
				left = mid + 1;
			}
		}
		return ans;
	}

	int mySqrt(int x) {  // 袖珍计算器算法
		if (x == 0) {
			return 0;
		}
		int ret = exp(log(x) * 0.5);
		return (ret + 1)*(ret + 1) <= x ? ret + 1 : ret;
	}
};

  • 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

牛顿迭代法：牛顿迭代法是一种可以用来快速求解函数零点的方法。牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C / x0)
            if abs(xi - x0) < 1e-7:
                break
            x0 = xi
        return int(x0)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

367.有效的完全平方数

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。不要使用任何内置的库函数，如 sqrt 。

class Solution {
public:
	bool isPerfectSquare(int num) {
		int left = 0;
		int right = num;
		while (left <= right) {
			long long mid = left + (right - left) / 2;
			if (mid * mid > num) {
				right = mid - 1;
			}
			else if(mid * mid < num)
			{
				left = mid + 1;
			}
			else {
				return true;
			}
		}
		return false;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

1, 4=1+3, 9=1+3+5, 16=1+3+5+7, … 以此类推，模仿它可以使用一个while循环，不断减去一个从1开始不断增大的奇数，若最终减成了0，说明是完全平方数，否则，不是。

class Solution {
public:
	bool isPerfectSquare(int num) {
		int n = 1;
		while (num > 0) {
			num -= n;
			n += 2;
		}
		return num == 0;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

暴力求解：时间复杂度 O(n^2)

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

本题最重要的限制条件就是原地移除元素，使用O(1)的额外空间。如果没有这个条件限制，那么本题是非常简单的，我们只需要遍历一遍, 将所有满足的元素放到另一个数组就完成操作了。因为限制条件的存在，我们必须寻找其他的思想, 只能在原数组上进行操作, 这样才能满足O(1)的空间复杂度。这样我们就不光需要找到满足的元素，还要同时找到满足的元素需要存放的位置，所以我们就需要使用 双指针 来同时确定这两个位置。

右指针right指向当前将要处理的元素，左指针left指向下一个将要赋值的位置。

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

双指针优化：

正常情况下需要移除的元素必然是远小于需要保留的元素的，那我们直接对 **移除元素 **进行操作更有效，这避免了需要保留的元素的重复赋值操作。

两个指针初始时分别位于数组的首尾，向中间移动遍历该序列,，只是此时两指针的含义有所不同：左指针就是直接指向需要被移除的元素val，只要满足条件，直接用右指针指向的元素将其替换，

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

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

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

双指针

class Solution {
public:
	int removeDuplicates(vector<int>& nums) {
		int slow = 0;
		int fast = 0;
		while (fast < nums.size()) {
			if (nums[slow] == nums[fast]) {
				fast++;
			}
			else {
				slow++;
				nums[slow] = nums[fast];
			}
		}
		return slow + 1;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		int slow = 0;
		int fast = 0;
		while (fast < nums.size()) {
			if (nums[fast] != 0) {
				nums[slow] = nums[fast];
				slow++;
			}
			fast++;
		}
		for (int i = slow; i < nums.size(); i++) {
			nums[i] = 0;
		}
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

844.比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。

重构字符串：用栈处理遍历过程，每次我们遍历到一个字符：如果它是退格符，那么我们将栈顶弹出；如果它是普通字符，那么我们将其压入栈中。

class Solution {
public:
	bool backspaceCompare(string s, string t) {
		return build(s) == build(t);
	}
private:
	string build(string s) {  // 栈
		string ret;
		for (char c : s) {
			if (c != '#') {
				ret.push_back(c);
			}
			else if (!ret.empty()) {
				ret.pop_back();
			}
		}
		return ret;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

双指针（官方题解）：一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

class Solution {
public:
	bool backspaceCompare(string s, string t) {
		int i = s.size() - 1, j = t.size() - 1;
		int skipS = 0, skipT = 0;

		while (i >= 0 || j >= 0) {
			while (i >= 0) {
				if (s[i] == '#') {
					skipS++;
					i--;
				}
				else if (skipS > 0) {
					skipS--;
					i--;
				}
				else {
					break;
				}
			}
			while (j >= 0) {
				if (t[j] == '#') {
					skipT++;
					j--;
				}
				else if (skipT > 0) {
					skipT--;
					j--;
				}
				else {
					break;
				}
			}
			if (i >= 0 && j >= 0) {
				if (s[i] != t[j]) return false;
			}
			else if (i >= 0 || j >= 0) return false;
			i--; j--;
		}
		return true;
	}
};

  • 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

双指针（简化版）：重构字符串（★★★★）

class Solution {
public:
	bool backspaceCompare(string s, string t) {
		rebuild(s);
		rebuild(t);
		return s == t;
	}
private:
	void rebuild(string &s) {
		int left = 0;
		for (char c : s) {
			if (c == '#') {
				if (left > 0) left--;
			}
			else {
				s[left] = c;
				left++;
			}
		}
		s.resize(left);
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

将数组 nums 中的数平方后直接排序

class Solution {
public:
	vector<int> sortedSquares(vector<int>& nums) {  // 平方后直接排序
		vector<int> ans;
		for (int a : nums) {
			ans.push_back(a * a);
		}
		sort(ans.begin(), ans.end());
		return ans;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

双指针：使用两个指针分别指向位置 0 和 n-1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针

class Solution {
public:
	vector<int> sortedSquares(vector<int>& nums) {  // 双指针
		int n = nums.size();
		vector<int> ret(n);
		int left = 0, right = n - 1;
		int pos = n - 1;
		while (left <= right) {
			if (nums[left] * nums[left] > nums[right] * nums[right])  {
				ret[pos] = nums[left] * nums[left];
				left++;
			}
			else {
				ret[pos] = nums[right] * nums[right];
				right--;
			}
			pos--;
		}
		return ret;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

暴力求解：

class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		int n = nums.size();
		int subLen = 0;  // 子序列长度
		int ret = INT32_MAX;  // 长度
		for (int i = 0; i < n; i++) {
			int count = 0;
			for (int j = i; j < n; j++) {
				count += nums[j];
				if (count >= target) {
					subLen = j - i + 1;
					ret = ret < subLen ? ret : subLen;
					break;
				}
			}
		}
		return ret == INT32_MAX ? 0 : ret;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

滑动窗口：滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2) 的暴力解法降为 O(n)。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        start, end = 0, 0
        total = 0
        res = n + 1
        while end < n:
            total += nums[end]
            while total >= target:
                res = min(res, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if res == n + 1 else res

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

不是for里放一个while就是 O ( n 2 ) O(n^2) O(n2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是 O(n)

904. 水果成篮（★★★★★）

在一排树中，第 i 棵树产生 tree[i] 型的水果。你可以从你选择的任何树开始，然后重复执行以下步骤：

  • 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
  • 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。

请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。用这个程序你能收集的水果树的最大总量是多少？

题目说的意思就是找到只包含两种元素的最长连续子序列的长度

滑动窗口：

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        n = len(fruits)
        if len(set(fruits)) < 2: return n
        left, right = 0, 0
        ret = 0
        while right < n:   # 左闭右开
            tag = set(fruits[left:right+1])
            if len(tag) > 2:
                left += 1
            elif len(tag) == 2:
                ret = max(ret, right - left + 1)
                right += 1
            else:
                right += 1
        return ret

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

滑动窗口：（unordered_map）

class Solution {
public:
	int totalFruit(vector<int>& fruits) {
		unordered_map<int, int> basket;
		int left = 0, right = 0;
		int ans = INT32_MIN;
		while (right < fruits.size()) {
			basket[fruits[right]]++;
			right++;
			while (basket.size() > 2) {   // 类数大于2，开始往外扔
				basket[fruits[left]]--;
				if (basket[fruits[left]] == 0) {
					basket.erase(fruits[left]);
				}
				left++;
			}
			ans = max(ans, right - left);
		}
		return ans;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

滑动窗口：窗口只平移，不缩小（★★★★）

class Solution {
public:
	int totalFruit(vector<int> &fruits) {
		int n = fruits.size();
		vector<int> count(n);
		int left = 0, right = 0;
		int diff = 0;  // 窗口里面的种类数
		while (right < n) {
			if (count[fruits[right]]++ == 0) {
				diff++;
			}
			if (diff > 2) {
				if (--count[fruits[left++]] == 0) {
					diff--;
				}
			}
			right++;
		}
		//  l和r组成的窗口一定会把最长的子串框出来，之后这个窗口会保持这个最大长度一直往后滑动
		return right - left; 
	}
};


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

76. 最小覆盖子串（★★★★★）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。

滑动窗口：

用 i,j 表示滑动窗口的左边界和右边界，通过改变 i,j 来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串 T 的所有元素，记录下这个滑动窗口的长度 j-i+1，这些长度中的最小值就是要求的结果。

  1. 不断增加 j 使滑动窗口增大，直到窗口包含了 T 的所有元素
  2. 不断增加 i 使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
  3. 让 i 再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到 j 超出了字符串 S 范围。


如何判断滑动窗口包含了T的所有元素？

  • 我们用一个字典need来表示当前滑动窗口中需要的各元素的数量，一开始滑动窗口为空，用 T 中各元素来初始化这个need，当滑动窗口扩展或者收缩的时候，去维护这个need字典，例如当滑动窗口包含某个元素，我们就让need中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，就让need中这个元素的数量加1。need始终记录着当前滑动窗口下，我们还需要的元素数量，我们在改变 i,j 时，需同步维护need。
  • 值得注意的是，只要某个元素包含在滑动窗口中，我们就会在need中存储这个元素的数量，如果某个元素存储的是负数代表这个元素是多余的。
  • 那么如何判断滑动窗口包含了 T 的所有元素？结论就是当need中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。


优化：

  • 如果每次判断滑动窗口是否包含了T的所有元素，都去遍历need看是否所有元素数量都小于等于0，这个会耗费O(k)的时间复杂度，k代表字典长度，最坏情况下，k可能等于len(S)
  • 我们可以维护一个额外的变量needCnt来记录所需元素的总数量，当我们碰到一个所需元素c，不仅need[c]的数量减少1，同时needCnt也要减少1，这样我们通过needCnt就可以知道是否满足条件，而无需遍历字典了。
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

  • 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
class Solution {
public:
	string minWindow(string s, string t) {
		for (char c : t) {
			need[c]++;
		}

		int needCnt = t.size();
		int l = 0, r = 0;
		int resL = 0, resR = INT32_MAX;

		for (int r = 0; r < s.size(); r++) {
			if (need[s[r]] > 0) {
				needCnt--;
			}
			need[s[r]]--;

			if (needCnt == 0) {  // 步骤一：滑动窗口包含所有T的元素
				while (true) {  // 步骤二：增加i，排除多余元素
					if (need[s[l]] == 0) break;
					need[s[l]]++;
					l++;
				}
				if (r - l < resR - resL) {  // 记录结果
					resL = l;
					resR = r;
				}
				need[s[l]]++;
				needCnt++;
				l++;
			}
		}
		return resR > s.size() ? "" : s.substr(resL, resR - resL + 1);
	}
private:
	unordered_map<int, int> need;   // 哈希表
}; 

  • 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

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> ret;
		int n = matrix.size(), m = matrix[0].size();   // n,m
		int left = 0, right = m - 1, up = 0, down = n - 1;
		int num = n * m;
		while (num >= 1) {
			for (int i = left; i <= right && num >= 1; i++) {
				ret.push_back(matrix[up][i]);
				num--;
			}
			up++;
			for (int j = up; j <= down && num >= 1; j++) {
				ret.push_back(matrix[j][right]);
				num--;
			}
			right--;
			for (int k = right; k >= left && num >= 1; k--) {
				ret.push_back(matrix[down][k]);
				num--;
			}
			down--;
			for (int l = down; l >= up && num >= 1; l--) {
				ret.push_back(matrix[l][left]);
				num--;
			}
			left++;
		}
		return ret;
	}
};

  • 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
def spiralOrder(matrix):
    m, n = len(matrix), len(matrix[0])
    visited = [[0] * n for _ in range(m)]
    total = m * n
    ret = [0] * total

    directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    row, column = 0, 0
    directionIndex = 0
    for i in range(total):
        ret[i] = matrix[row][column]
        visited[row][column] = 1
        nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
        if not (0 <= nextRow < m and 0 <= nextColumn < n and not visited[nextRow][nextColumn]):
            directionIndex = (directionIndex + 1) % 4
        row += directions[directionIndex][0]
        column += directions[directionIndex][1]
    return ret

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

技巧方法：

def spiralOrder2(matrix):
    res = []
    while matrix:
        res += matrix.pop(0)   # 削头（第一层）
        matrix = list(zip(*matrix))[::-1]  # 将剩下的逆时针转九十度，等待下次被削
    return res

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

必须坚持循环不变量原则。模拟顺时针画矩阵的过程:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

由外向内一圈一圈这么画下去。

左闭右开：

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> matrix(n, vector<int>(n, 0));
		int left = 0, right = n - 1, up = 0, down = n - 1;
		int number = 1;
		while (left < right && up < down) {   
			for (int i = left; i < right; i++) {  // 上行
				matrix[up][i] = number;
				number++;
			}
			for (int j = up; j < down; j++) {  // 右列
				matrix[j][right] = number;
				number++;
			} 
			for (int k = right; k > left; k--) {  // 下行
				matrix[down][k] = number;
				number++;
			}
			for (int l = down; l > up; l--) {
				matrix[l][left] = number;
				number++;
			}
			left++;
			right--;
			up++;
			down--;
		}
		// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
		if (n % 2 == 1) {
			matrix[n / 2][n / 2] = number;
		}
		return matrix;
	}
};

  • 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

生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程：

  • 定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；
  • 当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
    • 执行 num += 1：得到下一个需要填入的数字；
    • 更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
  • 使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。

最终返回 mat 即可。

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> matrix(n, vector<int>(n, 0));
		int left = 0, right = n - 1, up = 0, down = n - 1;
		int num = 1, tar = n*n;
		while (num <= tar) {
			for (int i = left; i <= right; i++) {
				matrix[up][i] = num++;
			}
			up++;
			for (int j = up; j <= down; j++) {
				matrix[j][right] = num++;
			}
			right--;
			for (int k = right; k >= left; k--) {
				matrix[down][k] = num++;
			}
			down--;
			for (int l = down; l >= up; l--) {
				matrix[l][left] = num++;
			}
			left++;
		}
		return matrix;
    }
};

  • 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

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

首先，将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间

  • 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
  • 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        res = [intervals[0]]
        for i in intervals[1:]:
            if res[-1][1] >= i[0]:
                res[-1][1] = max(i[1], res[-1][1])
            else:
                res.append(i)
        return res

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		if (intervals.size() == 0) {
			return{};
		}
		sort(intervals.begin(), intervals.end());
		vector<vector<int>> merged;
		for (int i = 0; i < intervals.size(); i++) {
			int L = intervals[i][0], R = intervals[i][1];
			if (!merged.size() || merged.back()[1] < L) {
				merged.push_back({ L, R });
			}
			else {
				merged.back()[1] = max(R, merged.back()[1]);
			}
		}
		return merged;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

724. 寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

前缀和：记数组的全部元素之和为 total \textit{total} total，当遍历到第 i i i 个元素时，设其左侧元素之和为 sum \textit{sum} sum，则其右侧元素之和为 total − nums i − sum \textit{total}-\textit{nums}_i-\textit{sum} total−numsi​−sum 。左右侧元素相等即为 sum = total − nums i − sum \textit{sum}=\textit{total}-\textit{nums}_i-\textit{sum} sum=total−numsi​−sum，即 2 × sum + nums i = total 2\times\textit{sum}+\textit{nums}_i=\textit{total} 2×sum+numsi​=total。

class Solution {
public:
	int pivotIndex(vector<int>& nums) {
		int n = nums.size();
		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum += nums[i];
		}
		int total = 0;
		for (int j = 0; j < n; j++) {
			if (total * 2 + nums[j] == sum) {
				return j;
			}
			total += nums[j];
		}
		return -1;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

PS

以上题解来源部分是【代码随想录】，在这基础上加入了自己的一些理解。

随缘更新，有错误请指出！

END

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/633007
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号