LiBK-铁甲依然在

插入排序

特点：

1. 所需时间受输入元素初始顺序的影响
2. 如果数据是局部有序的，那么用插入排序会很高效。
3. 也很适合小规模数组，在V8引擎里调用Array.prototype.sort()时，当数组长度大于10个的情况下，采用的是快速排序，而当长度小于等于10个时则切换为插入排序，以提高运算效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/*
 * @Description: insertSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function insertSort (arr) {
  if (arr === null || arr === undefined || arr.length < 2) {
    return
  }

  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
      }
    }
  }
}

基本规则

1. 异或操作满足交换律和结合律
2. 0^N = N
3. N^N = 0

用于交换两个数

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @Description: 使用异或操作实现交换，
 * 但是a和b不能相等，否则两者的数据都会被洗成0
 * @param {*} a
 * @param {*} b
 * @return {*}
 */
function swapByEor (a, b) {
  a = a ^ b
  b = a ^ b
  a = a ^ b
}

字符串逆序输出

1
2
3
4
5
6
7
8

/*
 * @Description: reverseString
 * @Author: libk
 * @Github: <https://github.com/libk>
 */
function reverseString (str) {
  return str.split('').reverse().join('')
}

问题描述

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

1
2
3

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

1
2
3

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

1
2
3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

问题描述

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

1
2
3

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

问题描述

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

1
2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

1
2

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

问题描述

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1
2

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

问题描述

Given an m x n matrix, return all elements of the matrix in spiral order.

Example :

1
2

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

问题描述

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

1
2
3
4
5

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

1
2

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

问题描述

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example :

1
2

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.