8000 update · SivaCse/leetcode-javascript@fba8bd4 · GitHub
[go: up one dir, main page]
Skip to content

Commit fba8bd4

Browse files
author
Chihung Yu
committed
update
1 parent b517b1a commit fba8bd4

5 files changed

+502
-0
lines changed

‎163 Missing Ranges.js

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} lower
4+
* @param {number} upper
5+
* @return {string[]}
6+
*/
7+
var findMissingRanges = function(nums, lower, upper) {
8+
var missing = [];
9+
if (nums.length === 0) {
10+
missing.push(getRange(lower,upper));
11+
return missing;
12+
}
13+
14+
// Only need to search range between lower and upper
15+
var next = lower;
16+
for(var i = 0; i < nums.length; i++) {
17+
var val = nums[i];
18+
19+
if (val < next) {
20+
continue;
21+
} else if (val === next) {
22+
next++;
23+
continue;
24+
}
25+
// val > next
26+
missing.push(getRange(next, val-1));
27+
next = val + 1;
28+
}
29+
30+
if (next <= upper) {
31+
missing.push(getRange(next, upper));
32+
}
33+
34+
return missing;
35+
};
36+
37+
function getRange(lower, upper) {
38+
return upper === lower ? `${lower}` : `${lower}->${upper}`;
39+
}

‎681 Next Closest Time .js

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
// Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.
2+
3+
// You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.
4+
5+
// Example 1:
6+
7+
// Input: "19:34"
8+
// Output: "19:39"
9+
// Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.
10+
// Example 2:
11+
12+
// Input: "23:59"
13+
// Output: "22:22"
14+
// Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.
15+
16+
17+
18+
19+
// Approach #1: Simulation [Accepted]
20+
// Intuition and Algorithm
21+
22+
// Simulate the clock going forward by one minute. Each time it moves forward, if all the digits are allowed, then return the current time.
23+
24+
// The natural way to represent the time is as an integer t in the range 0 <= t < 24 * 60. Then the hours are t / 60, the minutes are t % 60, and each digit of the hours and minutes can be found by hours / 10, hours % 10 etc.
25+
26+
/**
27+
* @param {string} time
28+
* @return {string}
29+
*/
30+
var nextClosestTime = function(time) {
31+
let cur = 60 * parseInt(time.substring(0, 2));
32+
cur += parseInt(time.substring(3));
33+
const allowed = new Set();
34+
35+
for(var i = 0; i < time.length; i++) {
36+
if (time[i] !== ':') {
37+
allowed.add(parseInt(time[i]));
38+
}
39+
}
40+
41+
while(true) {
42+
cur = (cur + 1) % (24*60);
43+
var curTime = [
44+
Math.floor(cur / 60 / 10), // hour 24 -> 2
45+
Math.floor(cur / 60) % 10, // hour 24 -> 4
46+
Math.floor((cur % 60) / 10), // minutes 59 -> 5
47+
cur % 60 % 10, // minutes 59 -> 9
48+
];
49+
50+
for(i = 0; i < curTime.length; i++) {
51+
var t = curTime[i];
52+
if (!allowed.has(t)) {
53+
break;
54+
}
55+
if (i === curTime.length - 1) {
56+
let hour = Math.floor(cur / 60);
57+
let min = cur % 60;
58+
59+
if (hour < 10) {
60+
hour = '0' + hour;
61+
} else {
62+
hour = '' + hour;
63+
}
64+
65+
if (min < 10) {
66+
min = '0' + min;
67+
} else {
68+
min = '' + min;
69+
}
70+
71+
return hour + ':' + min;
72+
}
73+
}
74+
}
75+
};

‎[0004] Median of Two Sorted Arrays.js

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
// /**
2+
// * @param {number[]} nums1
3+
// * @param {number[]} nums2
4+
// * @return {number}
5+
// */
6+
7+
// // http://blog.csdn.net/yutianzuijin/article/details/11499917
8+
// var findMedianSortedArrays = function(nums1, nums2) {
9+
// var m = nums1.length;
10+
// var n = nums2.length;
11+
// var total = m + n;
12+
13+
// if(total%2 === 1) {
14+
// return findKth(nums1, m, nums2, n, parseInt(total/2) + 1);
15+
// } else {
16+
// return (findKth(nums1, m, nums2, n, parseInt(total/2)) + findKth(nums1, m, nums2, n, parseInt(total/2) + 1))/2;
17+
// }
18+
// };
19+
20+
21+
// function findKth(a, m, b, n, k) {
22+
// // always assume that m is equal or smaller than n
23+
// if(m > n) {
24+
// return findKth(b, n, a, m, k);
25+
// }
26+
27+
// if(m === 0) {
28+
// return b[k-1];
29+
// }
30+
31+
// if(k === 1) {
32+
// return Math.min(a[0],b[0]);
33+
// }
34+
35+
// // divide k into two parts
36+
// var pa = Math.min(parseInt(k/2), m);
37+
// var pb = k - pa;
38+
39+
// if(a[pa - 1] < b[pb - 1]) {
40+
// return findKth(a.slice(pa), m - pa, b, n, k - pa);
41+
// } else if(a[pa - 1] > b[pb - 1]) {
42+
// return findKth(a, m, b.slice(pb), n - pb, k - pb);
43+
// } else {
44+
// return a[pa - 1];
45+
// }
46+
// }
47+
48+
49+
// /**
50+
// * @param {number[]} nums1
51+
// * @param {number[]} nums2
52+
// * @return {number}
53+
// */
54+
// var findMedianSortedArrays = function(nums1, nums2) {
55+
// var total = nums1.length + nums2.length;
56+
//
57+
// if (total % 2 === 1) {
58+
// return findKth(nums1, 0, nums2, 0, parseInt(total/2) + 1);
59+
// } else {
60+
// return (
61+
// findKth(nums1, 0, nums2, 0, parseInt(total/2))
62+
// + findKth(nums1, 0, nums2, 0, parseInt(total/2) + 1)
63+
// )/2;
64+
// }
65+
// };
66+
//
67+
// function findKth(nums1, start1, nums2, start2, kth) {
68+
// var len1 = nums1.length - start1;
69+
// var len2 = nums2.length - start2;
70+
//
71+
// if (len1 > len2) {
72+
// return findKth(nums2, start2, nums1, start1, kth);
73+
// }
74+
//
75+
// if (len1 === 0) {
76+
// return nums2[kth - 1];
77+
// }
78+
//
79+
// if (kth === 1) {
80+
// return Math.min(nums1[start1], nums2[start2]);
81+
// }
F987 82+
//
83+
// // divide kth into 2 parts
84+
// var part1 = Math.min(parseInt(kth/2), len1);
85+
// var part2 = kth - part1;
86+
//
87+
// if (nums1[start1 + part1 - 1] < nums2[start2 + part2 - 1]) {
88+
// return findKth(nums1, start1 + part1, nums2, start2, kth - part1);
89+
// } else if (nums1[start1 + part1 - 1] > nums2[start2 + part2 - 1]) {
90+
// return findKth(nums1, start1, nums2, start2 + part2, kth - part2);
91+
// } else {
92+
// return nums1[start1 + part1 - 1];
93+
// }
94+
// }
95+
96+
97+
98+
/**
99+
* @param {number[]} nums1
100+
* @param {number[]} nums2
101+
* @return {number}
102+
*/
103+
var findMedianSortedArrays = function(nums1, nums2) {
104+
const len = nums1.length + nums2.length;
105+
106+
if (len % 2 === 1) {
107+
return findKth(nums1, 0, nums2, 0, Math.floor(len/2) + 1);
108+
} else {
109+
const first = findKth(nums1, 0, nums2, 0, Math.floor(len/2));
110+
const second = findKth(nums1, 0, nums2, 0, Math.floor(len/2) + 1);
111+
112+
return (first + second) / 2;
113+
}
114+
};
115+
116+
function findKth(nums1, start1, nums2, start2, kth) {
117+
const len1 = nums1.length - start1;
118+
const len2 = nums2.length - start2;
119+
120+
if (len1 > len2) {
121+
return findKth(nums2, start2, nums1, start1, kth);
122+
}
123+
124+
if (len1 === 0) {
125+
return nums2[kth - 1];
126+
}
127+
128+
if (kth === 1) {
129+
return Math.min(nums1[start1], nums2[start2]);
130+
}
131+
132+
// Three conditions here, len1 < kth/2, len1 === kth/2, len1 > kth/2
133+
const kth1 = Math.min(Math.floor(kth/2), len1);
134+
const kth2 = kth - kth1;
135+
136+
const nums1Kth = nums1[start1 + kth1 - 1];
137+
const nums2Kth = nums2[start2 + kth2 - 1];
138+
139+
if (nums1Kth < nums2Kth) {
140+
return findKth(nums1, start1 + kth1, nums2, start2, kth2);
141+
} else if (nums1Kth > nums2Kth) {
142+
return findKth(nums1, start1, nums2, start2 + kth2, kth1);
143+
} else {
144+
return nums1Kth;
145+
}
146+
}

0 commit comments

Comments
 (0)
0