Summary of algorithm problems
1 Invert the word III in the string
Given a string, you need to reverse the character order of each word in the string, while still preserving the Spaces and the original order of the words.
Example:
Enter: “Let’s take LeetCode contest” Output: “s ‘tel ekat edoCteeL tsetnoc”
Tip:
In a string, each word is separated by a single space, and there are no extra Spaces in the string.
Export default (STR) => {return str.split(' ').map(item => {return item.split('').reverse().join('')}).join(' '). } // For the second solution, Export default (STR) => {return str.split(/\s/g).map(item => {return Item. The split ('). The reverse () join (' ')}). Join (' ')} / export/the third method default (STR) = > {return STR. The match (/ [\ w '] + / g). The map (the item => { return item.split('').reverse().join('') }).join(' ') }Copy the code2 counts binary substring
Given a string s, count the number of non-empty (continuous) substrings with the same number of zeros and ones, and all zeros and all ones in those substrings are continuous.
Repeated substrings count the number of times they occur.
Example 1:
Input: “00110011” Output: 6 Description: There are six substrings with the same number of consecutive 1s and 0s: “0011 “, “01”, “1100”, “10”, “0011 “and” 01 “.
Note that some repeated substrings count their occurrences.
Also, “00110011” is not a valid substring because all zeros (and ones) are not combined. Example 2:
Input: “10101” Output: 4 Explanation: There are four substrings: “10 “, “01”, “10”, “01”, which have the same number of consecutive ones and zeros.
Tip:
S. length is between 1 and 50,000. The s contains only 0 or 1 characters.
var countBinarySubstrings = function (s) { let all = 0; / / string match, took out a continuous field of 0 s and 1 s, returned array let m = s.m atch (/ ([1] +) | (0) + / g); If (m.length > 1) {// for (let I = 0; i < m.length - 1; i++) { all += Math.min(m[i].length, m[i+1].length); } } return all; };Copy the code3 Letter combination of the phone number
Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.
The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.
Example 1:
Input: who = “23” output: [” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”] example 2:
Output: [] Example 3:
[“a”,”b”,”c”]
Tip:
Length <= 4 digits[I] is a number in the range [‘2’, ‘9’].
Export default (STR) = > {/ / phone number keyboard mapping let map = [' ' ' ', 'ABC' and 'def', 'ghi', 'JKL', 'mno', 'PQRS', 'tuv', 'wxyz]; 234 => [2, 3, 4] let num = str.split(''); // Save the keyboard mapped letter contents, such as 23 => [' ABC ', 'def'] let code = []; num.forEach(item => { if (map[item]) { code.push(map[item]); }}); Let comb = (arr) => {// a temporary variable to hold the results of the first two combinations let TMP = []; For (let I = 0, il = arr[0]. Length; let I = 0, il = arr[0]. i < il; i++) { for (let j = 0, jl = arr[1].length; j < jl; j++) { tmp.push(`${arr[0][i]}${arr[1][j]}`); }} // replace arr.splice(0, 2, TMP) with the first two arr variables after the loop. If (arr.length > 1) {// Recursively comb(arr); }else { return arr[0]; If (arr. Length > 1) {//// recursively //comb(arr); //}else { //return tmp; //} //return arr[0]; } return comb(code); }Copy the codeThe solution is as follows:
4 Grouping cards
Given a deck of cards, each card has an integer written on it.
At this point, you need to select a number X, so that we can divide the whole deck into 1 or more groups according to the following rules:
Each group has X cards. All the cards in the group have the same integer written on them. Return true only if your optional X >= 2.
Example 1:
,2,3,4,4,3,2,1 input: [1] output: true explanation: feasible grouping is [1, 1], [2], [3], [4] example 2:
Input: [1,1,1,2,2,2,3,3] output: false description: no required grouping is available. Example 3:
Input: [1] Output: false Description: No required grouping is available. Example 4:
Input: [1,1] output: true explanation: the feasible grouping is [1,1] example 5:
,1,2,2,2,2 input: [1] output: true explanation: feasible grouping is [1, 1], [2], [2]
Tip:
1 <= deck.length <= 10000 0 <= deck[i] < 10000
Export default (arr) => {arr.sort((a, b) => a-b); Let min = number. MAX_SAFE_INTEGER; let dst = []; let result = true; for (let i = 0, len = arr.length, tmp = []; i < len; i++) { tmp.push(arr[i]); for (let j = i + 1; j < len - 1; j++) { if (arr[i] === arr[j]) { tmp.push(arr[j]); }else { if (min > tmp.length) { min = tmp.length; Dst.push ([].concat(TMP)); dst.push([].concat(TMP)); [] tmp.length = 0; [] tmp.length = 0; // I = j; break; DST. Every (item => {if (item.length % min!) {if (item.length % min! = 0) { result = false; return false; } }) return result; } export default (arr) => {arr.sort((a, b) => a-b); Let min = number. MAX_SAFE_INTEGER; let result = true; / / array is converted to a string first, and then match the string, and pulled out a continuous field, the returned array let DST = arr. Join ("). The match (/ ([0] +) | | (1) + (2) + | | (3) + (4) + | | (5) + (6) + | | (7) + + | (8) (9) + / g); For (I = 0, len = dst.length; i < len; i++) { if (dst[i].length < min) { min = dst.length; } dst.every(item => { if (item.length % min ! = 0) { result = false; return false; } }) return result; }Copy the codeFive flower problems
Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die.
Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.
Example 1:
Input: flowerBed = [1,0,0,0,1], n = 1
Input: flowerbed = [1,0,0,0,1], n = 2 output: false
Tip:
1 <= flowerbed. Length <= 2 * 104 FlowerBed [I] is 0 or 1. There are no two adjacent flowerbed
Export default (arr, n) => {// count let Max = 0; for (let i = 0, len = arr.length - 1; i < len; i++) { if (arr[i] ===0) { if (i === 0 && arr[1] ===0) { max++; i++; }else if (arr[i - 1] === 0 && arr[i + 1] === 0) { max++; i++; } } } return max >= n; }Copy the code6 Gray coding
Gray code is a binary number system in which two consecutive values differ by only one digit.
Given a non-negative integer n representing the total number of encoded digits, print its Gray encoding sequence. Even if there are multiple different answers, you only need to return one of them.
Gray coded sequences must begin with 0.
Example 1:
Input: 2
Output:,1,3,2 [0]
Explanation:
00-0
01-1
11-3
10-2
For a given n, its Gray code sequence is not unique. For example, [0,2,3,1] is also a valid gray encoding sequence.
00-0
10-2
11-3
01-1
Example 2:
Input: 0
Output: [0]
Explanation: We define that gray coded sequences must begin with 0. Given a Gray coding sequence with total number of bits n, its length is 2N. When n is equal to 0, length 2 to the 0 is equal to 1. Therefore, when n = 0, its Gray coding sequence is [0].
Export default (n) => {let make = (n) => {if (n == 1) {return ['0', '1']; }else { let prev = make(n - 1); let result = []; let max = Max.pow(2, n) -1; for (let i = 0, len = pre.length; i < len; i++) { result[i] = `0${pre[i]}`; result[max - i] = `1${pre[i]}`; } return result; } } return make(n); }Copy the codeParsing the legend
The first line is 0 and 1 and separated in the middle, and the next line is symmetrical in the middle, recursively
7 Repeated substrings
Given a non-empty string, determine whether it can be composed of one of its substrings repeated more than once. The given string contains only lowercase letters and is no longer than 10000 characters.
Example 1:
Input: “abab”
Output: True,
Explanation: can be formed by repeating the substring “ab” twice.
Example 2:
Input: “aba”
Output: False
Example 3:
Input: “abcabcabc”
Output: True,
export default (str) => {
var reg = /^(\w+)\1+$/;
return reg.test(str);
}
Copy the code8 Match the regular expression
Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ‘*’.
‘.’ matches any single character
The ‘*’ matches zero or more of the preceding elements
By matching, you want to cover the entire string S, not parts of the string.
Example 1:
Input: s = “aa” p = “a” Output: false Description: “A” cannot match the entire string “aa”.
Example 2:
Input: s = “aa” p = “a*” Output: true Thus, the string “aa” can be treated as ‘a’ repeated once.
Example 3:
Input: s = “ab” p = “.” Output: true Description: “.” Can match zero or more (‘*’) characters (‘.’).
Example 4:
Input: s = “aab” p = “CAB” Output: true Explanation: Since ‘*’ means zero or more, where ‘c’ is zero, ‘a’ is repeated once. So it matches the string “aab”.
Example 5:
Input: s = “Mississippi” p = “misisp*.” output: false
Tip:
0 <= s.length <= 20
0 <= p.length <= 30
S may be empty and contain only lowercase letters from A to Z.
P may be empty and contains only lowercase letters from A to Z, as well as the characters. And *.
Ensure that each occurrence of the character * is preceded by a valid character
Export the default (STR, mode) = > {/ / to regular screening / / screening mode variable is an array of the let modeArr = mode. The match (/ ([a-z.] \ *) | ([a-z] + (? =(a-z.)\*|$))/g); let cur = 0; let strLen = str.length; for (let i = 0, len = modeArr.length; i < len; I++) {/ / for the model is divided into three categories. * * | | a cdef m = modeArr [I] the split (' '); if (m[1] === '*') { if (m[0] === '.') { cur = strlen; break; }else { while (str[cur] === m[0]) { cur++; } } }else { for (let j = 0, jl = m.length; j < jl; j++) { if (m[j] ! == str[cur]) { return false; }else { cur++; } } } } return cur === strlen; }Copy the code
Bubble sort
Time complexity: number of runs;
Space complexity: occupied memory
Export default (arr) => {// Bubble sort // loop count for (let I = arr. Length -1; i > 0; I++) {// for (let j = 0; j < i; j++) { tmp = arr[j]; if (tmp > arr[j + 1]) { arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr; }Copy the code10 Selection Sort
Function selectionSort (arr) {var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }Copy the code[Top 10 Classic sorting algorithms (GIF demo) – one pixel – Blogblogs.com]
10 complement – Quicksort
Select an element from the array as a reference point; Sorted array, all elements smaller than the base value are placed on the left and those larger than the base value are placed on the right. At the end of each partition the reference value is inserted in the middle; Finally, using recursion, the array on the left and the array on the right perform the above 1 and 2 operations.
var quickSort = function (arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(privotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < piovt) {
left.push(arr[i]);
}else {
right.push(arr[i]);
}
}
return quickSort(left).concat([privot], quickSort(right));
}
Copy the code11 Maximum Spacing
Given an unordered array, find the largest difference between adjacent elements of the array after sorting.
If the number of elements is less than 2, 0 is returned.
Example 1:
Input: [3,6,9,1] output: 3 explanation: the sorted array is [1,3,6,9], where there is a maximum difference of 3 between adjacent elements (3,6) and (6,9).
Example 2:
Input: [10] Output: 0 Explanation: The number of elements in the array is less than 2, so return 0.
Description:
You can assume that all elements in the array are non-negative integers and that the values are in the range of 32-bit signed integers.
Try to solve this problem with linear time and space complexity.
Export default (arr) => {if (arr. Length < 2) {return 0; } // sort arr.sort(); // let Max = 0; for (let i = 0, len = arr.length, tmp; i < len; i++) { tmp = arr[i + 1] - arr[i]; if (tmp < max) { max = tmp; } } return max; }// Export default (arr) => {if (arr. Length < 2) {return 0; } let max = 0; let len = arr.length - 1; let space; For (let I = len, TMP; i > 0; i--) { for (let j = 0; j < i; j) { tmp = arr[j]; if (tmp < arr[j + 1]) { arr[j] = arr[j + 1]; arr[j + 1] = tmp; Arr [2] -arr [1], arr[1] -arr [0] If (I < len) {space = arr[I + 1] -arr [I]; if (space = arr[I + 1] -arr [I]; if (space > max) { max = space; Return Math. Max (Max, arr[1] -arr [0]); }Copy the codeSort array II by parity
Given an array of non-negative integers A, half of the integers in A are odd and half are even.
Sort the array so that when A[I] is odd, I is also odd; When A[I] is even, I is even.
You can return any array that meets the above criteria as an answer.
Example:
,2,5,7 input: [4] output:,5,2,7 [4] :,7,2,5 [4],,5,4,7 [2], [2,7,4,5] will be accepted.
Tip:
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
Export default (arr) => {// If (a, b) => a - b, arr.sort((a, b) => a - b); // declare an empty array to store even and odd sorted arrays let r = []; // let odd = 1; let even = 0; Arr. ForEach (item => {if (item % 2 === 1) {r[odd] = item; odd += 2; }else { r[even] = item; even += 2; } }) return r; }Copy the codeThe KTH largest element in the array 13
Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2 output: 5 example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4
You can assume that k is always valid, and that 1 ≤ k ≤ the length of the array.
Export default (arr, k) => {return arr.sort((a, b) => b-a)[k-1]; }// Export default (arr, k) => {let len = arr.length - 1; for (let i = len, tmp; i > len - k; i--) { for (let j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr[len - (k - 1)]; }Copy the code14 missing the first positive number
Given an unsorted integer array nums, find the smallest positive integer that does not appear in it.
Advanced: Can you implement a solution with O(n) time complexity and use only constant level extra space?
Example 1:
Nums = [1,2,0] output: 3 example 2:
Nums = [3,4,-1,1] Output: 2 Example 3:
Input: nums = [7,8,9,11,12] output: 1
0 <= nums.length <= 300 -231 <= nums[i] <= 231 – 1
Export default (arr) => {arr = arr.filter(item => item > 0); Arr [0] arr. Sort ((a, b) => a-b); arr[0] arr. If (arr[0]! == 1) { return 1; }else {for (let I = 0, len = arr.length - 1; i < len; i++) { if (arr[i + 1] - arr[i] > 1) { return arr[i] + 1; Return arr.pop() +1; return arr.pop() +1; }}else {// If an array is empty, return 1; Export default (arr) => {arr = arr.filter(item => item > 0); For (let I = 0, len = arr. Length, min; let I = 0, len = arr. Length, min; i < len; i++) { min = arr[i]; for (let j = i + 1; j < len; j++) { if (arr[j] < min) { let c = min; min = arr[j]; arr[j] = c; } } arr[i] = min; If (I > 0) {if (arr[I] -arr [i-1] > 1) {return arr[i-1] + 1; }else { return arr.pop() + 1; } }else { if (min ! == 1) { return 1; } } } }else { return 1; }}Copy the code15 Restore the IP address
Given a numeric string representing an IP address, return all valid IP addresses that can be obtained from S. You can return the answers in any order.
A valid IP address consists of four integers (each integer is between 0 and 255, and cannot contain a leading 0), separated by a hyphen (.).
For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “[email protected]” are invalid IP addresses.
Example 1:
Input: s = “25525511135” Output: [“255.255.11.135″,”255.255.111.35”] Example 2:
Input: S = “0000” Output: [“0.0.0.0”] Example 3:
Input: s = “1111” Output: [“1.1.1.1”] Example 4:
Input: s = “010010” output: [” 0.10.0.10 “, “0.100.1.0”] example 5:
Input: s = “101023” output: [” 1.0.10.23 “, “1.0.102.3”, “10.1.0.23”, “10.10.2.3”, “101.0.2.3”]
Tip:
0 <= S. length <= 3000 s Consists of digits only
Export default (s) => {var ret = []; The special case / / / / s length less than 4 (4 * 1) or more than 12 (4 * 3), then directly returns an empty array if (s.l ength < 4 | | s.l ength > 12) {return ret. Var isValid = (s) => {// This function is used to determine whether a string is converted to a number according to IP (0, 255). If (s.length === 1) {return true; }else {//088 if (s[0] === '0') {return false; If (Number(s) <= 255) {return true; if (Number(s) <= 255); //s is the original string, P is the subscript pointer, STR is the formed string, Var def = (s, p, STR, CNT) => {if (CNT == 4&&p == s.length) {ret. Push (STR); return; } / / CNT = 4, but it didn't go to the end, p p to walk to the end but not up to 4 CNT, the two are not directly to abandon the if (CNT = = 4 | | p = = s.l ength) {return; } // I can take 1, 2, 3 for (let I = 1; i < 4; If (p + I > s.length) {if (p + I > s.length) {break; } let cutStr = s.slice(p, p + i); If (isValid(cutStr)) {// DFS (s, p + I, STR + (p + I == s.length? curStr : curStr + '.'), cnt + 1); }else { continue; } } } dfs(s, 0, '', 0); return ret; }Copy the code16 concatenates substrings of all words
Given a string s and some words of the same length. Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.
Note that the substring must match exactly the words in words, without any other characters in the middle, but you do not need to consider the sequence in which words are concatenated.
Example 1:
Input: s = “barfoothefoobarman”, words = [“foo”,”bar”] Output: [0,9] Explanation: Substrings starting from index 0 and 9 are “barfoo” and “foobar”, respectively. The order of the outputs is not important, [9,0] is also a valid answer. Example 2:
Input: s = “wordgoodGoodGoodBestWord “, words = [“word”,”good”,”best”,”word”] output: []
export default (s, words) { if (! words || ! words.length) return []; let wordLen = words[0].length; let allWordsLen = wordLen * words.length; let ans = [], wordMap = {}; For (let w of words) {wordMap[w]? wordMap[w]++ : wordMap[w] = 1; } for (let i = 0; i < s.length - allWordsLen + 1; I++) {let wn = object. assign({}, wordMap); // I + allWordsLen - wordLen +1 for (let j = I; j < i + allWordsLen - wordLen +1; j += wordLen) { let w = s.slice(j, j + wordLen); if (wm[w]) { wm[w]--; }else { break; } } if (Object.values(wm).every(n => n === 0)) ans.push(i); } return ans; }Copy the code