Spent more than ten days, read “Algorithm” and then re-AC LeetCode, harvest quite a lot. Take notes this time. I put all the code for the problem on Github for reference. Project address: github.com/violetjack/… Subject address: leetcode.com/problemset/…
Ashamed to say, before writing “LeetCode logic problem sharing” actually do less by yourself, are to see the solution. More importantly, I did not systematically learn algorithms (self-taught programming). Therefore, the following problems are caused:
- See the topic do not understand methodology, understand others program difficulty.
- Solve the problem by looking at other people’s plans to summarize, copy. (In fact, it is written in a systematic algorithm)
- A lot of questions look at the answer just know it is and don’t know why.
- Many of the answers (the discussion board scheme) were wrong, but posted as if it were the right answer.
After that, I read algorithms (4th edition) and went back to it and tried the AC problem, and again it was a pile of problems. So it took longer than the first time.
Solutions to all kinds of problems
Without further ado, some algorithms and solutions to solve the problem are systematically sorted out
Binary tree
Most binary trees use recursion to recurse the left and right elements downward. Such as:
Calculate the maximum depth of binary tree
var maxDepth = function (root) {
if (root == null) return 0
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};
Copy the codeRepresent a binary tree as a two-dimensional array
var levelOrder = function(root) {
let ans = []
helper(root, ans, 0)
return ans
};
function helper(node, ans, i){
if (node == null) return
if (i == ans.length) ans.push([])
ans[i].push(node.val)
helper(node.left, ans, i + 1)
helper(node.right, ans, i + 1)
}
Copy the codeIt’s all about finding binary tree data level by level recursively.
Question of possibility
This kind of question usually tells you a set of data and then calculates the probability, minimum or maximum. Such as:
Given several denominations and a sum, use the fewest coins to make the sum.
var coinChange = function (coins, amount) {
let max = amount + 1
let dp = new Array(amount + 1)
dp.fill(max)
dp[0] = 0
for (let i = 1; i < max; i++) {
for (let j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
}
}
}
return dp[amount] > amount ? -1 : dp[amount]
};
Copy the codeDynamic programming (DP) is used to list the minimum number of coins needed from 0 to the target quota.
Figure out how many possibilities there are to go from the top left corner of the matrix to the bottom right corner, and only move down right.
var uniquePaths = function (m, n) {
const pos = new Array(m)
for (let i = 0; i < m; i++) {
pos[i] = new Array(n)
}
for (let i = 0; i < n; i++) {
pos[0][i] = 1
}
for (let i = 0; i < m; i++) {
pos[i][0] = 1
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
pos[i][j] = pos[i - 1][j] + pos[i][j - 1]
}
}
return pos[m - 1][n - 1]
};
Copy the codeThis problem is using dynamic programming to gradually list the possibilities of each grid, and finally return the possibilities of the bottom right corner.
Gets the maximum sum of consecutive elements in the given array
var maxSubArray = function (nums) {
let count = nums[0], maxCount = nums[0]
for (let i = 1; i < nums.length; i++) {
count = Math.max(count + nums[i], nums[i])
maxCount = Math.max(maxCount, count)
}
return maxCount
};
Copy the codeThe above problem preserves and returns the maximum value by continually comparing the maximum value.
In fact, the possibility of using dynamic programming is simpler and easier to understand than using DFS and BFS algorithms. (I often report TLE using DFS)
To find the
Generally encountered search problems, such as finding a value will generally use the following methods:
- Sorting algorithm (sorting is easy to find)
- Binary search
- Index move search (this method name is my own, probably this meaning ~)
Find a value in a two-dimensional matrix that increases both horizontally and vertically
var searchMatrix = function (matrix, target) {
if (matrix.length == 0) return false
let row = 0, col = matrix[0].length - 1
while (true) {
if (matrix[row][col] > target && col > 0) {
col--
} else if (matrix[row][col] < target && row < matrix.length - 1) {
row++
} else if (matrix[row][col] == target) {
return true
} else {
break
}
}
return false
};
Copy the codePosition the position in the upper right corner and find the target value by changing the position coordinates. The index move lookup method is used to find the results.
Locate the leftmost and rightmost numbers in the array
var searchRange = function (nums, target) {
let targetIndex = binarySearch(nums, target, 0, nums.length - 1)
if (targetIndex == -1) return [-1, -1]
let l = targetIndex, r = targetIndex
while(l > 0 && nums[l - 1] == target){
l--
}
while(r < nums.length - 1 && nums[r + 1] == target){
r++
}
return [l, r]
};
function binarySearch(arr, val, lo, hi) {
if (hi < lo) return -1
let mid = lo + parseInt((hi - lo) / 2)
if (val < arr[mid]) {
return binarySearch(arr, val, lo, mid - 1)
} else if (val > arr[mid]) {
return binarySearch(arr, val, mid + 1, hi)
} else {
return mid
}
}
Copy the codeThis problem uses dichotomy to find the index value of a target number, and then index moves to find characters left and right. Returns the index values for the left and right sides.
palindrome
The so-called palindrome is the same as reading backwards. Palindrome is determined by the way the sides of the index move to the middle.
Find the longest palindrome in the given string
var longestPalindrome = function (s) { let maxLength = 0, left = 0, right = 0 for (let i = 0; i < s.length; i++) { let singleCharLength = getPalLenByCenterChar(s, i, i) let doubleCharLength = getPalLenByCenterChar(s, i, i + 1) let max = Math.max(singleCharLength, doubleCharLength) if (max > maxLength) { maxLength = max left = i - parseInt((max - 1) / 2) right = i + parseInt(max / 2) } } return s.slice(left, right + 1) }; Function getPalLenByCenterChar(s, left, right) {// If (s[left]! = s[right]){ return right - left } while (left > 0 && right < s.length - 1) { left-- right++ if (s[left] ! = s[right]){ return right - left - 1 } } return right - left + 1 }Copy the codePath problem
Path problems can be done using depth-first (DFS) and breadth-first (BFS) algorithms. What I tend to do is use DFS. Recursively mark the path to find the target path. Such as:
Find if the word can be formed using neighboring letters in a two-dimensional alphabetic array given the word (212)
let hasWord = false var findWords = function (board, words) { var ans = [] for (let word of words) { for (let j = 0; j < board.length; j++) { for (let i = 0; i < board[0].length; i++) { if (board[j][i] == word[0]) { hasWord = false DFS(word, board, 0, j, i, "") if (hasWord) { if (! ans.includes(word)) ans.push(word) } } } } } return ans }; function DFS(word, board, index, j, i, subStr) { if (word[index] == board[j][i]) { subStr += board[j][i] board[j][i] = "*" if (j < board.length - 1) DFS(word, board, index + 1, j + 1, i, subStr) if (j > 0) DFS(word, board, index + 1, j - 1, i, subStr) if (i < board[0].length - 1) DFS(word, board, index + 1, j, i + 1, subStr) if (i > 0) DFS(word, board, index + 1, j, i - 1, subStr) board[j][i] = word[index] } if (index >= word.length || subStr == word) { hasWord = true } }Copy the codeSince DFS is a single path to black, a timeout will occur if each element is found using DFS. You can optimize the DFS lookup timeout by setting the cache if conditions allow (such as lookup an incrementing array).
Gets the maximum contiguous increasing array length in a two-dimensional matrix.
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]] var longestIncreasingPath = function (matrix) { if (matrix.length == 0) return 0 const m = matrix.length, n = matrix[0].length let max = 1 let cache = new Array(m) for (let i = 0; i < m; i++){ let child = new Array(n) child.fill(0) cache[i] = child } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { let len = dfs(matrix, i, j, m, n, cache) max = Math.max(max, len) } } return max } function dfs(matrix, i, j, m, n, cache){ if (cache[i][j] ! = 0) return cache[i][j] let max = 1 for (let dir of dirs){ let x = i + dir[0], y = j + dir[1] if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue; let len = 1 + dfs(matrix, x, y, m, n, cache) max = Math.max(max, len) } cache[i][j] = max return max }Copy the codeDFS is used to find the length of the cache, if other elements DFS to the current value, directly return the cache maximum.
The list
A linked list, from a JS perspective, is a data structure with a string of objects connected by Pointers. Appropriate use of the next pointer to change the pointer to complete a series of operations on the linked list. Such as:
List sort:
var sortList = function (head) { if (head == null || head.next == null) return head let prev = null, slow = head, fast = head while (fast ! = null && fast.next ! = null) { prev = slow slow = slow.next fast = fast.next.next } prev.next = null; let l1 = sortList(head) let l2 = sortList(slow) return merge(l1, l2) }; function merge(l1, l2) { let l = new ListNode(0), p = l; while (l1 ! = null && l2 ! = null) { if (l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } if (l1 ! = null) p.next = l1; if (l2 ! = null) p.next = l2; return l.next; }Copy the codeA top-down merge sort method is used to sort linked lists. Next and fast.next. Next speed are used to get the linked list nodes to get intermediate values.
Reverse order of a linked list
var reverseList = function(head) { let ans = null,cur = head while (cur ! = null) { let nextTmp = cur.next cur.next = ans ans = cur cur = nextTmp } return ans };Copy the codeThe sorting
Sort and find are the most important problems in the algorithm. Common sorting algorithms are:
- Insertion sort
- Selection sort
- Quick sort
- Merge sort
- Count sorting
More sorting algorithm knowledge points can refer to the “JS home sorting algorithm”, the author of the article illustrated all kinds of sorting algorithm, it is easy to understand. Here are a few examples of sorting algorithms:
Find the KTH largest value in the array
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
for (let i = 0; i <= k; i++) {
let max = i
for (let j = i; j < nums.length; j++) {
if (nums[j] > nums[max]) max = j
}
swap(nums, i, max)
}
return nums[k - 1]
};
function swap(arr, a, b) {
let tmp = arr[a]
arr[a] = arr[b]
arr[b] = tmp
}
Copy the codeA selection sort is used to rank the first K worthy results.
For arrays with duplicate values,0,2,1,1,0 [2]The sorting
var sortColors = function (nums) {
sort(nums, 0, nums.length - 1)
};
function sort(arr, lo, hi) {
if (hi <= lo) return
let lt = lo, i = lo + 1, gt = hi;
let v = arr[lo]
while (i <= gt) {
if (arr[i] < v) swap(arr, lt++, i++)
else if (arr[i] > v) swap(arr, i, gt--)
else i++
}
sort(arr, lo, lt - 1)
sort(arr, gt + 1, hi)
}
function swap(arr, a, b) {
let x = arr[a]
arr[a] = arr[b]
arr[b] = x
}
Copy the codeThis repeated value quicksort using three-way sharding is a great solution. Of course, counting sort is a good choice. And the list sort that I mentioned before uses merge sort.
arithmetic
The math seems simple, but the biggest problem you encounter is that if you use a constant maturity level of increment, a TLE (out of time limit) occurs for large numbers. So, we’re going to use exponential growth to find the results. Such as:
Compute x to the n
var myPow = function (x, n) {
if (n == 0) return 1
if (n < 0) {
n = -n
x = 1 / x
}
return (n % 2 == 0) ? myPow(x * x, parseInt(n / 2)) : x * myPow(x * x, parseInt(n / 2));
};
Copy the codeI started with x times x times n times, but I ran out of time when N was too large. Use the above scheme: 29 = 2 * 44 = 2 * 82 = 2 * 64 = 128 directly from the constant maturity level change to the exponential level change, this point should be noted in the mathematical operation.
Take the square root of x
var mySqrt = function (x) { let l = 0, r = x while (true) { let mid = parseInt(l + (r - l) / 2) if (mid * mid > x) { r = mid - 1 } else if (mid * mid < x) { if ((mid + 1) * (mid + 1) > x) { return mid } l = mid + 1 } else { return mid } } };Copy the codeThis problem uses dichotomy to find the result.
Binary problem
Binary problem, generally use the bitwise operators and binary conversion Number. The parseInt () and Number. The prototype, the toString () to solve.
To reverse the binary of a 32-bit number
var reverseBits = function(n) { var t = n.toString(2).split(""); while(t.length < 32) t.unshift("0"); Return parseInt(t.everse ().join(""), 2); };Copy the codeCommonly used algorithm
Said so much, in fact, in addition to the common sort, search, the other most commonly used is DP, DFS, BFS these three algorithms. It can be said that mastering sorting and these three algorithms can AC most of the algorithm problems. How about this awesome algorithm?
Talk a little bit about sort and search
- Bubble sort: Iterates through groups of numbers, comparing elements with neighboring ones, and switching if the current element is larger than the next. Do this from beginning to end, and get the last element to play in order. Then repeat the steps from 1 to n-1. Until finally the first and second elements compare in size. It’s sort of back to front.
- Selection sort: Iterate through the array, find the smallest element, switch with the first, then zoom out and start with the second, and repeat to the last. You can sort from back to front or you can sort from front to back.
function sort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
let min = i
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) min = j
}
swap(arr, i, min)
console.log(arr)
}
return arr
}
Copy the code- Insert sort: Iterate through the array, select an element, compare it with the previous adjacent element, if the current element is less than the previous element, switch places, continue to compare until the current element is less than the current element (or to the very first element), so sorting all elements. It’s sort of a front to back order.
function sort(arr) {
const len = arr.length
for (let i = 1; i < len; i++) {
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1)
console.log(arr)
}
}
return arr
}
Copy the code- Hill sort: Similar to insertion sort, an element is selected to compare the size and position of the first n elements of the element. And then I’m going to shrink the n. This method can reduce the problem of inserting the smallest value at the very end and then having to swap places one by one to know the most front. Reduce the number of switches. It’s sort of a front to back order.
- Merge sort: There are two kinds of merge sort mentioned in Algorithms: one is top-down merge sort. Divide the array down to the smallest unit (1 or 2 elements) and sort them, then compare the first two elements to the last two, and then sort the entire array. There’s another bottom-up merge sort that splits an array into subarrays, sorts them and then merges them.
let aux = new Array(arr.length)
function sort(arr, lo, hi) {
if (hi <= lo) return
let mid = lo + (parseInt((hi - lo) / 2))
sort(arr, lo, mid)
sort(arr, mid + 1, hi)
merge(arr, lo, mid, hi)
}
function merge(arr, lo, mid, hi) {
let i = lo, j = mid + 1
for (let k = lo; k <= hi; k++) {
aux[k] = arr[k]
}
for (let k = lo; k <= hi; k++) {
if (i > mid) arr[k] = aux[j++]
else if (j > hi) arr[k] = aux[i++]
else if (aux[j] < aux[i]) arr[k] = aux[j++]
else arr[k] = aux[i++]
}
console.log(arr)
}
Copy the code- Quicksort: Select the first value as the middle value, then place the elements smaller than the middle value to the left and the elements larger than the middle value to the right, and then cut the elements on both sides again to the smallest unit.
Function sort(arr, lo, hi) {if (hi <= lo + 1) return let mid = partition(arr, lo, hi) mid) sort(arr, mid + 1, hi) } function partition(arr, lo, hi) { let i = lo, j = hi + 1 let v = arr[lo] while(true) { while(arr[++i] < v) if (i == hi) break while(v < arr[--j]) if (j == lo) break if ((i >= j)) break swap(arr, i, j) console.log(arr) } swap(arr, lo, j) console.log(arr) return j }Copy the code- Tripartite quicksort: Similar to quicksort, the optimization point is that if an element is equal to the shard element, the element position does not change. And then the ones that are less than the shard elements go to the left, the ones that are equal to the shard elements go to the middle, and the ones that are larger than the shard elements go to the right. Applies to arrays with a large number of elements of the same size.
function sort(arr, lo, hi) {
if (hi <= lo) return
let lt = lo, i = lo + 1, gt = hi;
let v = arr[lo]
while (i <= gt) {
if (arr[i] < v) swap(arr, lt++, i++)
else if (arr[i] > v) swap(arr, i, gt--)
else i++
console.log(arr)
}
sort(arr, lo, lt - 1)
sort(arr, gt + 1, hi)
}
Copy the code- Heap sort: Heap sort can be said to be a selection sort that uses the concept of a heap to sort. Returns the maximum value of the current heap one by one using the priority queue return maximum feature.
- Counting sort: Store the number of occurrences of all elements in an array and return the sorted array in order from smallest to largest.
- Bucket sort: LSD and MSD sort of string sort. LSD uses index counting to move from the right to the left of the string, sorting by the current value. MSD uses the index counting method from left to right. After the first character of the string, the string array is divided into several arrays with the same beginning string for the second and third MSD sorting respectively.
- Binary lookup: An ordered array to compare the intermediate value to the target value. If the target value is less than the middle value, take the first half of the array and continue to divide. If the target value is greater than the intermediate value, take the last half of the array and continue to divide. If the target value is equal to the median, hit!
DP
About dynamic programming, you can see dynamic programming in detail – Zou Bo on dynamic programming, which tells the path, coins, the oldest sequence. These are all problems in LeetCode. Dynamic programming is an inference process that the next state can be obtained according to the previous state or the previous several states.
DFS
Depth-first search (DFS) is to search for one possibility from condition 1 to condition 2, and then return to search for another possibility, so that the bar is upgraded. For example, if there are five paths, the DFS algorithm simply sends out one scout to go down one path to scout, and if it doesn’t go down the next path.
DFS (vertex v) {flag v is traversed; DFS (u); for (for each adjacent point v and unmarked traversal point u) DFS (u); }Copy the codeDFS searches recursively.
Example: Find if you can use adjacent letters to form a target word in a two-dimensional alphabetic matrix.
var exist = function (board, word) { for (let y = 0; y < board.length; y++) { for (let x = 0; x < board[0].length; x++) { if (find(board, word, y, x, 0)) return true } } return false }; function find(board, word, y, x, d) { if (d == word.length) return true if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false; if (board[y][x] ! = word[d]) return false let tmp = board[y][x] board[y][x] = "*" let exist = find(board, word, y, x + 1, d + 1) || find(board, word, y, x - 1, d + 1) || find(board, word, y + 1, x, d + 1) || find(board, word, y - 1, x, d + 1) board[y][x] = tmp return exist }Copy the codeBFS
Breadth-first search (BFS) is a synchronous search that lists all possibilities from Condition 1 to condition 2. It is used to find shortest paths. For example, if there are five paths, the BFS algorithm sends scouts to each of the five paths to scout.
BFS() {input start point; Initialize all vertices to be marked as untraversed; Initialize a queue and put the starting point into the queue; While (queue is not empty) {delete a vertex S from the queue and mark it as traversed; Queue all points adjacent to S that have not been traversed; }}Copy the codeBFS is a way of storing the next vertex using an array.
Example: Change from word A to word B by changing the words in A given array one at A time. Items (127)
/** * @param {string} beginWord * @param {string} endWord * @param {string[]} wordList * @return {number} */ var ladderLength = function (beginWord, endWord, wordList) { if (! wordList.includes(endWord)) return 0 let set = new Set(), visited = new Set(), len = 1 set.add(beginWord) visited.add(beginWord) while (set.size ! = 0) { let tmp = new Set([...set]) for (let w of tmp) { visited.add(w) set.delete(w) if (changeOneChar(w, endWord)) return len + 1 for (let word of wordList){ if (changeOneChar(w, word) && ! visited.has(word)){ set.add(word) } } } len++ } return 0 }; function changeOneChar(a, b) { let count = 0 for (let i = 0; i < a.length; i++) if (a[i] ! = b[i]) count++ return count == 1 }Copy the codeThe last
After writing down the questions of AC once, the results are obtained.
- Know the methodology, start a lot more relaxed.
- There must be a methodology for finding the wheel.
- Don’t be clever and use a few tricks. It’s a waste of time if you don’t think the right way.
- Don’t think about making your own wheels (especially algorithms), most of the problems of the predecessors must have better and more perfect solutions. Building your own wheel takes a lot of time, takes a lot of work and doesn’t make much sense.
- Look at the answer and do their own are two different things, to achieve their own hands will be.
- The reason why algorithms exist is to adapt to some scenarios and solve some kinds of problems. Select the right algorithm in the right scene can reflect the value of the algorithm, do not abuse the algorithm.
- It is not necessary to master all algorithms, but at least when you encounter problems, you can find the best algorithm to solve the problem. That is to know the existence and use of algorithms, as needed in-depth study.
In fact, it is very interesting to brush algorithm questions, and I plan to brush all the questions in the LeetCode question bank
PS: If there are any mistakes or improvements in this article and related projects, please report. Progress together ~