8000 Merge branch 'master' of github.com:zbcoder/algorithm-exercise · freezeYe/leetcode-js@ae5cb2c · GitHub
[go: up one dir, main page]
Skip to content

Commit ae5cb2c

Browse files
author
jober
committed
Merge branch 'master' of github.com:zbcoder/algorithm-exercise
2 parents a810686 + 9251aba commit ae5cb2c

File tree

3 files changed

+141
-0
lines changed

3 files changed

+141
-0
lines changed

‎23.Array.H-MergeKSortedLists.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/**
2+
* Merge k sorted linked lists and return it as one sorted list.Analyze and describe its complexity.
3+
* Input:
4+
* [
5+
* 1 -> 4 -> 5,
6+
* 1 -> 3 -> 4,
7+
* 2 -> 6
8+
* ]
9+
* Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
10+
*/
11+
12+
/**
13+
* Definition for singly-linked list.
14+
* function ListNode(val) {
15+
* this.val = val;
16+
* this.next = null;
17+
* }
18+
*/
19+
/**
20+
* @param {ListNode[]} lists
21+
* @return {ListNode}
22+
*/
23+
var mergeKLists = function (lists) {
24+
if (!lists.length) return null
25+
if (lists.length === 1) return lists[0]
26+
function helper(lists, left, right) {
27+
if (left < right) {
28+
const middle = Math.trunc((left + right) / 2)
29+
return merge(helper(lists, left, middle), helper(lists, middle + 1, right))
30+
}
31+
return lists[left]
32+
}
33+
function merge(list1, list2) {
34+
let head = null
35+
let curNode = null
36+
while (list1 && list2) {
37+
let minNode = null
38+
if (list1.val < list2.val) {
39+
minNode = list1
40+
list1 = list1.next
41+
} else {
42+
minNode = list2
43+
list2 = list2.next
44+
}
45+
if (!head) {
46+
head = minNode
47+
curNode = head
48+
} else {
49+
curNode.next = minNode
50+
curNode = curNode.next
51+
}
52+
}
53+
if (head) {
54+
if (list1) curNode.next = list1
55+
if (list2) curNode.next = list2
56+
} else {
57+
if (list1) head = list1
58+
if (list2) head = list2
59+
}
60+
61+
return head
62+
}
63+
return helper(lists, 0, lists.length - 1)
64+
};

‎239.Array.H-SlidingWindowMaximum.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/**
2+
* Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
3+
* Return the max sliding window.
4+
* Note:
5+
* You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
6+
* Follow up:
7+
* Could you solve it in linear time?
8+
* Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
9+
* Output: [3,3,5,5,6,7]
10+
*/
11+
12+
/**
13+
* @param {number[]} nums
14+
* @param {number} k
15+
* @return {number[]}
16+
*/
17+
var maxSlidingWindow = function (nums, k) {
18+
const q = new Deque()
19+
const res = []
20+
for (let i = 0; i < nums.length; i++) {
21+
while (!q.empty() && q.front() == i - k) q.pop_front()
22+
while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back()
23+
q.push_back(i)
24+
if (i >= k - 1) res.push(nums[q.front()])
25+
}
26+
return res
27+
};
28+
29+
function Deque() {
30+
this.dqueue = []
31+
this.push_back = (num) => this.dqueue.push(num)
32+
this.front = () => this.dqueue[0]
33+
this.back = () => this.dqueue[this.dqueue.length - 1]
34+
this.pop_front = () => this.dqueue.shift()
35+
this.pop_back = () => this.dqueue.pop()
36+
this.empty = () => !this.dqueue.length
37+
}

‎76.Array.H-MinimumWindowSubstring.js

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/**
2+
* Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
3+
* Example:
4+
* Input: S = "ADOBECODEBANC", T = "ABC"
5+
* Output: "BANC"
6+
* Note:
7+
* If there is no such window in S that covers all characters in T, return the empty string "".
8+
* If there is such window, you are guaranteed that there will always be only one unique minimum window in S.} s
9+
*/
10+
11+
/**
12+
* @param {string} s
13+
* @param {string} t
14+
* @return {string}
15+
*/
16+
var minWindow = function (s, t) {
17+
const letterMap = {}
18+
let minLen = Infinity,
19+
left = 0,
20+
cnt = 0,
21+
res = ''
22+
for (let v of t) {
23+
if (letterMap[v] !== undefined) letterMap[v] = ++letterMap[v]
24+
else letterMap[v] = 1
25+
}
26+
for (let i = 0; i < s.length; i++) {
27+
if (--letterMap[s[i]] >= 0) cnt++
28+
while (cnt === t.length) {
29+
const localLen = i - left + 1
30+
if (minLen > localLen) {
31+
minLen = localLen
32+
res = s.substr(left, minLen)
33+
}
34+
if (++letterMap[s[left]] > 0) cnt--
35+
left++
36+
}
37+
38+
}
39+
return res
40+
};

0 commit comments

Comments
 (0)
0