zainzhao / eat-leetcode Goto Github PK

• 136 只出现一次的数字（排序、map统计、x^x == 0 + x^0 == x）
• 169 多数元素（排序、统计查找、摩尔投票法、(n >> (m-1)) & 1）
• 231 2的幂（字符串统计、n & n-1 == 0、n&-n == n）
• 191 位1的个数（n&1、n & n-1）
• 389 找不同（排序+遍历、map计数、求和法、^）
• 461 汉明距离（x ^ y + API、x ^ y + n & n-1、）
• 338 比特位计数（bitCount、i & (i-1)、bits[i>>1]+ (i & 1)）
• 268 丢失的数字（^、Hash）
• 78 子集（枚举、回溯、位运算）
• 405 数字转换为十六进制数（map + & 0xf）

2++

• 剑指 Offer 56 Ⅰ 数组中数字出现的次数
• 剑指 Offer 65 不用加减乘除做加法
• 剑指 Offer 56 Ⅱ 数组中数字出现的次数Ⅱ
• 371 两整数之和

& | ^ ~ 
<< 左移 右侧补0
>> 右移  右侧补符号位
>>> 右移 左侧补0


n ^ 0 = n
n ^ n = 0
    
- 乘 2 
n << 1
    
- 除 2
n >> 1

- 奇数
(n & 1) == 1
    
x % 2 ==> x & 1

- 不用临时变量交换两个数
a ^= b;
b ^= a;
a ^= b;

- 从低位到高位，取n的第m位
(n >> (m-1)) & 1
    
n & (n-1) 消除n中最后一个1
n & (n-1) == 0 或者 n & -n == n 就是 2 的幂次方

• 16 最接近的三数之和（三指针）
• 18 四数之和（四指针+双重循环+两数之和、暴力）
• 202 快乐数（Hash判环、快慢指针判环、硬编码）
• 203 移除链表元素（收集+重构、双指针遍历）
• 125 验证回文串（筛选+反转、头尾双指针）
• 345.反转字符串中的元音字母（头尾双指针）
• 167 两数之和Ⅱ-输入有序数组（暴力、hash、头尾双指针）
• 11 盛最多水的容器（双重循环+暴力、头尾指针+贪心）
• 26 删除排序数组中的重复项（双指针遍历）
• 27 移除元素（标准遍历双指针）
• 485 最大连续1的个数（标准遍历双指针）
• 283.移动零（标准遍历双指针）
• 344 反转字符串（标准遍历双指针）
• 392 判断子序列（标准遍历双指针）
• 925 长按键入（两串两指针）
• 643 子数组最大平均数Ⅰ（滑动窗口）
• 121 买卖股票的最佳时机（遍历-滑动窗口、暴力）
• 438 找到字符串中所有字母异位词（暴力、滑动窗口+Hash）
• 剑指offer 48 最长不含重复字符的子字符串（hash+滑动窗口）
• 424 替换后的最长重复字符（hash+滑动窗口）
• 3 无重复字符的最长子串 （hash + 滑动窗口）
• 76 最小覆盖子串（滑动窗口+hash）
• 1047 删除字符串中所有相邻重复项（栈、修改原数组）
• 83 删除排序链表中的中的重复元素 （遍历、递归、set判重）
• 82 删除排序链表中的中的重复元素Ⅱ （收集+双向队列、递归、双指针）
• 75 颜色分类 （sort、计数排序、双指针、三指针）

2++

• 剑指offer 21 调整数组顺序使奇数位于偶数前面
• 611 有效三角形的个数
• 443 压缩字符串
• 剑指 Offer 57 - Ⅱ 和为s的连续正数序列

用数组代替Hash表，0-127 为 所有英文字母、符号和数字 new int[128]

英文字母组成的Hash表 0-26  char - 'A'  new int[26]

双指针一般会和字符串一起考
双指针一般会和链表考（快慢指针、pre、dummy）

滑动窗口一般都会和Hash一起考

注意边界

经常会有贪心的**在里面


固定模板
	int left = 0;
	int right = 0;
	int[] hashTable = new int[26];
	while (right < str.length) {
		hash[str.charAt[right] - 'A']++;
		.....逻辑
		right++; // 向右扩张
		if () { // 窗口左移条件
			hash[str.charAt[left] - 'A']--;
			left++; // 左移
		}
	
	}

Character.isLetterOrDigit()
Character.toLowerCase()

map.containsKey()

Arrays.equals()

• 49 字母异位词分组（sort+hash、sort+groupBy、计数+Hash）
• 146 LRU缓存机制（继承LinkedHashMap、自定义链表 + Hash）
• 242 有效的字母异位词（数组Hash表、排序）
• 347 前K个高频元素（统计 + stream、大根堆）
• 525 连续数组（hash+前缀和）
• 697 数组的度（3map）
• 1207 独一无二的出现次数（统计）
• 剑指Offer 03 数组中重复的数字（排序、hashset）

2++

• 706 设计哈希映射

Hash 经常在链表中用来做收集
如果只涉及子母或者数字，经常使用数组来做hash表
仅包含小写子母 new int[26]

建堆
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
});

• 5 最长回文子串（暴力、dp[i][j] 从i到j是否为回文）
• 22 括号生成（规则、dfs、bfs）
• 42 接雨水（leftMax+rightMax、双指针）
• 62 不同路径（dp[i][j] = dp[i-1][j] + dp[i][j-1] ）
• 63 不同路径 Ⅱ（dp[i][j] = dp[i-1][j] + dp[i][j-1] ）
• 64 最小路径和（path[i][j] = Math.min( path[i][j-1], path[i-1][j]) + grid[i][j]）
• 70 爬楼梯 （dfs、dp[i] = dp[i-1] + dp[i-2]）
• 91 解码方法（dp[i] += dp[i-2]）
• 97 交错字符串（dp[i][j] = dp[i][j] || + (dp[i-1][j]) && s1.charAt(i-1) == s3.charAt(i+j-1) )）
• 120 三角形最小路径和（迭代）
• 121 买卖股票的最佳时机（贪心、滑动窗口、暴力）
• 122 买卖股票的最佳时机Ⅱ（贪心、new int[len][2]）
• 309 最佳买卖股票时机含冷冻期（new int[n][3]）
• 139 单词拆分（memo[i] 表示以i-1结尾的字符串是否能够被拆分）
• 152 乘积最大子数组（遍历交换、三数求最大+三数求最小）
• 198 打家劫舍（Math.max(nums[i] + dp[i-2], dp[i-1])）
• 213 打家劫舍Ⅱ（Math.max([0 , length - 1] , [1 , nums.length])）
• 221 最大正方形（以左上角为核心+暴力、dp[][]）
• 279 完全平方数（dp没太理解、减平方数）
• 300 最长递增子序列（dp[i]表示前i个数字的最长子序列）
• 322 零钱兑换（Math.min(dp[i], dp[i - coins[j]] + 1)）
• 518 零钱兑换Ⅱ（背包）
• 494 目标和（枚举 + dfs、推导sumP）
• 338 比特位计数（API、bits[i] = bits[i >>1] + (i & 1)）
• 647 回文子串（暴力、中心拓展法、dp[i][j]表示str【i , j】是否为回文串）
• 509 斐波那契数（dfs---fib(n-1)+fib(n-2)、dp[i-1]+dp[i-2]、a\b\c 不保存中间过程）
• 673 最长递增子序列的个数（dp[i]表示到nums[i]为止的最长递增子序列长度）
• 718 最长重复子数组（dp[i][j] 表示前面的A数组的第i个元素与B数组的第j个元素是否相等）
• 746 使用最小花费爬楼梯（dp[i]表示上到第i层的最小代价、滚动数组优化）
• 1137 第N个泰波那契数（dfs、dp）
• 1143 最长公共子序列（dp[m+1][n+1]表示串A的前m个字符与串B的前n个字符的最长公共子序列）
• 剑指 Offer 46 把数字翻译成字符串（dp）

2++

• 剑指 Offer 47 礼物的最大价值
• 583 两个字符串的删除操作
• 416 分割等和子集

 DP 还是经常与二维数组结合
 
题目中多会出现 "连续" 二字
 
有时候 dp[n][m]，有时候 dp[n+1][m+1]

二维 dp，一般长度为第一维，状态个数为第二维
 
dp总体** 与 dfs、二叉树都非常相似，都是最小化问题

Integer.bitCount()

需要再单独强化一下背包问题

子序列的dp问题，一般都是二维dp

• 17 电话号码的字母组合（dfs+set+没有回溯）
• 39 组合总数（注意重复）
• 40 组合总数Ⅱ（注意去重）
• 46 全排列（标准回溯）
• 47 全排列 Ⅱ（标准回溯+去重）
• 78 子集（位运算、迭代枚举、回溯）
• 79 单词搜索（二维回溯）
• 剑指 Offer 38 字符串的排列（字符串回溯）
• 93 复原IP地址（字符串回溯）
• 113 路径总和Ⅱ（二叉树回溯）

关键字：所有组合

回溯字方法四要素：存储结果的集合、当前集合、给定集合、条件集合（标记）

将 满足条件的当前集合 加入到存储结果的集合中，记得拷贝值

set转list
List<Inetger> ans = new ArrayList<>(set)

回溯 = backtrack

• 83 删除排序链表中的重复元素（收集、遍历、递归）
• 82 删除排序链表中的中的重复元素Ⅱ（递归、栈、双指针）
• 203 移除链表元素（收集、双指针）
• 148 排序链表（收集、堆、归并）
• 23 合并K个升序链表（收集、两两合并、堆）
• 24 两两交换链表中的节点（收集、递归、双指针）
• 86 分隔链表（双端队列、双链表）
• 2 两数相加（遍历、递归、队列收集）
• 445 两数相加Ⅱ（栈）
• 206 反转链表 = 剑指Offer 24 反转链表 （收集、头插法、递归、双端队列）
• 92 反转链表Ⅱ（头插法、配合反转链表、栈）
• 21合并两个有序链表（遍历、递归）
• 143 重排链表（存储、中点+反转+合并）
• 剑指offer 22 链表中倒数第k个节点（快慢指针、收集、递归）
• 19 删除链表的倒数第N个结点（快慢指针）
• 876 链表的中间结点（收集、快慢指针）
• 141 环形链表（快慢指针、set）
• 234 回文链表（栈、收集、中点+反转）
• 142 环形链表Ⅱ（收集，公式）
• 328 奇偶链表（收集、双指针）
• 25 K个一组反转链表 （收集、分段+反转、统计+递归）
• 138 复制带随机指针的链表（map、链接结点）
• 160 相交链表 = 剑指 Offer52 （map、a+b+c）
• 61 旋转链表（规律）

串联考点：
	递归、栈&队列、快慢指针 & 双指针、收集

链表的递归有点难的
链表的递归返回值都为链表

见到链表题首先应该想到的还是能不能用栈或者队列存储来做，相对简单一些


List<Integer> -> int[]
list.stream().mapToInt(Integer::valueOf).toArray()

• 20 有效括号（map+栈、数组模拟栈）
• 678 有效的括号字符串（计数*、贪心没理解）
• 32 最长有效括号（栈保存index）
• 1190 反转每对括号间的子串（栈 +队列、双指针+占位符）
• 1047 删除字符串中所有相邻重复项（数组模拟栈）
• 115 最小栈（双栈）
• 227 基本计算器Ⅱ（preSign）
• 225 用队列实现栈（双队列、单队列+循环倒腾）
• 232 用栈实现队列（双栈+push时就倒腾、双栈+pop时不够再倒腾）
• 剑指Offer09 用两个栈实现队列（双栈+push时就倒腾、双栈+pop时不够再倒腾）
• 622 设计循环队列（数组设计）
• 239 滑动窗口最大值（双端队列）
• 394 字符串解码（栈、dfs）
• 316 去除重复字母（单调栈、sb代替单调栈）
• 402 移掉K位数字（单调栈）
• 496 下一个更大元素Ⅰ（单调栈、遍历）
• 739 每日温度（迭代、单调栈、倒序动态规划）
• 剑指 Offer 30 包含min函数的栈（辅助list+排序、单调栈+只保存min、单调栈+一直保存min）
• 剑指 Offer 59 队列的最大值（辅助list+排序、单调减队列）
• 456 132模式（双端遍历）

2++

• 224 基本计算器 （打印错了）
• 946 验证栈序列

栈经常与（例如括号）出现

栈经常用来收集链表节点

Character.isDigit()

字符串 转 数字： num = num * s.charAt(i) - '0'

单调栈 
	for() {
		while (!stack.isEmpty() && 单调条件 ) {
			
		}
		stack.push();
	}

双端队列

Arrays.fill(arr, -1)

map.getOrDefault( , )

String.valueOf(arr, start, end)

Collections.sort()  升序

• 976 三角形的最大周长（sort+倒序遍历）
• 670 最大交换（正反、暴力保存）
• 470 用 Rand7() 实现 Rand10()（倍数概率相等、概率相乘）
• 463 岛屿的周长（+5-2、分层）
• 400 第N位数字（规律）
• 342 4的幂（遍历更新）
• 263 丑数（遍历）
• 258 各位相加（递归、%9）
• 224 基本计算器（栈）
• 202 快乐数（Hash判环、快慢指针判环）
• 168 Excel表列名称（26进制）
• 171 Excel表列序号（26进制）
• 72 编辑距离（背诵）
• 69 x的平方根（API、遍历i*i、二分法）
• 43 字符串相乘（字符串相加）
• 13 罗马数字转整数（遍历、规则+字符串替换）
• 9 回文数（转为字符串+头尾指针）
• 8 字符串转换整数（从左到右遍历）
• 7 整数反转（转为字符串）
• 2 两数相加（遍历、队列、dfs）

2++

• 343 整数拆分 == 剑指 Offer 14 剪绳子
• 50 Pow(x, n) == 剑指 Offer 16 数值的整数次方
• 剑指 Offer 60 n个骰子的点数

Arrays.sort(xxx, Collections.reverseOrder())
Math.sqrt(x)

swutch(ch){
	case 'I':return 1;
	case 'v':return 5;
	default:return 0;
}

• 剑指 Offer 45 把数组排成最小的数（stram、快排）
• 剑指Offer 05 替换空格（简单题...）
• 844 比较退格的字符串（栈、sb）
• 3 无重复字符的最长子串 (滑动窗口+map、滑动窗口+数组hash)
• 5 最长回文子串（暴力、动态规划）
• 647 回文子串（暴力、动态规划）
• 680 验证回文字符串Ⅱ（dfs）
• 6 Z 字形变换（每行一个 SB、模拟找规律）
• 7 整数反转（左移+末尾、字符串反转+catch exception）
• 58 最后一个单词的长度（split、从后查找）
• 67 二进制求和（API、SB遍历进位）
• 151 翻转字符串里的单词（后序遍历+双指针、stram）
• 415 字符串相加（后序遍历）
• 165 比较版本号（分割+三元运算、分块计算）
• 468 验证IP地址（str.split("\.", -1)）
• 459 重复子字符串（a+a包含a）
• 796 旋转字符串（a+a包含a，遍历判断）
• 556 下一个更大元素Ⅲ（查找交换）
• 557 反转字符串中的单词Ⅲ（SB反转、双指针反转）

2++

• 剑指 Offer 20 表示数值的字符串

字符串经常与双指针、滑动窗口结合
字符串也会经常与动态规划结合

Integer.toBinaryString()
Integer.parseInt(a, 2)
new BigInteger(a, 2).toString(2)

str.split("\\.", -1) 尽可能多的模式，比如 a,b,c,, 返回length为5

str.subString(startIndex, endIndex) -> [startIndex, endIndex)
str.subString(beginIndex) 

Arrays.sort(chars, j, chars.length) 数组部分排序  也是左闭右开

StringBuffer#deleteCharAt()

str.replaceAll(" ", "20")

IntSream.of(nums).mapToObj(String::valueOf).sorted((o1,o2) -> (o1+o2).compareTo(o2+o1)).collect(Collectors.joining());

Arrays.sort(strs, (o1,o2) -> (o1+o2).compareTo(o2+o1))

• 1 两数之和（暴力、两次遍历+hashMap、一次遍历+hashMap）
• 15 三数之和（sort+map、遍历+三指针）
• 31 下一个排列（倒序遍历）
• 41 缺失的第一个正数 （排序、拷贝+hash、原地 hash）
• 48 旋转图像（原地旋转、辅助数组）
• 54 螺旋矩阵（一层一层转折）
• 59 螺旋矩阵 Ⅱ（一层一层转折）
• 832 翻转图像（空间换时间、时间换空间）
• 867 转置矩阵（T[j][i] = R[i][j]）
• 剑指 Offer 13 机器人的运动范围（dfs）
• 240 搜索二维矩阵 Ⅱ（右上角）
• 118 杨辉三角（模拟迭代、dfs）
• 498 对角线遍历（模拟）
• 88 合并两个有序数组（合并 + 排序、双指针+从前往后、双指针+从后往前）
• 128 最长连续序列（排序+遍历、hashset+统计）
• 152 乘积最大子数组（遍历+交换、dp + 三值最大最小）
• 189 旋转数组（空间映射、三次反转）
• 200 岛屿数量（并查集+感染函数、BFS）
• 695 岛屿的最大面积（dfs、bfs）
• 238 除自身以为数组的乘积（双重遍历、统计0分类讨论、左右乘积列表、从左到右+从右到左）
• 349 两个数组的交集（set.retainall()、排序+双指针）
• 350 两个数组的交集Ⅱ（hasmap、排序+双指针）
• 384 打乱数组（洗牌算法）
• 442 数组中重复的数据（排序、负数标记、+n标记）
• 448 找到所有数组中消失的数字（map+遍历、原地交换、+n标记）
• 485 最大连续1的个数（遍历）
• 560 和为K的子数组（正序+双重遍历、倒序+双重遍历、map前缀和）
• 581 最短无序连续子数组（排序+对比、类似冒泡排序+更新）
• 621 任务调度器（模拟插入）
• 1365 有多少小于当前数字的数字（双重遍历统计、桶计数）
• 1480 一维数组的动态和（迭代）
• 1539 第K个缺失的正整数（集合求交、单遍历）
• 剑指 Offer 53 - Ⅱ 0~n-1中缺失的数字（二分法、位运算）
• 剑指 Offer 61 扑克牌中的顺子（sort+遍历）
• 剑指 Offer 62 圆圈中最后剩下的数字（遍历+%）
• 剑指 Offer 66 构建乘积数组（左连乘+右连乘）
• 剑指 Offer 04 二维数组中的查找（暴力、右上角、左下角、二分法）

2++

• 1539 第K个缺失的正整数（遍历+统计缺值、set排除）
• 162 寻找峰值

一般二维的话，模拟居多
System.arraycopy(source, start, target, start, num)

Arrays.asList(1,2,3,4,5)

set1.retainAll(set2) # 交集保存在 set2 中

int[] 转 List<Integer> Arrays.stram(arr).boxed().collect(Collectors.toList())

本地 hash

前缀和 还需要加强练习

满足条件的连续子数组

模拟遍历

感染

• 4 寻找两个正序数组的中位数（合并+排序、二分法难理解）
• 14 最长公共前缀（纵向扫描、横向扫描、横向扫描+二分法）
• 33 搜索旋转排序数组（分两段进行二分）
• 34 在排列数组中查找元素的第一个和最后一个位置（遍历、共用二分函数）
• 35 搜索插入位置（二分法、遍历）
• 69 x的平方根（API、遍历、二分法）
• 74 搜索二维矩阵（搜索+条件判断、两次二分查找、一次二分查找）
• 153 寻找旋转排序数组中的最小值（二分**）
• 278 第一个错误的版本（dfs、二分法）
• 287 寻找重复数字（set、标志位、二分法、快慢指针）
• 704 二分查找（标准）
• 剑指 Offer 53-Ⅰ 在排序数组中查找数字 Ⅰ（二分法）
• 剑指 Offer 11 旋转数组的最小数字（遍历、排序、二分法）

二分法的数组一定有序

注意边界

关键词 “排序数组+目标值”

一般二分法都可以遍历来做，主要就是为了减小时间复杂度


有等号就 +1 -1
if( == ){
	return XX
}else if ( < ) {
    left = mid + 1;
}else {
	right = mid - 1;
}


if ( >= ) {
	right = mid;  // 不+1
}else {
	left = mid + 1; // +1
}

• 236 二叉树的最近公共祖先（收集父节点、dfs）

• 199 二叉树的右视图（dfs、bfs层次遍历+保存数目）

• 662 二叉树最大宽度（层次遍历、dfs）

• 129 求根节点到叶节点数字之和（dfs、bfs）

• 101 对称二叉树（镜像）

• 226 翻转二叉树（dfs、bfs）

• 114 二叉树展开为链表（收集+dfs、收集+bfs、bfs+原地、旋转）

• 112 路径总和（dfs、bfs+双栈）

• 124 二叉树中的最大路径和（dfs）

• 872 叶子相似的树（dfs）

• 257 二叉树的所有路径（经典dfs、经典bfs）

• 100 相同的树（bfs、dfs）

• 94 二叉树的中序遍历（bfs、dfs）

• 145 二叉树的后续遍历（bfs、dfs）

• 144 二叉树的前序遍历（bfs、dfs）

• 102 二叉树的层序遍历（bfs+两个while）

• 104 二叉树的最大深度（dfs，bfs+两个while）

• 111 二叉树的最小深度（dfs）

• 958 二叉树的完全性检验（收集）

• 543 二叉树的直径（dfs）

• 110 平衡二叉树（dfs+计算法、dfs+标记法）

• 617 合并二叉树（dfs、bfs）

• 106 从中序与后序遍历序列构造二叉树（dfs）

• 105 从前序与中序遍历序列构造二叉树（dfs+copy）

• 98 验证二叉搜索树（dfs、中序遍历）

• 230 二叉搜索树中第K小的元素（dfs+中序收集、迭代+剪枝）

• 450 删除二叉搜索树中的节点（dfs）

• 572 另一颗树的子树（双重dfs）

• 96.不同的二叉搜索树（动态规划）

• 538 把二叉搜索树转换为累加树（dfs）

• 剑指 Offer 33 二叉搜索树的后续遍历序列（dfs）

• 剑指 Offer 54 二叉搜索树的第k大节点（中序收集、倒序）

• 337 打家劫舍Ⅲ（dfs+动态规划、dfs+Hash、纯dfs）

• 208 实现Trie(前缀树)

• 297 二叉树的序列化与反序列化（bfs、dfs）

2++

• 103 二叉树的锯齿形层序遍历
• 113 路径总和Ⅱ
• 剑指 Offer 36 二叉搜索树与双向链表

二叉搜索树的中序遍历 => 从小到大

Arrays.copyOfRange(arr, start, end)  左闭右开

• 56 合并区间（排序+找左右端点）
• 148 排序链表（收集+构造、PriorityQueue+构造、归并排序）
• 179 最大数（Stram+(A+B>B+A)）
• 215 数组中的第K个最大元素（API、PriorityQueue建堆、手写大根堆、手写快排）
• 912 排序数组（手写各种排序算法）
• 1122 数组的相对排序 （遍历+标记+拼接、桶排序）
• 1365 有多少小于当前数字的数字（双重遍历、桶计数）
• 剑指Offer 51 数组中的逆序对（TODO）

List<int[]> 转 int[][]  res.toArray(new int[0][])  TODO

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序
• 归并排序
• 堆排序

• 215 数组中的第K个最大元素（排序、大根堆）
• 347 前K个高频元素（栈）
• 剑指 Offer 40 最小的k个数（排序、小根堆）
• 264 丑数Ⅱ （最小堆+set去重、三指针+动态规划）
• 295 数据流的中位数（双堆）

堆：有大小顺序，并且要找第n个   

小根堆（升序）
new PriorityQueue<Integer>((a,b) -> (a-b)) #前-后 Comparator.reverseOrder()
默认就是小根堆

Arrays.sort() # 默认是升序

相关第K大、第K小都可以使用排序和优先队列

• 跳跃游戏（逆序+需跳长度）

• 406 根据身高重建队列（先排序+再插队）

• 53 最大子序和（动态规划）

• 134 加油站（贪心）

• 跳跃游戏Ⅱ（贪心+反向）

数组的话，贪心通常会逆序进行

• 207 课程表（回溯+判环）
• 547 省份数量（感染函数）

• 10月-4 链表 + 位运算
• 11月-1 动态规划
• 11月-2 字符串
• 11月-3 双指针
• 11月-4 二叉树
• 12月-1 栈
• 12月-2 数组
• 12月-3 all