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