Introduction to the
All the topics in the article are carefully selected uHF topics, so you can keep them
Copyright notice: All titles are from LeetCode, not commercial!!
Applicable people
Basic knowledge of data structures (linked list, binary tree, binary heap, recursion), and a basic understanding of time and space complexity.
Eating guide
Write each question listed in the text by hand at least three times
Before the interview can be sorted out according to the topic of this article directly through
instructions
Article update frequency: the solution of a question will be updated under the topic every day except on rest days
LeetCode with the original title will be pasted with the original address, not in the article title description
Tc: Time complexity
Sc: Space complexity
Topic type
An array of article
1. TwoSum [request Tc: O(n) Sc:O(n)] (Bytedance)
LeetCode first
According to the question, the first thing that comes to our mind is the two-layer cyclic violence solution:
Time = O(n²), Space = O(1)
Iterating through each element nums[j] and finding if there is a target element equal to target-nums [j].
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return[i,j]; }}}return [];
}
Copy the codeTime = O(n), Space = O(n) :
We can change time by hashing the table space. At the same time as iterating and inserting the element into the table, we go back and check whether the target element of the current element already exists in the hash table. If so, we find the solution to the problem and return it (O(n) time complexity, O(n) space complexity).
✌ bingo
var twoSum = function(nums, target) {
let reduceHash = {};
for (let i = 0; i < nums.length; i++) {
let reduceResult = target - nums[i];
if(reduceHash[reduceResult] ! = =undefined) {
return[reduceHash[reduceResult], i]; } reduceHash[nums[i]] = i; }};Copy the code2. Missing digits [request Tc: O(n) Sc:O(n)] (Bytedance)
53
Solution:
We first hash all the entered numbers into the hash table. Since the array is ordered, we can iterate over the hash table again. If a number does not exist in the hash table, it is the missing number
var missingNumber = function(nums) {
const hash = {};
for (let i = 0; i < nums.length; i++) {
hash[nums[i]] = true;
}
let expectedNumCount = nums.length + 1;
for (let i = 0; i < expectedNumCount; i++) {
if(! hash[i]) {returni; }}return -1;
};
console.log(missingNumber([0.1.2.4]));/ / 3
Copy the code3. Move zero [Tc: O(n) Sc:O(1), cannot change the original relative position of other elements after moving] (second-line company)
LeetCode 283 questions
Solution:
If the fast pointer encounters a non-0, replace the characters in the position of the slow pointer. Until the fast pointer has traversed all the elements of the array. (typical two baffles, three zones idea), and replace all elements after the slow pointer with 0.
Homomorphic property:
Physical meaning of variable: any number on the left side of slow that does not contain slow is non-zero, and any number on the right side of slow that contains slow should be zero. According to this physical meaning, the requirements of in-situ algorithm can be met. Because the fast and slow Pointers run in the same direction, the algorithm is stable (it does not affect the relative positions of elements).
var moveZeroes = function(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if(nums[fast] ! = =0) { nums[slow++] = nums[fast]; }}while (slow < nums.length) {
nums[slow++] = 0; }};const input = [0.1.5.8.4.3.0.5.0];
moveZeroes(input);
console.log(input);
Copy the code4. Shuffle algorithm (random number group)[requires Tc: O(n) Sc:O(1), requires the same probability of each element disruption] (Fast hand)
LeetCode 384 questions
Solution:
The fisher-Yates shuffle algorithm is used to shuffle cards.
function shuffle(arr) {
let m = arr.length;
while (m) {
let random = (Math.random() * m--) | 0;
[arr[random],arr[m]] = [arr[m],arr[random]];
}
return arr;
}
console.log(shuffle([1.5.6.7.6]));
Copy the code5. Intersection of two arrays [require Tc: O(n) Sc:O(n)]
LeetCode 349 questions
Solution:
If nums1 contains a nums2 element, add it to the result and return it.
let res = [];
for (let i = 0; i < nums1.length; i++) {
const cur = nums1[i];
if(nums2.includes(cur)) { res.push(cur); }}return Array.from(new Set(res));
Copy the code6.RainbowSort [require Tc: O(n) Sc:O(1)]
Given a series of balls whose colors can only be red, yellow, or blue, sort the balls so that all red balls are grouped on the left, all yellow balls are grouped in the middle, and all blue balls are grouped on the right.
Ex. :
[red] is sorted as [red]
[yellow, red] is sorted as [red, yellow]
[Yellow, red, red, blue, yellow, red, blue] is sorted as [red, red, red, yellow, yellow, blue, blue]
Assumptions:
The input array is not null.
corner case:
What if the length of the input array is zero? In this case, we should just return the empty array.
Solution:
Three blocks and four areas are used to divide the array elements.
Physical meaning of the baffle: [0 and I) are all red, [I, j) is yellow, (k – > n – 1) for all blue, [j] – k to explore unknown areas
J is a fast pointer
const input = ['yellow'.'red'.'red'.'blue'.'yellow'.'red'.'blue']
function rainbowSort(rainbow) {
let i = 0, j = 0, k = rainbow.length - 1;
while (j <= k) {
if (rainbow[j] === 'red') {
swap(rainbow,i,j);
i++;
j++;
}
if (rainbow[j] === 'yellow') {
j++;
}
if (rainbow[j] === 'blue') {
swap(rainbow, j, k); J ++ is not written here because the element swapped from k is not guaranteed to be yellow. To be safe, the next loop checks the j position again.k--; }}}// Auxiliary exchange function
function swap(arr,i,j) {
[arr[i],arr[j]] = [arr[j],arr[i]]
}
rainbowSort(input);
console.log(input);
Copy the code7. Remove element [Tc: O(n) Sc:O(1)]
LeetCode question 27
Solution:
When a fast pointer encounters a character other than val, the slow pointer replaces the character at the position of the slow pointer. The slow pointer advances until all elements of the array are iterated. (Typical two baffle, three zone idea)
Physical meaning of variables: any element to the left of slow that does not contain slow is non-Val, and any element to the right of slow that contains slow should be an element that does not contain Val. According to this physical meaning, the requirements of the in-situ algorithm can be met. Because the fast and slow Pointers run in the same direction, the algorithm is stable (it does not affect the relative positions of elements).
Baffle properties:
Go in the same direction: The left of the slow pointer is the processed element and the right of the fast pointer is the unknown exploration area. The middle of the two baffles is not concerned (the final result will not change the relative position of the element).
var removeElement = function(nums, val) {
let slow = 0;
for(let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== val) {
nums[slow++] = nums[fast];
}
}
return slow; // To retrieve the removed array: nums.slice(0,slow);
};
Copy the code8. Sort array by odd and even (Tc: O(n) Sc:O(1))
LeetCode 905 questions
Solution:
[0-i] is an even number, and [J-N-1] is an unexplored area
Baffle properties:
Go in the same direction: The left of the slow pointer is the processed element and the right of the fast pointer is the unknown exploration area. The middle of the two baffles is not concerned (the final result will not change the relative position of the element).
Solution 1:(Do not change the relative positions of elements: go in the same direction)
var sortArrayByParity = function(A) {
for (let i = 0, j = 0; j < A.length; j++) {
if (A[j] % 2= = =0) swap(A, i++, j);
}
return A;
};
function swap(arr,l,r) {
[arr[l],arr[r]] = [arr[r],arr[l]];
}
console.log(sortArrayByParity([3.1.2.4]));
Copy the codeBaffle properties:
The left side of the pointer is the processed element, the right side of the pointer is the processed element, and the unprocessed area is between the two baffles (the final result may change the relative position of the elements).
Solution 2:(Change the relative position of the elements: walk in the opposite direction)
var sortArrayByParityII = function(A) {
let i = 0, j = A.length - 1;
while (i <= j) {
if (A[i] % 2= = =0) {
i++;
} else if (A[j] % 2! = =0) {
j--;
} else { //i % 2 ! == 0 && j % 2 === 0swap(A,i,j); i++; j--; }}return A;
};
function swap(arr, l, r) {
[arr[l], arr[r]] = [arr[r], arr[l]];
}
console.log(sortArrayByParityII([3.1.2.4]));
Copy the code9. The number that occurs more than half of the time in array [Tc: O(n) Sc:O(1)]
LeetCode 169 questions
In the end, more than half of the elements are left.
I keep the first element, and then I iterate, and if I see something that’s the same, I increase it, if I don’t, I decrease it, and if it’s zero, I switch to another element.
For example: A B C A
Keep A for the first time, fight with the rest with A, and reduce the number of A by 1 if you meet someone who is not A. If you meet A, increase the number until you meet different elements and cancel out the number of A. Then kick A off and reset the number to 1.
So eventually there’s going to be something extra that’s going to be the solution.
var majorityElement = function(array) {
let count = 1;
let num = array[0];
for (let i = 1; i < array.length; i++) {
if(num ! == array[i]) { count--;if (count === 0) {
num = array[i];
count = 1; }}else{ count++; }}return num;
};
let halfValue = majorityElement([1.1.2.3]);
console.log(halfValue); / / 1
Copy the code10. Merge two ordered arrays (Tc: O(m + n) Sc:O(n))
Ex. :
Input :nums1 = [1,3], nums2 = [4,5,7]
Output:,3,4,5,7 [1]
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] < right[j] ? left[i++] : right[j++]);
}
while (i < left.length) {
result.push(left[i++]);
}
while (j < right.length) {
result.push(right[j++]);
}
return result;
}
let merged = merge([1.3], [4.5.7]);
console.log(merged);
Copy the code11. The number of ordered arrays less than a certain number
Ex. :
Input :[1, 2, 3, 4]
Enter the target value :2
Output: 1.
2. Ordered arrays (logn) In fact, this problem is to write a binary search, think about it, you want to find the number of the index does not mean that there are several smaller numbers than him?
function binarySearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const mid = (low + (high - low) / 2) | 0;
const middleValue = array[mid];
if (middleValue > target) {
high = mid - 1;
} else if (middleValue < target) {
low = mid + 1;
} else {
returnmid; }}}const minCount = binarySearch([1.2.3.4].2);
console.log(minCount); / / 1
Copy the code12. Array deduplication [Tc: O(n) Sc:O(1)]
LeetCode 26 questions
This algorithm requires in situ algorithm, so continue to use the baffle idea (do not understand can go back to the above mentioned to continue to understand).
Since at least one element will not be repeated (at least one element will remain), it starts with the subscript 1.
Solution 1: Start at index 1 (processed elements do not contain slow positions)
var removeDuplicates = function(arr) {
let slow = 1;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] === arr[slow - 1]) {
continue;
}
arr[slow++] = arr[fast];
}
return slow; Arr. Slice (0, slow);
};
Copy the codeSolution 2: Start at index 0 (processed elements include slow positions)
var removeDuplicates = function(arr) {
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] === arr[slow]) {
continue;
}
arr[++slow] = arr[fast];
}
return slow + 1; Arr. Slice (0, slow + 1);
};
Copy the code13. Remove consecutive A’s and C’s and keep all B’s (Tc: O(n) Sc:O(1) elements unchanged relative position)
Train of thought: still use fast and slow pointer, same direction but line
function removeAC(arr) {
let slow = 0,fast = 0;
while (fast < arr.length) {
if (arr[fast] === 'b') {
arr[slow++] = arr[fast++];
} else {
let begin = fast;
while (fast < arr.length && arr[fast + 1] === arr[begin]) {
fast++;
}
if (fast - begin === 0) {
arr[slow++] = arr[fast++];
} else{ fast++; }}}return arr.slice(0,slow).join(' ');
}
const result = j1(['a'.'a'.'b'.'c'.'b'.'c'.'c']);
console.log(result);//bcb
Copy the code14. Longest Public Prefix (Spell Duo Duo)
Example: [‘ aaAFSD ‘, ‘aawwewer’, ‘aaddfff’] => ‘aa’
LeetCode question 14
function LCP(arr) {
if(! arr.length) {return ' ';
}
let ans = arr[0];
for (let i = 1; i < arr.length; i++) {
let j = 0;
for(; j < ans.length && j < arr[i].length; j++) {if(ans[j] ! == arr[i][j]) {break;
}
}
ans = ans.substr(0,j);
if (ans === "") {
returnans; }}return ans;
}
let result = LCP(['aaafsd'.'aawwewer'.'aaddfff']);
console.log(result);
Copy the code15. Given an array of integers A, 1 ≤ a[I] ≤ n (n is the length of the array), where some elements occur twice and others occur once, find all elements that occur twice.
Example: input: [4,3,2,7,8,2,3,1] output: [2,3]
Solution: No idea at present
16. What is the maximum number of elements in an array?
Example: [50, 2, 5, 9] => 95502
If we order the largest number in descending order, it must be the largest number.
var largestNumber = function(nums) {
nums = nums.sort((a, b) = > {
let S1 = `${a}${b}`;
let S2 = `${b}${a}`;
return S2 - S1;
});
return nums[0]? nums.join(' ') : '0';
};
Copy the codeLeetCode 179 questions
String article
1. Palindrome [asked Tc: O (log10n) Sc: O (1) or Tc: O (n) Sc: O (1)] (tencent)
LeetCode 9 questions
Use a double pointer, one in front, one in back, before and after comparison. Return false if two Pointers are different.
function palindrome(x) {
let i = 0, j = x.length - 1;
while (i <= j) {
if(x[i] ! == x[j]) {return false;
} else{ i++; j--; }}return true;
}
let result = palindrome('lol');
console.log(result);
Copy the code2. Reverse string [Tc: O(n) Sc:O(1)]
LeetCode 344 questions
Use a double pointer, one in front, one in back, and swap each time
var reverseString = function(s) {
let slow = 0;
for (let fast = s.length - 1, slow = 0; fast >= slow; fast--) { swap(s, slow++, fast); }};function swap(arr, l, r){
let temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
Copy the code3. Flip word order [request Tc: O(n) Sc:O(n)] (Bytedance)
58
Split the string by space, then swap the word order as above.
var reverseWords = function(s) {
let strArr = s.split(' ').filter(Boolean);
let reversed = strArr;
reverse(reversed, 0, reversed.length - 1);
return reversed.join(' ');
};
function reverse(input, left, right) {
if (left >= right) {
return;
}
swap(input, left, right);
reverse(input, left + 1, right -1);
}
function swap(arr, l, r) {
[arr[l],arr[r]] = [arr[r],arr[l]];
}
Copy the code4. Effective Anagram [Tc: O(n) Sc:O(n)]
LeetCode 242 questions
We can use a hash to store the number of occurrences of each word, then iterate over another string to subtract, returning false whenever the number of occurrences is not equal to zero
var isAnagram = function(s, t) {
if(s.length ! == t.length)return false;
let map = new Map(a);for (let item of s) {
if (map.get(item)) {
map.set(item, map.get(item) + 1);
} else {
map.set(item, 1); }}for (let item of t) {
if (map.get(item)) {
map.set(item, map.get(item) - 1);
} else {
return false; }}return true;
};
Copy the codeTc: O(n) Sc:O(n)
Example 1: Enter ‘abccdTC’
Output: ‘c’
Example 2: Enter ‘abbbbCCdTC’
Output: ‘b’
function maxCount(str) {
let hash = {};
let maxCount = 0;
let maxElement = ' ';
for (let i = 0; i < str.length; i++) {
let cur = str[i];
if (hash[cur]) {
hash[cur]++;
} else {
hash[cur] = 1;
}
if(maxCount < hash[cur]) { maxElement = cur; maxCount = hash[cur]; }}return maxElement;
}
let letter = maxCount('abccdtc');
console.log(letter);
Copy the code6. Replace Spaces [requires Tc: O(n) Sc:O(1) not to allow regular expressions]
5
The fast pointer is responsible for judging whether it is a space, and the left side of the slow pointer are all processed elements.
var replaceSpace = function(s) {
s = s.split(' ');
for (let fast = 0; fast < s.length; fast++) {
if (s[fast] === ' ') {
s[fast] = '% 20'; }}return s.join(' ');
};
Copy the codeOther solutions (not recommended in an interview):
var replaceSpace = function(s) {
s = s.split(' ').join('% 20');
return s;
};
var replaceSpace = function(s) {
s = s.replace(/\s+/g.'% 20');
return s;
};
Copy the code7. The first character that occurs only once [requires Tc: O(n) Sc:O(n)]
50
If the current value appears for the first time, set it to false. If the current value is false, return it directly.
var firstUniqChar = function(s) {
let hash = {};
let firstAppearLetter = ' ';
if (s === ' ') {
return ' ';
} else {
for (let i = 0; i < s.length; i++) {
if (hash[s[i]] === undefined) {
hash[s[i]] = false;
} else {
hash[s[i]] = true; }}}for (let [key, value] of Object.entries(hash)) {
if(! value) {returnkey; }}return ' '
};
Copy the code8. Left-rotate string [Tc: O(n) Sc:O(n)]
58
var reverseLeftWords = function(s, n) {
let frontStr = s.slice(0, n);
let backStr = s.slice(n);
return backStr + frontStr;
};
Copy the codeTc: O(n!) Sc:O(n²)
38
var permutation = function(s) {
let solution = [];
if (s.length === 0) {
return solution;
}
permutationHelper(s, solution);
return solution;
};
function permutationHelper(s, solution, used = [], path = []) {
if (path.length === s.length) {
solution.push(path.slice(0).join(' '));
return;
}
let levelSet = new Set(a);for (let i = 0; i < s.length; i++) {
if(! levelSet.has(s[i])) {if(! used[i]) { used[i] =true;
levelSet.add(s[i]);
path.push(s[i]);
permutationHelper(s, solution, used, path);
used[i] = false; / / back
path.pop();// When you go right back to the parent node, you should delete the added node to prevent unexpected results from remaining}}}}Copy the code10. Merge consecutive numbers [require Tc: O(n) Sc:O(1)] (Toutiao)
Title description:
Input :[0, 2, 3, 5, 6, 7, 8, 9, 11, 13, 56, 57]
Output result:
0, 2, 3, 5-9,11,13,56-57
The pointer to the left of slow is the processed element. The F pointer moves forward quickly. The begin pointer records the beginning of the interval, and the prev pointer records the end of the interval.
function combine(arr) {
let f = 1, slow = 0;
let prev = -1;
while (f < arr.length) {
let begin = f - 1;
prev = arr[begin];
while (f < arr.length && arr[f] - prev === 1) {
prev = arr[f];
f++;
}
if (f - begin === 1) {
if (arr[f + 1] - arr[f] ! = =1) {
!begin ? arr[slow++] = arr[begin] : arr[slow++] = arr[f];
} else {
if(! begin) arr[slow++] = arr[begin]; } f++; }else {
arr[slow++] = arr[begin] + ` - `+ prev; }}return arr.slice(0, slow).join(', ');
}
let res = combine([0.2.3.5.6.7.8.9.11.13.56.57]);
console.log(res);
Copy the code11. String Addition (Tencent)
LeetCode 415 questions
var addStrings = function(num1, num2) {
let res = [];
let i = num1.length - 1, j = num2.length - 1, carry = 0;
while (i >= 0 || j >= 0) {
let n1 = i >= 0 ? num1.charAt(i) - 0: 0;
let n2 = j >= 0 ? num2.charAt(j) - 0: 0;
let tmp = n1 + n2 + carry;
carry = parseInt(tmp / 10);// Calculate the ten digits
res.push(tmp % 10);// Calculate the units digit
i--; j--;
}
if(carry == 1) res.push('1');
return res.reverse().join(' ')};Copy the codeStack/queue chapter
1. Implementation of a stack, push, pop, return min complexity of 0(1) (didi)
LeetCode 115 questions
If a new element in stack1 is larger than the top element in Stack2, the element at the top of Stack2 will become the smallest element in stack2.
var MinStack = function() {
this.stack1 = [];
this.stack2 = [];
};
/ * * *@param {number} x
* @return {void}* /
MinStack.prototype.push = function(x) { // Sync plus sync minus Push pop
this.stack1.push(x);
if (this.stack2.length === 0) {
this.stack2.push(x);
} else {
let temp = this.stack2[this.stack2.length - 1];
if (x < temp) {
this.stack2.push(x)
} else {
this.stack2.push(temp); }}};/ * * *@return {void}* /
MinStack.prototype.pop = function() {
if (this.stack1.length) {
this.stack1.pop();
this.stack2.pop(); }};/ * * *@return {number}* /
MinStack.prototype.top = function() {
return this.stack1[this.stack1.length - 1];
};
/ * * *@return {number}* /
MinStack.prototype.getMin = function() {
return this.stack2[this.stack2.length - 1];
};
Copy the code2. Use two stacks to implement a queue (didi)
9
Stack1 is the primary stack, stack2 is the secondary stack, and stack2 is the secondary stack.
var CQueue = function() {
this.stack1 = [];1 / / 2
this.stack2 = [];
this.count = 0;
};
/ * * *@param {number} value
* @return {void}* /
CQueue.prototype.appendTail = function(value) {
while (this.stack1.length) { // If there are elements in stack1, put all elements in stack2
this.stack2.push(this.stack1.pop());
}
this.stack1.push(value);// Add new values to stack1
while (this.stack2.length) {
this.stack1.push(this.stack2.pop()); // Then put stack2 elements into Stack1
}
// This step means that Stack1 has the nature of a queue (first in, first out) because Stack2 represents the previous data in Stack1, which is then pushed on top of the new data
this.count++;
};
/ * * *@return {number}* /
CQueue.prototype.deleteHead = function() {
if (this.count == 0) {
return -1;
}
this.count--;
return this.stack1.pop();// Use the pop stack method, because we use the auxiliary stack inverted so the direct pop result is according to the nature of the queue output advanced values
};
Copy the code3. Valid parentheses [require Tc: O(n) Sc:O(n)]
Questions LeetCode 20
If the match fails, return false. If the match fails, return false. Finally, check whether the stack is empty or not (whether all parentheses are cancelled out).
var isValid = function(str) {
let map = {
'{': '} '.'(': ') '.'[': '] '
}
let stack = []
for (let i = 0; i < str.length; i++) {
if (map[str[i]]) {
stack.push(str[i]);
} else if(str[i] ! == map[stack.pop()]) {return false; }}return stack.length === 0
};
Copy the codeList article
1. Print single linked list from end to end [Tc: O(n) Sc:O(n)]
6
The result can be obtained by going through the list from beginning to end, and then popping up the list in the order of stack.
var reversePrint = function(head) {
let stack = [];
let cur = head;
while(cur ! = =null) {
stack.push(cur.val);
cur = cur.next;
}
let print = [];
while (stack.length) {
print.push(stack.pop())
}
return print;
};
Copy the codeTc: O(L) Sc:O(1) Tc: O(L) Sc:O(1)
LeetCode question 19
var removeNthFromEnd = function(head, n) {
let dummyNode = new ListNode(0);
dummyNode.next = head;
let fast = dummyNode, slow = dummyNode;
// Quick n+1 step first
while(n--) {
fast = fast.next
}
// Go fast and slow together
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return dummyNode.next
};
Copy the codeTc: O(n) Sc:O(1) Tc: O(n) Sc:O(1)
LeetCode 141 questions
var hasCycle = function(head) {
if (head === null) {
return false;
}
let slow = fast = head;
while(fast.next ! = =null&& fast.next.next ! = =null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true; }}return false;
};
Copy the code4. Reverse single linked list [Tc: O(n) Sc:O(1)] (Linked list class UHF)
24
Reverse the process:
Original list: head -> 2 -> 3 -> 4 -> NULL
<- 2 3 -> 4 -> null
pre(null) cur next
null <- 2 <- 3 4 -> null
pre cur next
null <- 2 <- 3 <- 4 null
cur next
pre
null <- 2 <- 3 <- 4 null
pre cur next
<--------------------pre is the newHead to be returned
Copy the codeIterative solution (reverse left to right):
var reverseList = function(head) {
if (head === null || head.next === null) {
return head;
}
let pre = null, cur = head;
while(cur ! = =null) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};
Copy the codeRecursive solution :(inverts from right to left)
var reverseList = function(head) {
if(head === null || head.next === null) {
return head;
}
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Copy the codeOriginal linked list: 2 -> 3 -> NULL
The first call to reverseList:
2 -> 3 -> null
head newHead
Copy the codeHead. Next. Next = head does: (2 next is 3, 3 next points to 2) : 2 <-> 3Copy the codeHead. Next = null null < -2 < -3 headCopy the codeReturn newHead: null < -2 < -3 newHeadCopy the codeThe second call to reverseList:
2 -> 3 -> null
head
base case: return newHead = 3
Copy the codeC :O(m+n) Sc:O(n) c:O(n)
LeetCode 160 questions
headA:a+c+b
headB:b+c+a
Because a+ C +b === B + C +a so at some point they can intersect
var getIntersectionNode = function(headA, headB) {
if (headA === null || headB === null) {
return null;
}
let nodeA = headA;
let nodeB = headB;
while(nodeA ! == nodeB) { nodeA = nodeA ? nodeA.next : headB; nodeB = nodeB ? nodeB.next : headA; }return nodeA;
};
Copy the codeTc: O(n) Sc:O(1) Tc: O(n) Sc:O(1)
LeetCode 876 questions
var middleNode = function(head) {
let slow = head;
let fast = head;
while(fast ! = =null&& fast.next ! = =null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
Copy the codeTc: O(m+n) Sc:O(1)
25
var mergeTwoLists = function(l1, l2) {
let dummyHead = new ListNode(0);
let cur1 = l1;
let cur2 = l2;
let tail = dummyHead;
while(cur1 ! = =null&& cur2 ! = =null) {
if (cur1.val < cur2.val) {
tail.next = cur1;
cur1 = cur1.next;
} else {
tail.next = cur2;
cur2 = cur2.next;
}
tail = tail.next;
}
if(cur1 ! = =null) {
tail.next = cur1;
}
if(cur2 ! = =null) {
tail.next = cur2;
}
return dummyHead.next;
};
Copy the codeTc: O(n) Sc:O(1) Tc: O(n) Sc:O(1)
22
var getKthFromEnd = function(head, k) {
let fast = head, slow = head;
for (let i = 0; i < k; i++) {
fast = fast.next;
}
while(fast ! =null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
Copy the codeBinary tree
1. Binary tree deletion implementation [Tc: O(H) Sc:O(H)] (Bytedance)
LeetCode 450 questions
var deleteNode = function(root, key) {
this.root = recursionDelete(root, key);
return this.root;
};
function recursionDelete(root, key) {
if (root === null) {
return null;
}
if (root.val > key) {
root.left = recursionDelete(root.left, key);
return root;
} else if (root.val < key) {
root.right = recursionDelete(root.right, key);
return root;
} else { / / 3
if (root.left === null && root.right === null) { / / 1
root === null;
return root;
}
if (root.left === null) { / / 2
root = root.right;
return root;
} else if (root.right === null) { / / 2
root = root.left;
return root;
}
let aux = null; / / 3
let current = root.right;
while(current ! =null&& current.left ! =null) {
current = current.left;
}
aux = current;
root.val = aux.val;
root.right = recursionDelete(root.right,aux.val);
returnroot; }}Copy the code2. Determine whether a tree is a balanced tree (Tc: O(n) Sc:O(n))
LeetCode 110 questions
var isBalanced = function(root) {
if (root === null) {
return true;
}
const lh = maxDepth(root.left);
const rh = maxDepth(root.right);
if (Math.abs(lh - rh) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
};
function maxDepth(root) {
if (root === null) {
return 0;
}
const left = maxDepth(root.left);
const right = maxDepth(root.right);
return Math.max(left, right) + 1;
};
Copy the code3. Maximum depth of binary tree [Tc: O(n) Sc:O(n)]
55
function maxDepth(root) {
if (root === null) {
return 0;
}
const left = maxDepth(root.left);
const right = maxDepth(root.right);
return Math.max(left, right) + 1;
};
Copy the code5. Binary tree neutral path of a certain value [Tc: O(n) Sc:O(n)] (bytedance)
34
34.
var pathSum = function(root, sum) {
if(! root)return [];
const solution = [];
let path = []
pathSumHelper(root,sum,solution,path);
return solution;
};
function pathSumHelper(root,sum,solution,path) {
path.push(root.val);
if(root.left == null && root.right == null && calcPath(path) == sum) {
solution.push([...path]);
}
if(root.left){
pathSumHelper(root.left,sum,solution,path);
}
if(root.right){
pathSumHelper(root.right,sum,solution,path);
}
path.pop();
}
function calcPath(path){
let total = 0;
for(let i = 0; i<path.length; i++){ total += path[i]; }return total;
}
Copy the code6.LCA[request Tc: O(n) Sc:O(n)]
LeetCode 236 questions
var lowestCommonAncestor = function(root, p, q) {
if(! root || root.val == p.val || root.val == q.val)return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
// Return right if left has no p or q. If left exists and right does not, the left result is returned. Return the root node if both left and right are present
if(left == null) return right;
else if(right == null) return left;
return root;
};
Copy the code7. Binary tree traversal [require Tc: O(n) Sc:O(n)]
LeetCode 102 questions
var levelOrder = function(root) {
if (root === null) {
return [];
}
const result = [];
let queue = [root];
while (queue.length) {
const level = [];
let size = queue.length;
for (let i = 0; i < size; i++) {
let cur = queue.shift();
if (cur.left) {
queue.push(cur.left);
}
if (cur.right) {
queue.push(cur.right);
}
level.push(cur.val);
}
result.push(level);
}
return result;
};
Copy the codeTc: O(n) Sc:O(n) Sc:O(n)
LeetCode 98 questions
var isValidBST = function(root) {
let min = -Infinity;
let max = Infinity;
return isValidBSTHelper(root, min, max);
};
function isValidBSTHelper(root, min, max) {
if (root === null) {
return true;
}
if(root.val <= min || root.val >= max) {
return false;
}
return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
}
Copy the codeTc: O(n) Sc:O(n)
LeetCode 958 questions
var isCompleteTree = function(root) {
if (root === null) {
return true;
}
let queue = [root];
let flag = false;
while (queue.length) {
let cur = queue.shift();
if (cur.left === null) {
flag = true;
} else if (flag) {
return false;
} else {
queue.push(cur.left);
}
if (cur.right === null) {
flag = true;
} else if (flag) {
return false;
} else{ queue.push(cur.right); }}return true;
};
Copy the code10. Flip binary tree [Tc: O(n) Sc:O(n)]
LeetCode 226 questions
var invertTree = function(root) {
if(root == null) {
return [];
}
invertTreeHelper(root);
return root;
};
function invertTreeHelper(root) {
if (root == null) {
return;
}
let tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
}
Copy the code11. Right view of binary tree [Tc: O(n) Sc:O(n)] (Bytedance)
LeetCode 199 questions
var rightSideView = function(root) {
const result = [];
if (root === null) {
return result;
}
let queue = [root];
while (queue.length) {
const level = [];
let size = queue.length;
for (let i = 0; i < size; i++) {
let cur = queue.shift();
if (i === size - 1) {
level.push(cur.val);
}
if (cur.left) {
queue.push(cur.left);
}
if (cur.right) {
queue.push(cur.right);
}
}
result.push(level);
}
return result;
};
Copy the code12. Judge the symmetric binary tree [Tc: O(n) Sc:O(n)]
LeetCode 101 questions
var isSymmetric = function(root) {
return isSymmetricHelper(root, root);
};
function isSymmetricHelper(one, two) {
if (one === null && two === null) {
return true;
} else if (one === null || two === null) {
return false;
} else if(one.val ! == two.val) {return false;
}
return isSymmetricHelper(one.left,two.right) && isSymmetricHelper(one.right,two.left);
}
Copy the code12. Binary tree zigzag traversal [Tc: O(n) Sc:O(n)] (Bytedance)
LeetCode 103 questions
var zigzagLevelOrder = function(root) {
const printArr = []
if(! root)return printArr
const list = []
list.push({ level: 0.node: root })
while(list.length > 0) {
const { level, node } = list.shift()
if(! printArr[level]) { printArr[level] = [] }if (level % 2= = =0) {
printArr[level].push(node.val)
} else {
printArr[level].unshift(node.val)
}
node.left && list.push({ level: level + 1.node: node.left })
node.right && list.push({ level: level + 1.node: node.right })
}
return printArr
};
Copy the codeConstruct a binary tree
LeetCode 106 questions
var buildTree = function(preorder, inorder) {
function help(inorder) {
if(! inorder|| ! inorder.length)return null;
let top = preorder.shift(), p = inorder.indexOf(top);
let root = new TreeNode(top);
root.left = help(inorder.slice(0, p));
root.right = help(inorder.slice(p+1));
return root;
}
return help(inorder);
};
Copy the codeLeetCode 105 questions
var buildTree = function(preorder, inorder) {
function help(inorder) {
if(! inorder|| ! inorder.length)return null;
let top = preorder.shift(), p = inorder.indexOf(top);
let root = new TreeNode(top);
root.left = help(inorder.slice(0, p));
root.right = help(inorder.slice(p + 1));
return root;
}
return help(inorder);
};
Copy the codeHeap/priority queue sections
1. Search for the KTH Big Element [ask Tc: O(nlogn) Sc:O(1)] (Tencent, Bytedance, Alibaba)
Common topic
Copy the codeBinary search
1. Search for the given value [Tc: O(logn) Sc:O(1)] (binary search high frequency)
LeetCode 704 questions
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const mid = (left + (right - left) / 2) | 0;
const middleValue = array[mid];
if (middleValue > target) {
right = mid - 1;
} else if (middleValue < target) {
left = mid + 1;
} else {
returnmid; }}}const index = binarySearch([1.2.3.4].2);
console.log(index); / / 1
Copy the codeTc: O(logn) Sc:O(1)
Given the target integer T and an array of integers A sorted in ascending order, find the index I in A so that A [I] is closest to T.
Assumptions:
Arrays can have duplicate elements, and we can return any index with the same value.
Ex. :
A = [1,2,3], T = 2, return 1
A =[1, 4, 6], T = 3, return 1
A = [1, 4, 6], T = 5, return 1 or 2
A = [1, 3, 3, 4], T = 2, return 0 or 1 or 2
corner case:
What if A is empty or A is zero? In this case, we should return -1.
function binarySearch(array, target) {
if (array.length === 0) {
return -1;
}
let left = 0;
let right = array.length - 1;
while (left < right - 1) {
const mid = (left + (right - left) / 2) | 0;
const middleValue = array[mid];
if (middleValue === target) {
return mid;
} else if (middleValue < target) {
left = mid;
} else{ right = mid; }}if (Math.abs(target - array[left]) >= Math.abs(target - array[right])) {
return right;
} else {
returnleft; }}const index = binarySearch([1.2.5.6].4);
console.log(index); / / 2
Copy the code3. The first occurrence of the target value [Tc: O(logn) Sc:O(1)]
Given the target integer T and an array of integers A sorted in ascending order, find the index in A where T first appears, or return -1 if there is no such index.
assumptions
Arrays can have duplicate elements.
Ex. :
A = [1,2,3], T = 2, return 1
A = [1,2,3], T = 4, return -1
A = [1,2,2,2,3], T = 2, return 1
corner case:
What if A is zero or A of length zero? In this case, we should return -1.
function binarySearch(array, target) {
if (array.length === 0) {
return -1;
}
let left = 0;
let right = array.length - 1;
while (left < right - 1) {
const mid = (left + (right - left) / 2) | 0;
const middleValue = array[mid];
if (middleValue === target) {
right = mid;
} else if (middleValue < target) {
left = mid + 1;
} else {
right = mid + 1; }}return array[right] === target ? right : array[left] === target ? left : -1;
}
console.log(binarySearch([1.2.2.2.3].2)); / / 1
Copy the codeTc: O(logn + k) Sc:O(1)
Given A target integer T, A non-negative integer K, and an array of integers A sorted in ascending order, find the K digits in A that are closest to T. If there is a tie, the smaller element is always preferred.
Assumptions:
A is not empty, K is guaranteed to be greater than or equal to 0, and K is guaranteed to be less than or equal to 0.
Ex. :
A = [1,2,3], T = 2, K = 3, return [2, 1, 3] or [2, 3, 1]
A = [1,4,6,8], T = 3, K = 3,
function binarySearch(array, target, k) {
if (array.length === 0) {
return -1;
}
let left = 0;
let right = array.length - 1;
while (left < right - 1) {
const mid = (left + (right - left) / 2) | 0;
const middleValue = array[mid];
if (middleValue === target) {
right = mid;
} else if (middleValue < target) {
left = mid;
} else{ right = mid; }}// post-processing find the closest number
let closeIdx = 0;
if (Math.abs(array[left] - target) <= Math.abs(array[right] - target)) {
closeIdx = left;
} else {
closeIdx = right;
}
// These two should be the closest to target
let result = new Array(k);
let l = closeIdx;
let r = closeIdx + 1;
// this is a typical merge operation
for (let i = 0; i < k; i++) {
// we can advance the left pointer when:
// 1. right pointer is already out of bound
// 2. right pointer is not out of bound, left pointer is not out of bound and array[left] is closer to target.
if (r >= array.length) {//can be merged two conditions
result[i] = array[l--];
} else if (l < 0) {
result[i] = array[r++];
} else if (Math.abs(array[l] - target) <= Math.abs(array[r] - target)) {
result[i] = array[l--];
} else{ result[i] = array[r++]; }}return result;
}
console.log(binarySearch([1.4.6.8].3.3)); // [4，1，6]
Copy the codeDynamic programming
1. Fibonacci sequence (Tc: O(n) Sc:O(n)/O(1)) (Dynamic programming class UHF)
LeetCode 704 questions
var fib = function(n) {
let a = 0, b = 1, sum;
for (let i = 0; i < n; i++) {
sum = a + b;
a = b;
b = sum;
}
return a;
};
Copy the code2. Stair climbing (Tc: O(N) Sc:O(n)/O(1)) (Dynamic programming UHF)
LeetCode 70 questions
var climbStairs = function(n) {
if (n === 1) {
return 1;
}
let dp = [];
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
Copy the codeRecursive article
1. Number of islands (Tc: O(MN) Sc:O(MN))
LeetCode 200 questions
let dfs = function (grid, i, j) {
// Change the current entry to 0 to prevent re-lookup
grid[i][j] = 0;
// Check the current item
if (grid[i - 1] && grid[i - 1][j] == 1) dfs(grid, i - 1, j); / /
if (grid[i + 1] && grid[i + 1][j] == 1) dfs(grid, i + 1, j); / /
if (grid[i][j - 1] && grid[i][j - 1] = =1) dfs(grid, i, j - 1); / / left
if (grid[i][j + 1] && grid[i][j + 1] = =1) dfs(grid, i, j + 1); / / right
}
var numIslands = function(grid) {
if (grid.length < 1) return 0;
let islands = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
islands++; // Islands add 1
dfs(grid, i, j); // Find the ones adjacent to the current item and make them 0}}}return islands;
};
Copy the code2. Find N numbers in an array that sum to all possibilities of M (cannot reuse already used elements)
1
2
Tc: O(N×2N) Sc:O(N×2N)
LeetCode 78 questions
var subsets = function(nums) {
if(! nums.length) {return [];
}
let solution = [];
let levelResult = [];
subsetsHelper(nums,0,levelResult,solution);
return solution;
};
function subsetsHelper(nums,level,lresult,solution) {
//base base
if (level === nums.length) {
solution.push([].concat(lresult));
return;
}
lresult.push(nums[level]);
subsetsHelper(nums, level + 1,lresult, solution);/ / back
lresult.pop();
subsetsHelper(nums, level + 1, lresult, solution);/ / back
}
Copy the code5. Flatten the object (shrimp skin)
Input:
{
"a": {
"b": {
"c": {
"d": 1
}
}
},
"aa": 2,
"c": [
1,
2
]
}
Copy the codeRequired output:
{ 'a.b.c.d': 1, aa: 2, 'c[0]': 1, 'c[1]': 2 }
Copy the codefunction convert(obj) {
let str = ' ', res = {};
const inner = (obj) = > {
const keys = Object.keys(obj);
keys.forEach((item) = > {
const type = Object.prototype.toString.call(obj[item]).slice(8, -1);
if (type === 'Object') {
str += item + '. ';
inner(obj[item], str, res);
} else if (type === 'Array') {
obj[item].forEach((items, index) = > {
const key = `${item}[${index}] `;
res[key] = items;
});
} else {
str += item;
res[str] = obj[item];
str = ' '; }});return res;
};
return inner(obj);
}
console.log(convert(obj));
Copy the code6. Categorize (Tmall)
Input:const industry_list = [
{
"parent_ind": "Women's"."name": "Dress"
},
{
"name": "Women's"
},
{
"parent_ind": "Women's"."name": "Skirt"
},
{
"parent_ind": "Women's"."name": "A word skirt"
},
{
"name": "Digital"
},
{
"parent_ind": "Digital"."name": "Computer Accessories"
},
{
"parent_ind": "Computer Accessories"."name": "Memory"},]; > output:/ * {" digital ": {" computer accessories" : {" memory ": {}}}," women's ": {" dress" : {}, "skirts" : {}, "A word skirt" : {}}} * /
function convert_format(data) {
const res = {};
const map = data.reduce((res, v) = > (res[v.name] = v, res), {});
console.log(map);
for (const item of data) {
if (!item.parent_ind) {
res[item.name] = {};
}
}
for (const item of data) {
if (item.parent_ind in map) {
if (map[item.parent_ind].parent_ind) {
const path = dfs(item.name);
let re = res[path[0]].for (let i = 1; i < path.length; i++) {
if (i === path.length - 1) {
re[path[i]] = {};
} else{ re = re[path[i]]; }}}else{ res[item.parent_ind][item.name] = {}; }}}return res;
function dfs(name) {
let path = [];
const inner = (name, path) = > {
path.unshift(name);
if(! map[name].parent_ind) {return;
}
inner(map[name].parent_ind, path);
};
inner(name, path);
returnpath; }}const result = convert_format(industry_list);
console.log(result);
Copy the codeSorting article
1. Quick sort (Tc: O(nlogn) Sc:O(nlogn))
function quickSort(array) {
if (array === null || array.length === 0) {
return array;
}
doQuickSort(array, 0, array.length - 1);
return array;
}
function doQuickSort(array,left,right) {
if (left >= right) {
return;
}
let pivotPos = partition(array,left,right);
doQuickSort(array,left, pivotPos - 1);
doQuickSort(array,pivotPos + 1, right);
}
function partition(array,left,right) {
let pivotIdx = (left + Math.random() * (right - left + 1)) | 0;
let pivot = array[pivotIdx];
// Swap pivot element to the far right
swap(array, right, pivotIdx);
let leftBound = left;
let rightBound = right - 1;
while (leftBound <= rightBound) {
// [0,leftBound),(rightBound,right-1] is an explored area, and [leftBound+1, rightbound-1] is an unexplored area.
// When leftBound == rightBound, the index should not be checked
if (array[leftBound] < pivot) {
leftBound++;
} else if (array[rightBound] >= pivot) {
rightBound--;
} else{ swap(array, leftBound, rightBound); leftBound++; rightBound--; }}// leftBound == rightBound + 1
// swap returns the pivot element to the middle position
swap(array, leftBound, right);
return leftBound;
}
function swap(array, i, j) {
let tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
Copy the code2. Merge sort (Tc: O(nlogn) Sc:O(n))
function mergeSort(array) {
if (array.length > 1) {
const length = array.length;
const mid = Math.floor(length / 2);
const left = mergeSort(array.slice(0,mid));
const right = mergeSort(array.slice(mid,length));
array = merge(left,right);
}
return array;
}
function merge(left,right) {
let i = 0,j = 0;
const result = [];
while (i < left.length && j < right.length) {
result.push(left[i] > right[j] ? left[i++] : right[j++]);
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
Copy the codeInsert sort (Tc: O(n²) Sc:O(1))
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i;
temp = array[i];
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
}
Copy the codeLeetCode 912 questions
conclusion
The above questions are selected high-frequency questions, I hope to help you.