当前位置:   article > 正文

LeetCode:数组刷题(17道经典题目)_leetcode题库

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} totalnumsisum 。左右侧元素相等即为 sum = total − nums i − sum \textit{sum}=\textit{total}-\textit{nums}_i-\textit{sum} sum=totalnumsisum,即 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
推荐阅读
相关标签
  

闽ICP备14008679号