Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
1. Time complexity and space complexity
An algorithm is a set of methods used to manipulate data and solve a program problem. The advantages and disadvantages of the algorithm can be measured by time complexity and space complexity. In general, time complexity is more problematic than space complexity, so it is time complexity that is studied more.
1.1 Time Complexity
Generally speaking, the corresponding elapsed time can be obtained by running the program once, but the results may vary depending on machine performance, data size and other factors. Theoretically, it is only necessary to obtain a time evaluation index to obtain the general trend of algorithm time consumption.
In general, the time an algorithm takes is proportional to the number of code statements executed, and the more times the code is executed, the longer it takes. We call the number of times an algorithm is executed the time frequency, which is called T(n). The asymptotic time complexity (time complexity for short) is represented by capital O, so it is also called the big O notation. The time complexity of the algorithm is T(n)=O(f(n)). It means that T(n) approaches f(n) as n approaches positive infinity. Common time complexity is O(1) constant; O(log n) log type; O(n) linear type; O(nlog n) linear log type; O(n2) square; O(2n) exponential.
The time complexity is usually calculated by finding the execution statement and counting the number of times the statement is executed, denoted by big O. Where, when represented by big O, 1 is used to represent The Times of constant level execution, only the highest order term of the function is retained, and the coefficient in front of the highest order is removed.
int j = 0; / / 1.
for (int i = 0; i < n; i++) { / / 2.
j = i; / / 3.
j++; / / 4.
}
Copy the codeIn the above code, the frequency of statement ① is 1, the frequency of statement ② is N, the frequency of statement ③ is n-1, and the frequency of statement ④ is n-1, so the time frequency T(n)=1+ N +n-1+n-1=3n-1, and the ellipse coefficient and constant term get T(n)=O(n).
1.2 Space Complexity
Space complexity refers to the size of the memory required to execute an algorithm. Similar to time complexity, space complexity is also estimated and is expressed in terms of S(n)=O(f(n)). S(n) is the space complexity and the required storage space is expressed in terms of F (n).
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
j = i;
j++;
}
Copy the codeIn the code above, only when m is created, the array space is allocated, and no memory space is added in the for loop, so the space complexity S(n)=O(n).
2. The title
2.1 Sum of two numbers
Leetcode address
Instead of returning two numbers whose sum is equal to the target, you cannot change the position of the subscripts in the array, so you cannot use the double pointer method. In the process of writing specific code, the use of map, and then the array of data traversal, map does not save and for the target number of another number as a key, and the number of the subscript as a value; If the number is present in the map, the map retrieves the value and the index of the number into the array and returns it.
var twoSum = function (nums, target) {
let map = new Map(a)for (let i = 0; i < nums.length; i++) {
if(! map.has(nums[i])) { map.set(target - nums[i], i) }else {
return [map.get(nums[i]), i]
}
}
return[]}.Copy the code2.2 Sum of three numbers
Leetcode address
When finding the sum of three numbers, we use the two-pointer method, so first we need to arrange them in ascending order. The first number is obtained by traversing the array, the second and third numbers are obtained by double-pointer method, and the three numbers that meet the conditions are placed in the array each time. It is worth noting that the meaning of the question clearly states that repeated triples cannot be included, so every number determined needs to be de-duplicated to prevent repetition. In addition, after obtaining the triplet that matches the problem, it is necessary to remove the subscript first and then move it.
var threeSum = function (nums) {
if(nums.length<3) return []
nums.sort((a, b) = > a - b)
let res = []
for (let i = 0; i < nums.length - 1; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue / / to heavy
let l = i + 1, r = nums.length - 1
while (l < r) {
let sum = nums[i] + nums[l] + nums[r]
if (sum === 0) {
res.push([nums[i], nums[l], nums[r]])
while (l < r && nums[l] === nums[l + 1]) { / / to heavy
l++
}
while (l < r && nums[r] === nums[r - 1]) { / / to heavy
r--
}
l++
r--
} else if (sum < 0) {
l++
} else {
r--
}
}
}
return res
};
Copy the code2.3 Sum of four numbers
Leetcode address
After looking at the sum of three numbers, the sum of four numbers is easy to understand. The first two numbers are obtained through array traversal, and the last two are obtained through double Pointers.
var fourSum = function (nums, target) {
if (nums.length < 4) return []
nums.sort((a, b) = > a - b)
let res = []
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
for (let j = i + 1; j < nums.length - 1; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue
let l = j + 1, r = nums.length - 1
while (l < r) {
let sum = nums[i] + nums[j] + nums[l] + nums[r]
if (sum === target) {
res.push([nums[i], nums[j], nums[l], nums[r]])
while (l < r && nums[l] === nums[l + 1]) {
l++
}
while (l < r && nums[r] === nums[r - 1]) {
r--
}
l++
r--
} else if (sum < target) {
l++
} else {
r--
}
}
}
}
return res
}
Copy the code2.4 The sum of the nearest three numbers
Leetcode address
It’s kind of like a sum of three, but the other thing to do here is, every time you get the sum of three you have to compare it to the previous one, and find the closest one.
var threeSumClosest = function (nums, target) {
nums.sort((a,b) = >a-b)
let res=nums[0]+nums[1]+nums[nums.length-1]
for(let i=0; i<nums.length-1; i++){let l=i+1,r=nums.length-1
while(l<r){
let sum=nums[i]+nums[l]+nums[r]
if(sum<target){
l++
}else{
r--
}
if(Math.abs(target-res)>Math.abs(target-sum)){
res=sum
}
}
}
return res
};
Copy the code2.5 Forward traversal of binary trees
Leetcode address
The first thing to know is that a pre-traversal gets the root node, then the left subtree node, and finally the right subtree node. Of course the recursive way is relatively simple, if interested in iterative writing can be studied.
var preorderTraversal = function (root) {
let res = []
function traversal(tree) {
if(! tree)return
res.push(tree.val)
traversal(tree.left)
traversal(tree.right)
}
traversal(root)
return res
};
Copy the code2.6 Middle order traversal of binary trees
Leetcode address
The middle-order traversal first obtains the nodes of the left subtree, then the root node, and finally the nodes of the right subtree.
var inorderTraversal = function(root) {
let result=[]
function inorder(tree){
if(! tree)return
inorder(tree.left)
result.push(tree.val)
inorder(tree.right)
}
inorder(root)
return result
};
Copy the code2.7 Backward traversal of binary trees
Leetcode address
The preceding traversal obtains the node of the left subtree first, then the node of the right subtree, and finally the root node.
var postorderTraversal = function(root) {
let result=[]
function postorder(tree){
if(! tree)return
postorder(tree.left)
postorder(tree.right)
result.push(tree.val)
}
postorder(root)
return result
};
Copy the code2.8 Maximum depth of a binary tree
Leetcode address
With DFS, return 0 if the node is empty, otherwise get the depth of the left and right subtrees and calculate larger values, increment 1 since the current node is not empty.
var maxDepth = function (root) {
if(! root)return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
Copy the code2.9 Balanced binary trees
Leetcode address
This is the same thing as finding the maximum depth association of a binary tree. If the node is empty, it is directly judged as a balanced binary tree; otherwise, it is judged whether the height difference between the left and right subtrees is greater than 1; otherwise, it is not a balanced binary tree; otherwise, it continues to recursively judge the left and right subtrees.
var isBalanced = function (root) {
if(! root)return true
function getHeight(tree) {
if(! tree)return 0
return Math.max(getHeight(tree.left), getHeight(tree.right)) + 1
}
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
return false
}
return isBalanced(root.left) && isBalanced(root.right)
};
Copy the code2.10 Mirroring of binary trees
Leetcode address
Returns null if the node is empty, otherwise gets a mirror image of the left and right subtrees and swaps the positions of the subtrees.
var mirrorTree = function (root) {
if(! root)return null;
let left = mirrorTree(root.right);
let right = mirrorTree(root.left);
root.left = left;
root.right = right;
return root;
}
Copy the code2.11 Symmetric binary trees
If both trees are empty, it is a symmetric binary tree. If one is empty and the other is not empty, it is not a symmetric binary tree. Otherwise, you need to compare the values of the two nodes. If they are equal then we need to recursively compare the right node of the first tree to the left node of the second tree.
var isSymmetric = function (root) {
if(! root)return true
function compare(left, right) {
if(! left && ! right)return true
else if(! left || ! right)return false
return left.val === right.val && compare(left.left, right.right) && compare(left.right, right.left)
}
return compare(root, root)
};
Copy the code2.12 Merge two ordered lists
Leetcode address If one list is empty, return another list. If the node value of one list is larger than that of the other list, merge the larger list and the result of the merge with the other list to return the list.
var mergeTwoLists = function (list1, list2) {
if(! list1)return list2
if(! list2)return list1
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2)
return list1
} else {
list2.next = mergeTwoLists(list1, list2.next)
return list2
}
};
Copy the code2.13 Intersecting linked lists
Leetcode address
The problem uses the idea of a double pointer. If either list is empty, null is returned. In the case that neither of the two linked lists is empty, the Pointers A and B point to headA and headB respectively. If the two Pointers a and B are not equal, the judgment will be made all the time. Pointer A is not empty and points to the next node, and if it is empty, it points to headB. If Pointers A and B are equal (both may be null), return one of the Pointers, and this is the intersecting node (may be null).
var getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) {
return null
}
let a = headA, b = headB
while(a ! == b) { a = a ! = =null? a.next : headB b = b ! = =null ? b.next : headA
}
return a
};
Copy the code2.14 Deleting a Node from a linked list
Leetcode address
To delete node, change the value of node to node.next.
var deleteNode = function (node) {
node.val = node.next.val
node.next = node.next.next
};
Copy the code2.15 Circular linked lists
Leetcode address
This problem uses the idea of fast and slow Pointers. Iterating with fast Pointers returns NULL if the next node of the fast pointer is NULL, otherwise fast Pointers take two steps and slow Pointers take one. When the fast and slow Pointers meet, it indicates that there is a ring, so the fast Pointers reset the head node, and then the fast and slow Pointers do not take another step, and when they meet again, it is the entrance of the ring.
var detectCycle = function (head) {
let fast = head, slow = head
while (fast) {
if (fast.next === null) return null
fast = fast.next.next
slow = slow.next
if (fast === slow) {
fast = head
while (true) {
if (fast === slow) return slow
fast = fast.next
slow = slow.next
}
}
}
return null
};
Copy the code2.16 Print the linked list from end to end
Leetcode address
Use an array to store the printed result, traverse each node of the list, insert the result from the head of the array, the array is printed from the end.
var reversePrint = function (head) {
let res = []
while (head) {
res.unshift(head.val)
head = head.next
}
return res
};
Copy the codeThe KTH last node in the linked list
Leetcode address
The idea of a fast or slow pointer is used. First let the fast pointer take k steps, after k steps, the fast and slow Pointers together, return the slow pointer.
var getKthFromEnd = function (head, k) {
let fast = head,slow = head
while (fast) {
fast = fast.next
k--
if (k < 0) {
slow = slow.next
}
}
return slow
}
Copy the code2.18 Reverse the linked list
Leetcode address
Make prev the first node of head, point prev to head. Next, head. Next and head to the previous node
var reverseList = function (head) {
let prev = null
while (head) {
[head.next, prev, head] = [prev, head, head.next]
}
return prev
};
Copy the code2.19 take the stairs
Leetcode address
The idea of dynamic programming can be used in this problem. First of all, we can think of f(x) as the number of ways to climb x stairs, so we can get the equation f(x)=f(x-1)+f(x-2), which means that the number of ways to climb X stairs is the number of ways to climb X stairs plus the number of ways to climb x stairs. If an array is used to store the number of options for each staircase, the space complexity can be obtained as O(n), but in fact, only the number of options for X stairs needs to be obtained, so the space complexity can be reduced to O(1) by using the idea of rolling array.
var climbStairs = function (n) {
let prev = 1, cur = 1
for (let i = 2; i <= n; i++) {
const temp = cur
cur += prev
prev = temp
}
return cur
};
Copy the code2.20 Fibonacci sequence
Leetcode address
Similar to climbing stairs, it should be said that climbing stairs is an application of Fibonacci numbers.
var fib = function (n) {
if (n < 2) return n
let prev = 0, cur = 1
for (let i = 2; i <= n; i++) {
const temp = cur
cur = (cur + prev) % 1000000007
prev = temp
}
return cur
};
Copy the code2.21 Maximum sum of contiguous subarrays
Leetcode address
This problem uses the idea of dynamic programming. Iterate over the number group, compare each number and the cumulative value after increasing the number, take a larger value, and then sum the value and compare to get a larger value.
var maxSubArray = function (nums) {
let prev = 0, sum = nums[0]
for (const num of nums) {
prev = Math.max(prev + num, num)
sum = Math.max(prev, sum)
}
return sum
}
Copy the code2.22 and are consecutive positive sequences of S
Leetcode address
This topic adopts the idea of sliding window. First find the middle value mid and execute the loop when I is less than or equal to mid. When the cumulative value is less than the target value, the cumulative value increases, and the value is stored in the temporary array temp. When the cumulative value is greater than or equal to the target value, the temporary array temp can be placed in the result array if the cumulative value is equal to the target value, and the cumulative value is decremented by decreasing the value of the first element in the temp array. Decreases to less than the target value and increases again.
var findContinuousSequence = function (target) {
let mid = Math.ceil(target / 2)
let i = 1, sum = 0, res = [], temp = []
while (i <= mid) {
while (sum < target) {
sum += i
temp.push(i++)
}
while (sum >= target) {
if (sum === target) {
res.push([...temp])
}
sum -= temp.shift()
}
}
return res
}
Copy the code2.23 The oldest string without repeating characters
Leetcode address
This topic adopts the idea of sliding window. Iterate over each element of the number group and store it in an array. When encountering an element that already exists in the array, delete the number before the repeated element and the current element. Each iteration compares the length of the array to the length of the previous array, taking a larger value.
var lengthOfLongestSubstring = function (s) {
let arr = [], max = 0
for (const char of s) {
const index = arr.indexOf(char)
if(index ! = = -1) {
arr.splice(0, index + 1)
}
arr.push(char)
max = Math.max(arr.length, max)
}
return max
}
Copy the code2.24 Sort a number that occurs only once in an array
Leetcode address
I saw that xOR was a quick solution, so I just used it.
var singleNonDuplicate = function (nums) {
return nums.reduce((acc, cur) = > acc ^ cur)
}
Copy the code2.25 The KTH largest node of the binary search tree
Leetcode address
Using the characteristics of binary search tree, the value of the node of the left subtree is smaller than the value of the root node, and the value of the node of the right subtree is larger than the value of the root node, then the array sequence from large to small can be obtained through inverse middle order traversal. And because the problem only needs to get the KTH big node, the recursive operation can be stopped after the value of this node is obtained.
var kthLargest = function (root, k) {
let res = root.val
function traversal(tree) {
if(! tree)return
traversal(tree.right)
k--
if (k === 0) {
res = tree.val
return
}
traversal(tree.left)
}
traversal(root)
return res
}
Copy the codeReferences cloud.tencent.com/developer/a…