#数字范围按位与
function rangeBitwiseAnd(left: number, right: number): number {
if (left === right || left === 0) {
return left
}
if (left.toString(2).length !== right.toString(2).length) {
return 0
}
let result = left
for (let i = left + 1; i <= right; i++) {
result &= i
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
#只出现一次的数字 II
function singleNumber(nums: number[]): number {
const obj = {}
for(const num of nums) {
if (!obj[num]) {
obj[num] = 0
}
obj[num] += 1
}
for(const num of nums) {
if (obj[num] === 1) {
return num
}
}
return nums[0]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 思路：如果3个数相等，那么相加起来一定能被3整除
function singleNumber(nums: number[]): number {
let ans = 0;
for (let i = 0; i < 32; ++i) {
let total = 0;
for (const num of nums) {
total += ((num >> i) & 1);
}
// 存在
if (total % 3 !== 0) {
ans |= (1 << i);
}
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#只出现一次的数字
// 亦或
function singleNumber(nums: number[]): number {
let result = nums[0]
for(let i = 1; i < nums.length; i++) {
result ^= nums[i]
}
return result
};
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
#颠倒二进制位
function reverseBits(n: number): number {
return Number.parseInt(n.toString(2).split('').reverse().join('').padEnd(32, '0'),2)
};
1
2
3
2
3
#二进制求和
function addBinary(a: string, b: string): string {
const len = Math.max(a.length, b.length)
if (a.length < len) {
a = a.padStart(len, '0')
} else {
b = b.padStart(len, '0')
}
let result = ''
let left = 0
for (let i = len - 1; i >= 0; i--) {
const sum = Number(a[i]) + Number(b[i]) + left
if (sum <= 1) {
left = 0
result = sum.toString() + result
} else {
let val = sum % 2
result = val.toString() + result
left = sum - (val === 0 ? 1 : 2)
}
}
if (left > 0) {
result = '1' + result
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#最大正方形
function maximalSquare(matrix: string[][]): number {
// 先循环遍历一遍，统一x轴方向和y轴方向的1
const m = matrix[0].length
const n = matrix.length
const x: number[][] = []
for(let i = 0; i < n; i++) {
x[i] = []
for(let j = 0; j < m; j++) {
if (j === 0) {
x[i][j] = matrix[i][j] === '0' ? 0 : 1
} else {
if (matrix[i][j] === '0') {
x[i][j] = 0
} else {
x[i][j] = x[i][j-1] + 1
}
}
}
}
const y: number[][] = []
for(let i = 0; i < m; i++) {
y[i] = []
for(let j = 0; j < n; j++) {
if (j === 0) {
y[i][j] = matrix[j][i] === '0' ? 0 : 1
} else {
if (matrix[j][i] === '0') {
y[i][j] = 0
} else {
y[i][j] = y[i][j-1] + 1
}
}
}
}
// 正方形最大面积
let result = 0
// i和j表示是否为正方形
const dp: number[][] = []
for(let i = 0; i < n; i++) {
dp[i] = []
for(let j = 0; j < m; j++) {
if (matrix[i][j] === '0') {
dp[i][j] = 0
} else {
// 判断是否为正方形
const val = Math.min(dp[i-1]?.[j-1] ?? -1, x[i][j] - 1, y[j][i] - 1)
if (val > 0 && x[i][j] > val && y[j][i] > val) {
dp[i][j] = val + 1
} else {
dp[i][j] = 1
}
result = Math.max(result, dp[i][j] ** 2)
}
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function maximalSquare(matrix: string[][]): number {
// 先循环遍历一遍，统一x轴方向和y轴方向的1
const m = matrix[0].length
const n = matrix.length
// 正方形最大边长
let result = 0
// i和j表示以i和j为右下角的最大正方形边长度
const dp: number[][] = []
for(let i = 0; i < n; i++) {
dp[i] = []
for(let j = 0; j < m; j++) {
if (matrix[i][j] === '0') {
dp[i][j] = 0
} else {
// 判断是否为正方形
dp[i][j] = Math.min(dp[i-1]?.[j-1] ?? 0, dp[i-1]?.[j] ?? 0, dp[i][j-1] ?? 0) + 1
result = Math.max(result, dp[i][j])
}
}
}
return result ** 2
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#最长回文子串
function longestPalindrome(s: string): string {
// dp[i][j] 表示从i到j是否是回文
const len = s.length
const dp: boolean[][] = []
let str = s[0]
for(let i = len - 1; i >= 0; i--) {
dp[i] = []
for(let j = len - 1; j >= i; j--) {
if (j - i === 0) {
dp[i][j] = true
} else if (j - i === 1) {
dp[i][j] = s[i] === s[j]
} else {
dp[i][j] = dp[i+1][j-1] && s[i] === s[j]
}
if (dp[i][j] && j - i + 1 > str.length) {
str = s.slice(i, j + 1)
}
}
}
return str
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#最小路径和
function minPathSum(grid: number[][]): number {
const m = grid[0].length
const n = grid.length
// 第一层直接相加
for(let i = 1; i < m; i++) {
grid[0][i] += grid[0][i - 1]
}
for(let i = 1; i < grid.length; i++) {
for(let j = 0; j < m; j++) {
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1] ?? grid[i-1][j])
}
}
return grid[n-1][m-1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#三角形最小路径和
function minimumTotal(triangle: number[][]): number {
let dp: number[] = [triangle[0][0]]
for (let i = 1; i < triangle.length; i++) {
for (let j = 0; j < triangle[i].length; j++) {
triangle[i][j] += Math.min(dp[j] ?? dp[j - 1], dp[j - 1] ?? dp[j])
}
dp = [...triangle[i]]
}
return Math.min(...dp)
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
// 不需要dp
function minimumTotal(triangle: number[][]): number {
for (let i = 1; i < triangle.length; i++) {
for (let j = 0; j < triangle[i].length; j++) {
triangle[i][j] += Math.min(triangle[i - 1][j] ?? triangle[i - 1][j - 1], triangle[i - 1][j - 1] ?? triangle[i - 1][j])
}
}
return Math.min(...triangle.pop()!)
};
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
#交错字符串
// 运行失败，但是逻辑是可行的，使用回溯
function isInterleave(s1: string, s2: string, s3: string): boolean {
const len1 = s1.length
const len2 = s2.length
const len3 = s3.length
if (len1 + len2 !== len3) {
return false
}
const cascader = (s1: string, s2: string, start: number, isS1 = true, m = 0, n = 0) => {
if (start === len3) {
return Math.abs(m - n) <= 1
}
for (let i = start; i < len3; i++) {
const word = s3.slice(start, i + 1)
if (isS1) {
if (s1.startsWith(word)) {
if (cascader(s1.slice(i - start + 1), s2, i + 1, false, m + 1, n)) {
return true
}
} else {
return false
}
} else {
if (s2.startsWith(word)) {
if (cascader(s1, s2.slice(i - start + 1), i + 1, true, m, n + 1)) {
return true
}
} else {
return false
}
}
}
return false
}
return cascader(s1, s2, 0, false) || cascader(s1, s2, 0, true)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 动态规划
function isInterleave(s1: string, s2: string, s3: string): boolean {
const len1 = s1.length
const len2 = s2.length
const len3 = s3.length
if (len1 + len2 !== len3) {
return false
}
if (len1 === 0 && len2 === 0 && len3 === 0) {
return true
}
// dp[i][j] 表示s1的前i个和s2的前j个能否组成s3的前i + j个
const dp: boolean[][] = []
dp[0] = [true]
for(let i = 0; i <= len1; i++) {
if (!dp[i]) {
dp[i] = []
}
for(let j = 0; j <= len2; j++) {
if (i > 0) {
dp[i][j] = s1[i-1] === s3[i+j-1] && dp[i-1][j]
}
if (j > 0) {
dp[i][j] ||= s2[j-1] === s3[i+j-1] && dp[i][j-1]
}
}
}
return dp[len1][len2]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#阶乘后的零
function trailingZeroes(n: number): number {
if (n === 0) {
return 0
}
let result = 0
let fiveNum = 0
for (let i = 1; i <= n; i++) {
let num = i
while (num % 10 === 0) {
num /= 10
result++
}
while (num % 5 === 0) {
num /= 5
fiveNum++
}
}
return result + Math.min(fiveNum, twoNum)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#相同的树
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p && !q || (!p && q)) {
return false
}
if (!p && !q) {
return true
}
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
#求根节点到叶节点数字之和
// 递归解法
function sumNumbers(root: TreeNode | null): number {
if (!root) {
return 0
}
let result = 0
const cascader = (root: TreeNode | null, num = '') => {
if (!root) {
return
}
if (!root.left && !root.right) {
result += Number(num + root.val)
return
}
if (root.left) {
cascader(root.left, num + root.val)
}
if (root.right) {
cascader(root.right, num + root.val)
}
}
cascader(root)
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 迭代解法
function sumNumbers(root: TreeNode | null): number {
if (!root) {
return 0
}
let result = 0
const nodes = [root]
while(nodes.length) {
const node = nodes.shift()!
if (!node.left && !node.right) {
result += node.val
} else {
if (node.left) {
node.left.val = Number(node.val.toString() + node.left.val)
nodes.push(node.left)
}
if (node.right) {
node.right.val = Number(node.val.toString() + node.right.val)
nodes.push(node.right)
}
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#汇总区间
function summaryRanges(nums: number[]): string[] {
const result: string[] = []
const len = nums.length
if (len === 0) {
return []
}
let start = nums[0].toString()
nums.push(nums[0])
for (let i = 1; i < nums.length; i++) {
if (nums[i] - 1 !== nums[i - 1]) {
if (start !== nums[i - 1].toString()) {
result.push(`${start}->${nums[i - 1]}`)
} else {
result.push(start)
}
start = nums[i].toString()
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#单词规律
function wordPattern(pattern: string, s: string): boolean {
const arr = s.split(' ')
if (arr.length !== pattern.length) {
return false
}
const map = new Map()
for(let i = 0; i < arr.length; i++) {
// 避免不同字符对应相同单词
if (map.has(pattern[i]) || map.has('$' + arr[i])) {
if (arr[i] !== map.get(pattern[i])) {
return false
}
} else {
map.set(pattern[i], arr[i])
map.set('$' + arr[i], pattern[i])
}
}
return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function wordPattern(pattern: string, s: string): boolean {
const arr = s.split(' ')
if (arr.length !== pattern.length) {
return false
}
const set = new Set()
for(let i = 0; i < arr.length; i++) {
if (set.has(arr[i]) || set.has(pattern[i] + '_')) {
if (!set.has(arr[i] + '_' + pattern[i])) {
return false
}
} else {
set.add(arr[i])
set.add(arr[i] + '_' + pattern[i])
set.add(pattern[i] + '_')
}
}
return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#相对名次
function findRelativeRanks(score: number[]): string[] {
const newArr = [...score].sort((a, b) => b - a)
const map = new Map<number, number>()
for(let i = 0; i < newArr.length; i++) {
map.set(newArr[i], i)
}
const result: string[] = []
for(let i = 0; i < score.length; i++) {
const index = map.get(score[i])
if (index === 0) {
result[i] = 'Gold Medal'
} else if (index === 1) {
result[i] = 'Silver Medal'
} else if (index === 2) {
result[i] = 'Bronze Medal'
} else {
result[i] = (index + 1).toString()
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#最长连续序列
地址(opens new window)
解释说明(opens new window)
function longestConsecutive(nums: number[]): number {
const set = new Set(nums)
let result = 0
while(set.size) {
const value = set.values().next().value
let loopNum = value - 1
let val = 1
while (set.has(loopNum)) {
set.delete(loopNum)
val++
loopNum--
}
loopNum = value + 1
while (set.has(loopNum)) {
set.delete(loopNum)
val++
loopNum++
}
result = Math.max(result, val)
set.delete(value)
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 官方解法
function longestConsecutive(nums: number[]): number {
const set = new Set(nums)
let result = 0
for (let num of set) {
if (!set.has(num - 1)) {
let val = 1
while(set.has(num + 1)) {
num++
val++
}
result = Math.max(result, val)
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#两数之和 II - 输入有序数组
// 时间复杂度为O(nlogn)，空间复杂度O(1)
function twoSum(numbers: number[], target: number): number[] {
const len = numbers.length
for (let i = 0; i < len; i++) {
let prev = i + 1
let last = len - 1
const val = target - numbers[i]
while (prev < last) {
let mid = Math.ceil((prev + last) / 2)
if (numbers[mid] === val) {
return [i + 1, mid + 1]
} else if (numbers[mid] > val) {
last = mid - 1
} else {
prev = mid
}
}
if (val === numbers[prev]) {
return [i + 1, prev + 1]
}
}
// 不存在的值
return [-1, -1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function twoSum(numbers: number[], target: number): number[] {
const len = numbers.length
for (let i = 0; i < len; i++) {
if (target - numbers[i] > numbers[len - 1]) {
continue
}
const index = numbers.indexOf(target - numbers[i], i + 1)
if (index > -1) {
return [i + 1, index + 1]
}
}
// 不存在的值
return [-1, -1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 双指针
// 时间复杂度为O(n)，空间复杂度为O(1)
function twoSum(numbers: number[], target: number): number[] {
let prev = 0
let last = numbers.length - 1
while (prev < last) {
const sum = numbers[prev] + numbers[last]
if (sum === target) {
return [prev + 1, last + 1]
} else if (sum > target) {
last--
} else {
prev++
}
}
// 不存在的值
return [-1, -1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#除自身以外数组的乘积
function productExceptSelf(nums: number[]): number[] {
const len = nums.length
// 从左扫到右，获取除当前值的乘积
const resultLeft: number[] = [1]
const resultRight: number[] = []
resultRight[len - 1] = 1
for (let i = 1; i < len; i++) {
resultLeft[i] = nums[i - 1] * resultLeft[i - 1]
}
// 从右扫到左，获取当前值的乘积
for (let i = len - 2; i >= 0; i--) {
resultRight[i] = nums[i + 1] * resultRight[i + 1]
}
for (let i = 0; i < len; i++) {
nums[i] = resultLeft[i] * resultRight[i]
}
return nums
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function productExceptSelf(nums: number[]): number[] {
const len = nums.length
// 从左扫到右，获取除当前值的乘积
const result: number[] = [1]
for (let i = 1; i < len; i++) {
result[i] = nums[i - 1] * result[i - 1]
}
let num = nums[len - 1]
for (let i = len - 2; i >= 0; i--) {
result[i] *= num
num *= nums[i]
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#O(1) 时间插入、删除和获取随机元素
// 解题思路来源于教程
class RandomizedSet {
private idxVal: Map<number, number>
private arr: number[] = []
constructor() {
this.idxVal = new Map()
}
insert(val: number): boolean {
if (this.idxVal.has(val)) {
return false
}
const index = this.arr.length
this.arr.push(val)
this.idxVal.set(val, index)
return true
}
remove(val: number): boolean {
if (!this.idxVal.has(val)) {
return false
}
const id = this.idxVal.get(val)!
this.arr[id] = this.arr[this.arr.length - 1]
this.arr.pop()
this.idxVal.set(this.arr[id], id)
this.idxVal.delete(val)
return true
}
getRandom(): number {
return this.arr[Math.floor(this.arr.length * Math.random())];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#删除有序数组中的重复项 II
function removeDuplicates(nums: number[]): number {
const len = nums.length
if (len === 1) {
return 1
}
let prev = len - 2
let num = 1
while (prev >= 0) {
// 判断是否需要删除
if (nums[prev] === nums[prev+1]) {
num++
if (num > 2) {
while (nums[prev] === nums[prev+1] && prev >= 0) {
nums.splice(prev, 1)
prev--
}
num = 1
}
} else {
num = 1
}
prev--
}
return nums.length
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function removeDuplicates(nums: number[]): number {
const len = nums.length
let prev = 1
let next = 1
let num = 1
while (prev < len) {
// 判断是否需要删除
if (nums[prev] === nums[prev-1]) {
num++
if (num > 2) {
while (nums[prev] === nums[prev-1] && prev < len) {
prev++
}
num = 1
}
} else {
num = 1
}
if (prev < len) {
nums[next++] = nums[prev++]
}
}
nums.length = next
return next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
官方解题思路中把num这个变量给删除了，通过排序这个特点来判断是否超过了两个
function removeDuplicates(nums: number[]): number {
const len = nums.length
if (len <= 2) {
return len
}
let fast = 2
let slow = 2
while (fast < len) {
if (nums[fast] !== nums[slow - 2]) {
nums[slow] = nums[fast]
++slow
}
fast++
}
return slow
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#H 指数
// console.log(hIndex([100]));
// console.log(hIndex([1,100]));
// console.log(hIndex([1,2]));
// console.log(hIndex([11,15]));
// console.log(hIndex([1,11,15]));
// console.log(hIndex([2,4,8,9,9,3]));
// console.log(hIndex([0]));
function hIndex(citations: number[]): number {
const len = citations.length
// 排序
citations.sort((a, b) => a - b)
let result = 0
let i = 0
while(i < len) {
if (citations[i - 1] === citations[i]) {
i++
} else {
if (len - i >= citations[i]) {
result = citations[i++]
} else {
// 这一步容易出错
result = Math.max(result, len - i)
break
}
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function hIndex(citations: number[]): number {
const len = citations.length
// 排序
citations.sort((a, b) => a - b)
let result = 0
let i = 0
while(i < len) {
// 起码存在 len - i 篇 论文至少被引用了 citations[i] 次
if (len - i > citations[i]) {
// 不满足需求
i++
} else if(len - i <= citations[i]) {
result = len - i
break
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
计数排序
// 判断论文数与引用次数篇数
function hIndex(citations: number[]): number {
const len = citations.length
const arr = Array.from<number>({ length: len + 1 }).fill(0)
for (let i = 0; i < len; i++) {
if (citations[i] >= len) {
arr[len]++
} else {
arr[citations[i]]++
}
}
let result = len
let total = 0
while (result > 0) {
total += arr[result]
if (total >= result) {
return result
}
result--
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#多数元素
// 注意单个的情况
// 时间复杂度O(n)，空间复杂度O(n/2)就是O(n)
function majorityElement(nums: number[]): number {
const len = nums.length
if (!len) {
return 0
}
if (len === 1) {
return nums[0]
}
const half = Math.floor(len / 2)
const obj = {}
for (const num of nums) {
if (obj[num]) {
obj[num] += 1
if (obj[num] > half) {
return num
}
} else {
obj[num] = 1
}
}
return 0
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 中间的值肯定是多数元素
// 时间复杂度O(nlogn)，空间复杂度为logn
function majorityElement(nums: number[]): number {
nums.sort((a, b) => a - b)
return nums[Math.floor(nums.length / 2)]
};
1
2
3
4
5
6
2
3
4
5
6
// Boyer-Moore 投票算法
// 基本含义就是不同的数值相互抵消
// 时间复杂度为O(n)，空间复杂度为O(1)
function majorityElement(nums: number[]): number {
let time = 1
let cur = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i] === cur) {
time++
} else {
if (time === 0) {
cur = nums[i]
} else {
time--
}
}
}
return cur
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#合并两个有序数组
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
let start = 0
for(let i = 0; i < n; i++) {
while(nums2[i] >= nums1[start] && start < m + i) {
start++
}
// 合适的位置插入值
nums1.splice(start, 0, nums2[i])
}
nums1.length = m + n
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
// 逆向双指针
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
let p1 = m - 1
let p2 = n - 1
let all = m + n - 1
let cur = 0
while (p1 >= 0 || p2 >= 0) {
if (p1 < 0) {
cur = nums2[p2--]
} else if (p2 < 0) {
cur = nums1[p1--]
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--]
} else {
cur = nums2[p2--]
}
nums1[all--] = cur
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#最大连续1的个数 III
function longestOnes(nums: number[], k: number): number {
let m = 0
let prev = 0
let next = 0
const len = nums.length
let result = 0
while(next < len) {
// 如果遇到1那么什么都不做
if (nums[next]) {
next++
continue
}
// 如果碰到0，那么需要判断，如果未达到翻转上限，那么继续下去
if (m < k) {
m++
next++
continue
}
// 达到翻转上限
result = Math.max(result, next - prev)
while(prev < len && nums[prev] === 1) {
prev++
}
prev++
next++
}
return Math.max(result, next - prev)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#存在重复元素 II
function containsNearbyDuplicate(nums: number[], k: number): boolean {
const obj: Record<number, number> = {}
for(let i = 0; i < nums.length; i++) {
if (typeof obj[nums[i]] === 'number') {
if (i - obj[nums[i]] <= k) {
return true
}
}
obj[nums[i]] = i
}
return false
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
// 滑动窗口
function containsNearbyDuplicate(nums: number[], k: number): boolean {
const set = new Set()
for(let i = 0; i < nums.length; i++) {
if (i > k) {
set.delete(nums[i-k-1])
}
if (set.has(nums[i])) {
return true
}
set.add(nums[i])
}
return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
#二叉搜索树与双向链表
var treeToDoublyList = function(root) {
if (!root) {
return root
}
let prev = null
let head = null
const cascader = (root) => {
if (!root) {
return root
}
// 左
cascader(root.left)
if (prev) {
prev.right = root
} else {
head = root
}
root.left = prev
prev = root
// 右
cascader(root.right)
}
cascader(root)
head.left = prev
prev.right = head
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#单词搜索
function exist(board: string[][], word: string): boolean {
const m = board.length
const n = board[0].length
const obj: Record<string, boolean> = {}
const cascader = (col = 0, row = 0, len = 0) => {
if (len === word.length) {
return true
}
if (len > 0) {
// 如果重复或者不相等
if (obj[`${col}_${row}`] || board[col][row] !== word[len]) {
return false
}
obj[`${col}_${row}`] = true
// 往右走
if (row < n - 1 && cascader(col, row + 1, len + 1)) {
return true
}
// 往左走
if (row > 0 && cascader(col, row - 1, len + 1)) {
return true
}
// 往上走
if (col > 0 && cascader(col - 1, row, len + 1)) {
return true
}
// 往下走
if (col < m - 1 && cascader(col + 1, row, len + 1)) {
return true
}
obj[`${col}_${row}`] = false
return false
}
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if (obj[`${i}_${j}`] || board[i][j] !== word[len]) {
continue
}
if (word.length === 1) {
return true
}
obj[`${i}_${j}`] = true
// 往右走
if (j < n - 1 && cascader(i, j + 1, len + 1)) {
return true
}
// 往左走
if (j > 0 && cascader(i, j - 1, len + 1)) {
return true
}
// 往上走
if (i > 0 && cascader(i - 1, j, len + 1)) {
return true
}
if (i < m - 1 && cascader(i + 1, j, len + 1)) {
return true
}
obj[`${i}_${j}`] = false
}
}
return false
}
return cascader()
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 把上一个函数优化
function exist(board: string[][], word: string): boolean {
const m = board.length
const n = board[0].length
const obj: Record<string, boolean> = {}
const cascader = (col = 0, row = 0, len = 0) => {
// 如果重复或者不相等
if (obj[`${col}_${row}`] || board[col][row] !== word[len]) {
return false
}
len += 1
obj[`${col}_${row}`] = true
if (len === word.length) {
return true
}
// 往右走
if (row < n - 1 && cascader(col, row + 1, len)) {
return true
}
// 往左走
if (row > 0 && cascader(col, row - 1, len)) {
return true
}
// 往上走
if (col > 0 && cascader(col - 1, row, len)) {
return true
}
// 往下走
if (col < m - 1 && cascader(col + 1, row, len)) {
return true
}
obj[`${col}_${row}`] = false
len -= 1
return false
}
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if (board[i][j] !== word[0]) {
continue
}
if (cascader(i, j, 0)) {
return true
}
}
}
return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#设计前中后队列
class FrontMiddleBackQueue {
arr: number[]
constructor() {
this.arr = []
}
pushFront(val: number): void {
this.arr.unshift(val)
}
pushMiddle(val: number): void {
const i = Math.floor(this.arr.length / 2)
this.arr.splice(i, 0, val)
}
pushBack(val: number): void {
this.arr.push(val)
}
popFront(): number {
return this.arr.shift() ?? -1
}
popMiddle(): number {
const i = Math.ceil(this.arr.length / 2) - 1
return this.arr.splice(i, 1)[0] ?? -1
}
popBack(): number {
return this.arr.pop() ?? -1
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#将整数减少到零需要的最少操作数
function minOperations(n: number): number {
let m = 0
let result = 0
while (n) {
m = Math.log2(n)
if (m === n) {
return result
}
n = Math.min(n - 2 ** Math.floor(m), 2 ** Math.ceil(m) - n)
result++
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#合并两个二维数组 - 求和法
function mergeArrays(nums1: number[][], nums2: number[][]): number[][] {
const result = nums1.map(item => [item[0], item[1]])
let j = 0
const len2 = nums2.length
let i = 0
while(i < len2) {
if (result[j]?.[0] === undefined || result[j][0] > nums2[i][0]) {
result.splice(j, 0, nums2[i])
j++
i++
continue
}
if (result[j][0] === nums2[i][0]) {
result[j][1] += nums2[i][1]
j++
i++
continue
}
if (result[j][0] < nums2[i][0]) {
j++
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#最小无法得到的或值
function minImpossibleOR(nums: number[]): number {
const set = new Set([...nums])
let i = 1
if (!set.has(1)) {
return 1
}
while (i) {
if (set.has(i)) {
i++
continue
}
// 判断是否存在，如果前面都存在，那么求出都是1的二进制的值，然后继续
const num = Number.parseInt((i - 1).toString(2).replace(/0/g, '1'), 2)
i = num + 1
if (set.has(i)) {
continue
}
return i
}
return i
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#修改两个元素的最小分数
function minimizeSum(nums: number[]): number {
const len = nums.length
if (len === 3) {
return 0
}
nums.sort((a, b) => a - b)
// 要么修改最前面两个
// 要么修改最后面两个
// 要么修改最前一个和最后一个
return Math.min(nums[len - 1] - nums[2], nums[len - 3] - nums[0], nums[len - 2] - nums[1])
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
#替换一个数字后的最大差值
function minMaxDifference(num: number): number {
const str = num.toString()
const len = str.length
let i = 0
while(i < len) {
if (Number(str[i]) < 9) {
break
}
i++
}
const max = i === len ? num : str.replace(new RegExp(str[i], 'g'), '9')
const min = str.replace(new RegExp(str[0], 'g'), '0')
return Number(max) - Number(min)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#链表的中间结点
// 时间复杂度O(n)，空间复杂度O(1)
function middleNode(head: ListNode | null): ListNode | null {
if (!head) {
return head
}
let node = head
let m = 0
while(node) {
m++
node = node.next
}
let half = Math.ceil((m - 1) / 2)
m = 0
node = head
while(m < half) {
node = node.next
m++
}
return node
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function middleNode(head: ListNode | null): ListNode | null {
if (!head) {
return head
}
let prev = head
let n = head
while(n?.next) {
prev = prev.next
n = n.next.next
}
return prev
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#复制带随机指针的链表
function copyRandomList(head: Node | null): Node | null {
if (!head) {
return head
}
const map = new WeakMap()
let node = head
let i = 0
const result: Node = new Node(head.val)
let node1 = result
const resultArr: Node[] = [node1]
// 先遍历一遍
while(node) {
if (i) {
node1.next = new Node(node.val)
node1 = node1.next
resultArr.push(node1)
}
map.set(node, i++)
node = node.next
}
// 设置random
node = head
node1 = result
i = 0
while(node) {
node1.random = resultArr[map.get(node.random)]
node1 = node1.next
node = node.next
i++
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#扁平化多级双向链表
// 拆出值，然后一个一个封装进去
function flatten(head: Node | null): Node | null {
if (!head) {
return null
}
const arr: number[] = []
const stack: number[] = []
let cur = head
while (cur) {
arr.push(cur.val)
if (!cur.child) {
cur = cur.next
continue
}
let node = cur.next
let arr1: number[] = []
while(node) {
arr1.push(node.val)
node = node.next
}
stack.unshift(...arr1)
cur = cur.child
}
arr.push(...stack)
let node = new Node(arr[0])
cur = node
for(let i = 1; i < arr.length; i++) {
cur.next = new Node(arr[i], cur)
cur = cur.next
}
return node
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function flatten(head: Node | null): Node | null {
if (!head) {
return null
}
let cur = head
while(cur) {
// 是否存在子元素
if (!cur.child) {
cur = cur.next
continue
}
let node1 = cur.child
while(node1.next) {
node1 = node1.next
}
// 如果存在next
if (cur.next) {
cur.next.prev = node1
node1.next = cur.next
}
cur.child.prev = cur
cur.next = cur.child
cur.child = null
cur = cur.next
}
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#两数相加 II
// 拆分成数组然后从后往前加
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
if (!l1) {
return l2
}
if (!l2) {
return l1
}
const arr1: number[] = []
const arr2: number[] = []
let node = l1
while(node) {
arr1.push(node.val)
node = node.next
}
node = l2
while(node) {
arr2.push(node.val)
node = node.next
}
const arr3: number[] = []
let add = 0
while(arr1.length || arr2.length) {
let sum = (arr1.pop() ?? 0) + (arr2.pop() ?? 0) + add
if (sum > 9) {
add = 1
} else {
add = 0
}
sum = sum > 9 ? sum % 10 : sum
arr3.unshift(sum)
}
if (add === 1) {
arr3.unshift(1)
}
let cur = new ListNode(arr3.shift())
node = cur
while(arr3.length) {
node.next = new ListNode(arr3.shift())
node = node.next
}
return cur
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#子字符串异或查询
function substringXorQueries(s: string, queries: number[][]): number[][] {
const arr: string[] = queries.map(([a, b]) => (b ^ a).toString(2))
const result: number[][] = []
for (let j = 0; j < arr.length; j++) {
const index = s.indexOf(arr[j])
if (index > -1) {
result.push([index, arr[j].length + index - 1])
} else {
result.push([-1,-1])
}
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#找出数组的串联值
function findTheArrayConcVal(nums: number[]): number {
let sum = 0
const len = nums.length
if (!len) {
return sum
}
while(nums.length) {
if (nums.length === 1) {
return sum + nums[0]
}
sum += Number.parseInt((nums.shift() ?? 0 ).toString() + (nums.pop() ?? 0).toString())
}
return sum
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#合并两个链表
// 注意审题，不是相等，是下标
function mergeInBetween(list1: ListNode | null, a: number, b: number, list2: ListNode | null): ListNode | null {
let delPrev: ListNode | null = null
let delNext: ListNode | null = null
const node = new ListNode(0, list1)
let cur = node
let n = 0
while (cur) {
if (n === a) {
delPrev = cur
}
if (n === b + 1) {
delNext = cur.next
break
}
cur = cur.next
n++
}
delPrev.next = list2
cur = list2
while(cur.next) {
cur = cur.next
}
cur.next = delNext
return node.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#交换链表中的节点
// 时间复杂度为O(n)，空间复杂度为O(1)
function swapNodes(head: ListNode | null, k: number): ListNode | null {
if (!head) {
return head
}
let sum = 0
let node = head
// 正数节点
let fast = head
while(node) {
if (sum === k - 1) {
fast = node
}
sum++
node = node.next
}
node = head
// 倒数节点
let slow = head
let n = 0
while(node) {
if (n === sum - k) {
slow = node
break
}
n++
node = node.next
}
n = fast.val
fast.val = slow.val
slow.val = n
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 时间复杂度为O(n)，空间复杂度为O(n)
function swapNodes(head: ListNode | null, k: number): ListNode | null {
if (!head) {
return head
}
const stack: ListNode[] = []
let node = head
while(node) {
stack.push(node)
node = node.next
}
const num = stack[k-1].val
const end = stack[stack.length - k]
stack[k - 1].val = end.val
end.val = num
return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function swapNodes(head: ListNode | null, k: number): ListNode | null {
if (!head) {
return head
}
const stack: ListNode[] = []
let node: ListNode | null = head
while(node) {
stack.push(node)
node = node.next
}
// 在中间不需要换
if (k === stack.length - k + 1) {
return head
}
stack.unshift(new ListNode(0, head))
let min = k - 1
let end = stack.length - k - 1
if (min > end) {
min = end
end = k - 1
}
const s = stack[min]
const e = stack[end]
const n = s.next
const e2 = e.next
s.next = s.next?.next ?? null
e.next = e.next?.next ?? null
// 相互挨着的情况
if (end - min === 1) {
s.next!.next = e
return stack[0].next
}
if (n) {
n.next = e.next
e.next = n
}
if (e2) {
e2.next = s.next
s.next = e2
}
return stack[0].next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#找出临界点之间的最小和最大距离
// 时间复杂度为O(n)，空间复杂度为O(1)
function nodesBetweenCriticalPoints(head: ListNode | null): number[] {
if (!head || !head.next || !head.next.next) {
return [-1, -1]
}
let max = -1
let min = Infinity
let minPrev = -1
let prev = -1
let end = 0
while (head.next.next) {
if (head.next.val > head.val && head.next.val > head.next.next.val || (head.next.val < head.val && head.next.val < head.next.next.val)) {
if (prev !== -1) {
max = end - minPrev + 1
min = Math.min(end - prev + 1, min)
}
prev = end + 1
if (minPrev === -1) {
minPrev = prev
}
}
end++
head = head.next
}
return [Number.isFinite(min) ? min : -1, max]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#螺旋矩阵 IV
// 时间复杂度为O(m * n)，空间复杂度为O(m * n)
function spiralMatrix(m: number, n: number, head: ListNode | null): number[][] {
const result: number[][] = Array.from({ length: m }, () => [])
let left = 0
let right = n - 1
let top = 0
let bottom = m - 1
while (top <= bottom) {
// 从左到右
for(let i = left; i <= right; i++) {
if (result[top][i] !== undefined) {
break
}
result[top][i] = head?.val ?? -1
head = head?.next
}
// 从上到下
for(let i = top + 1; i <= bottom; i++) {
if (result[i][right] !== undefined) {
break
}
result[i][right] = head?.val ?? -1
head = head?.next
}
// 从右到左
for(let i = right - 1; i >= left; i--) {
if (result[bottom][i] !== undefined) {
break
}
result[bottom][i] = head?.val ?? -1
head = head?.next
}
// 从下到上
for(let i = bottom - 1; i > top; i--) {
if (result[i][left] !== undefined) {
break
}
result[i][left] = head?.val ?? -1
head = head?.next
}
if (left < right) {
left++
right--
}
top++
bottom--
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#从链表中移除节点
// 时间复杂度O(n)、空间复杂度为O(n)
function removeNodes(head: ListNode | null): ListNode | null {
if (!head) {
return null
}
const arr: number[] = []
while(head) {
while(arr.length && head.val > arr[arr.length - 1]) {
arr.pop()
}
arr.push(head.val)
head = head.next
}
if (!arr.length) {
return null
}
const node = new ListNode(arr[0])
let cur = node
for(let i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i])
cur = cur.next
}
return node
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 递归
// 时间复杂度O(n)，空间复杂度O(n)
function removeNodes(head: ListNode | null): ListNode | null {
if (!head || !head.next) {
return head
}
let node = removeNodes(head.next)
if (node && head.val < node.val) {
return node
}
head.next = node
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#搜索旋转排序数组
// 时间复杂度为O(logn)，空间复杂度为O(1)
function search(nums: number[], target: number): number {
let start = 0
let end = nums.length - 1
while(start < end) {
let mid = Math.floor((start + end) / 2)
if (nums[mid] === target) {
return mid
}
// 中间的值处于左边递增的情况
if (nums[mid] > nums[end]) {
if (nums[mid] > target && nums[start] <= target) {
end = mid
} else {
start = mid + 1
}
continue
}
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1
} else {
end = mid
}
}
return nums[start] === target ? start : -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function search(nums: number[], target: number): number {
let start = 0
let end = nums.length - 1
while(start < end) {
let mid = Math.floor((start + end) / 2)
if (nums[mid] === target) {
return mid
}
if ((nums[mid] > nums[end] && (nums[mid] < target || nums[start] > target)) || (nums[mid] < nums[end] && nums[mid] < target && nums[end] >= target)) {
start = mid + 1
} else {
end = mid
}
}
return nums[start] === target ? start : -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#合并K个升序链表
// ?时间复杂度O(nm + nlogn)，空间复杂度为O(n)
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const nums: number[] = []
for(let i = lists.length - 1; i >=0; i--) {
let list = lists[i]
while(list) {
nums.push(list.val)
list = list.next
}
}
if (!nums.length) {
return null
}
nums.sort((a, b) => a - b)
const head = new ListNode(nums[0])
let node = head
for(let i = 1; i < nums.length; i++) {
node.next = new ListNode(nums[i])
node = node.next
}
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 参考下面的两两合并
// ?时间复杂度为O(n(m+n))，空间复杂度为O(m+n)
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
if (!lists.length) {
return null
}
let result = lists[0]
for(let i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i])
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
#合并两个有序链表
// 迭代
// 时间复杂度O(m+n)，空间复杂度为O(1)
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if (!list1) {
return list2
}
if (!list2) {
return list1
}
const result = new ListNode(-100, list1)
let node = result
while (node.next && list2) {
if (node.next.val <= list2.val) {
node = node.next
continue
}
node.next = new ListNode(list2.val, node.next)
list2 = list2.next
node = node.next
}
if (!node.next) {
node.next = list2
}
return result.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 递归
// 时间复杂度为O(m+n)，空间复杂度为O(m+n)
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if (!list1) {
return list2
}
if (!list2) {
return list1
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2)
return list1
}
list2.next = mergeTwoLists(list1, list2.next)
return list2
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#删除链表的中间节点
// 快慢指针，时间复杂度为O(n)、空间复杂度为O(1)
function deleteMiddle(head: ListNode | null): ListNode | null {
if (!head || !head.next) {
return null
}
let slow: ListNode | null = head
let fast = head.next.next
while(fast?.next) {
slow = slow?.next ?? null
fast = fast.next.next
}
if (slow?.next) {
slow.next = slow.next.next
}
return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#回文链表
// 时间复杂度为O(n)，空间复杂度为O(n)
function isPalindrome(head: ListNode | null): boolean {
// 也可以使用字符串
const arr: number[] = []
while(head) {
arr.push(head.val)
head = head.next
}
for (let i = 0, j = arr.length - 1; i < j; i++, j--) {
if (arr[i] !== arr[j]) {
return false
}
}
return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 递归写法
// 时间复杂度 时间复杂度为O(n) 空间复杂度O(n)
function isPalindrome(head: ListNode | null): boolean {
let prev = head
const cascader = (cur: ListNode | null) => {
if (!cur) {
return true
}
let bool = cascader(cur.next)
if (!bool) {
return false
} else if (prev.val !== cur.val) {
return false
}
prev = prev.next
return true
}
return cascader(head)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 时间复杂度为O(n), 空间复杂度为O(1)
// 先获取中间位置的节点，然后反转右半部分的节点，然后进行对比
function isPalindrome(head: ListNode | null): boolean {
if (!head || !head.next) {
return true
}
const getMid = (head: ListNode | null) => {
let slow = head
let fast = head.next
while (fast) {
fast = fast.next?.next
slow = slow.next
}
return slow
}
const reverse = (head: ListNode | null) => {
let prev = null
let cur = head
while(cur) {
let next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}
let prev = getMid(head)
let next = reverse(prev)
while(head && next) {
if (head.val !== next.val) {
return false
}
head = head.next
next = next.next
}
return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#对链表进行插入排序
// 时间复杂度O(n^2) 空间复杂度O(1)
function insertionSortList(head: ListNode | null): ListNode | null {
if (!head) {
return head
}
let node = new ListNode(head.val)
head = head.next
while (head) {
let cur: ListNode | null = node
while (cur.next && cur.next.val < head.val) {
cur = cur.next
}
if (cur.val > head.val) {
node = new ListNode(head.val, node)
} else {
cur.next = new ListNode(head.val, cur.next)
}
head = head.next
}
return node
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 时间复杂度O(n^2) 空间复杂度O(1)
function insertionSortList(head: ListNode | null): ListNode | null {
if (!head) {
return head
}
// 空节点
let node = new ListNode(0, head)
// 排序后链表的最后一个节点
let lastNode: ListNode | null = head
// 未排序的第一个节点
let cur = head.next
while(cur) {
if (lastNode!.val <= cur.val) {
lastNode = lastNode!.next
} else {
// 找到需要排序前的一个节点，然后改变指针指向
let prev = node
while(prev && prev.next!.val < cur.val) {
prev = prev.next!
}
lastNode!.next = cur.next
cur.next = prev.next
prev.next = cur
}
cur = lastNode!.next
}
return node.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#排序链表
// 时间复杂度为O(nlogn)，空间复杂度为O(n)
function sortList(head: ListNode | null): ListNode | null {
const arr: number[] = []
while(head) {
arr.push(head.val)
head = head.next
}
arr.sort((a, b) => a - b)
let node = new ListNode(0)
let cur = node
for (const val of arr) {
cur.next = new ListNode(val)
cur = cur.next
}
return node.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#链表组件
// 时间复杂度为O(n)，空间复杂度为O(m)
function numComponents(head: ListNode | null, nums: number[]): number {
const set = new Set(nums)
let cur = head
let result = 0
let num = 0
while(cur) {
if (set.has(cur.val)) {
if (num === 0) {
result++
}
num++
} else {
num = 0
}
cur = cur.next
}
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 参考官方解法，把num改成一个boolean
function numComponents(head: ListNode | null, nums: number[]): number {
const set = new Set(nums)
let cur = head
let result = 0
let isFirst = true
while(cur) {
if (set.has(cur.val)) {
if (isFirst) {
result++
isFirst = false
}
} else {
isFirst = true
}
cur = cur.next
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#分隔链表
// 时间复杂度O(n)、空间复杂度O(n)
function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
let sum = 0
let cur = head
let arr: (ListNode | null)[] = []
while(cur) {
cur = cur.next
sum++
}
cur = head
let n = Math.ceil(sum / k)
sum -= n
k--
while(cur) {
if (n === 1) {
n = Math.ceil(sum / k)
sum -= n
k--
let next = cur.next
cur.next = null
arr.push(head)
head = next
cur = next
continue
}
cur = cur.next
n--
}
for (let i = 0; i <= k; i++) {
arr.push(null)
}
return arr
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
let cur = head
let sum = 0
let arr: (ListNode | null)[] = []
while(cur) {
sum++
cur = cur.next
}
cur = head
let m = 0
for (let i = k; i > 0; i--) {
m = Math.ceil(sum / i)
sum -= m
if (m === 0) {
arr.push(null)
continue
}
while(m > 1) {
cur = cur.next
m--
}
let next = cur.next
cur.next = null
arr.push(head)
head = next
cur = next
}
return arr
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 递归解法
// 时间复杂度O(n)、空间复杂度O(n)
function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
let cur = head
let sum = 0
let arr: (ListNode | null)[] = []
while(cur) {
sum++
cur = cur.next
}
for (let i = k; i > sum; i--) {
arr.push(null)
k--
}
let n = Math.floor(sum / k)
sum -= n
k--
const cascader = (head: ListNode | null) => {
if (!head) {
return head
}
const node = cascader(head.next)
n--
if (n === -1) {
n = Math.floor(sum / k)
k--
sum -= n
arr.unshift(node)
head.next = null
n--
return head
}
return head
}
cascader(head)
if (head) {
arr.unshift(head)
}
return arr
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#数组中字符串的最大值
function maximumValue(strs: string[]): number {
// 使用正则判断是否存在字符串
const reg = /[a-z]/
let num = 0
for (const str of strs) {
num = Math.max(num, reg.test(str) ? str.length : Number.parseInt(str))
}
return num
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10