Javascript in Leetcode 04–06 | 面試問題
resource code也可以到我的github找喔 | 來這裡
04-Median-of-Two-Sorted-Arrays
More explanation | Here
Leetcode 04 Problems | Here
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
// merge sort // complexity O(n + m) function findMedianSortedArrays(nums1 = [], nums2 = []) { let i1 = 0; let i2 = 0; const len1 = nums1.length; const len2 = nums2.length; const len = len1 + len2; if (len === 0) { return null; } const merged = []; while (i1 < len1 && i2 < len2) { if (nums1[i1] <= nums2[i2]) { merged.push(nums1[i1++]); } else { merged.push(nums2[i2++]); } } while (i1 < len1) { merged.push(nums1[i1++]); } while (i2 < len2) { merged.push(nums2[i2++]); } const isOdd = len % 2; if (isOdd) { return merged[(len - 1) / 2]; } else { return (merged[merged.length / 2] + merged[merged.length / 2 - 1]) / 2; } } const nums1 = [1, 3]; const nums2 = [2]; console.log(findMedianSortedArrays(nums1, nums2));
05-Longest-Palindromic-Substring
如果需要,直接去討論區看吧!! 😂
Leetcode problem 05 | Here💪
Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consist of only digits and English letters.
var longestPalindrome = function (s) { if (s.length < 2) return s; let max = ""; for (let i = 0; i < s.length; i++) { let left = helper(i, i, s); let right = helper(i, i + 1, s); let currMax = left.length >= right.length ? left : right; max = currMax.length > max.length ? currMax : max; } return max; }; function helper(left, right, s) { let curr = ""; while (left >= 0 && right < s.length && s[left] === s[right]) { curr = s.substring(left, right + 1); left -= 1; right += 1; } return curr; }
06. Zigzag Conversion
Leetcode Problem 06 | Here
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Example 3:
Input: s = "A", numRows = 1 Output: "A"
Constraints:
1 <= s.length <= 1000
s
consists of English letters (lower-case and upper-case),','
and'.'
.1 <= numRows <= 1000
function convert(s, numRows) { if (numRows === 1) { return s; } const N = s.length; const arr = [...Array(numRows)].map((r) => []); for (let i = 0; i < N; i++) { const pos = i % (2 * numRows - 2); const ii = pos < numRows ? pos : 2 * numRows - 2 - pos; arr[ii].push(s[i]); } return arr.map((r) => r.join("")).join(""); }