Record the leetcode top100
This part only records the easy difficulty, because of the easy difficulty, so basic directly put the solution
1. two sum
Sum of two numbers – Finds two numbers in an unordered array with a constant value, and returns the subscript
Because we need to return subscripts, sorting first and then sweeping two Pointers (front -> back, back -> front) (NlogN) does not work. Therefore, the form solution similar to hash is selected. Key is an array value and value is a subscript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
const map = {};
nums.forEach((num, index) = > map[num] = index);
const len = nums.length;
for(let i = 0; i < len; i++) {
const otherIndex = map[target - nums[i]];
if(otherIndex && otherIndex ! = i) {return [Math.min(i, otherIndex), Math.max(i, otherIndex)]
}
}
};
Copy the code20. Valid Parentheses
Check if the input string contains only (,), {,}, [and]
- The open parenthesis must be closed with the same type of parenthesis.
- The open parentheses must be closed in the correct order.
/** * @param {string} s * @return {boolean} */
var isValid = function(s) {
const stack = [];
const helpMap = {
'(': ') '.'[': '] '.'{': '} '
}
for(let i = 0; i < s.length; i++) {
const char = s[i];
if(char in helpMap) {
stack.push(helpMap[char]);
} else if(char ! == stack.pop()){return false; }}return stack.length === 0;
};
Copy the code21. Merge Two Sorted Lists
Merge two sorted lists and return them as new lists. The new list should be done by concatenating the nodes of the previous two lists.
- Solution one: recursion
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
var mergeTwoLists = function (l1, l2) {
if(! l1)return l2;
if(! l2)return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
returnl2; }};Copy the code- Solution 2: cycle
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
var mergeTwoLists = function (l1, l2) {
if(! l1)return l2;
if(! l2)return l1;
const newList = new ListNode(null);
let newPointer = newList;
while (l1 && l2) {
if (l1.val < l2.val) {
newPointer.next = l1;
l1 = l1.next;
} else {
newPointer.next = l2;
l2 = l2.next;
}
newPointer = newPointer.next;
}
if (l1) newPointer.next = l1;
if (l2) newPointer.next = l2;
return newList.next;
};
Copy the code35. Search Insert Position
Given the sorted array and target value, the index is returned if the target is found. If not, return the index inserted in order.
It’s kind of a binary search variant
Usually binary search recursion to write more, here to do not use recursion version
/** * @param {number[]} nums * @param {number} target * @return {number} */
var searchInsert = function(nums, target) {
let start = 0, end = nums.length - 1;
let mid = Math.ceil((end + start) / 2);
while(nums[mid] ! == target) {if(end <= start) {
// Where to insert if not found
return nums[end] < target ? end + 1 : end;
}
if(nums[mid] > target) {
// Protect from becoming negative
end = Math.max(mid - 1.0);
} else {
// Take care not to cross the line
start = Math.min(mid + 1, nums.length - 1);
}
mid = Math.floor((end + start) / 2);
}
return mid;
};
Copy the code52. Maximum Subarray
Find the sum of the largest subsequence in an array
Solution: iterate through each array element from beginning to end. If the sum of the previous elements is positive, add the value of the element to continue the search. If the sum of previous elements is negative, the element starts a new sum count. And pay attention to the maximum update sum during the whole process.
/** * @param {number[]} nums * @return {number} */
var maxSubArray = function(nums) {
let cache = 0;
let max = -Infinity;
nums.forEach(num= > {
cache += num;
if(cache > max) max = cache;
if(cache < 0) cache = 0;
})
return max;
};
Copy the code70. Climbing Stairs
Jump step, classic DP
/** * @param {number} n * @return {number} */
var climbStairs = function(n) {
const dp = [0.1.2];
for(let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]
};
Copy the code100. Same Tree
Bad way to write: use short circuit and other features to write the code in a line, pay attention to do value protection
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */
var isSameTree = function(p, q) {
return (p || q) ? (p || {}).val === (q || {}).val && isSameTree((p || {}).left, (q || {}).left) && isSameTree((p || {}).right, (q || {}).right) : true
};
Copy the code101. Symmetric Tree
Determine whether a binary tree is a mirror image solution 1: continue the line
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {boolean} */
var isSymmetric = function(root) {
return childIsSymmetric((root || {}).left, (root || {}).right);
};
function childIsSymmetric (left, right) {
return (left || right) ? (left || {}).val === (right || {}).val && childIsSymmetric((left || {}).left, (right || {}).right) && childIsSymmetric((left || {}).right, (right || {}).left) : true;
}
Copy the codeMethod 2:
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {boolean} */
var isSymmetric = function(root) {
if(! root)return true;
function areMirror(left, right) {
if(! left && ! right)return true;
if((left && ! right) || (right && ! left))return false;
if(left.val ! = right.val)return false;
return areMirror(left.left, right.right) && areMirror(left.right, right.left);
}
return areMirror(root.left, root.right);
};
Copy the code104. Maximum Depth of Binary Tree
Find the depth of the binary tree
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {number} */
var maxDepth = function(root, deep = 0) {
if(! root)return deep;
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};
Copy the code121. Best Time to Buy and Sell Stock
Give an array where the ith element is the price of the given stock on day I. You can only buy and sell once for maximum profit
First set maximum profit and minimum price:
- If the stock price on the current day is less than the lowest price, set the lowest price to the stock price on that day.
- If the maximum profit is less than the day’s price minus the lowest price, set the maximum profit to the day’s price minus the lowest price.
/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
if(! prices.length)return 0;
let minPrice = Infinity, maxProfit = -Infinity;
prices.forEach(price= > {
if(price < minPrice) {
minPrice = price;
}
if(maxProfit < (price - minPrice)) { maxProfit = (price - minPrice); }});return maxProfit;
};
Copy the code136. Single Number
Classic problem, one line of code xor solution
/** * @param {number[]} nums * @return {number} */
var singleNumber = function(nums){
return nums.reduce((a,b) = > { returnA ^ b}); }Copy the code141. Linked List Cycle
To determine whether a linked list has a ring, you cannot use the extra space method: use two Pointers, fast Pointers take two steps at a time, slow Pointers take one step at a time. So each time the fast Pointers take one more step than the slow Pointers, if there are rings that can eventually meet.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {boolean} */
var hasCycle = function (head) {
let slow = head;
let fast = head;
while (fast) {
slow = slow.next;
fast = fast.next && fast.next.next;
if(slow === fast && fast ! = =null) {
return true; }}return false;
};
Copy the code155. Min Stack
Design a stack that supports push, pop, top, and retrieving the smallest element in constant time.
- Push (x) — Pushes element X onto the stack
- Pop () — Removes the element at the top of the stack
- Top () — gets the top element
- GetMin () — Retrieves the smallest element in the stack
Optimal solution -o (1) :
We can maintain a stack minStack, which acts like a cache, to record what the smallest element is at the time of the push. At each push, we update our cache by comparing the current element to the top element of the minStack and pushing the smallest element into the minStack. This means that the minimum value should be the smallest element in the previous stack and the smallest element in the new one.
/** * initialize your data structure here. */
var MinStack = function() {
this.stack = [];
this.minStack = [];
};
/** * @param {number} x * @return {void} */
MinStack.prototype.push = function(x) {
this.stack.push(x);
const minStackTop = this.minStack[this.minStack.length - 1];
this.minStack.push(Math.min(x, minStackTop === undefined ? Infinity : minStackTop));
};
/** * @return {void} */
MinStack.prototype.pop = function() {
this.stack.pop();
this.minStack.pop();
};
/** * @return {number} */
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
/** * @return {number} */
MinStack.prototype.getMin = function() {
return this.minStack[this.minStack.length - 1];
};
/** * Your MinStack object will be instantiated and called as such: * var obj = Object.create(MinStack).createNew() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */
Copy the code160. Intersection of Two Linked Lists
Find a node with the common beginning of two singly linked lists.
- Returns if the two linked lists do not intersect at all
null. - When the function returns, the link list must retain its original structure.
- You can assume that there are no loops in the entire link structure.
- The code runs in O(n) time and only uses O(1) memory.
We also have to deal with the case of two linked lists with no common nodes:
As shown in the figure above, the pointer starting from A goes A + B, and the pointer starting from B also goes B + A, so they will be undefined after the next step. That is to say, if the two lists have no common nodes, Just check that both Pointers are undefined.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */
var getIntersectionNode = function(headA, headB) {
let nodeA = headA, nodeB = headB;
while(nodeA ! == nodeB) { nodeA = nodeA ? nodeA.next : headB; nodeB = nodeB ? nodeB.next : headA; }return nodeA || null;
};
Copy the code169. Majority Element
Find the number in the array that occurs more than ‘⌊ n/2 ⌋’.
- And since it’s more than half, you can sort it and see what’s in the middle
- Moore Voting Algorithm: ‘Finds a different pair of elements each time and removes them from the array until the array is empty or has only one element
- Boyer-Moore Algorithm(Majority voting algorithm) : Records a current majority variable
AAnd the number ofnumADuring traversal, if the current element and the record elementAEqual,numAAdd 1; If it is not equal, thennumAMinus 1. ifnumAIf the value is zero, it is updatedAAnd resetnumA. The essence of this is that when I iterate over a number set, ifnumAIs 0, indicating that there are no candidate elements, that is, the previous traversal process did not find more than half of the elements. So if more than half of the elementsAExists, thenAIn the rest of the subarrays, it must be more than half the time. So we can turn the original problem into its subproblems.Here is a visual flow
/** * @param {number[]} nums * @return {number} */
var majorityElement = function(nums) {
let result, count = 0
nums.forEach(num= > {
if(result ! == num) {if(count === 0) {
count = 1;
result = num;
} else{ count--; }}else {
count++
}
});
return result;
};
Copy the code198. House Robber
You’re a professional robber, planning to raid homes along a street. There is a certain amount of money stored in each house, and the only constraint that prevents you from robbing a house is that, because the houses are connected by a security system, if two neighbouring houses are broken into on the same night, they will automatically contact the police, so you can’t rob neighbouring houses. Given a list of non-negative integers representing the amount of money in each house, calculate the maximum amount of money that can be robbed in one night without alerting the police.
DP: For the ith room, our choice is to steal or not to steal
- If you decide to steal, then the i-1 room must not be stolen, then this step is going to be
dp[i] = nums[i-1] + dp[i -2], it is assumed thatdp[i]Represents the maximum amount of money accumulated by robbing house I - If you don’t steal, then it doesn’t matter if you’ve already stolen,
dp[i] = dp[i -1] - so
dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1] )
/** * @param {number[]} nums * @return {number} */ var rob = function(nums) { if(! nums.length) return 0; const dp = [nums[0]]; for(let i = 1; i < nums.length; i++){ dp[i] = Math.max(dp[i - 1], (dp[i - 2] || 0) + nums[i]); } return dp[nums.length - 1]; };Copy the code206. Reverse Linked List
Reverse a linked list
Can loop/recurse honestly:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {ListNode} */
var reverseList = function (head) {
if(! head)return head;
let start = head;
let end = head
while (end.next) {
const node = end.next;
end.next = node.next;
node.next = start;
start = node;
}
return start;
}
Copy the codeYou can also operate it:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {ListNode} */
var reverseList = function (head, pre) {
if(! head)return head
const next = head.next;
head.next = pre || null
return next ? reverseList(next, head) : head;
};
Copy the code226. Invert Binary Tree
Invert the binary tree
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {TreeNode} */
var invertTree = function(root) {
if(! root)return [];
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root
};
Copy the code234. Palindrome Linked List
To determine whether a linked list is a palindrome requires O(n) time and O(1) space
In this case, the violent solution is to go through the list and convert it to a string, and then see if it’s a palindrome, which meets the time complexity requirement, but not the space complexity requirement
Order one space, you have to start with the list itself. First of all, judging palindromes is nothing more than going from side to middle or from middle to side. Since we can do things with the list itself, we should consider making the list accessible backwards (because O(1) space is required, we can’t make it a two-way list directly). Since we can only make the list go in one direction, we can think of ways to choose from the middle to the sides, left forward (pre), right backward (Next).
So how do we find the middle node? – The middle node is half the list, so we use one fast pointer to go two steps at a time, and one slow pointer to go one step at a time, so when the fast pointer goes to the end, the slow pointer should go to the middle of the list. Also be careful to distinguish whether the list length is odd or even: if it is odd, the middle node does not need to be judged and should be compared with the first and second nodes.
The final code looks like this:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {boolean} */
var isPalindrome = function(head) {
if(! head)return true;
if(! head.next)return true;
let fast = head.next, slow = head;
let pair = null;
while(fast ! =null&& fast.next ! =null) {
slow.next.pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if(! fast || fast.next) {/ / odd
pair = slow.next;
slow = slow.pre;
} else {
/ / even
pair = slow.next;
}
while(pair) {
if(pair.val ! == slow.val)return false;
pair = pair.next;
slow = slow.pre;
}
return true;
};
Copy the code283. Move Zeroes
Given an array nums, write a function to move all zeros to its end while preserving the relative order of the non-zero elements. Additional requirements:
- You must do this in place without making a copy of the array
- Minimize the total number of operations. Ideas:
- Minimize operation: the operation is completed in the process of traversal, and no additional movement operation is required
- Let’s call the number of zeros zero
zeroesNumsAnd then move each non-zero number forwardzeroesNums, and finally zero at the end of the array
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */
var moveZeroes = function(nums) {
let zeroesNums = 0;
nums.forEach((num, index) = > {
if(num === 0) {
zeroesNums++;
} else{ nums[index - zeroesNums] = num; }});for(let i = nums.length - 1; zeroesNums > 0; i--) {
nums[i] = 0; zeroesNums--; }};Copy the code437. Path Sum III
Given a binary tree where each node is an integer (can be positive or negative), find how many paths add up to a given value. Note that the path does not need to start or end at the root or leaf, but must go down (that is, only from the parent node to the child node).
Solution 1: violent solution, using BFS and recursion to search the path that meets the conditions. It is important to note that this approach does not make use of any cache, that is, all path nodes are re-iterated as the sum of each path is computed. Time order n ^ 2.
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @param {number} sum * @return {number} */
var pathSum = function(root, sum) {
if(! root)return 0;
let result = 0;
const queue = [root];
while(stack.length) {
const node = queue.shift();
result += reslove(node, sum);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return result
};
function reslove(root, sum) {
if(! root)return 0;
let result = 0;
if(sum === root.val) result++;
return result + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}
Copy the codeSolution 2: If you don’t want to use queue, you can just use recursive search
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @param {number} sum * @return {number} */
var pathSum = function(root, sum) {
if(! root)return 0;
return reslove(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
};
function reslove(root, sum) {
if(! root)return 0;
return ((sum === root.val) ? 1 : 0) + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}
Copy the codeSolution three (O(n)) : In the first two solutions, we iterate through each layer of nodes from the top down (the first layer is traversed once, the second layer is traversed twice…). . At this point, we should find a way to reduce the number of iterations using caching.
So we have this O(n) complexity solution (the idea is in the comments)
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @param {number} sum * @return {number} */
var pathSum = function(root, sum) {
/ / cache
const hashMap = {};
let currentSum = 0;
return pathSumRecursive(root, currentSum, hashMap, sum);
};
function pathSumRecursive(node, currentSum, hashMap, target) {
if(! node) {return 0;
}
const newCurrentSum = currentSum + node.val;
// Let's see if we can use the previous cache to calculate all line segments in one walk
// Current path sum - target value - essentially looks at whether there is a path sum equal to the target value
For example, if the path is 2-5-3 and the target is 8, then the sum of the paths at 3 is 10, and the target is 2 after subtracting 8. There is a sum of 2 in the previous path, so there is a sum of 8 in the middle
let totalPaths = hashMap[newCurrentSum - target] || 0;
if (newCurrentSum === target) {
totalPaths++;
}
// Update the cache
if (hashMap[newCurrentSum]) {
hashMap[newCurrentSum]++;
} else {
hashMap[newCurrentSum] = 1;
}
totalPaths += pathSumRecursive(node.left, newCurrentSum, hashMap, target);
totalPaths += pathSumRecursive(node.right, newCurrentSum, hashMap, target);
// After traversing the subsequent nodes, delete itself from the cache before going back to the previous level to ensure that the cache data is correct (only the previous path should be present).
hashMap[newCurrentSum]--;
return totalPaths;
}
Copy the code438. Find All Anagrams in a String
Finding isomorphisms in strings: Given a string S and a non-empty string P, find all starting indexes of isomorphisms of P in s. What is isomorphism: Two string letters are the same, but the order of the letters in the string may be different, for example ab and BA are isomorphic
Solution a:
For this, the first thought is to use cache to improve efficiency, here we first use the form of Map mapping. Use sliding Windows at the same time – two Pointers (subscripts) to point to the current substring. And then I scan from front to back to see if there’s a match through the Map. if
- The current character is present in our Map, but has already been matched, so we need to sweep back the pointer to the beginning until we encounter the same character.
- The current character does not exist in our Map at all, which means that there is no string up to this character. Therefore, we need to restore the Map and start looking for the next character
/** * @param {string} s * @param {string} p * @return {number[]} */
var findAnagrams = function(s, p) {
const targetMap = {};
/ / build the map
for(let char of p) {
if(targetMap[char]) {
targetMap[char]++;
} else {
targetMap[char] = 1; }}let start = 0;
let cacheLen = p.length;
const result = [];
for(let i = 0; i < s.length; i++) {
const char = s[i];
// If char still has
if(targetMap[char]) {
targetMap[char]--;
cacheLen--;
// If all matches
if(cacheLen === 0) {
result.push(start); / / propulsion
// All move forward one bittargetMap[s[start]]++; start++; cacheLen++; }}else if(targetMap[char] === 0) {
// select * from char; // select * from char
while(s[start] ! == char) { targetMap[s[start]]++; start++; cacheLen++; } start++; }else {
// char doesn't have one at all
while(start < i) { targetMap[s[start]]++; start++; } start++; cacheLen = p.length; }}return result;
};
Copy the codeMethod 2: Obj is used for Mapping, we can also use array and character subscript for Mapping
/** * @param {string} s * @param {string} p * @return {number[]} */
var findAnagrams = function (s2, s1) {
const map = Array(128).fill(0);
let start = 0,
end = 0,
counter = s1.length;
const res = [];
for (let i = 0; i < s1.length; ++i) {
map[s1.charCodeAt(i)]++;
}
while (end < s2.length) {
if (map[s2.charCodeAt(end)] > 0) {
counter--;
}
map[s2.charCodeAt(end)]--;
end++;
while (counter == 0) {
if (end - start == s1.length) {
res.push(start);
}
if (map[s2.charCodeAt(start)] == 0) { counter++; } map[s2.charCodeAt(start)]++; start++; }}return res;
};
Copy the code448. Find All Numbers Disappeared in an Array
All the digits in the array are in [1, n], and no extra space is available. This problem can be used to reverse the corresponding position of the number: the number in the corresponding position of the number in the negative, and then traverse to find those positive numbers, its subscript +1 is the number that does not appear
/** * @param {number[]} nums * @return {number[]} */
var findDisappearedNumbers = function(nums) {
nums.forEach(num= > {
num = Math.abs(num);
if(nums[num - 1] > 0) {
nums[num - 1] = -nums[num - 1]}});const result = [];
nums.forEach((num, index) = > {
if(num > 0) {
result.push(index + 1); }});return result;
};
Copy the codeBit operations SAO operation version: first of all, a simple understanding of a few bit operations is what:
- JavaScript bit operations treat their operands as a sequence of 32-bit bits, with the left-most bit of the signed number being 1
- 1 < < 31:10000000000000000000000000000000
- 1 < < 31-1 to 01111111111111111111111111111111
- Proceed with 1 << 31
|To change a number (positive or negative) to a negative number (just change the sign bit). - Proceed with 1 << 31-1
&Operation, will change a number (whether positive or negative) to a positive number (only modify the sign bit) the solution avoids the sign judgment in the above manner
/** * @param {number[]} nums * @return {number[]} */
var findDisappearedNumbers = function(nums) {
for (var i = 0; i < nums.length; i++) {
nums[(nums[i] & ((1 << 31) - 1)) - 1] | = (1 << 31);
// The unified positive and negative operations become negative numbers
}
ans = [];
for (var i = 0; i < nums.length; i++) {
// If it is not a negative number, push it forward
if ((nums[i] & (1 << 31)) != (1 << 31))
ans.push(i+1);
}
return ans;
};
Copy the code461. Hamming Distance
Hamming Distance represents the number of different characters in the corresponding positions of two strings of equal length, and also measures the minimum number of substitutions required to change string X to y by substituting characters.
1. Conventional solution: after converting to binary bit by bit, it is necessary to manually fill bits or manually judge undefined
/** * @param {number} x * @param {number} y * @return {number} */
var hammingDistance = function (x, y) {
let binaryX = x.toString(2);
let binaryY = y.toString(2);
const len = Math.max(binaryX.length, binaryY.length);
if (binaryX.length < len) {
binaryX = binaryX.padStart(len, '0')}else {
binaryY = binaryY.padStart(len, '0')};let result = 0;
for (let i = len - 1; i >= 0; i--) {
if(binaryX[i] ! == (binaryY[i])) { result++ } }return result;
};
Copy the code2. Bit operation: xor by bit, do not need to consider the complement length, more concise
/** * @param {number} x * @param {number} y * @return {number} */
var hammingDistance = function (x, y) {
var res = x ^ y;
var count = 0;
while(res ! =0) {
if (res % 2= =1) count++;
res = Math.floor(res / 2); // res = res >> 1;
}
return count;
};
Copy the code538. Convert BST to Greater Tree
Each node in the binary search tree is appended with the values of all nodes greater than it: each key in the original BST is changed to the original key plus the sum of all keys greater than the original key in the BST.
Solution a:
- The properties of BST are as follows
- If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.
- If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
- Its left and right subtrees are also binary sort trees respectively.
- Traverse from large to small using right -> middle -> left order and utilize
cacheValTo cache values larger than the current node to achieve O(n) time complexity - I’m doing it recursively
cacheValInstead of saving the value in the outer layer (a bit of trouble, since you need to deal with the leftmost node of the right subtree:The code line 29) - Since the left-most node of the right subtree is only the smallest except for the current node, the left-most node of the right subtree has the largest value (the sum of all nodes larger than the current node). So the current node only needs to add the value of the leftmost node of the right subtree
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {TreeNode} */
var convertBST = function(root) {
if(root) {
converVal(root);
return root;
} else {
return[]; }};function converVal(root, cacheVal = 0) {
if(root.right) {
cacheVal = converVal(root.right, cacheVal);
}
root.val += cacheVal;
cacheVal = root.val;
if(root.left) {
// Process the left-most node of the right subtree and return it to the upper level recursively (at this time, the left-most node of the right subtree is the value of the upper level node)
return converVal(root.left, cacheVal);
}
return root.val;
}
Copy the codeSolution 2: Take cacheVal from solution 1 and put it around a closure so that instead of passing it recursively, you can simply iterate through it from large to small.
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {TreeNode} */
var convertBST = function(root) {
let sum = 0;
return function inner(root) {
if (root == null) return null;
inner(root.right);
root.val += sum;
sum = root.val;
inner(root.left);
return root;
}(root);
};
Copy the code543. Diameter of Binary Tree
Given a binary tree, calculate the diameter length of the tree – the diameter of the binary tree is the length of the longest path between any two nodes in the tree. This path may or may not go through the root node.
Recursion, since it is to find the longest path, is divided into two cases:
- Find the single longest path to the left and right subtrees of the current subtree and return it to the upper layer
- Returns the longest path of the current subtree (the longest path of the left subtree + the current root node (1) + the longest path of the right subtree for the upper layer to use
Find the larger of the two
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {number} */
var diameterOfBinaryTree = function(root) {
if(! root)return 0;
// Return a maximum
return Math.max(... diameterOfSubtree(root)) -1;
};
function diameterOfSubtree(root) {
if(! root.left && ! root.right)return [1.1];
let left = 0, leftBig = 0, right = 0, rightBig = 0;
if(root.left) [left, leftBig] = diameterOfSubtree(root.left);
if(root.right) [right, rightBig] = diameterOfSubtree(root.right);
// The longest path of the current subtree
const cacheBig = Math.max(leftBig, rightBig, left + right + 1);
return [1 + Math.max(left, right), cacheBig];
}
Copy the code572. Subtree of Another Tree
Determine if a tree is a substructure of another tree
Solution 1: Directly recurse to see if it’s a subtree, but it’s iterating
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} s * @param {TreeNode} t * @return {boolean} */
var isSubtree = function (s, t) {
return!!!!! (subtree(s, t) || (s.left && isSubtree(s.left, t)) || (s.right && isSubtree(s.right, t))); };function subtree(s, t) {
if(! s && ! t)return true;
return ((s || {}).val === (t || {}).val) &&
subtree(s.left, t.left) &&
subtree(s.right, t.right);
}
Copy the codeSolution 2: preorder the tree, save as a string, and see if the source contains target
var isSubtree = function(s, t) {
let string1 = {str: ""};
let string2 = {str: ""};
treeString(s, string1);
treeString(t, string2);
return string1.str.includes(string2.str);
}
function treeString(root, string) {
if(! root) { string.str +="X";
return;
}
string.str += `,${root.val}, `
treeString(root.left, string);
treeString(root.right, string);
}
Copy the code581. Shortest Unsorted Continuous Subarray
Shortest unsorted continuous subarray: Given an array of integers, you need to find the shortest contiguous subarray that will be sorted in ascending order if the subarray is sorted in ascending order.
The first simple way is to sort the array, so the number of differences between the original array and the new array is bound, but this complexity is O(NLGN) (sort traversal)
Or we could use two Pointers, one from front to back and one from back to front
- Search back and forth for the last index that is not the maximum value
- Find the first non-minimum index from back to front
And then you can figure out which paragraph is not sorted in ascending order
/** * @param {number[]} nums * @return {number} */
var findUnsortedSubarray = function(nums) {
let last = 0, first = - 1, max = -Infinity, min = Infinity;
for(let i = 0, j = nums.length - 1; j >= 0; j--, i++){
max = Math.max(max, nums[i]);
if(nums[i] ! == max) first = i; min =Math.min(min, nums[j]);
if(nums[j] ! == min) last = j; }return first - last + 1;
};
Copy the code617. Merge Two Binary Trees
[bug] testcase:
Input: [] []
Expected: []
Output: null
Copy the codeRecursive:
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} t1 * @param {TreeNode} t2 * @return {TreeNode} */
var mergeTrees = function(t1, t2) {
if(! t1) {return t2;
}
if(! t2) {return t1;
}
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
};
Copy the codeNonrecursive: use stack plus tree hierarchical traversal writing
var mergeTrees = function (t1, t2) {
if (t1 === null) {
return t2;
}
const stack = [];
stack.push([t1, t2]);
while(stack.length ! = =0) {
const t = stack.pop();
if (t[0= = =null || t[1= = =null) {
continue;
}
t[0].val += t[1].val;
if (t[0].left === null) {
t[0].left = t[1].left;
} else {
stack.push([t[0].left, t[1].left]);
}
if (t[0].right === null) {
t[0].right = t[1].right;
} else {
stack.push([t[0].right, t[1].right]); }}return t1;
};
Copy the code