This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

65. Partition list

The label

  • The list
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a list of head nodes and a specific value x, separate the list so that all nodes less than x appear before nodes greater than or equal to x.

You should preserve the initial relative position of each node in the two partitions.

Input: head = [1,4,3,2,5,2], x = 3 output: [1,2,2,4,3,5]Copy the code

The basic idea

  1. Two linked lists are constructed, one for nodes smaller than x and the other for nodes larger than x.
  2. Start a scan at the head of the original linked list, and then group the two types of points into two new linked lists.
  3. Since the original linked list is scanned from scratch, the original order in the original linked list will still be preserved.
  4. The final result will be stored in the two new lists. The final answer can be obtained by joining the two lists, which are smaller than X, to the front of the list which is larger than X.

Basic steps

  1. Create two linked lists, big && Small
  2. Create two lists of virtual headers that handle empty boundary conditions
  3. Start traversing, sorting the sizes
  4. Size array concatenation, tail null, return small array header.

Writing implement

var partition = function(head, x) {
  // Create two lists, one greater than x and one less than x
  let [small, big] = [new ListNode(0), new ListNode(0)]
  // Create two lists of virtual head nodes, handle the head node is empty boundary condition more convenient
  let [smallPreHead, bigPreHead] = [small, big]
  // Start to make small, big lists
  while(head ! = =null) {
    if (head.val < x) {
      small.next = head;
      small = small.next;
    } else {
      big.next = head;
      big = big.next;
    }
    head = head.next;
  }
  // The end of the big array is empty
  big.next = null;
  // Array link
  small.next = bigPreHead.next;
  return smallPreHead.next;
}
Copy the code

66. Merge two ordered arrays (merge-sorted-array)

The label

  • An array of
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Merge nums2 into nums1 to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

Example:

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]Copy the code

The relevant knowledge

Array.prototype.splice()

The splice() method modifies an array by deleting or replacing existing elements or adding new ones in place, and returns the modified contents as an array. This method changes the original array.

// Delete 0 and add 'Feb' to index === 1
const months = ['Jan'.'March'.'April'.'June'];
months.splice(1.0.'Feb');
// inserts at index 1
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "June"]

// Delete 1 element ("June") at index === 4 and add 'May'
months.splice(4.1.'May');
// replaces 1 element at index 4
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "May"]
Copy the code

grammar

array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

parameter

  • start

    • Specifies the starting position of the modification (counting from 0).
    • If the length of the array is exceeded, the contents are appended from the end of the array.
    • If it is negative, it represents the number of bits from the end of the array (counting from -1, which means -n is the NTH element to the last and equivalent to array.length-n);
    • If the absolute value of a negative number is greater than the length of the array, the starting position is bit 0.

  • DeleteCount optional

    • The integerSaid,The number of array elements to remove.
    • If deleteCount is greater than the total number of elements after start, all elements after start are deleted (including the start bit).
    • If deleteCount is omitted, or its value is greater than or equal to array.length-start (that is, if it is greater than or equal to the number of all elements after start), then all elements in the array after start are deleted.
    • If deleteCount is 0 or negative, the element is not removed. In this case, at least one new element should be added.

  • item1, item2, ... optional

    • The element to add to the array
    • Start at the start position. If not specified, splice() will delete only array elements.

The return value

  • An array of deleted elements.
  • If only one element is removed, an array containing only one element is returned. If no element is deleted, an empty array is returned.

Note that if the number of elements added to the array does not equal the number of elements removed, the length of the array changes accordingly.

Array.prototype.sort()

The sort() method sorts the elements of an array using an in-place algorithm and returns the array. The default sort order is built when converting elements to strings and then comparing their UTF-16 code unit value sequences.

const months = ['March'.'Jan'.'Feb'.'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

// Note that the order of 1,100000 is not what we expect
const array1 = [1.30.4.21.100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]
Copy the code

grammar

arr.sort([compareFunction])

parameter

  • CompareFunction optional
    • Used to specify ordering in a certain orderfunction.
    • If omitted, the element is sorted by the Unicode loci of each character in the converted string.

The return value

Sorted array. Note that the array is sorted in place and is not copied.

Pay attention to

  • If compareFunction is not specified, the element is sorted by the Unicode loci of the characters in the converted string.

    • For example, “Banana” will be placed before “cherry”.
    • When numbers are sorted from smallest to largest, 9 appears before 80, but because (no compareFunction is specified) the comparison number is converted to a string first, “80” precedes “9” in Unicode order.

  • If compareFunction is specified, the array is sorted by the value returned from calling the function. That is, a and B are the two elements to be compared:

    • If compareFunction(a, b) is less than 0, then A is placed before B;
    • If compareFunction(a, b) is equal to 0, the relative positions of a and B remain the same. Note: The ECMAScript standard does not guarantee this behavior, and not all browsers comply (Mozilla prior to 2003, for example);
    • If compareFunction(a, b) is greater than 0, b will be placed before A.
    • CompareFunction (a, b) must always return the same comparison result on the same input, otherwise the sorting result will be indeterminate.

Therefore, the format of the comparison function is as follows:

function compare(a, b) {
  if (a < b ) {           // By some sort of comparison, a is less than B
    return -1;
  }
  if (a > b ) {
    return 1;
  }
  // a must be equal to b
  return 0;
}
Copy the code

To compare numbers instead of strings, the comparison function can simply be a minus b, and the following function will sort the array in ascending order

function compareNumbers(a, b) {
  return a - b;
}
Copy the code

The sort method can be conveniently written using function expressions:

var numbers = [4.2.5.1.3];
numbers.sort(function(a, b) {
  return a - b;
});
console.log(numbers); It can also be written as:var numbers = [4.2.5.1.3];
numbers.sort((a, b) = > a - b);
console.log(numbers);

// [1, 2, 3, 4, 5]
Copy the code

Objects can be sorted by an attribute:

var items = [
  { name: 'Edward'.value: 21 },
  { name: 'Sharpe'.value: 37 },
  { name: 'And'.value: 45 },
  { name: 'The'.value: -12 },
  { name: 'Magnetic' },
  { name: 'Zeros'.value: 37}];// sort by value
items.sort(function (a, b) {
  return (a.value - b.value)
});

// sort by name
items.sort(function(a, b) {
  var nameA = a.name.toUpperCase(); // ignore upper and lowercase
  var nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});
Copy the code

So we can use sort in all sorts of combinations.

The basic idea

  1. Rewrite array nums1, equivalent to merge
  2. And then sort it

Writing implement

// Note that it modifies nums1 in place
var merge = function(nums1, m, nums2, n) { nums1.splice(m, nums1.length - m, ... nums2); nums1.sort((a, b) = > a - b);
};
Copy the code

Of course, we can also use double Pointers, but we don’t waste time with this simple question, too!

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference

  • Developer.mozilla.org/zh-CN/docs/…
  • Developer.mozilla.org/zh-CN/docs/…