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("");
}