The owner of the building in a few months ago WXG, back and forth 3, 4, worthy of the wechat business group, or malicious attention to the algorithm, the outcome or hung. Write it down here. Keep up the good work.

A, the impression of several algorithm questions are as follows:

1. Implement binary tree mirroring (flipping)

function treeFun(root) {
  if (root === null) return null;
  function treeList(node) {
    let left = node.left;
    let right = node.right;
    node.left = right;
    node.right = left;
  }
  After the sequence traversal before / / | | sequence traversal
  treeFun(root);
  treeList(root.left);
  treeList(root.right);
  return root;
}
Copy the code

2. The string is transformed into an integer

let strToNumberFun = function (str) {
  let res = parseInt(str); // If the number cannot be converted, NAN is used
  let max = Math.pow(2.31);
  let min = Math.pow(-2.31);
  if (isNaN(res)) {
    return 0;
  } else if (res > max) {
    return max;
  } else if (res < min) {
    return min;
  } else {
    returnres; }};Copy the code

3. Find the primes in the array

/ / to omit
Copy the code

4. Write a quicksort

function quickArrFun(arr) {
  let leng = arr.length;
  if (leng === 1) return arr;
  let quick = arr[0];
  let left = [],
    right = [],
    res = [];
  for (let i = 1; i < leng; i++) {
    if (quick < arr[i]) right.push(arr[i]);
    if (quick > arr[i]) left.push(arr[i]);
  }
  res = [...quickArrFun(left), quick, ...quickArrFun(right)];
  return res;
}
Copy the code

Other js basic correlation is not a list…

Ii. The following are the algorithms reviewed by myself:

1. Binary tree

/* binary tree start*/
function treeFun(root) {
  if (root === null) return null;
  let temp = root.left;
  root.left = root.right;
  root.right = temp;
  treeFun(root.left);
  treeFun(root.right);
}

// Order traversal in binary tree
function treeFunMid(root) {
  let result = [];
  var inorderTraversal = (node) = > {
    if (node) {
      // Iterate through the left subtree
      inorderTraversal(node.left);
      // The root node
      result.push(node.val);
      // Walk through the right subtree for the last timeinorderTraversal(node.right); }}; inorderTraversal(root);return result;
}

const inorderTraversal = (root) = > {
  let list = [];
  let stack = [];
  let node = root;

  while (node || stack.length) {
    // Iterate over the left subtree
    while (node) {
      stack.push(node);
      node = node.left;
    }

    node = stack.pop();
    list.push(node.val);
    node = node.right;
  }
  return list;
};

var inorderTraversal = function (root) {
  if (root === null) return [];
  let stack = [root]; // Use the stack to traverse the tree
  let res = [];
  while (stack.length) {
    let current = stack.pop();
    if (current === null) continue;
    if(! current.visited) {// The node is not accessed
      current.visited = true; // Sets a variable to indicate whether the node is accessed
      stack.push(current.right, current, current.left); // All entries are pushed in the order of right root, left root, and continue
    } else {
      // The node has been accessed, outputs the value, traverses the next node in the stackres.push(current.val); }}return res;
};

// The KTH largest node of the binary tree
function treeKFun(root, k) {
  if (root === null) return null;
  let res = [];
  function treeNode(node) {
    treeNode(node.left);
    res.push(node.val);
    treeNode(node.right);
  }
  treeNode(root);
  return res[res.length - k];
}

/* binary tree end*/
Copy the code

2, sorting,

/ * start * /

// Bubble sort
function arrFun(arr) {
  let leng = arr.length;
  if (leng === 1) return arr;
  for (let i = 0; i < leng; i++) {
    for (let j = i + 1; j < leng; j++) {
      if (arr[i] > arr[j]) {
        lettemp = arr[j]; arr[i] = temp; arr[j] = arr[i]; }}}return arr;
}

// Select sort
function arrSelectFun(arr) {
  let leng = arr.length;
  if (leng === 1) return arr;
  for (let i = 0; i < leng; i++) {
    let mix = i;
    for (let j = i + 1; j < leng; j++) {
      if (arr[mix] > arr[j]) {
        mix = j;
      }
      lettemp = arr[i]; arr[i] = arr[mix]; arr[mix] = temp; }}return arr;
}

// Quicksort
function quickArrFun(arr) {
  let leng = arr.length;
  if (leng === 1) return arr;
  let quick = arr[0];
  let left = [],
    right = [],
    res = [];
  for (let i = 1; i < leng; i++) {
    if (quick < arr[i]) right.push(arr[i]);
    if (quick > arr[i]) left.push(arr[i]);
  }
  res = [...quickArrFun(left), quick, ...quickArrFun(right)];
  return res;
}

/ * sort end * /
Copy the code

3. Related to LeetCode

/*LeetCode start*/

// merge two ordered arrays
/ * input: nums1 =,2,3,0,0,0 [1], m = 3 nums2 = [6] 2, n = 3 output: * /,2,2,3,5,6 [1]
function concactArrFun(nums1, m, nums2, n) { nums1.splice(m, n, ... nums2); nums1.sort((a, b) = > {
    a - b;
  });
  return nums1;
}

// leetcode415 adds the string
/* Given two non-negative integers num1 and num2 in the form of strings, compute their sum. Example: "111" + "2222" = "2333" */

function addStringFun(num1, num2) {
  let result = ' ';
  let temp = 0;
  let arr1 = num1.splice(' ');
  let arr2 = num2.splice(' ');
  while (arr1.length || arr2.length || temp) {
    temp += ~~arr1.pop() + ~~arr2.pop();
    result = (temp % 10) + result;
    temp = ~~(result / 10);
  }
  return result.replace(/ ^ 0 + /.' ');
}

// Tencent &leetcode43: string multiplication
/* Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, whose product is also represented as strings. Example 1: Input num1 = "2", num2 = "3" Output: "6" Example 2: Input num1 = "123", num2 = "456" Output: "56088" */
function stringMultiply(num1, num2) {
  let result = 0;
  let temp = 0;
  let arr1 = num2.splice(' ');
  while (arr1.length) {
    result += ~~num1 * ~~arr1.pop() * factorial(temp);
    temp += 1;
  }
  function factorial(n) {
    if (n === 0) return 1;
    return 10 * factorial(n - 1);
  }
  return result;
}

// 5. The longest substring leetcode
var longestPalindrome = function (s) {
  if (s.length < 2) {
    return s;
  }
  let res = ' ';
  for (let i = 0; i < s.length; i++) {
    // The length of the substring is odd
    helper(i, i);
    // The length of the substring is even
    helper(i, i + 1);
  }

  function helper(m, n) {
    while (m >= 0 && n < s.length && s[m] == s[n]) {
      m--;
      n++;
    }
    // Notice that the values of m and n are exactly at the moment when the loop condition is not satisfied
    // The distance between m and n is n-m+1, but the distance between m+1 and n-1 should be n-m-1
    if (n - m - 1 > res.length) {
      // Slice also takes the interval m+1,n-1
      res = s.slice(m + 1, n); }}return res;
};
console.log(longestPalindrome('asdasddsadfg'));

Given a string, your task is to calculate how many substrings there are in the string. Substrings with different starting or ending positions are treated as different substrings, even if they are composed of the same characters. Example 1: Input: "ABC" Output: 3 Description: Three callback substrings: "A "," B ", "C" Example 2: Input: "AAA" Output: 6 Description: Six callback substrings: "A "," A ", "AA "," AA ", "AAA" */

// Unpack
function backStringFun(str) {
  let count = 0;
  let leng = str.length;
  for (let i = 0; i < leng; i++) {
    for (let j = i; j < leng; j++) {
      if (addFun(str.substring(i, j + 1))) { count++; }}}function addFun(res) {
    let i = 0,
      j = res.length - 1;
    while (i < j) {
      if(res[i] ! = s[j])return false;
      i++;
      j--;
    }
    return true; }}Finding two / * is ordinal group median https://github.com/sisterAn/JavaScript-Algorithms/issues/162 * /
const arr1 = [1.2.10];
const arr2 = [2.5.7.8];

function findMiddleNumber(arr1, arr2) {
  // error tolerance
  if(! arr1.length && ! arr2.length)return null;
  // merge and sort
  const total = [...arr1, ...arr2].sort((a, b) = > a - b);
  // Median index
  let midIndex = (total.length - 1) / 2;

  / / two
  if (String(midIndex).includes('. ')) {
    const left = parseInt(midIndex);
    const right = parseInt(midIndex) + 1;
    const midNumber = (total[left] + total[right]) / 2;
    return midNumber.toFixed(5);
  } else {
    / / a
    return total[midIndex].toFixed(5); }}console.log(findMiddleNumber(arr1, arr2));

/* const arr = [101,19,12,51,32,7,103,8]; Problem 1: Find the number of continuous maximum ascending */ problem 2: Find the number of discontinuous maximum ascending */

const findLengthOfLCIS = (nums) = > {
  if (nums.length <= 1) return nums.length;
  let max = 1,
    count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      count += 1;
    } else {
      count = 1;
    }
    max = Math.max(max, count);
  }
  return max;
};

function queryFn(arr) {
  if(! arr.length)return 0;
  let res = 1;
  let num = 0;
  let lastVal = 0;
  for (let i = 0, len = arr.length - 1; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[j] > lastVal) {
        num++;
        lastVal = arr[j];
      }
    }
    res = Math.max(res, num);
  }
  return res;
}

/ * after rain https://github.com/sisterAn/JavaScript-Algorithms/issues/122 n nonnegative integer in each given width of 1 column height map, calculate according to the arrangement of pillars, how much rain can meet after the rain. Example 1: input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] The height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case six units of rain can be caught (the blue parts are rain). * /
/ / double pointer
function trap(height) {
  let total = 0;
  let left = 0,
    right = height.length - 1,
    leftMax = 0,
    rightMax = 0;
  while (left <= right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (leftMax < rightMax) {
      total += leftMax - height[left];
      left++;
    } else{ total += rightMax - height[right]; right--; }}return total;
}

/*LeetCode end*/
Copy the code

4, list

/ * list start * /
/* leetcode 19. Given a list, delete the NTH node from the bottom of the list and return the head of the list. Advanced: Can you try using a scan implementation? Example 1: input: head = [1, 2, 3, 4, 5], n = 2 output: * /,2,3,5 [1]
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
  * @param {number} n
  * @return {ListNode}* /
var removeNthFromEnd = function (head, n) {
  var ret = new ListNode(0, head);
  var slow = (fast = ret);
  while (n--) {
    fast = fast.next;
  }
  if(! fast)return ret.next;
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return ret;
};

// leetcode024. 'reverse linked list'
/* input: head = [1,2,3,4,5] output: [5,4,3, 1] */
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
  * @return {ListNode}* /
var reverseList = function (head) {
  if(! head || ! head.next)return head;
  let temp = null,
    pre = null,
    cur = head;
  while (cur) {
    temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }
  // temp = cur = null;
  return pre;
};
/ * list end * /
Copy the code