- 数组类总结
- 找规律
- 双指针
- 哈希
- 其他
题解：遍历数组交换 + 标记重复的数字
https://leetcode.cn/problems/find-all-duplicates-in-an-array/solutions/1476879/by-ac_oier-0m3c/
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int i = 0;
while (i < nums.size()) {
if (nums[i] == 0 || nums[i] == i + 1) {
++i;
continue;
}
else if (nums[nums[i] - 1] == nums[i]) {
res.push_back(nums[i]);
nums[i] = 0;
++i;
} else {
int tmp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = tmp;
}
}
return res;
}
};给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
将数组nums1的元素放入一个set中，然后遍历nums2的元素nums2[i]，判断它是否在set中，如果在set中，则说明这个元素是交集的部分，将它加入结果中。
设nums1的大小为m，数组nums2的大小为n
- 时间复杂度：O(m + n)
- 空间复杂度：O(m)
C++代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
if(nums1.empty() || nums2.empty())
return vector<int>();
unordered_set<int> st;
for(auto a : nums1)
st.insert(a);
vector<int> res;
for(int a : nums2)
{
if(st.count(a) > 0)
{
res.push_back(a);
st.erase(a);
}
}
return res;
}
};Python代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
s = set()
res = []
for a in nums1:
s.add(a)
for a in nums2:
if a in s:
res.append(a)
s.remove(a)
return res先将nums1和nums2排序(从小到大排序)，维护一个set存放交集元素，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：
- 如果
nums1[p1] == nums2[p2]，则将numns[p1]放入set，同时++p1,++p2； - 否则，
nums1[p1] < nums2[p2] ? ++p1 : ++p2。
直到p1或p2到达数组尾部。
最后将set中的元素放入结果数组中即可。
设nums1的大小为m，数组nums2的大小为n
- 时间复杂度：O(m log m + n log n)
- 空间复杂度：O(max(m,n))
C++代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
vector<int> res;
set<int> st;
int p1 = 0,p2 = 0;
while(p1 < nums1.size() && p2 < nums2.size())
{
if(nums1[p1] == nums2[p2])
{
st.insert(nums1[p1]);
++p1;
++p2;
}
else{
nums1[p1] < nums2[p2] ? ++p1 : ++p2;
}
}
for(auto a : st) res.push_back(a);
return res;
}
};Python代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i = 0
s = set()
res = []
i,j = 0,0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
s.add(nums1[i])
i += 1
j += 1
elif nums1[i] > nums2[j]:
j += 1
else:
i += 1
for a in s:
res.append(a)
return res现将nums1从小到大排序，遍历数组nums2的每一个元素nums2[i]，同时在nums1中二分查找nums2[i]，如果能找到nums2[i]，则将它加入set中；否则，跳过。最后，将set中的元素放入结果数组即可。
设nums1的大小为m，数组nums2的大小为n
- 时间复杂度：O((m + n) log m)
- 空间复杂度：O(min(m,n))
C++代码
class Solution {
public:
bool binarySearch(const vector<int>& vec,int target)
{
int l = 0,r = vec.size() - 1;
while(l <= r)
{
int m = (l + r) / 2;
if(vec[m] < target) l = m+1;
else if(vec[m] > target) r = m-1;
else return true;
}
return false;
}
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
set<int> st;
vector<int> res;
for(auto a : nums2)
{
if(binarySearch(nums1,a))
st.insert(a);
}
for(auto a : st) res.push_back(a);
return res;
}
};给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
用unordered_map（无序哈希表）来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组，如果当前字符在哈希表中的个数大于0，则将此字符加入结果中，然后哈希表的对应值自减1。
设nums1的大小为m，数组nums2的大小为n
- 时间复杂度：O(m + n)
- 空间复杂度：O(max(m,n))
C++代码
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
unordered_map<int,int> mp;
for(auto a : nums1) ++mp[a];
for(auto b : nums2)
{
if(mp[b] > 0)
{
res.push_back(b);
--mp[b];
}
}
return res;
}
};Python代码
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
dt = {}
res = []
for a in nums1:
if a not in dt:
dt[a] = 1
else:
dt[a] += 1
for b in nums2:
if b in dt and dt[b] > 0:
res.append(b)
dt[b] -= 1
return res优化空间：哈希表统计两数组中长度较小的那个数组的元素个数。
- 时间复杂度：O(m + n)
- 空间复杂度：O(min(m,n))
C++代码
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
unordered_map<int,int> mp;
if(nums1.size() > nums2.size())
{
//长度较小的数组拷贝到临时数组
vector<int> tmp(nums2);
nums2 = nums1;
nums1 = tmp;
}
for(auto a : nums1) ++mp[a];
for(auto b : nums2)
{
if(mp[b] > 0)
{
res.push_back(b);
--mp[b];
}
}
return res;
}
};先将nums1和nums2排序(从小到大排序)，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：
- 如果
nums1[p1] == nums2[p2]，则将numns[p1]放入结果，同时++p1,++p2； - 否则，
nums1[p1] < nums2[p2] ? ++p1 : ++p2。
直到p1或p2到达数组尾部。
设nums1的大小为m，数组nums2的大小为n
- 时间复杂度：O(m log m + n log n)
- 空间复杂度：O(max(m,n))
C++代码
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
vector<int> res;
int p1 = 0,p2 = 0;
while(p1 < nums1.size() && p2 < nums2.size())
{
if(nums1[p1] == nums2[p2])
{
res.push_back(nums1[p1]);
++p1;
++p2;
}
else{
nums1[p1] < nums2[p2] ? ++p1 : ++p2;
}
}
return res;
}
};给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
利用杨辉三角的性质，利用上一行的数值推导出下一行，推导关系式为：
- 时间复杂度：O(n2)
- 空间复杂度：O(n2)
C++代码
class Solution {
public:
vector<int> transform(vector<int> vec)
{
vector<int> res;
res.push_back(1);
int len = vec.size();
for(int i=1;i<len;i++)
{
res.push_back(vec[i-1] + vec[i]);
}
res.push_back(1);
return res;
}
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if(numRows == 0)
return res;
if(numRows == 1)
{
res.push_back({1});
return res;
}
res.push_back({1});
for(int i=1;i<numRows;i++)
{
res.push_back(transform(res[i-1]));
}
return res;
}
};Python代码
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
基于原数组建立哈希表，key为元素，value为元素个数，找出value > len/2的元素就是众数
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> mp;
int len = nums.size();
int res = INT_MIN;
for(auto a : nums)
{
mp[a]++;
if(mp[a] > len/2)
{
res = a;
break;
}
}
return res;
}
};Python代码
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 0;
int res = 0;
for(int i=0;i<nums.size();i++)
{
if(cnt == 0)
{
cnt++;
res = nums[i];
}
else if(nums[i] == res)
cnt++;
else
cnt--;
}
return res;
}
};Python代码
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
双指针法，快指针i遍历一遍数组，当快指针的元素非零时，令慢指针idx的元素等于快指针元素，同时慢指针前进一步。最后，所有的非零元素都移到了数组前半部分（相对顺序不变），然后将之后的元素全部置0。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
if(nums.empty())
return;
int idx = 0;
for(int i=0;i<nums.size();i++)
{
if(nums[i] != 0)
{
nums[idx++] = nums[i];
}
}
for(;idx<nums.size();idx++)
nums[idx] = 0;
return;
}
};Python代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow = fast = 0
while fast < len(nums):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
fast += 1
for i in range(slow,len(nums)):
nums[i] = 0给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
将原数组的所有元素和0~n的所有数字做异或运算，得到结果就是缺失的数字
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = 0;
for(int i=0;i<nums.size();i++)
{
res ^= (i + 1) ^ nums[i];
}
return res;
}
};Python代码
等差数列求0~n的和减去数组所有元素相加得到的和即为缺失的数字
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0;
int n = nums.size();
for(auto num : nums) sum += num;
return (int)((1 + n) * n / 2) - sum;
}
};
Python代码
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
利用unordered_set无序集合，遍历数组的时候将元素放入集合中，找出已经在集合中出现的元素就是重复的元素
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.empty())
return false;
int len=nums.size();
unordered_set<int> st;
for(auto a:nums)
{
if(st.find(a) != st.end())
return true;
else
st.insert(a);
}
return false;
}
};Python代码
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
st = set()
for a in nums:
if a in st:
return True
st.add(a)
return False给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
维护一个hash表，边遍历数组边存储值到hash表中，当遍历到nums[i]时，如果hash[target - nums[i]] > 0，那么就找到了符合条件的两个值
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res(2,-1);
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++) {
if(hash.count(target - nums[i]) != 0) {
res[0] = hash[target - nums[i]];
res[1] = i;
break;
}
hash[nums[i]] = i;
}
return res;
}
};Python代码
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路和三数之和类似：先排序数组，遍历数组取第一个数(只到数组倒数第三个元素)，剩下两个数在第一个数的右边部分，定义双指针l和r分别指向i+1和len-1，当前三数和tmp = nums[l] + nums[r] + nums[i]，然后向中间移动，移动规则如下：
- 如果
tmp < target，则++l，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res - 如果
tmp > target，则--r，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res - 如果
tmp == target，则tmp即为所求
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int len = nums.size();
if(len < 3) return INT_MAX;
int res = nums[0] + nums[1] + nums[2];
for(int i=0;i<len-2;i++)
{
if(i == 0 || nums[i] != nums[i-1])
{
int l = i+1,r = len-1;
while(l < r)
{
int tmp = nums[l] + nums[r] + nums[i];
if(tmp < target)
{
res = abs(res - target) < abs(target - tmp) ? res : tmp;
++l;
}
else if(tmp > target)
{
res = abs(res - target) < abs(target - tmp) ? res : tmp;
--r;
}
else{
return tmp;
}
if(i > 0)
{
while(l < r && nums[l] == nums[l-1]) ++l;
while(l < r && nums[r] == nums[r+1]) --r;
}
}
}
}
return res;
}
};Python代码
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if n < 3:
return []
nums.sort()
res = nums[0] + nums[1] + nums[2]
for i in range(n - 2):
if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
l = i + 1
r = n - 1
while l < r:
tmp = nums[i] + nums[l] + nums[r]
if abs(tmp - target) < abs(res - target):
res = tmp
if tmp < target:
l += 1
elif tmp > target:
r -= 1
else:
return tmp
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r - 1] == nums[r]:
r -= 1
if r < n - 1 and nums[r] == nums[r + 1]:
r -= 1
return res给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
对整个数组排序，先遍历数组取三数中的第一个数nums[i]，注意num[i]只到数组的倒数第三个元素，然后剩下两个数需要满足条件target = 0 - nums[i],这两个数在数组中num[i]后面部分，维持两个双指针l和r，令tmp = nums[l] + nums[r]，处理情况如下：
- 如果
tmp < target，则l右移一步； - 如果
tmp > target，则r左移一步； - 否则，满足条件，添加两个数到结果数组中，同时将
l和r分别右移和左移到下一个不重复的元素处。
注意：遍历数组的时候取第一个数的时候过滤重复元素，可以提高查找效率
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
if(len < 3)
return vector<vector<int>>();
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<len-2;i++)
{
if(i == 0 || (i > 0 && nums[i] != nums[i-1]))
{
int l = i+1;
int r = len-1;
int target = 0 - nums[i];
while(l < r)
{
int tmp = nums[l] + nums[r];
if(target > tmp)
{
l++;
}
else if(target < tmp)
{
r--;
}
else{
res.push_back({nums[i],nums[l],nums[r]});
l++;
r--;
while(l < r && nums[l] == nums[l-1])
l++;
while(l < r && nums[r] == nums[r+1])
r--;
}
}
}
}
return res;
}
};Python代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
nums.sort()
for i in range(n - 2):
if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
l = i + 1
r = n - 1
tmp = 0 - nums[i]
while l < r:
if tmp < nums[l] + nums[r]:
r -= 1
elif tmp > nums[l] + nums[r]:
l += 1
else:
res.append([nums[i] , nums[l] , nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
return res给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
双指针，快指针i遍历数组，每当找到下一个不重复的元素即nums[i] != nums[i-1]时，慢指针idx位置的值nums[idx++] = nums[i]（同时idx前进一步）。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
if(len == 0)
return 0;
int index = 1;
for(int i=1;i<len;i++)
{
if(nums[i] != nums[i-1])
nums[index++] = nums[i];
}
while(nums.size() != index)
nums.pop_back();
return index;
}
};给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化
nums1和nums2的元素数量分别为m和n。 - 你可以假设
nums1有足够的空间（空间大小大于或等于m + n）来保存nums2中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
双指针法，思路同合并两个有序链表
- 时间复杂度：O(m + n)
- 空间复杂度：O(m + n)
C++代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i=m,j=0;i<m+n ;i++)
nums1[i] = nums2[j++];
vector<int> vec(m + n,0);
int l = 0;
int r = m;
int cnt = 0;
while(l < m && r < m + n)
{
vec[cnt++] = nums1[l] < nums1[r] ? nums1[l++] : nums1[r++];
}
while(l < m)
vec[cnt++] = nums1[l++];
while(r < m + n)
vec[cnt++] = nums1[r++];
copy(vec.begin(),vec.end(),nums1.begin());
}
};Python代码
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的原地算法。
设数组的长度为len，k对len取模得到k1 = k % len，开辟一个新数组cp拷贝nums，nums的值清空，然后进行如下步骤：
- 将
cp数组的最后k1个元素添加到数组nums尾部 - 将
cp数组的开始len-k1个元素添加到数组nums尾部
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
int k1 = k%len;
vector<int> cp(nums);
nums.clear();
copy(cp.end() - k1,cp.end(),back_inserter(nums));
copy(cp.begin(),cp.end() - k1,back_inserter(nums));
}
};Python代码
设数组的长度为len，k对len取模得到k1 = k % len，然后进行如下步骤：
- 反转数组的最后k1个元素
- 反转数组的前面len - k1个元素
- 反转整个数组
最后得到的数组的就是旋转之后的数组
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(k == nums.size())
return;
int len = nums.size();
int k1 = k % len;
reverse(nums.begin(),nums.end() - k1);
reverse(nums.end() - k1,nums.end());
reverse(nums.begin(),nums.end());
}
};Python代码
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
要求对矩阵顺时针打印，可以分解问题，子问题是对矩阵每层进行顺时针打印。处理子问题知道矩阵每层左上角元素(x1,y1)和右下角元素(x2,y2)的位置即可。
注意：打印的几种特殊情况
(x1,y1)和(x2,y2)在同一行(x1,y1)和(x2,y2)在同一列(x1,y1)和(x2,y2)是同一个元素
-
时间复杂度：O(mn)
-
空间复杂度：O(mn)
C++代码
class Solution {
public:
void solution(int x1,int y1,int x2,int y2,vector<int>& vec,vector<vector<int>>& matrix)
{
int i=x1,j=y1;
if(x1 < x2 && y1 < y2)
{
for(;j<y2;j++)
{
vec.push_back(matrix[i][j]);
}
for(;i<x2;i++)
{
vec.push_back(matrix[i][j]);
}
for(;j>y1;j--)
{
vec.push_back(matrix[i][j]);
}
for(;i>x1;i--)
{
vec.push_back(matrix[i][j]);
}
}
else if(x1 == x2)
{
for(;j<=y2;j++)
vec.push_back(matrix[i][j]);
}
else if(y1 == y2)
{
for(;i<=x2;i++)
vec.push_back(matrix[i][j]);
}
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.empty())
return vector<int>();
vector<int> res;
int m = matrix.size();
int n = matrix[0].size();
int x1 = 0,y1 = 0;
int x2 = m-1,y2 = n-1;
while(x1<=x2 && y1<=y2)
{
solution(x1++,y1++,x2--,y2--,res,matrix);
}
return res;
}
};Python代码
class Solution:
def solution(self,x1,y1,x2,y2,vec:List[int],matrix:List[List[int]]):
i = x1
j = y1
if x1 < x2 and y1 < y2:
while j < y2:
vec.append(matrix[i][j])
j += 1
while i < x2:
vec.append(matrix[i][j])
i += 1
while j > y1:
vec.append(matrix[i][j])
j -= 1
while i > x1:
vec.append(matrix[i][j])
i -= 1
elif x1 == x2:
while j <= y2:
vec.append(matrix[i][j])
j += 1
else:
while i <= x2:
vec.append(matrix[i][j])
i += 1
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if len(matrix) == 0:
return matrix
res = list()
m = len(matrix)
n = len(matrix[0])
x1 = 0
y1 = 0
x2 = m-1
y2 = n-1
while x1 <= x2 and y1 <= y2:
self.solution(x1,y1,x2,y2,res,matrix)
x1 += 1
y1 += 1
x2 -= 1
y2 -= 1
return res给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路和 螺旋矩阵 相同，还是分层处理，不过螺旋矩阵是从矩阵读取值，这一题是写入值到矩阵。可以定义一个变量cnt用于全局计数，直到cnt等于n2的时候终止写入。
- 时间复杂度：O(n2)
- 空间复杂度：O(n2)
C++代码
class Solution {
public:
void setVal(int x1,int y1,int x2,int y2,vector<vector<int>>& vec)
{
if(x1 == x2)
{
for(int i=y1;i<=y2;i++)
{
vec[x1][i] = cnt++;
}
return;
}
if(y1 == y2)
{
for(int i=x1;i<=x2;i++)
{
vec[i][y1] = cnt++;
}
return;
}
for(int i=y1;i<y2;i++)
{
vec[x1][i] = cnt++;
}
for(int i=x1;i<x2;i++)
{
vec[i][y2] = cnt++;
}
for(int i=y2;i>y1;i--)
{
vec[x2][i] = cnt++;
}
for(int i=x2;i>x1;i--)
{
vec[i][y1] = cnt++;
}
}
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res;
if(n == 0) return res;
cnt = 1;
const int sum = n*n;
res.resize(n,vector<int>(n));
int x1 = 0,y1 = 0,x2 = n-1,y2 = n-1;
while(x1 <= x2 && y1 <= y2)
{
setVal(x1++,y1++,x2--,y2--,res);
}
return res;
}
private:
int cnt;
};Python代码
class Solution:
def solution(self,x1,y1,x2,y2,matrix:List[List[int]],cnt) -> int:
i = x1
j = y1
if x1 < x2 and y1 < y2:
while j < y2:
matrix[i][j] = cnt
cnt += 1
j += 1
while i < x2:
matrix[i][j] = cnt
cnt += 1
i += 1
while j > y1:
matrix[i][j] = cnt
cnt += 1
j -= 1
while i > x1:
matrix[i][j] = cnt
cnt += 1
i -= 1
elif x1 == x2:
while j <= y2:
matrix[i][j] = cnt
cnt += 1
j += 1
else:
while i <= x2:
matrix[i][j] = cnt
cnt += 1
i += 1
return cnt
def generateMatrix(self, n: int) -> List[List[int]]:
if n == 0:
return [[]]
cnt = 1
res = [[0]*n for i in range(n)]
x1 = 0
y1 = 0
x2 = n - 1
y2 = n - 1
while x1 <= x2 and y1 <= y2:
cnt = self.solution(x1,y1,x2,y2,res,cnt)
x1 += 1
y1 += 1
x2 -= 1
y2 -= 1
return res给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
对矩阵顺时针旋转90度，可以分解为子问题：对矩阵的每一层顺时针旋转。这时候问题就简化了，矩阵的单层顺时针旋转相当于将这一层四边的元素一次进行替换即可。例如，先保存左边的元素，然后上边替换左边，右边替换上边，下边替换右边，之前保存的元素替换下边。
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
void rotate_circle(int x1,int y1,int x2,int y2,vector<vector<int>>& vec)
{
vector<int> tmp;
for(int i=x1;i<x2;i++)
{
tmp.push_back(vec[i][y1]);
}
int i = x2 - 1;
int j = y2 - 1;
while(i >= x1 && j >= y1)
{
vec[i--][y1] = vec[x2][j--];
}
i = x1 + 1;
j = y2 - 1;
while(j >= y1 && i <= x2)
{
vec[x2][j--] = vec[i++][y2];
}
i = x1 + 1;
j = y1 + 1;
while(i <= x2)
{
vec[i++][y2] = vec[x1][j++];
}
j = y2;
i = 0;
while(j > y1)
{
vec[x1][j--] = tmp[i++];
}
}
void rotate(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
int a1 = 0,b1 = 0;
int a2 = row - 1,b2 = col - 1;
while(a1 < a2 && b1 < b2)
{
rotate_circle(a1++,b1++,a2--,b2--,matrix);
}
}
};Python代码
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
matrix[:] = list(zip(*matrix[::-1]))给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
遍历数组，判断当前元素nums[i]是否和位置i+1相等：
- 如果
nums[i] == i+1，则nums[i]位于它自己的位置，++i遍历下一个元素； - 否则，找到位置是
nums[i]-1位置的元素nums[nums[i] - 1]：- 如果
nums[nums[i] - 1] == nums[i],则找到重复元素nums[i] - 否则，交换
nums[nums[i] - 1]和nums[i]
重复情况2的过程，直到nums[i] == i+1时，执行情况1。
- 如果
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int findDuplicate(vector<int>& nums) {
if(nums.empty())
return 0;
for(int i=0;i<nums.size();i++)
{
while(nums[i] != i+1)
{
int tmp = nums[i];
if(nums[tmp-1] == tmp)
return tmp;
swap(nums[i],nums[tmp-1]);
}
}
return -1;
}
};Python代码
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
if len(nums) <= 0:
return False
for i in range(len(nums)):
while i != nums[i]:
m = nums[i]
if m == nums[m]:
return m
else:
a = nums[i]
nums[i] = nums[m]
nums[m] = a
return False给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
由于output[i] = nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*...*nums[len-1],可以将output[i]分为两部分，前半部分为C[i] = nums[0]*nums[1]*...*nums[i-1],后半部分为D[i] = nums[i+1]*...*nums[len-1]。可以发现规律，数组C和D相邻元素之间存在递推关系：
C[i] = C[i-1]*nums[i-1] (i = 1~len-1)
D[i] = D[i+1]*nums[i+1] (i = 0~len-2)
因此求出数组output的每一项output[i] = C[i]*D[i]。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
if(len == 0) return nums;
vector<int> res(len,1);
vector<int> C(len,1);
vector<int> D(len,1);
for(int i=1;i<len;i++)
{
C[i] = nums[i-1]*C[i-1];
}
for(int i=len-2;i>=0;i--)
{
D[i] = D[i+1]*nums[i+1];
}
for(int i=0;i<len;i++)
{
res[i] = C[i]*D[i];
}
return res;
}
};Python代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
nums_l,nums_r = [1 for x in range(n)],[1 for x in range(n)]
res = []
for i in range(1,n):
nums_l[i] = nums_l[i-1] * nums[i-1]
for i in range(n - 2,-1,-1):
nums_r[i] = nums_r[i + 1] * nums[i + 1]
for i in range(n):
res.append(nums_l[i] * nums_r[i])
return res先将数组C的数值计算到输出数组res中，然后定义一个变量tmp代替数组D的递推关系计算，对数组res从后向前进行递推计算得出最终结果。可以优化空间复杂度到常数时间。
- 时间复杂度：O(n) (输出数组不被视为额外空间)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
if(len == 0) return nums;
vector<int> res(len,1);
for(int i=1;i<len;i++)
{
res[i] = res[i-1] * nums[i-1];
}
int tmp = 1;
for(int i=len-2;i>=0;i--)
{
tmp *= nums[i+1];
res[i] *= tmp;
}
return res;
}
};Python代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [1 for x in range(n)]
for i in range(1,n):
res[i] = nums[i-1] * res[i-1]
tmp = 1
for i in range(n - 1,-1,-1):
res[i] *= tmp
tmp *= nums[i]
return res给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
- 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
定义两个标记数组row和col(类型bool),如果矩阵第i行的数字存在0，那么置位row[i]为true，如果矩阵第j列的数字存在0，那么置位col[j]为true。然后，遍历矩阵的每一个元素matrix[i][j]，如果row[i]和col[j]中有一个是true，则置matrix[i][j]为0。
- 时间复杂度：O(mn)
- 空间复杂度：O(m + n)
C++代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int h = matrix.size();
int l = matrix[0].size();
vector<bool> row(h,false),col(l,false);
for(int i=0;i<h;i++)
for(int j=0;j<l;j++)
{
if(matrix[i][j] == 0)
{
row[i] = true;
col[j] = true;
}
}
for(int i=0;i<h;i++)
{
for(int j=0;j<l;j++)
{
if(row[i])
matrix[i][j] = 0;
if(col[j])
matrix[i][j] = 0;
}
}
}
};Python代码
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
dt_h,dt_l = dict(),dict()
m,n = len(matrix),len(matrix[0])
for i in range(m):
dt_h[i] = False
for i in range(n):
dt_l[i] = False
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
dt_h[i] = True
dt_l[j] = True
for i in range(m):
for j in range(n):
if dt_h[i] or dt_l[j]:
matrix[i][j] = 0
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
双指针法，定义两个指针l和r分别指向数组两端，两个指针向中间移动，移动规则如下：
- 如果height[l] < height[r]，则++l
- 否则，--r
每走一步，计算容器装水量为左右边缘较小的那个高度乘边缘的的距离min(height[l],height[r]) * (r - l),然后和结果比较去较大值。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int maxArea(vector<int>& height) {
int len = height.size();
if(len == 0) return 0;
int res = 0;
int l = 0;
int r = len - 1;
while(l < r)
{
int tmp = min(height[l],height[r]);
int sum = (r - l)*tmp;
if(height[l] < height[r])
++l;
else
--r;
res = max(res,sum);
while(l < r && tmp == height[l]) ++l;
while(l < r && tmp == height[r]) --r;
}
return res;
}
};Python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
l = 0
r = n - 1
res = 0
while l < r:
tmp = min(height[l],height[r])
res = max(res,(r - l) * tmp)
if height[l] < height[r]:
l += 1
else:
r -= 1
while l < r and tmp == height[l]:
l += 1
while l < r and tmp == height[r]:
r -= 1
return res给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
现将数组元素按照区间起点大小从小到大进行排序，遍历数组，将元素放入结果数组res中，同时比较结果数组中末尾元素的区间终点tail和当前元素interval[i]的区间起点：
- 如果
tail >= intervals[i].start，则区间出现重叠，更新结果数组res末尾元素的区间终点为tail和intervals[i]的较大值； - 如果
tail < intervals[i].start，则区间为重叠，加入intervals[i]到结果数组res。
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
C++代码
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
int len = intervals.size();
if(len == 0 || len == 1)
return intervals;
sort(intervals.begin(),intervals.end(),
[](const Interval& a,const Interval& b)
{
return a.start<b.start;
});
vector<Interval> res;
res.push_back(intervals[0]);
for(int i=1;i<len;i++)
{
int tail = res.back().end;
if(intervals[i].start <= tail)
{
res[res.size() - 1].end = max(tail,intervals[i].end);
}
else
res.push_back(intervals[i]);
}
return res;
}
};Python代码
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
此题需要找出规律，举一个例子来说明，有如下的一个数组
1 2 7 4 3 1
下一个排列为：
1 3 1 2 4 7
那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再以这个2的位置的后一个位置开始，从前往后找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字（不包括3的位置）反转一下即可，步骤如下：
1 2 7 4 3 1
1 2 7 4 3 1
1 3 7 4 2 1
1 3 1 2 4 7
再举几个例子验证仍然符合这个规律。因此，处理过程可总结以下几个步骤：
- 从后往前遍历数组，找到数值开始减小的那个位置
idx，即nums[idx-1] < nums[idx]； - 令
idx_l = idx-1，从idx位置从前往后移动直到找到最后一个数值大于nums[idx_l]的元素； - 交换
nums[idx_l]和nums[idx]的值； - 反转数组在
idx位置之后的所有元素。
最后，就可以得到下一个排列。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int len = nums.size();
if(len <= 0)
return;
int idx = len - 1;
for(;idx >= 1 && nums[idx-1] >= nums[idx];idx--);
if(idx == 0)
{
reverse(nums.begin(),nums.end());
return;
}
int idx_l = idx - 1;
for(int i=idx;idx<len;idx++)
{
if(nums[idx] <= nums[idx_l])
break;
}
swap(nums[idx-1],nums[idx_l]);
reverse(nums.begin() + idx_l + 1,nums.end());
return;
}
};Python代码
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
使用unordered_set结构的集合st装入nums中的元素，同时找到nums元素的最大值Max，然后遍历1~Max范围内的数，找到第一个不在集合st中数就是缺失的第一个正数，如果都在集合st中，那么缺失的第一个正数就在1和Max+1的较小值中取得。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> st;
int Max = INT_MIN;
for(auto a : nums)
{
st.insert(a);
Max = max(Max,a);
}
for(int i=1;i<=Max;i++)
{
if(st.count(i) == 0)
return i;
}
return max(Max + 1,1);
}
};Python代码
对于大小为n（n>0）的数组，这n个数可以分为以下几种情况：
- 这n个数都小于等于0
- 这n个数都大于n
- 存在一个或多个位于[1,n]的数
对于情况1和情况2，要查找的第一个缺失的正数就是1；
问题是对于情况3应该怎么考虑呢？
假设这些位于[1,n]的数i，在数组中的位置应该为i-1，而小于等于0的数，以及大于n的数，在数组剩余位置：
- 如果数组所有的数都在
[1,n]，那么每个元素都在其值减1的位置，此时要找的第一个缺失的整数就是n+1； - 否则，数组中，必然存在一个位置
idx，其元素值不等于idx+1，而范围[1,n]就是正数序列最开始的n个数，因此，从左往右查找第一个下标加1不等于值的位置，那么要找的第一个缺失的正数就是该位置的下标加1。
注意：交换元素的方法可以将范围在[1,n]的元素放置到正确的位置,详见 寻找重复数
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
if(len == 0) return 1;
for(int i=0;i<len;i++)
{
while(nums[i] > 0 && nums[i] <= len && nums[i] != i+1 && nums[nums[i] - 1] != nums[i])
{
swap(nums[nums[i] - 1],nums[i]);
}
}
for(int i=0;i<len;i++)
{
if(nums[i] != i + 1)
return i + 1;
}
return len + 1;
}
};给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
双指针法，设置指针i和j分别指向字符串s和t
- 如果
s[i] == t[j]，则i前进一步，j前进一步 - 否则，
j前进一步
最后，判断指针i是否走完s，就能判断s是否为t的子序列。
- 时间复杂度：O(m+n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
bool isSubsequence(string s, string t) {
int len = s.size();
int len1 = t.size();
if(len > len1) return false;
int i = 0,j = 0;
while(i < len && j < len1)
{
if(s[i] == t[j])
{
i++;
}
j++;
}
if(i == len) return true;
return false;
}
};Python代码
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
根据二维矩阵的排序规律，从矩阵的右上角开始搜索矩阵元素matrix[i][j]：
- 如果
target > matrix[i][j]，i++往下移动一行； - 如果
target < matrix[i][j]，j--往左移动一行； - 否则，找到
target。
设二维矩阵的行数为m，列数为n
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
C++代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty())
return false;
int row = matrix.size();
int col = matrix[0].size();
int i = 0;
int j = col-1;
while(i < row && j >= 0)
{
if(target > matrix[i][j])
{
i++;
}
else if(target < matrix[i][j])
{
j--;
}
else
return true;
}
return false;
}
};Python代码
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0:
return False
m,n = len(matrix),len(matrix[0])
i,j = 0,n - 1
while i < m and j >= 0:
if target < matrix[i][j]:
j -= 1
elif target > matrix[i][j]:
i += 1
else:
return True
return False判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫格内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符'.'。 - 给定数独永远是
9x9形式的。
要判断是否出现重复元素，只需要遍历的时候用哈希表记录每一个字符ch(介于'1'~'9'之间)出现的次数，当字符再次出现的时候判断ch在哈希表中的次数是否大于0，就可以判断是否出现重复的字符。由于在每一行、每一列和每一个3x3宫格内都不能出现重复的字符，那么需要以逐行、逐列和逐个3x3宫格的方式分别遍历，同时利用哈希表记录并判断，便能得出结果。
- 时间复杂度：O(9x9) = O(1)
- 空间复杂度：O(9) = O(1)
C++代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_map<char,int> mp;
int row = board.size();
int col = board[0].size();
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
int ch = board[i][j];
if(ch != '.')
{
mp[ch]++;
if(mp[ch] > 1)
return false;
}
}
mp.clear();
}
for(int i=0;i<col;i++)
{
for(int j=0;j<row;j++)
{
char ch = board[j][i];
if(ch != '.')
{
mp[ch]++;
if(mp[ch] > 1)
return false;
}
}
mp.clear();
}
for(int i=0;i<row;i+=3)
{
for(int j=0;j<col;j+=3)
{
for(int x=i;x<i+3;x++)
for(int y=j;y<j+3;y++)
{
char ch=board[x][y];
if(ch != '.')
{
mp[ch]++;
if(mp[ch] > 1)
return false;
}
}
mp.clear();
}
}
return true;
}
};Python代码
双指针
Python代码
class Solution:
def fourSum(self, nums: list, target: int) -> list:
nums.sort()
if len(nums) < 4:
return []
idx1 = 0
out_list = []
while idx1 < len(nums) - 3:
idx2 = idx1 + 1
while idx2 < len(nums) - 2:
target_tmp = target - nums[idx1] - nums[idx2]
l = idx2 + 1
r = len(nums) - 1
while l < r:
if target_tmp > nums[l] + nums[r]:
l += 1
elif target_tmp < nums[l] + nums[r]:
r -= 1
else:
tmp_list = [nums[idx1], nums[idx2], nums[l], nums[r]]
if tmp_list not in out_list:
out_list.append(tmp_list)
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r - 1] == nums[r]:
r -= 1
l += 1
r -= 1
idx2 += 1
while idx2 < len(nums) - 2 and nums[idx2] == nums[idx2 - 1]:
idx2 += 1
idx1 += 1
while idx1 < len(nums) - 3 and nums[idx1] == nums[idx1 - 1]:
idx1 += 1
return out_list摩尔投票法 要求 > N / k为众数，则这样的数最多有k - 1个 因此维护两个候选变量cand1和cand2 两个阶段，抵消 + 计数 cand1和cand2的初始值任意，这里设为0 只要发现有计数为0，则马上更新新的cand 每考察到一个数，只有以下5种情况
是cand1，则计数器++ 是cand2，则计数器++ 都不是，且两个计数器都 > 0，则两个计数器-- 都不是，且count1是0，则让新的数成为cand1，且count1++ 都不是，且count2是0，则让新的数成为cand2，且count2++ 易错点 本质上是三个一比 当且仅当碰到的数既不是cand1也不是cand2，且两个计数器都 > 0时，计数器才会--，其他情况一律不减 cand1和cand2可能一样，所以在计数阶段每个数只能算到一个候选人头上，即必须用if else语句
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res{};
int res1, res2, cnt1, cnt2;
res1 = res2 = cnt1 = cnt2 = 0;
for (const auto& a : nums) {
if (a == res1) ++cnt1;
else if (a == res2) ++cnt2;
else if (cnt1 > 0 && cnt2 > 0) {
--cnt1;
--cnt2;
} else if (cnt1 == 0) {
res1 = a;
++cnt1;
} else {
res2 = a;
++cnt2;
}
}
cnt1 = 0, cnt2 = 0;
for (const auto& a : nums) {
if (a == res1) ++cnt1;
else if (a == res2) ++cnt2;
}
if (cnt1 > nums.size() / 3) res.push_back(res1);
if (cnt2 > nums.size() / 3) res.push_back(res2);
return res;
}
};