1. Fibonacci stack implementation

function fibStack (n) {
  let arr = [n]
  let val = 0
  while (arr.length) {
    let cur = arr.pop()
    if (cur === 1 || cur === 2) {
      val++
    }
    if (cur > 2) {
      arr.push(cur - 1, cur - 2)}}return val
}
Copy the code

2. The KMP algorithm

2.1 What is KMP

String match, gets substring index

2.2 Why Do I Not Perform the Rollback?

It doesn’t make sense if you go back and you can’t guarantee that everything matches, but if you go back and everything matches, you can definitely do that by moving j.

        i
a a a b c d e f g
  a a b d
        j
Copy the code
  • Everything j can trace back to is recorded
  • Next [j]] ensures that STR [0, next[j]] is matched, and next[j] ensures that the number of matches is maximum
2.3 When moving J, is it possible to match more without moving to Next?

Can’t be

Must first clear, must start from the head of the substring matching to be meaningful, moving to the next [j] position, assuming that some of the front element is matching (such as the following examples, at this time in front of 123 match), but at this point is meaningless, because at the end of the entire string must be started don’t match the right, There must be a mismatch after 123, and if everything after 123 matches, next[] must contain the corresponding traceback position

1 2 3 4 5 6 7 1 2 3 a b C d e f G H 1 2 3 4 5 6 7 1 2 3 a b D 1 2 3 4 5 6 7 1 2 3 a b DCopy the code
2.4 Implementation Code
// Get the next location to jump to
function getNext (ps) {
  var next = []
  next[0] = -1 // initialize to -1
  let j = 0
  let k = -1
  while (j < ps.length - 1) {
    if (k == -1 || ps[j] == ps[k]) {
      next[j + 1] = k + 1
      j++
      k++
    } else {
      // if ps[j] = next[k] and ps[k] = next[k]
      // Ps [j] == ps[k] next[j] == ps[k] next[j
      // If the first element is not equal, then k = next[k] will be equal to -1
      k = next[k]
    }
  }
  return next
}

// ts main string; Ps substring
function KMP (ts, ps) {
  let i = 0 // The main string position
  let j = 0 // The position of the pattern string
  let next = getNext(ps) // Next is only about ps
  while (i < ts.length && j < ps.length) {
    if (j == -1 || ts[i] == ps[j]) {
      // When j is -1, we move I, and of course j returns to 0
      i++
      j++
    } else {
      j = next[j] Ps [0] = ts[j] = ts[j]}}if (j == ps.length) {
    return i - j // returns the position of the first character in ps
  } else {
    return -1}}Copy the code

3. Spatial complexity of recursive algorithm

The spatial complexity of the recursive algorithm = the spatial complexity of each recursion * the depth of recursion

Each time a function is called, new content is pushed onto the stack. The amount of space required for a single recursion is the same, so it is O(1). If the recursion depth is N, the space complexity is O(n).

4. Cueing of middle order binary trees

// Cue binary tree
typedef struct ThreadNode {
	ElemType data;
	struct ThreadNode* lchild, * rchild; // 0 refers to the child. 1 refers to the precursor
	int ltag, rtag;
} ThreadNode, *ThreadTree;

void InThread(ThreadTree p, ThreadTree pre) {
	if(p ! =NULL) {
		InThread(p->lchild, pre); Serialize the left subtree recursively
	}
	if (p->lchild == NULL) {
		p->lchild = pre;
		p->ltag = 1;
	}
	if(pre ! =NULL && pre->rchild == NULL) {
		pre->rchild = p; // Establish the relationship between the precursor nodes
		pre->rtag = 1;
	}
	pre = p;
	InThread(p->rchild, pre); Serialize the right subtree recursively
}

void CreateInThread(ThreadTree T) {
	ThreadTree pre = NULL;
	if(T ! =NULL) {
		InThread(T, pre);
		pre->rchild = NULL; // Process the last node of the traversal
		pre->rtag = 1; }}Copy the code

The overall train of thought

  1. Serialized recursively, the leftmost one must be at the front of the sequence, so it confirms the relationship with Pre first. Here the prodrome and the retrodrome refer to the relation between the middle order and the diachronic correspondence;
  2. When the left subtree is NULL, the current node is set to P and the relationship with Pre is determined.
  3. Then set the current p to pre and serialize the right subtree. Since it is middle-order, the current p must be the precursor of the right subtree.
  4. Subtrees and clues are distinguished by Rtag and Ltag

5. Prove the node with serial number I of complete binary tree, and its subtree nodes are 2i and 2i+1 respectively