面试算法

快手 - 2024/9/13

找出两个数组中的重复元素。 深入思考： 1.优化时间复杂度 2.优化空间复杂度 3.如果一个数组比另一个数组长很多怎么改？

function findDuplicates(nums1, nums2) {
  // 去除重复添加的元素
  const ans = new Set();
  if (nums1.length === 0 || nums2.length === 0) return [];
  for (let num1 of nums1) {
    for (let num2 of nums2) {
      if (num1 === num2) {
        ans.add(num1);
      }
    }
  }
  return Array.from(ans);
}
function findDuplicates(nums1, nums2) {
  const ans = new Set();
  if (nums1.length === 0 || nums2.length === 0) return [];
  const nums1Set = new Set(nums1);
  for (let num2 of nums2) {
    if (nums1Set.has(num2)) {
      ans.add(num2);
    }
  }
  return Array.from(ans);
}
//时间复杂度为O(n+m)

function findDuplicates(nums1, nums2) {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  const ans = [];
  let i = 0;
  let j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] === nums2[j]) {
      ans.push(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return ans;
}

百度 - 2024/10/19

重排链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  const mid = middle(head);
  let head2 = reverseList(mid);
  while (head2.next !== null) {
    const nxt1 = head.next;
    const nxt2 = head2.next;
    head.next = head2;
    head2.next = nxt1;
    head2 = nxt2;
    head = nxt1;
  }
};
function middle(head) {
  let slow = head,
    fast = head;
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}
function reverseList(head) {
  let pre = null,
    cur = head;
  while (cur !== null) {
    let nxt = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nxt;
  }
  return pre;
}

字节 - 2024/9/24

下一个排列(要求最优解)

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    [nums[j], nums[i]] = [nums[i], nums[j]];
  }
  let l = i + 1;
  let r = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++;
    r--;
  }
};