1、数组/链表
1、前缀和数组技巧
- 区域和检索 - 数组不可变（中等）
- 二维区域和检索 - 矩阵不可变（中等）
- 和为K的子数组（中等）
class PrefixSum {
// 前缀和数组
private int[] prefix;
/* 输⼊⼀个数组，构造前缀和 */
public PrefixSum(int[] nums) {
prefix = new int[nums.length 1];
// 计算 nums 的累加和
for (int i = 1; i < prefix.length; i ) {
prefix[i] = prefix[i - 1] nums[i - 1];
}
}
/* 查询闭区间 [i, j] 的累加和 */
public int query(int i, int j) {
return prefix[j 1] - prefix[i];
}
}class NumMatrix {
// preSum[i][j] 记录矩阵 [0, 0, i, j] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
if (m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = new int[m 1][n 1];
for (int i = 1; i <= m; i ) {
for (int j = 1; j <= n; j ) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i-1][j] preSum[i][j-1] matrix[i - 1][j - 1] - preSum[i-1][j-1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[x2 1][y2 1] - preSum[x1][y2 1] - preSum[x2 1][y1] preSum[x1][y1];
}
}2、差分数组技巧
- 区间加法（中等）
- 航班预订统计（中等）
- 拼车（中等）
// 差分数组⼯具类
class Difference {
// 差分数组
private int[] diff;
/* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏ */
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i ) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] = val;
if (j 1 < diff.length) {
diff[j 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i ) {
res[i] = res[i - 1] diff[i];
}
return res;
}
}3、双指针技巧秒杀七道链表题目
- 合并两个有序链表（简单）
- 合并K个升序链表（困难）
- 环形链表（简单）
- 环形链表 II（中等）
- 链表的中间结点（简单）
- 相交链表（简单）
- 删除链表的倒数第 N 个结点（中等）
1、合并两个有序链表
代码语言：java复制ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}k个有序链表">2、合并<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">k</font>个有序链表
代码语言：java复制class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (0 == lists.length) return null;
ListNode mp = new ListNode(-1), p = mp;
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, (a, b) -> (a.val - b.val));
for (ListNode node : lists) {
if (null != node) {
pq.add(node);
}
}
while (!pq.isEmpty()) {
ListNode node = pq.poll();
if (null != node) {
p.next = node;
}
if (node.next != null) {
pq.add(node.next);
}
p = p.next;
}
return mp.next;
}
}k个节点">3、寻找单链表的倒数第<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">k</font>个节点
代码语言：java复制// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i ) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点，也就是倒数第k个元素
return p2;
}删除倒数第n个元素
代码语言：java复制class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头节点 防止null指针异常
ListNode mp = new ListNode(-1);
mp.next = head;
// 删除倒数第 n 个，要先找倒数第 n 1 个节点
ListNode node = findNodeFromEnd(mp, n 1);
if (null != node) {
// 删掉倒数第 n 个节点
node.next = node.next.next;
}
return mp.next;
}
public ListNode findNodeFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1先走k步
for (int i = 0; i < k; i ) {
p1 = p1.next;
}
ListNode p2 = head;
while (null != p1) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}4、寻找单链表的中点
代码语言：java复制ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}5、判断单链表是否包含环并找出环起点
代码语言：java复制boolean hasCycle(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇，说明含有环
if (slow == fast) {
return true;
}
}
// 不包含环
return false;
}ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}6、判断两个单链表是否相交并找出交点
代码语言：java复制 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}4、双指针技巧秒杀七道数组题目
- 删除有序数组中的重复项（简单）
- 删除排序链表中的重复元素（简单）
- 两数之和 II - 输入有序数组（中等）
- 移除元素（简单）
- 移动零（简单）
- 反转字符串（简单）
- 最长回文子串（中等）
1、快慢指针技巧
代码语言：java复制int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow ;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast ;
}
// 数组长度为索引 1
return slow 1;
}ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow ;
slow = slow.next;
}
// fast
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
} void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
int p = removeElement(nums, 0);
// 将 nums[p..] 的元素赋值为 0
for (; p < nums.length; p ) {
nums[p] = 0;
}
}
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow ] = nums[fast];
}
fast ;
}
return slow;
}2、左右指针的常用算法
1、二分查找
代码语言：java复制int binarySearch(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (right left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}2、求两数之和
代码语言：java复制int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left 1, right 1};
} else if (sum < target) {
left ; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}3、反转数组
代码语言：java复制void reverseString(char[] s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length - 1;
while (left < right) {
// 交换 s[left] 和 s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left ;
right--;
}
}4、回文串判断
代码语言：java复制class Solution {
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i ) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i 1] 为中心的最长回文子串
String s2 = palindrome(s, i, i 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 双指针，向两边展开
l--;
r ;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l 1, r);
}
}5、我写了首诗，把滑动窗口算法算法变成了默写题
- 最小覆盖子串（困难）
- 字符串的排列（中等）
- 找到字符串中所有字母异位词（中等）
- 无重复字符的最长子串（中等）
思考：现在开始套模板，只需要思考以下四个问题：
1、当移动<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">right</font>扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">left</font>缩小窗口？
3、当移动<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">left</font>缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
代码语言：java复制public String minWindow(String s, String t) {
//目标字符表
HashMap<Character, Integer> need = new HashMap<Character, Integer>();
//填充数据，注意此处，一定要 1，因为可能有重复元素！！！
for (char c : t.toCharArray())
need.put(c, need.getOrDefault(c, 0) 1);
//记录窗口当前的目标字符情况 窗口字符表
HashMap<Character, Integer> window = new HashMap<Character, Integer>();
// 窗口左右下标
int left = 0, right = 0;
// 表示窗口中满足need条件的字符个数
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
// 开始滑动
while (right < s.length()) {
//进入窗口的字符
char c = s.charAt(right);
// 扩大窗口
right ;
// 判断字符是否是目标字符
if (need.containsKey(c)) {
//如果是目标字符 进入windows字符记录表且数量 1，注意此处的先添加再对比！！！注意代码顺序
window.put(c, window.getOrDefault(c, 0) 1);
//判断目标字符的数量是否相等
if (window.get(c).equals(need.get(c))) {
valid ;
}
}
//目标字符一样且数量相等时 左侧窗口要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left < len) {//不断“打擂”找满足条件的len最短值,并记录最短的子串的起始位序start
len = right - left;
start = left;
}
char d = s.charAt(left);
left ;
// 判断字符是否是目标字符
if (need.containsKey(d)) {
//判断目标字符的数量是否相等
if (window.get(d).equals(need.get(d))) {
valid--;
}
//如果是目标字符 windows字符记录表且数量-1，注意此处的先对比再减去！！！注意代码顺序
//window.put(d,window.get(d)-1);——bug：若一进去就将window对应的键值缩小，
//就永远不会满足下面的if，while也会一直执行，直到left越界，因此，尽管和上面对窗口的处理几乎一样，但是这个处理的顺序还是很关键的！要细心！
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ? "" : s.substring(start, start len);
}class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> need = new HashMap<>();
for (char c : s1.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) 1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0, count = 0;
while (right < s2.length()) {
char c = s2.charAt(right );
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) 1);
if (window.get(c).equals(need.get(c))) {
count ;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= s1.length()) {
//判断是否满足条件
if (count == need.size())
return true;
char d = s2.charAt(left );
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
count--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
// 未找到符合条件的子串
return false;
}
}class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
HashMap<Character, Integer> need = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) 1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0, count = 0;
while (right < s.length()) {
char c = s.charAt(right );
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) 1);
if (window.get(c).equals(need.get(c)))
count ;
}
while (right - left >= p.length()) {
if (count == need.size())
res.add(left);
char d = s.charAt(left );
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d)))
count--;
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
return res;
}
}class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()) {
char c = s.charAt(right );
window.put(c, window.getOrDefault(c, 0) 1);
//大于1说明有重复，需要缩小窗口
while (window.get(c) > 1) {
char d = s.charAt(left );
window.put(d, window.getOrDefault(d, 0) - 1);
}
//缩小后代表没有重复元素了，然后取最大值即可
res = Math.max(res, right - left);
}
return res;
}
}6、我写了首诗，把二分搜索变成了默写题
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 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 if (nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 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 if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
// left >= nums.length 防止target大于所有元素
// nums[left] != target 防止target小于所有元素
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 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 if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid 1;
}
}
// 最后要检查 right 越界的情况，
// right < 0 防止target小于数组所有元素，
// nums[right] != target 防止target大于所有元素
if (right < 0 || nums[right] != target)
return -1;
return right;
}7、二分搜索题型套路分析
8、田忌赛马背后的算法决策
<font style="color:rgb(89, 89, 89);">870 题「优势洗牌」</font>
代码语言：java复制class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
//num2优先级队列降序
PriorityQueue<int[]> maxpq = new PriorityQueue<>(
(int[] pair1, int[] pair2) -> {
return pair2[1] - pair1[1];
}
);
for (int i = 0; i < nums2.length; i ) {
maxpq.offer(new int[]{i, nums2[i]});
}
//num1 升序
Arrays.sort(nums1);
int[] res = new int[nums1.length];
int left = 0, right = nums1.length - 1;
while (!maxpq.isEmpty()) {
int[] pair = maxpq.poll();
int index = pair[0], maxval = pair[1];
//不能使用最强的马对阵对方最强的马，也不能使用自己最弱的马对阵对方最强的马
//先判断自己最强的马能不能战胜对方最强的，能的话亲自上阵，
//不能的话使用自己最弱的马抵消对方最强的马
if (maxval < nums1[right]) {
res[index] = nums1[right--];//亲自上阵
} else {
res[index] = nums1[left ];//送分
}
}
return res;
}
}9、链表操作的递归思维一览
206反转链表
92反转链表2
代码语言：java复制class Solution {
public ListNode reverseList(ListNode head) {
if (null == head || null == head.next) return head;
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
}2、队列和栈
1、一文秒杀三道括号题目
<font style="color:rgb(89, 89, 89);">20.有效的括号（</font><font style="color:rgb(64, 118, 0);">Easy</font><font style="color:rgb(89, 89, 89);">）</font>
<font style="color:rgb(89, 89, 89);">921.使括号有效的最小插入（</font><font style="color:rgb(214, 168, 65);">Medium</font><font style="color:rgb(89, 89, 89);">）</font>
<font style="color:rgb(89, 89, 89);">1541.平衡括号串的最少插入（</font><font style="color:rgb(214, 168, 65);">Medium</font><font style="color:rgb(89, 89, 89);">）</font>
代码语言：java复制class Solution {
public boolean isValid(String s) {
if (s.isEmpty()) {
return true;
}
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if ('{' == c) {
stack.push('}');
} else if ('[' == c) {
stack.push(']');
} else if ('(' == c) {
stack.push(')');
} else if (stack.isEmpty() || c != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
} class Solution {
public int minAddToMakeValid(String s) {
int res = 0;//实际插入的次数
int need = 0;//最终要添加的右括号
for (char c : s.toCharArray()) {
if (c == '(') {
//右括号 1
need ;
}
if (c == ')') {
//右括号-1
need--;
//如果==-1或者小于0，代表 ）太多了，此时需要插入一个左括号,need归零
if (need == -1) {
res ;
need = 0;
}
}
}
return res need;
}
} class Solution {
public int minInsertions(String s) {
int res = 0;//实际插入的次数
int need = 0;//最终要添加的右括号
for (char c : s.toCharArray()) {
if (c == '(') {
need = 2;
//若对右括号的需求量为奇数，需要插入 1 个右括号，然后对右括号的需求-1
if (need % 2 == 1) {
res ;//注意，代表插入一个右括号
need--;
}
}
if (c == ')') {
need--;
//need = -1代表插入的)太多了，次数需要插入一个(和一个)
if (need == -1) {
res ;
need = 1;
}
}
}
return res need;
}
}2、单调栈结构解决三道算法题
Java栈复习
https://blog.csdn.net/renxingzhadan/article/details/118371740
- 下一个更大元素 I（简单）
- 下一个更大元素II（中等）（环形数组）
- 每日温度（中等）
//单调栈模板
int[] findNextGreaterElement(int[] nums) {
int n = nums.length;
// 存放答案的数组
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.isEmpty() && s.peek() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}
//下一个更大元素
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//找到num2中所有元素的下一个更大元素
int[] nums2Res = findNextGreaterElement(nums2);
HashMap<Integer, Integer> nums2Map = new HashMap<>();
for (int i = 0; i < nums2.length; i ) {
nums2Map.put(nums2[i], nums2Res[i]);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i ) {
res[i] = nums2Map.get(nums1[i]);
}
return res;
}
//每日温度
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> s = new Stack<>();
for (int i = temperatures.length - 1; i >= 0; i--) {
//弹出比当前温度低的
while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
s.pop();
}
res[i] = s.empty() ? 0 : (s.peek() - i);
s.push(i);
}
return res;
}环形数组
int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 数组长度加倍模拟环形数组
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引 i 要求模，其他的和模板一样
while (!s.isEmpty() && s.peek() <= nums[i % n]) {
s.pop();
}
res[i % n] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i % n]);
}
return res;
}3、单调队列结构解决滑动窗口问题
Java队列复习
https://blog.csdn.net/qq1620657419/article/details/123046420
https://blog.csdn.net/m0_45861545/article/details/120720557
<font style="color:rgb(89, 89, 89);">239. 滑动窗口最大值（</font><font style="color:rgb(255, 76, 0);">困难</font><font style="color:rgb(89, 89, 89);">）</font>
代码语言：java复制class Solution {
//队列 先进先出
class MonotonicQueue {
// 双端队列 LinkedList 双向链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
private LinkedList<Integer> maxq = new LinkedList<>();
//从尾部插入，只要小于n的数据都移除
public void push(int n) {
// 将头部小于自己的元素都删除
while (!maxq.isEmpty() && maxq.getLast() < n) {
//移除队尾元素
maxq.removeLast();
}
//添加到队列尾部
maxq.addLast(n);
}
//从队列头部弹出，此处很关键，如果移除的是队列头部首元素，
//那就是移除最大值，此时需要removeFirst，否则就无需操作
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.removeFirst();
}
}
//队列头部的就是最大值
public int max() {
return maxq.getFirst();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
List<Integer> resList = new ArrayList<>();
MonotonicQueue window = new MonotonicQueue();
for (int i = 0; i < nums.length; i ) {
if (i < k - 1) {
//先填满窗口的前 k - 1
window.push(nums[i]);
} else {
//窗口向前滑动，加入新数字
window.push(nums[i]);
//记录当前窗口的最大值
resList.add(window.max());
//移出旧数字
window.pop(nums[i - k 1]);
}
}
//需要转成 int[] 数组再返回
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i ) {
res[i] = resList.get(i);
}
return res;
}
}4、一道数组去重的算法题把我整不会了
第 316 题「去除重复字母」，难度 Hard
第 1081 题「不同字符的最小子序列」，难度 Medium（解法和316完全一样）
代码语言：java复制class Solution {
//要求一、要去重。
//要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
//要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
public static String removeDuplicateLetters1(String s) {
boolean[] inStack = new boolean[256];//去重
Stack<Character> stack = new Stack<>();//保证顺序
for (char c : s.toCharArray()) {
//判断是否在栈中
if (inStack[c]) continue;
stack.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.empty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
public static String removeDuplicateLetters2(String s) {
boolean[] inStack = new boolean[256];//去重
Stack<Character> stack = new Stack<>();//保证相对顺序
for (char c : s.toCharArray()) {
//判断是否在栈中
if (inStack[c]) continue;
// 插入之前，和之前的元素比较一下大小
// 如果字典序比前面的小，pop 前面的元素,保证字典顺序
while (!stack.isEmpty() && stack.peek() > c) {
// 弹出栈顶元素，并把该元素标记为不在栈中
inStack[stack.pop()] = false;
}
stack.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.empty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
//要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
public static String removeDuplicateLetters(String s) {
//在弹出栈时判断后续是否还有这个元素
int[] nums = new int[256];
for (char c : s.toCharArray()) {
nums[c] ;
}
boolean[] inStack = new boolean[256];//去重
Stack<Character> stack = new Stack<>();//保证字符相对顺序
for (char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
nums[c]--;
//判断是否在栈中
if (inStack[c]) continue;
// 插入之前，和之前的元素比较一下大小
// 如果字典序比前面的小，pop 前面的元素,保证字典顺序
while (!stack.isEmpty() && stack.peek() > c) {
// 若之后不存在栈顶元素了，则停止 pop
if (nums[stack.peek()] == 0) {
break;
}
// 弹出栈顶元素，并把该元素标记为不在栈中
inStack[stack.pop()] = false;
}
stack.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.empty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}3、数据结构设计
1、算法就像搭乐高：带你手撸 LRU 算法
<font style="color:rgb(89, 89, 89);">146 题「LRU缓存机制」</font>
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}2、算法就像搭乐高：带你手撸 LFU 算法
注意：
putIfAbsent()方法作用：<font style="color:rgb(56, 58, 66);background-color:rgb(250, 250, 250);">如果key不存在或者key已存在但是值为null，才put进去。put进去时返回null，不put进去时返回原值。</font>
<font style="color:rgb(56, 58, 66);background-color:rgb(250, 250, 250);"></font>
<font style="color:rgb(89, 89, 89);">460 题「LFU缓存机制」</font>
class LFUCache {
//key -> value 存放数据
HashMap<Integer, Integer> keyToVal;
//key -> 频次 记录每个key对应的频次
HashMap<Integer, Integer> keyToFreq;
//频次对应的key集合，可以通过LinkedHashSet.ketSet获取最先插入的数据
HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
// 记录 freqToKeys 最小的频次
int minFreq;
// 记录 LFU 缓存的最大容量
int cap;
public LFUCache(int capacity) {
keyToVal = new HashMap<>();
keyToFreq = new HashMap<>();
freqToKeys = new HashMap<>();
minFreq = 0;
cap = capacity;
}
public int get(int key) {
if (!keyToVal.containsKey(key)) {
return -1;
}
// key 对应的 freq 1
increaseFreq(key);
return keyToVal.get(key);
}
public void put(int key, int value) {
if (cap <= 0) return;
if (keyToVal.containsKey(key)) {
//更新值
keyToVal.put(key, value);
// key 对应的 freq 1
increaseFreq(key);
} else {
//插入新值 需要判断容量
if (cap <= keyToVal.size()) {
//删除最小频次的key
removeMinFreqKey();
}
/* 插入 key 和 val，对应的 freq 为 1 */
// 插入 KV 表
keyToVal.put(key, value);
// 插入 KF 表
keyToFreq.put(key, 1);
// 插入 FK 表,putIfAbsent
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
freqToKeys.get(1).add(key);
// 插入新 key 后最小的 freq 肯定是 1
minFreq = 1;
}
}
//给key的频次 1
private void increaseFreq(int key) {
//更新kf表
Integer freq = keyToFreq.get(key);
keyToFreq.put(key, freq 1);
//更fks表
//将key放入 freq 1 的集合中
freqToKeys.putIfAbsent(freq 1, new LinkedHashSet<>());
freqToKeys.get(freq 1).add(key);
//移除 freq 的 key，移除之后要判断集合是否为空
freqToKeys.get(freq).remove(key);
//如果频次所对应的集合空 移除频次，并刷新最小频次
if (freqToKeys.get(freq).isEmpty()) {
freqToKeys.remove(freq);
// 如果这个 freq 恰好是 minFreq，更新 minFreq,
if (freq == minFreq) {
minFreq = freq 1;
}
}
}
//删除最小频次的数据
private void removeMinFreqKey() {
// freq 最小的 key 列表
LinkedHashSet<Integer> ketSet = freqToKeys.get(minFreq);
//获取最小频次对应的 key 集合中队列头部的数据
int oldKey = ketSet.iterator().next();
//ketSet 移除目标 key
ketSet.remove(oldKey);
//如果 ketSet 为空 移除最小频次
if (ketSet.isEmpty()) {
freqToKeys.remove(minFreq);
//此时应该刷新最小频次，但是此方法的调用方法中会刷新 所以此处就不用刷新 minFreq 了
}
keyToVal.remove(oldKey);
keyToFreq.remove(oldKey);
}
}3、给我常数时间，我可以删除/查找数组中的任意元素
<font style="color:rgb(89, 89, 89);">380 常数时间插入、删除和获取随机元素</font>
<font style="color:rgb(89, 89, 89);">710 避开黑名单的随机数</font>
代码语言：java复制class RandomizedSet {
//存放值的数组,插入都是插入到最后一个位置，删除中间位置时，先将数组最后一个位置的元素覆盖到该中间位置，再直接删除数组最后一个位置
List<Integer> nums;
//val -> index
Map<Integer, Integer> indexMap;
Random random;
public RandomizedSet() {
nums = new ArrayList<Integer>();
//val -> index
indexMap = new HashMap<Integer, Integer>();
random = new Random();
}
public boolean insert(int val) {
if (indexMap.containsKey(val)) {
return false;
}
indexMap.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
if (!indexMap.containsKey(val)) {
return false;
}
//获取目标值的索引，也就是要删除数据的索引位置
int index = indexMap.get(val);
//获取数组最后一个位置的值
int lastElement = nums.get(nums.size() - 1);
//更新 lastElement 的位置信息
indexMap.put(lastElement, index);
//把最后一个值放入要被删除的位置
nums.set(index, lastElement);
//删除val的索引位置
indexMap.remove(val);
//删除最后一个位置，最后一个位置的值已经被插入到 原来 val所在的位置了
nums.remove(nums.size() - 1);
return true;
}
public int getRandom() {
int randomIndex = random.nextInt(nums.size());
return nums.get(randomIndex);
}
}class Solution {
Random random;
int len;
HashMap<Integer, Integer> map;
public Solution(int n, int[] blacklist) {
random = new Random();
len = n - blacklist.length;
map = new HashMap<>();
for (int b : blacklist) {
map.put(b, -1);
}
int last = n - 1;
for (int b : blacklist) {
//如果坐标本来就在[len,n)之内，就不用管
if (b >= len) {
//注意：这里无需-1，因为 b > len时必定在map中，下面的 while 循环会 -1
//last--
continue;
}
//如果要映射的位置也在黑名单内，寻找下一个合适的位置
while (map.containsKey(last))
last--;
//将[0,len)的黑名单位置映射到[len,n)不是黑名单的位置
map.put(b, last--);
}
System.out.println(map);
}
public int pick() {
int index = random.nextInt(len);
//将[0,len)的黑名单位置映射到[len,n)不是黑名单的位置
if (map.containsKey(index))
return map.get(index);
return index;
}
}4、一道求中位数的算法题把我整不会了
巧妙利用两个优先级队列(大顶堆和小顶堆)
<font style="color:rgb(89, 89, 89);">295 数据流中的中位数</font>
代码语言：java复制class MedianFinder {
//大顶堆，堆顶元素是最大
private PriorityQueue<Integer> small;
//小顶堆，堆顶元素是最小
private PriorityQueue<Integer> large;
public MedianFinder() {
//默认是
large = new PriorityQueue<Integer>();
small = new PriorityQueue<Integer>((a, b) -> {
return b - a;
});
}
//核心方法 确保 small 中的任何一个元素都比 large 中的小
public void addNum(int num) {
//向large中插入数据
if (small.size() >= large.size()) {
//先将数据放入small中 再置换出最大的那一个，放入 large 中
small.offer(num);
large.offer(small.poll());
} else {
//先将数据放入 large 中 再置换出最小的那一个，放入 small 中
large.offer(num);
small.offer(large.poll());
}
}
// large 最小堆的堆顶 或者 small 最大堆的堆顶 或者两者平均值就是中位数
public double findMedian() {
if (large.size() > small.size()) {
return large.peek();
} else if (large.size() < small.size()) {
return small.peek();
}
return (large.peek() small.peek()) / 2.0;
}
}5、如何实现一个计算器
//提取字符串中数字的技巧
String s = "a458b";
int n = 0;
for (int i = 0; i < s.length(); i ) {
char c = s.charAt(i);
if (Character.isDigit(c))
n = 10 * n (c - '0');
}
// n 现在就等于 458
System.out.println(n);public static void main(String[] args) {
String s = "1 2 * 2 - 3";
System.out.println(calculate(s));
}
//简单计算器 只包括 数字 - * / 和空格，暂时没办法处理括号（）
private static int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0;
char sign = ' ';
for (int i = 0; i < s.toCharArray().length; i ) {
char c = s.charAt(i);
//如果是数字 循环提取数字
if (Character.isDigit(c))
num = num * 10 (c - '0');
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
switch (sign) {
case ' ':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
//拿到前一个数字 再运算
stack.push(stack.pop() * num);
break;
case '/':
//拿到前一个数字 再运算
stack.push(stack.pop() / num);
break;
}
sign = c;
num = 0;
}
}
int sum = 0;
while (!stack.isEmpty()) {
sum = sum stack.pop();
}
return sum;
}
