Published on

Algorithm Fundamentals

Authors

This article is not about algorithm basics in the traditional sense, but rather some points I've summarized after learning algorithms for a while that I think are quite important for beginners.

Intervals

The concept of intervals is actually very common in real life:

  • How many floors do you need to climb from the 7th to the 18th floor?
  • How many days are there from January 10th to January 30th?
  • How many days are there between January 10th and January 30th?

With the concept of intervals, these can be easily solved:

  • (7, 18]: From 7th to 18th floor, excluding 7th but including 18th, then you need to climb 18 - 7 = 11 floors.
  • [10, 30]: Including both 10th and 30th, then 30 - 10 + 1 = 21 days
  • (10, 30): Excluding both 10th and 30th, then 30 - 10 - 1 = 19 days

Those who are good at summarizing have noticed: closed intervals use [], open intervals use (), and the corresponding calculation formulas are:

  • [i, j]: j - i + 1
  • (i, j): j - i - 1
  • (i, j]: j - i

Don't underestimate this knowledge point - if you're not familiar with the concept of intervals, binary search can be a nightmare🥲

If you agree, please give me a 👍 at the bottom of the article.

Traversal

Let's look at the role of intervals in traversal. Here's the result:

For loop invariants, if it's a closed interval then include, if it's an open interval then exclude.

// [2, 28]
for (let i = 2; i <= 28; ++i) {}
// [2, 28)
for (let i = 2; i < 28; ++i) {}

There's not much to say about one-dimensional array traversal. Let's mainly look at two-dimensional array traversal. In dynamic programming, the direction and method of traversal have certain techniques.

Spiral Traversal

Spiral traversal is a bit similar to BFS, requiring while and for loops to work together, along with four boundaries for contraction.

let count = 0
let top = 0,
  left = 0,
  bottom = m - 1,
  right = n - 1
while (count < 25) {
  // Traverse top row interval [left, right]
  for (let i = left; i <= right; ++i) {
    console.log(Arr[top][i])
    count++
  }
  top++
  // Traverse right column [top, bottom]
  for (let i = top; i <= bottom; ++i) {
    console.log(Arr[i][right])
    count++
  }
  right--
  // Traverse bottom row in reverse [left, right]
  for (let i = right; i >= left; --i) {
    console.log(Arr[bottom][i])
    count++
  }
  bottom--
  // Traverse left column in reverse [top, bottom]
  for (let i = bottom; i >= top; --i) {
    console.log(Arr[i][left])
    count++
  }
  left++
}

Diagonal Traversal

As shown in the figure, how do we traverse in this order?

First, let's understand:

  • Main diagonal: from top-left to bottom-right, coordinates i === j; property: i - j is constant
  • Secondary diagonal: from bottom-left to top-right, coordinates i + j === len - 1; property: i + j is constant

And this constant value happens to be equal to the index of diagonal line l in diagonal traversal. (My personal summary using mathematical induction😂)

Upper
// Array size is 5 * 5, diagonal indices are [1, 4], so outer for loop traverses diagonals
for (let l = 1; l < len; ++l) {
  for (let i = 0; i < len - l; ++i) { // i interval is [0, len - l]
    const j = l + i // Main diagonal i - j is constant
    console.log(arr[i][j])
  }
}
Lower
for(let l = 1; l < len; ++l) {
  for(let j = 0; j < len - l; ++j) { // Just swap i and j positions
    const i = l + j
    console.log(arr[i][j])
  }
}

The secondary diagonal is left for you🐶 (Of course, I don't recommend memorizing by rote, you should master the basic principles, observe and think more.)

Recursion

Recursion is calling yourself, often used to handle complex problems in a more intuitive and effective way. For conventional recursion teaching, I suggest searching Google directly. Here I'll record some points I think are important for understanding recursion:

  • Recursion must have termination conditions to prevent infinite loops
  • Pay attention to return during recursion, be mindful of the output parameters
  • Make good use of recursion function input parameters to save and pass information

Recursive Order

Many recursion tutorials don't cover recursive order, but it's actually very important for understanding recursion.

/**
 *        1
 *       / \
 *      2   3
 *     / \ / \
 *    4  5 6  7
 *
 * The go function below performs recursive order traversal of this binary tree
 * Each node will be processed 3 times, at positions 1, 2, 3; actual traversal order:
 *
 * 1(1), 2(1), 4(1), 4(2), 4(3),
 * 2(2), 5(1), 5(2), 5(3), 2(3),
 * 1(2), 3(1), 6(1), 6(2), 6(3),
 * 3(2), 7(1), 7(2), 7(3), 3(3), 1(3)
 *
 * Pre-order (root-left-right(1)) result: 1, 2, 4, 5, 3, 6, 7
 * In-order (left-root-right(2)) result: 4, 2, 5, 1, 6, 3, 7
 * Post-order (left-right-root(3)) result: 4, 5, 2, 6, 7, 3, 1
 */
funcion go(head) {
  if(head == null) return;
  // 1 Pre-order
  go(head.left);
  // 2 In-order
  go(head.right);
  // 3 Post-order
}

We often use more recursion with just pre-order + post-order, and the characteristics of post-order are very important - it can access information returned during the previous call stack's return phase.

Let's look at how to solve lc.206 Reverse Linked List (easy) using recursion:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (head === null || head.next == null) return head
  const newHead = reverseList(head.next)
  head.next.next = head
  head = null
  return newHead
}

Just 5 lines of code, but it's really hard for beginners to understand😂. Why does return newHead directly give the final result?

The return newHead in this recursion is below the recursive function, which is in the post-order position. Each return is the node pointer returned by the last round of recursive call stack, which is the pointer to the last node. In tree recursion, for example, when looking for a certain node, if found then return. For recursive calls in for loops, you need to handle them. The core pseudo-code is:

const find = () => {
  for (let i = 0; i < list; ++i) {
    if (find(list[i].children)) return true
  }
}

Finally, one very important point about recursion: never try to challenge recursion depth with your brain, don't get caught up in it, your brain will stack overflow💥~

Discuss on Twitter • View on GitHub

SHARE