刷100道leetcode后总结
2021-7-30数据结构（c语言的）略
1.斐波那契
略
2.基础排序（冒泡，选择，插入）
后2者相当于把前面排好序的数，在接下来的遍历里面排除再去排序，减少遍历次数。
选择不稳定，插入稳定。
3.高级排序（希尔，归并，快速，堆排序，计数，桶排序，基数排序）
a.二分查找，每次迭代取中间值去对比target，取范围值，直到等于target。
其余略
4.刷leetcode 后总结
思想（略）：（1.穷举 2.贪心 3.回溯 4.分治 5.动态规划）
模型技巧：
dfs bfs 二叉树 暴力 双指针 滑动窗口 贪心 回溯 动归
暴力：
最为最好想到的方法，实际中最好解决问题，但是中等和困难会超时。
//17. 电话号码的字母组合
var letterCombinations = function (digits) {
let results = []
const enume = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z'],
}
if (!digits) return results
if (digits.length === 1) return enume[digits]
const digitsArr = digits.split('').map(v => enume[v])
const len = digitsArr.length
const getCombination = (left, right) => {
let res = []
if (!left.length) return right
for (let i = 0; i < left.length; i++) {
for (let j = 0; j < right.length; j++) {
res.push(left[i] + right[j])
}
}
return res
}
for (let i = 0; i < len; i++) {
results = results.concat(getCombination(results, digitsArr[i]))
}
return results.filter(v => v.length === len)
}
212. 单词搜索 II
var findWords = function (board, words) {
const clen = board.length
const rlen = board[0].length
let results = new Set()
const helper = (col, row, word, index) => {
if (!word[index]) {
results.add(word)
}
if (col < 0 || col >= clen || row < 0 || row >= rlen) {
return
}
const target = board[col][row]
if (target === word[index]) {
board[col][row] = '-'
helper(col + 1, row, word, index + 1)
helper(col - 1, row, word, index + 1)
helper(col, row + 1, word, index + 1)
helper(col, row - 1, word, index + 1)
board[col][row] = target
}
}
const getInitCoord = word => {
for (let i = 0; i < clen; i++) {
for (let j = 0; j < rlen; j++) {
if (board[i][j] === word[0]) {
helper(i, j, word, 0)
}
}
}
}
for (let i = 0; i < words.length; i++) {
const word = words[i]
const coord = getInitCoord(word)
}
return [...results]
}二叉树（前中后序）：
其他变种的题都是根据以下dsf和bsf模型来得出的。
// 104. 二叉树的最大深度
// dsf
var maxDepth = function (root) {
if (!root) return 0
let max = 0
const recursion = (node, depth) => {
if (!node) return
if (!node.left && !node.left) max = Math.max(max, depth)
node.left && recursion(node.left, depth + 1)
node.right && recursion(node.right, depth + 1)
}
recursion(root, 1)
return max
}
// bsf
var maxDepth = function (root) {
if (!root) return 0
let queue = [root]
let depth = 0
while (queue.length) {
let len = queue.length
depth++
for (let i = 0; i < len; i++) {
const node = queue.shift()
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
}
return depth
}双指针（对撞指针，快慢指针）：
// 167. 两数之和 II - 输入有序数组
var twoSum = function (numbers, target) {
debugger
let left = 0
let right = numbers.length - 1
while (left < right) {
const val = numbers[left] + numbers[right] - target
if (val > 0) {
right--
} else if (val < 0) {
left++
} else {
return [left + 1, right + 1] //题目要求下标按1 开始
}
}
}
// 125. 验证回文串
var isPalindrome = function (s) {
s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
let left = 0
let right = s.length - 1
while (left < right) {
if (s[left] !== s[right]) {
return false
} else {
left++
right--
}
}
return true
}滑动窗口（每次迭代增大或缩小窗口，当满足条件记录对比）：
// 209. 长度最小的子数组
var minSubArrayLen = function (target, nums) {
let left = 0
let right = - 1
let sum = 0
let result = Infinity
while (left < nums.length) {
if (sum < target) {
sum += nums[++right]
} else {
sum -= nums[left]
left++
}
if (sum >= target) {
result = Math.min(result, right - left + 1)
}
}
return result === Infinity ? 0 : result
}链表：
// 206. 反转链表
//关键步骤：最小单位（上中下）1.下保存 2.下赋值上 3.上赋值中
//不要用数组的形式想链表，得不到答案
var reverseList = function (head) {
let prev = null
let curent = head
while (curent !== null) {
let save = curent.next
curent.next = prev
prev = curent
curent = save
}
// 退出while循环的条件是 cur 为 null。只要明白一件事情
// pre 指向的是cur的前一个元素。所以翻转之后返回的应该是pre
return prev
//有时候很链表很恶心，转成数组会方便很多
// 19. 删除链表的倒数第 N 个结点
var removeNthFromEnd = function (head, n) {
let i = 1
let current = head
let arr = []
const getArr = (current) => {
arr.unshift(current.val)
if (current.next) {
getArr(current.next)
}
}
getArr(current)
arr.splice(n - 1, 1)
let _cur = null
for (let i = 0; i < arr.length; i++) {
_cur = {
val: arr[i],
next: _cur
}
}
return _cur
}
//但是有时候数组没法解决问题，像下面
// 146. LRU 缓存机制
// 这题彻底把我搞服，终于知道什么场景下必须用链表了，要达到O(1)数组直接没考虑！！！
//时间戳没法判断 前后，因为程序太快了，都毫秒都是一样
class DoubleNode {
constructor(key, val) {
this.key = key
this.val = val
this.prev = null
this.next = null
}
}
class LRUCache {
constructor(max) {
this.max = max
this.map = new Map()
this.head = null
this.tail = null
}
get(key) {
const node = this.map.get(key)
if (!node) {
return -1
} else {
const res = node.val
this.remove(node)
this.appendHead(node)
return res
}
}
put(key, value) {
let node = this.map.get(key)
if (node) {
node.val = value
this.remove(node)
this.appendHead(node)
} else {
node = new DoubleNode(key, value)
if (this.map.size >= this.max) {
this.map.delete(this.tail.key)
this.remove(this.tail)
this.appendHead(node)
this.map.set(key, node)
} else {
this.appendHead(node)
this.map.set(key, node)
}
}
}
/**
* 把头部指针的改变成新的node
* @param {DoubleNode} node
*/
appendHead(node) {
if (this.head === null) {
this.head = this.tail = node
} else {
node.next = this.head
this.head.prev = node
this.head = node
}
}
/**
* 删除某个节点
* @param {DoubleNode} node
*/
remove(node) {
if (this.head === this.tail) {
this.head = this.tail = null
} else {
if (this.head === node) {
this.head = this.head.next
node.next = null
} else if (this.tail === node) {
this.tail = this.tail.prev
this.tail.next = null
node.prev = null
} else {
node.prev.next = node.next
node.next.prev = node.prev
node.prev = node.next = null
}
}
}
}贪心 :
// 122. 买卖股票的最佳时机 II
var maxProfit = function (prices) {
let len = prices.length
let max = 0
for (let i = 1; i < len; i++) {
max += Math.max(0, prices[i] - prices[i - 1])
}
return max
}
//找零钱
function MinCoinChange2(coins) {
var coins = coins.sort(function (a, b) {
return b - a;
});
this.makeChange = function (amount) {
var change = [],
total = 0;
for (var i = 0; i < coins.length; i++) {
var coin = coins[i];
while (total + coin <= amount) {
change.push(coin);
total += coin;
}
}
return change;
}
}回溯 :
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择暴力穷举算法，有时带上剪枝
//46. 全排列
var permute = function (nums) {
let results = []
const recursion = (nums, res) => {
if (nums.length === 1) {
results.push([...res, ...nums])
}
for (let i = 0; i < nums.length; i++) {
const _num = nums[i]
const _nums = nums.slice(0, i).concat(nums.slice(i + 1))
//每次遍历, 保证剩下的数组是一样, 并且每个位置都要开头一次
res.push(_num)
recursion(_nums, res)
//开过头就删除, 避免同一个数组所加的res除开nums[i]前面的数与_nums有重复
res.pop()
}
}
recursion([...nums], [])
return results
}动规 :
以最小单位的动态转移方程dp去得到0位置起的所有答案，根据题意取出需要的值
套路：
dp[0][0][…] = base
进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for …
dp[状态1][状态2][…] = 求最值(选择1，选择2…)
// 746. 使用最小花费爬楼梯
// 1. 0或1开始
// 2.min(dp[i]+arr[i+1],dp[i]+arr[i+2])
var minCostClimbingStairs = function (cost) {
let dp = []
let len = cost.length
let i = 2
dp[0] = dp[1] = 0;
for (i; i <= len; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
}
return dp[i - 1]
}eg利用以上模型来解题：
回溯和递归：
// 22. 括号生成
// start,end 左右括号的数量
// 保证不能以"）"开始的括号 start > end
var generateParenthesis = function (n) {
let results = []
const recursion = (start, end, prev) => {
if (start < 0 || end < 0 || start > end) return
if (start === 0 && end === 0) {
results.push(prev)
return
}
recursion(start - 1, end, prev + '(')
recursion(start, end - 1, prev + ')')
}
recursion(n, n, '')
return results
}
// 77. 组合
// 1.第一层数组减少1个
// 2.第二层数组每个节点减少1个
// 3.总结规律：每次取值，数组都要减少一个
// 这里基本是这类题，我的万能模板 + 剪枝的更胜
var combine = function (n, k) {
let results = []
let arr = new Array(n).fill(0).map((v, i) => i + 1)
const recursion = (k, arr, res) => {
if (k === 0) return results.push(res)
k--
while (arr.length) {
const num = arr.shift()
// res.push(num)
recursion(k, [...arr], [...res, num])
// res.pop()
}
}
recursion(k, arr, [])
return results
}
// 51. N 皇后
// 1.row最多一个
// 2.col最多一个
// 3.斜线上最多1个
//推理等得到：对角线右上和左下的坐标和都为i+j, 对角线左上和右下的坐标差都为i-j
var solveNQueens = function (n) {
let results = []
let grid = new Array(n).fill('.').map(v => new Array(n).fill('.'))
const getIsQueuePosition = (row, col, grid) => {
const sum = row + col
const difference = row - col
for (let i = 0; i < row; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 'Q' && (j == col || i + j === sum || i - j === difference)) {
return false
}
}
}
return true
}
const recursion = (row, grid) => {
if (row === n) {
//二维数组只能在这个改第一层
//如果最后在改, 第一层之间的grid下的子集会相互影响
const _grid = [...grid].map(v => v.join(''))
return results.push(_grid)
}
for (let col = 0; col < n; col++) {
if (getIsQueuePosition(row, col, [...grid])) {
grid[row][col] = 'Q'
recursion(row + 1, [...grid])
grid[row][col] = '.'
}
}
}
recursion(0, grid)
return results
}
// 37. 解数独
// 1-9
// 1. 横向不重复
// 2. 竖向不重复
// 3. 九宫格内不重复
var solveSudoku = function (board) {
let m = board.length
let n = board[0].length
const getIsSudoku = (row, col, num) => {
for (let i = 0; i < m; i++) {
if (board[i][col] === num || board[row][i] === num) return false
}
const startRow = Math.floor(row / 3) * 3
const startCol = Math.floor(col / 3) * 3
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[startRow + i][startCol + j] === num) return false
}
}
return true
}
const recursion = (row, col) => {
if (col === n) {
row++
col = 0
if (row === m) return true
}
if (board[row][col] !== '.') return recursion(row, col + 1)
for (let i = 1; i <= 9; i++) {
if (!getIsSudoku(row, col, String(i))) continue
board[row][col] = String(i)
if(recursion(row, col + 1)){
return true //基于board[row][col] = String(i), 成功数独则返回true
} else{
board[row][col] = '.' //失败就还原
}
}
// return false //根据题意 保证 输入数独仅有一个解，这里用不着false
}
recursion(0, 0)
return board
}动规：
//322. 零钱兑换
// dp[120] = Math.min(dp[119] + 1, dp[118] + 1, dp[115] + 1); coint=1,2,5
// dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)
const coinChange = (coins, amount) => {
let dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0
for (let coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
}
// 198. 打家劫舍
//dp[i]=max(dp[i],dp[i-2]+arr[i]) 要么当前值+前2位的储存最大值，要么i-1的最大值
var rob = function (nums) {
let len = nums.length
let dp = []
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
if (len === 1) {
return dp[0]
} else if (len === 2) {
return dp[1]
}
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
return dp[len - 1]
}
//01背包
// 1.max(dp[i-1,j], v[i]+dp[C-i,j-1]), 上一行的最大值或当前商品价值+剩余空间价值
var knapsack01 = function (w, v, C) {
let dp = new Array(w.length+1).fill(0).map(k => k = new Array(C+1).fill(0))
let i=1;
for (i ; i < w.length; i++) {
for (let j = 1; j <= C; j++) {
const newVal= w[i] > j ? 0 : v[i] + dp[i - 1][j - w[i]] //装不下时0其实为上一次的值，但以为下面有了，所以可以写0
dp[i][j] = Math.max(dp[i - 1][j], newVal)
}
}
return dp[i-1][C]
}
// 1143. 最长公共子序列
// 以dp[i][j]结尾的的字符串网格公共子序列的个数
// dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
var longestCommonSubsequence = function (text1, text2) {
let len1 = text1.length
let len2 = text2.length
let dp = new Array(len1).fill(1).map(v => new Array(len2).fill(0))
const helper = (i, j) => {
if (i === len1 || j === len2) {
return 0
}
if (dp[i][j] !== 0) {//减少遍历次数
return dp[i][j]
}
if (text1.charAt(i) === text2.charAt(j)) {
dp[i][j] = 1 + helper(i + 1, j + 1)
} else {
dp[i][j] = Math.max(
helper(i + 1, j),
helper(i, j + 1)
)
}
return dp[i][j]
}
return helper(0, 0)
}
// 221. 最大正方形
// 定义 dp[i][j]：以坐标(i, j) 为右下角的最大正方形边长。
// (i, j) 为 0 时，无法构成正方形，dp[i][j] = 0
// (i, j) 为 1 时，dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
// 以面积为4的正方形去作为最小单位思考(画图):
// 一个正方形的最大边长决定于它左方、上方、斜上方的位置所能形成的最大正方形的边长，即：三者的最小值 + 1。
// 然后把这个正方形缩小成2，继续与它左方、上方、斜上方的位置 去重复上一句话
// 为了避免边界条件判断，可以将 dp 数组的长和宽都增加 1 !!!!!
var maximalSquare = function (matrix) {
let m = matrix.length
let n = matrix[0].length
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
let max = 0
//处理边界
for (let i = 0; i < m; i++) {
if (matrix[i][0] === '1') {
dp[i][0] = 1
max = Math.max(max, dp[i][0])
}
}
for (let j = 0; j < n; j++) {
if (matrix[0][j] === '1') {
dp[0][j] = 1
max = Math.max(max, dp[0][j])
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if ((matrix[i][j] === '1')) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max = Math.max(max, dp[i][j])
console.log(max)
}
}
}
return max * max
}拓扑排序：
// 207. 课程表
//构建有向无环图
class Graph {
constructor(noOfVertices) {
this.noOfVertices = noOfVertices; // 顶点数量
this.adjList = new Map(); // 邻接表
}
// 增加顶点
addVertex(v) {
this.adjList.set(v, []);
}
// 增加单向边
addEdge(v, w) {
this.adjList.get(v).push(w);
}
dfs() {
const visited = Array(this.noOfVertices).fill(false);
const vertices = this.adjList.keys();
console.log(vertices)
for (let v of vertices) {
if (!this.dfsUntil(v, visited)) return false;
}
return true;
}
dfsUntil(v, visited) {
if (visited[v]) return false
visited[v] = true
const neighs = this.adjList.get(v);
for (let neigh of neighs) {
if (!this.dfsUntil(neigh, visited)) return false;
}
visited[v] = false;
return true;
}
}
var canFinish = function (numCourses, prerequisites) {
var g = new Graph(numCourses)
for (var i = 0; i < numCourses; i++) {
g.addVertex(i)
}
prerequisites.forEach(([i, j]) => g.addEdge(i, j))
return g.dfs()
}略见github的jsoo篇,更多见github…