算法学习
滑动窗口&双指针
✅ 一、“最多”类问题 —— 常见逻辑是:
✅ 窗口尽量扩大,然后只要条件超了,就收缩左边
🧩 示例: • 最多两个不同水果(Leetcode 904) • 最多有 k 个 0 的最长子数组 • 转换字符开销不超过 maxCost 的最长子字符串
🧠 思路流程: 1. 右边 end++ 不断扩展窗口 2. 当**“非法值”超出限制**时(例如出现了第三种水果,或者 0 超过了 1 个) • 左边 start++ 缩小窗口直到满足条件 3. 每一步都记录满足条件的最大窗口长度
🔁 关键词: • 最多 • 不超过 k 个 • 总和不超过 X • 转换成本 ≤ maxCost
✅ 更新答案的时机:
在满足条件的窗口内,每一步都可以更新最大值
✅ 二、“最少”类问题 —— 常见逻辑是:
✅ 一旦窗口满足条件,开始尝试缩小窗口以找到最小值
🧩 示例: • 长度最小的子数组(和 ≥ target) • 最短包含所有字符的子串(滑窗 + 哈希表) • 最短覆盖所有种类的窗口
🧠 思路流程: 1. 右边 end++ 扩展窗口直到满足条件 2. 一旦满足条件: • 开始移动 start++ 来缩小窗口,直到不满足 • 每次满足时更新最小值
🔁 关键词: • 至少 • 和 ≥ target • 最短包含所有字母 • 最小覆盖子串
✅ 更新答案的时机:
只在满足条件的那一刻更新最小值
二分查找
搜索插入位置
原题:leetcode35.搜索插入位置
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
解题思路
二分法思路比较简单,难的是处理边界条件。
首先判断插入情况,分为以下几种:
- target = mid,不用插值,返回 mid。
- target > mid && target< mid+1 ,插值返回 mid+1
- target 在所有元素之前
- target 在所有元素之后
class Solution {
public int searchInsert(int[] nums, int target) {
int right = nums.length - 1;
int left = 0;
int n = 0;
if(target > nums[right]) {
return right + 1;
}
while(left < right) {
int mid = left + (right - left) / 2;
if(target == nums[mid]) {
return mid;
} else if(target > nums[mid] && target < nums[mid+1]) {
return mid + 1;
} else if(target > nums[mid]) {
left = mid + 1;
} else if(target < nums[mid]) {
right = mid - 1;
}
}
return target > nums[left] ? left + 1 : left;
}
}
Grind 75
符号匹配校验
思路:模拟栈,遍历数组,遇到左边符号压入,右边弹出上一个匹配
function isValid(s: string): boolean {
let map = new Map();
map.set('(',')');
map.set('[',']');
map.set('{','}');
let stacKArr:string[] = []
if(!map.has(s[0])||map.has(s.charAt(s.length -1))){
return false
}
for(let char of s){
if(map.has(char)){
stacKArr.push(char)
}else{
var last = stacKArr.pop()
if(map.get(last)!=char){
return false
}
}
}
return true
};
优化思路:
function isValid(s: string): boolean {
let map = new Map();
map.set('(',')');
map.set('[',']');
map.set('{','}');
let stacKArr:string[] = []
if(!map.has(s[0])||map.has(s.charAt(s.length -1))){
return false
}
for(let char of s){
if(map.has(char)){
stacKArr.push(char)
}else{
var last = stacKArr.pop()
if(map.get(last)!=char){
return false
}
}
}
return true
};
数组融合排序
模拟链表
class ListNode {
next:ListNode|null
val:number
constructor(val:number,next:ListNode|null){
this.val = val === undefined?0:val;
this.next = (next===undefined ? null : next)
}
}
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode|null {
let dump = ListNode[0]
while(list2?.next&&list1?.next){
if(list1?.val>list2.val){
dump.next = list2
list2 = list2.next
}else{
dump.next = list1
list1 = list1.next // 想在跳转外部
}
}
return dump;
};
股票最高利润
思路: 动态更新最低价格和最高利润
function maxProfit(prices: number[]): number {
if(prices.length<=1){
return 0;
}
let minPrice:number = prices[0];
let maxProfit:number = 0;
for(let i = 0; i< prices.length;i++){
if(minPrice>prices[i]){
minPrice = prices[i];
}
if(maxProfit<prices[i]- minPrice){
maxProfit = prices[i]- minPrice
}
}
return maxProfit
};
回溯算法
算法框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
DFS 和 BFS
DFS用于穷举全部路径,BFS用于寻找最短路径