排序
快速排序
#include <iostream>
#include <vector>
using namespace std;
// 快速排序函数，传入引用，以便修改原始数组
void quick_sort(vector<int>& q, int l, int r) {
// 边界条件：如果左边界大于等于右边界，说明已排序完成
if (l >= r) return;
// 初始化双指针，i从左向右移动，j从右向左移动
int i = l - 1, j = r + 1;
// 选择中间值作为基准值
int mid = q[(l + r) >> 1]; // (l + r) >> 1 相当于 (l + r) / 2
while (i < j) {
// 从左向右找到第一个大于等于基准值的元素
do i++; while (q[i] < mid);
// 从右向左找到第一个小于等于基准值的元素
do j--; while (q[j] > mid);
// 如果i小于j，交换它们的位置，确保左边的元素小于等于基准值，右边的元素大于等于基准值
if (i < j) swap(q[i], q[j]);
}
// 递归排序左半部分和右半部分
quick_sort(q, l, j); // 对左半部分排序
quick_sort(q, j + 1, r); // 对右半部分排序
}
int main() {
// 输入
int n;
cin >> n;
vector<int> q(n);
for (int i = 0; i < n; i++) {
cin >> q[i];
}
// 排序
quick_sort(q, 0, n - 1); // 调用快速排序函数对整个数组排序
// 输出
for (int i = 0; i < n; i++) {
cout << q[i] << " "; // 打印排序后的数组
}
return 0;
}
哈希
1.两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
// 看能否找到 nums[i]，it返回索引
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
// 如果能找到
return {it->second, i};
}
// 记录每个数字的索引
hashtable[nums[i]] = i;
}
return {};
}
};
2. 49 字母异位词
class Solution:
def groupAnagrams(self, strs):
mp = {}
for str in strs:
# sorted 后是个列表，需要''.join一下
key = ''.join(sorted(str))
if key not in mp:
# 第一次遍历到，就创建一个[]
mp[key] = []
mp[key].append(str)
ans = []
for value in mp.values():
ans.append(value)
return ans
3. 128 最长连续序列
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 不重复的集合
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num);
}
int longestStreak = 0;
for (const int& num : num_set) {
// 找前一位
if (!num_set.count(num - 1)) {
// 设置起始数字
int currentNum = num;
// 长度初始化为 1
int currentStreak = 1;
// 只要能找到下一个位置的数
while (num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// 更新最长长度
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
双指针
283 移动0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int indexNow = 0; // 赋值
int indexNum = 0;
int m = nums.size();
// 初始化双指针指向 index 0
// indexNum 扫描是否为 0
// 如果不为 0 就交换，并递增 Now（始终指向0）
// 如果为 0，递增indexNum (始终指向非0，或下一个元素)
while(indexNum < m) {
if (nums[indexNum] != 0) {
nums[indexNow++] = nums[indexNum];
}
++indexNum;
}
for (int i = indexNow; i < m; i++) {
nums[i] = 0;
}
}
};
11 盛水最多的容器
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int maxV = 0;
while (l < r) {
int len = r - l;
maxV = max(min(height[l], height[r]) * len, maxV);
// 收缩小的那一边
if (height[l] <= height[r]) {
++l;
} else {
--r;
}
}
return maxV;
}
};
15 三数之和
class Solution:
def threeSum(self, nums):
# 对数组进行排序
nums.sort()
n = len(nums)
res = []
# 遍历数组，以first作为第一个元素的指针
for first in range(n):
# 跳过重复元素，避免重复解
if first >= 1 and nums[first] == nums[first - 1]:
continue
# 初始化第三个元素的指针，从数组末尾开始
third = n - 1
# 目标和为当前first元素的相反数
target = -nums[first]
# 遍历数组中剩下的元素，以second作为第二个元素的指针
for second in range(first + 1, n):
# 跳过重复元素，避免重复解
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 调整third指针，使得nums[first] + nums[second] + nums[third]接近于0
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果second和third重合，退出循环
if second == third:
break
# 如果找到满足条件的组合，添加到结果列表中
if nums[second] + nums[third] == target:
res.append([nums[first], nums[second], nums[third]])
return res
42 接雨水
class Solution {
public:
int trap(vector<int>& height) {
// 初始化左右两侧的最大高度
int leftMax = 0;
int rightMax = 0;
int l = 0, r = height.size() - 1;
int ans = 0;
while(l < r) {
// 更新左右两边最大值
leftMax = max(leftMax, height[l]);
rightMax = max(rightMax, height[r]);
// 用高度的较小值更新
if (height[l] < height[r]) {
ans += leftMax - height[l];
l++;
}else {
ans += rightMax - height[r];
r--;
}
}
return ans;
}
};
滑动窗口
3.无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s):
# 使用一个布尔数组来标记字符是否出现过
occ = [False] * 200
n = len(s)
res = 0
# 使用滑动窗口的方法，l 和 r 分别表示窗口的左右边界
l, r = 0, 0
# 扩展右窗口
while r < n:
# 是否循环收缩左窗口？
# 如果字符 s[r] 在窗口中已存在
# 则移动左边界 l，直到 s[r] 不在窗口中
while occ[ord(s[r])] and l < r:
occ[ord(s[l])] = False
l += 1
# 标记字符 s[r] 在窗口中出现
occ[ord(s[r])] = True
# 更新最大子串长度
res = max(res, r - l + 1)
# 移动右边界，扩大窗口
r += 1
return res
438 找到字符串中所有字母异位词
class Solution:
def findAnagrams(self, s, p):
# 获取字符串 s 和 p 的长度
m, n = len(s), len(p)
# 如果 s 比 p 短，返回空列表
if m < n:
return []
# 初始化检查表，记录 p 中每个字符的出现次数
checkTable = [0] * 26
for ch in p:
checkTable[ord(ch) - ord('a')] += 1
ret = []
l, r = 0, 0
while r < m:
# 移动右指针 r，更新检查表
checkTable[ord(s[r]) - ord('a')] -= 1
# 如果某个字符的计数小于0，移动左指针 l，直至计数不小于0
while checkTable[ord(s[r]) - ord('a')] < 0:
checkTable[ord(s[l]) - ord('a')] += 1
l += 1
# 如果当前窗口大小等于 p 的长度，记录起始位置
if r - l + 1 == n:
ret.append(l)
r += 1
return ret
