LeetCode整理

2021年11月15日

快速幂(LeetCode 50 Pow(x,n))
动态规划(LeetCode 1510 石子游戏4)
Z字形查找(LeetCode 240 搜索二维矩阵2)

2021年11月16日

确定有限状态自动机(LeetCode 8 字符串转换整数)
二分查找(LeetCode 704,278,35)
双指针(LeetCod 283 移动零)
双指针(LeetCode 167 两数之和2)
哈希表(LeetCode 1 两数之和)
最大堆、最小堆(LeetCode 414 第K大的数)
线性扫描(LeetCode 328 三个数的最大乘积)

2021年11月17日

哈希表 (LeetCode 645 错误的集合) > getOrDefault(key,default) > 作用：如果存在相应的key则返回其对应的value，否则返回给定的默认值 > 用例: hash.put(c,hash.getOrDefault(c,0)+1); //若没有就是0，若有就是原有值加1
哈希表(LeetCode 41 缺失的第一个正数)

负号占位，正号归位(打标记)
哈希表(LeetCode 697 数组的度)

Map.Entry 的使用

2021年11月19日

动态规划(LeetCode 118 杨辉三角)
滚动数组(LeetCode 119 杨辉三角2) > 用后面的数据覆盖前面的数据 > 优化空间复杂度

位运算优化空间(LeetCode 661 图片平滑器) > 数据为0 - 255 > 低八位储存数据 > 高八位储存平均值

class Solution {
    public static int[][] imageSmoother(int[][] img) {
        if (img == null || img.length == 0) return img;
        int rows = img.length;
        int cols = img[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int count = 0;
                int res = 0;
                for (int nr = i - 1; nr <= i + 1; ++nr) {
                    for (int nc = j - 1; nc <= j + 1; ++nc) {
                        if (0 <= nr && nr < rows && 0 <= nc && nc < cols) {
                            count++;
                            // 取低8位的值
                            res += img[nr][nc] & 0xff;
                        }
                    }
                }
                img[i][j] ^= (res / count) << 8;
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 更新新值
                img[i][j] >>= 8;
            }
        }
        return img;
    }
}

经典题目

动态规划

LeetCode 118 杨辉三角解法:转移方程 dp[i][j] = dp[i-1][j-1]+dp[i-1][j] 0<j<i

哈希表

LeetCode 448 找到所有数组中消失的数字解法: 鸽笼原理用原有数组充当哈希表 > update: 2021年11月17日10:30:19
LeetCode 41 缺失的第一个正数解法: 负号占位，正号归位(打标记) > update: 2021年11月17日11:15:58
LeetCode 697 数组的度解法: Map.Entry 内部类 > update: 2021年11月17日12:37:25

排序

LeetCode 274 H指数解法: 排序后遍历、记忆排序 > update: 2021年11月17日12:33:24

二分查找

广度优先搜索

深度优先搜索

递归回溯

双指针

贪心算法

滑动窗口

优先队列(堆)

LeetCode 414 第三大的数解法: 使用哈希集去重，用优先队列扫描一次得到第K大的值

update: 2021年11月16日21:12:21

位运算

LeetCode 645 错误的集合解法: 使用位运算遍历(异或)

update: 2021年11月17日10:21:51

模拟

分治

二叉搜索树

字典树

有序集合

记忆化搜索

模拟

单调栈

状态压缩

刷题顺序

一. 数组

~~数组的遍历 485、495、414、628~~ > 2021年11月16日23:49:33 done.

~~统计数组中的元素 645、697、448、442、41、274~~ > 2021年11月17日12:42:57 - 697 未完成

~~数组的改变、移动 453、665、283~~ > 2021年11月17日19:41:13

~~二维数组及滚动数组 118、119、661、598、419~~ > 2021年11月19日19:33:18 - 419 未完成

数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238

二. 字符串

字符 520 回文串的定义 125 公共前缀 14 单词 434、58 字符串的反转 344、541、557、151 字符的统计 387、389、383、242、49、451、423、657、551、696、467、535 数字与字符串间转换 299、412、506、539、553、537、592、640、38、443、8、13、12、273、165、481 子序列 392、524、521、522 高精度运算 66、67、415、43、306 字符串变换 482、6、68 字符串匹配 28、686、459、214 中心拓展法 5、647

三. 数与位

数字的位操作 7、9、479、564、231、342、326、504、263、190、191、476、461、477、693、393、172、458、258、319、405、171、168、670、233、357、400 简单数学题 492、29、507 快速幂 50、372

四. 栈与递归

用栈访问最后若干元素 682、71、388 栈与计算器 150、227、224 栈与括号匹配 20、636、591、32 递归 385、341、394

五. 链表

链表的删除 203、237、19 链表的遍历 430 链表的旋转与反转 61、24、206、92、25 链表高精度加法 2、445 链表的合并 21、23

六. 哈希表

哈希表的查找、插入及删除 217、633、349、128、202、500、290、532、205、166、466、138 哈希表与索引 1、167、599、219、220 哈希表与统计 594、350、554、609、454、18 哈希表与前缀和 560、523、525

七. 贪心算法

数组与贪心算法 605、121、122、561、455、575、135、409、621、179、56、57、228、452、435、646、406、48、169、215、75、324、517、649、678、420 子数组与贪心算法 53、134、581、152 子序列与贪心算法 334、376、659 数字与贪心 343 单调栈法 496、503、456、316、402、321、84、85

八. 双指针法

头尾指针 345、680、167、15、16、18、11、42 同向双指针、滑动窗口 27、26、80、83、82、611、187、643、674、209、3、438、567、424、76、30 分段双指针 86、328、160、88、475 快慢指针 141、142、143、234、457、287

九. 树

树与递归 100、222、101、226、437、563、617、508、572、543、654、687、87 树的层次遍历 102、429、690、559、662、671、513、515、637、103、107、257、623、653、104、111、112、113、129、404、199、655、116、117 树的前序遍历 144、589 树的前序序列化 606、331、652、297、449 树的后序遍历 145、590 树的中序遍历与二叉搜索树 94、700、530、538、230、98、173、669、450、110、95、108、109 重构二叉树 105、106 二叉树的展开 114 最近公共祖先 235、236 Morris中序遍历 501、99 四叉树 558、427

十. 图与搜索

图的建立与应用 565 深度优先搜索 17、397 回溯法 526、401、36、37、51、52、77、39、216、40、46、47、31、556、60、491、78、90、79、93、332 回溯法与表达式 241、282、679 回溯法与括号 22、301 回溯法与贪心 488 广度优先搜索 133、200、695、463、542、130、417、529、127、126、433、675 并查集 547、684、685 拓扑排序 399、207、210 有限状态自动机 65、468

十一. 二分查找

二分查找应用(简单) 374、35、278、367、69、441 二分查找应用(中等) 34、540、275、436、300、354、658、162、4 二分查找与旋转数组 153、154、33、81 二分查找与矩阵 74、240 二分答案法 378、668、410、483

十二. 二进制运算的应用

异或的应用 89、136、137、260、268 与或非的应用 371、318、201

十三. 动态规划

数组中的动态规划 509、70、338、45、55、198、213、650、91、639、552、123、188、309、32、264、313、403 子数组、子序列中的动态规划 689、413、446、368、416、279 背包问题 322、518、474、494、377 矩阵中的动态规划 62、63、64、120、576、688、221、629、174、96、329 动态规划与字符串匹配 583、72、97、115、516、132、131、139、140、514、10、44 状态压缩动态规划 464、691、698、638、473 区间中的动态规划 486、664、375、312、546 树形dp 337、124 数位dp 233、600

十四. 数据结构

数据结构设计——栈与队列 225、232、284、622、641、155 数据结构设计——哈希表 676、355、380、381 数据结构设计——哈希与双向链表 432、146、460 前缀树 208、211、648、386、677、472、421、212、336、440 堆 23、373、378、632、347、692、502、630、407、295、480 树状数组 307、315、493、327、673 线段树 699 平衡树(set/map) 352、218、363