Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit e19c670

Browse files
feat: 增加一些Js解法
1 parent fb72abf commit e19c670

10 files changed

+737
-182
lines changed

‎Array/KthLargestElementInAnArray.js

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} k
4+
* @return {number}
5+
*/
6+
7+
// 写了个快排和归并。
8+
function sort(arr) {
9+
// 快排
10+
if (arr.length === 0) {
11+
return arr
12+
}
13+
14+
// 选种
15+
let bean = Math.floor((arr.length-1) / 2)
16+
let base = arr[bean]
17+
let bigger = []
18+
let smaller = []
19+
20+
for (let [index, item] of arr.entries()) {
21+
if (index === bean) {
22+
continue
23+
}
24+
25+
if (item >= base) {
26+
bigger.push(item)
27+
} else {
28+
smaller.push(item)
29+
}
30+
}
31+
32+
return [...sort(smaller), base, ...sort(bigger)]
33+
34+
}
35+
36+
// 归并
37+
function split(arr) {
38+
let bean = Math.floor((arr.length-1) / 2)
39+
let left = arr.slice(0, bean)
40+
let right = arr.slice(bean)
41+
42+
return [left, right]
43+
}
44+
45+
function merge(arr, arr2) {
46+
let result = []
47+
48+
let index1 = 0
49+
let index2 = 0
50+
51+
while (index1 <= arr.length - 1 && index2 <= arr2.length - 1) {
52+
if (arr[index1] < arr2[index2]) {
53+
result.push(arr[index1])
54+
index1 += 1
55+
} else if (arr[index1] > arr2[index2]) {
56+
result.push(arr2[index2])
57+
index2 += 1
58+
} else {
59+
result.push(arr[index1], arr2[index2])
60+
index1 += 1
61+
index2 += 1
62+
}
63+
}
64+
// 如果第一个arr
65+
if (index1 <= arr.length - 1) {
66+
result.push(...arr.slice(index1))
67+
}
68+
69+
if (index2 <= arr2.length - 1) {
70+
result.push(...arr2.slice(index2))
71+
}
72+
73+
return result
74+
}
75+
76+
function sort2(arr) {
77+
if (arr.length <= 8) {
78+
return sort(arr)
79+
}
80+
let sp = split(arr)
81+
// return sp.reduce((a,b) => merge(a,b))
82+
return merge(sort2(sp[0]), sort2(sp[1]))
83+
}
84+
85+
86+
87+
var findKthLargest = function(nums, k) {
88+
// nums = nums.sort((a,b) => b-a)
89+
// nums = sort(nums)
90+
// nums = split(nums)
91+
// nums = merge(nums[0], nums[1])
92+
nums = sort2(nums)
93+
// console.log(nums)
94+
return nums[nums.length-k]
95+
};

‎Array/LinkedListCycle.js

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
9+
/**
10+
* @param {ListNode} head
11+
* @return {boolean}
12+
*/
13+
14+
// 两个指针,一个一次走一步,一个一次走两步,如果有环会在某处相遇。
15+
var hasCycle = function(head) {
16+
if (!head) {
17+
return false
18+
}
19+
let oneIndex = head
20+
let twoIndex = head.next
21+
22+
if (!twoIndex) {
23+
return false
24+
}
25+
26+
while (oneIndex && twoIndex) {
27+
if (oneIndex === twoIndex) {
28+
return true
29+
}
30+
31+
oneIndex = oneIndex.next
32+
twoIndex = twoIndex.next
33+
34+
if (!twoIndex || !twoIndex.next) {
35+
return false
36+
}
37+
38+
twoIndex = twoIndex.next
39+
}
40+
41+
return false
42+
};

‎Array/ReverseLinkedList.js

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val, next) {
4+
* this.val = (val===undefined ? 0 : val)
5+
* this.next = (next===undefined ? null : next)
6+
* }
7+
*/
8+
/**
9+
* @param {ListNode} head
10+
* @return {ListNode}
11+
*/
12+
13+
// 翻转链表的思路
14+
// 把head取出来,把head.next取出来,head.next.next也取出来。
15+
// head.next = head
16+
// 新的(head.next和head)与head.next.next进行新一轮交换。
17+
// 直至空。
18+
// PS,链表操作好麻烦。
19+
var reverseList = function(head) {
20+
21+
let newHead = null
22+
23+
// 先不判断进行一次交换
24+
let nHead = head
25+
if (!nHead) {
26+
return null
27+
}
28+
let next = nHead.next
29+
if (!next) {
30+
return nHead
31+
}
32+
let lNext = next.next
33+
34+
next.next = nHead
35+
nHead.next = null
36+
37+
newHead = next
38+
39+
while (nHead && next && next.next) {
40+
nHead = lNext
41+
if (!nHead) {
42+
return newHead
43+
}
44+
45+
next = nHead.next
46+
47+
if (!next) {
48+
nHead.next = newHead
49+
return nHead
50+
}
51+
lNext = next.next
52+
53+
next.next = nHead
54+
nHead.next = newHead
55+
56+
newHead = next
57+
58+
}
59+
};

‎Array/ReverseNodesInk-Group.js

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
// 这个有图,直接看链接吧。
2+
// https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
3+
// hard
4+
5+
/**
6+
* Definition for singly-linked list.
7+
* function ListNode(val, next) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.next = (next===undefined ? null : next)
10+
* }
11+
*/
12+
/**
13+
* @param {ListNode} head
14+
* @param {number} k
15+
* @return {ListNode}
16+
*/
17+
18+
// 思路就是获取k个节点,然后翻转。
19+
// 循环这个操作。
20+
// 思路不难,个人感觉难点在于ListNode是在不好操作。
21+
var reverseKGroup = function(head, k) {
22+
function getKNodes(head) {
23+
let nodes = []
24+
let newHead = head
25+
26+
//
27+
while (nodes.length < k && newHead) {
28+
nodes.push(newHead)
29+
newHead = newHead.next
30+
}
31+
32+
return nodes
33+
}
34+
35+
function reverse(nodes) {
36+
// 将nodes里的ListNode关系翻转
37+
if (!nodes.length) {
38+
return null
39+
}
40+
41+
if (nodes.length === 1) {
42+
return [nodes[0],null,null]
43+
}
44+
45+
// 新开始的节点应为最后一个节点的下一个
46+
let newStartNode = nodes[nodes.length - 1].next
47+
// 最后一个节点是翻转前的第一个节点
48+
let lastNode = nodes[0]
49+
50+
let rNodes = nodes.reverse()
51+
// 翻转后的头节点是翻转后的最后一个节点。
52+
let first = rNodes[0]
53+
let indexF = first
54+
for (let i of rNodes.slice(1)) {
55+
i.next = null
56+
indexF.next = i
57+
indexF = i
58+
}
59+
// 返回新的头
60+
// 和下次迭代应该开始新头,为原nodes[-1]的next
61+
return [first, newStartNode, lastNode]
62+
63+
}
64+
65+
let first = getKNodes(head)
66+
67+
if (!first.length) {
68+
return null
69+
}
70+
71+
if (first.length < k) {
72+
return head
73+
}
74+
75+
let [newHead, newStartNode, lastNode] = reverse(first)
76+
let indexNewHead = lastNode
77+
78+
// 循环翻转
79+
// newHead为新的head,返回用,newStartNode是下一次取K个node开始的节点。
80+
// lastNode为当前节点的最后一个节点,用来将新的节点的head接到最后一个节点上。
81+
while (1) {
82+
if (!newStartNode) {
83+
return newHead
84+
}
85+
let kNodes = getKNodes(newStartNode)
86+
if (kNodes.length < k) {
87+
if (indexNewHead) {
88+
indexNewHead.next = kNodes[0]
89+
}
90+
return newHead
91+
}
92+
93+
let [n, ns, l] = reverse(kNodes)
94+
indexNewHead.next = n
95+
newStartNode = ns
96+
lastNode = l
97+
indexNewHead = l
98+
}
99+
};

‎Array/twoSum.js

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} target
4+
* @return {number[]}
5+
*/
6+
// 简单的O(1)查找。
7+
var twoSum = function(nums, target) {
8+
let dicts = {}
9+
10+
for (let [index, data] of nums.entries()) {
11+
dicts[data] ? dicts[data].push(index) : (dicts[data] = [index])
12+
}
13+
14+
15+
for (let i of nums) {
16+
if (dicts[target - i]) {
17+
if (target-i === i) {
18+
if (dicts[i].length === 2) {
19+
return [dicts[i][0], dicts[i][1]]
20+
} else {
21+
continue
22+
}
23+
24+
}
25+
26+
return [dicts[i][0], dicts[target-i][0]]
27+
}
28+
}
29+
};

‎DP/ClimbingStairs.js

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* @param {number} n
3+
* @return {number}
4+
*/
5+
var climbStairs = function(n) {
6+
let dp = [
7+
1,
8+
2
9+
]
10+
11+
if (n <= 2) {
12+
return dp[n-1]
13+
}
14+
15+
for (let i=2;i<n;i++) {
16+
dp.push(dp[i-2]+dp[i-1])
17+
}
18+
return dp[n-1]
19+
};

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /