Effective brackets

Power button link

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order.

  const left = ['('.'{'.'[']
  const map = {
    ') ': '('.'} ': '{'.'] ': '['
  }

  function isValid(str) {
    var arr = str.split(' ')
    var stack = []
    for (var i = 0; i < arr.length; i++) {
      var item = arr[i]
      if (stack.length === 0 && left.includes(item) === -1) {
        return false
      }
      if (left.includes(item)) {
        stack.push(item)
      } else {
        if(map[item] ! == stack.pop()) {return false}}}if (stack.length) {
      return false
    }
    return true
  }

  console.log(isValid("()"))//true
  console.log(isValid("[the] {} ()"))//true
  console.log(isValid("(]"))//false
  console.log(isValid("([]"))//false
  console.log(isValid("{[]}"))//true
Copy the code

palindrome

Power button link

Given an integer x, return true if x is a palindrome integer; Otherwise, return false.

Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

  var isPalindrome = function() {
    // Special case:
    // As mentioned above, x is not a palindrome when x < 0.
    // Similarly, if the last digit of a number is 0, in order to make the number palindrome,
    // The first digit should also be 0
    // Only 0 satisfies this property
    if (x < 0 || (x % 10= = =0&& x ! = =0)) {
        return false;
    }

    let revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x = Math.floor(x / 10);
    }

    // When the number length is odd, we can use revertedNumber/10 to remove the median number.
    // For example, at the end of the while loop we get x = 12, revertedNumber = 123,
    // Since the number in the middle does not affect the palindrome (it is always equal to itself), we can simply remove it.
    return x === revertedNumber || x === Math.floor(revertedNumber / 10);
};

Copy the code

Use higher order functions

var isPalindrome = function(x) { 
    if (x < 0 || (x % 10= = =0&& x ! = =0)) {
        return false;
    }
    return Array.from(String(x)).reverse().join(' ') = = =String(x) 
};
Copy the code

Merge sort linked lists

Power button link

Given an array of linked lists, each list is already sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

// Js does not have a linked list structure, so we need to build our own
// Array list
// list merge sort
// List results are displayed as arrays
function ListNode(val) {
    this.val = val;
    this.next = null;
}
// Array list function
function ListNode(val) {
  this.val = val;
  this.next = null;
}
// Array list function
function generateList(arr) {
  let fakeHead = new ListNode(0);
  let current = fakeHead;
  for (let index = 0; index < arr.length; index++) {
    current.next = { val: arr[index], next: null }
    current = current.next
  }
  return fakeHead.next
}
// List to array
function generateArray(list) {
  let res = [];
  while (list) {
    res.push(list.val);
    list = list.next
  }
  return res;
}
var mergeKLists = function (lists) {
  lists = lists.map(item= > generateList(item))
  var newList = new ListNode('head')
  var lastList = newList
  while (lists.length > 0) {
    var nullIndex = 0;
    let min = null
    for (let i = 0; i < lists.length; i++) {
      var item = lists[i]
      if (min === null) {
        min = item.val;
        nullIndex = i
        continue;
      }
      if (min > item.val) {
        min = item.val
        nullIndex = i

        continue;
      }
    }
    lastList.next = new ListNode(min)
    lastList = lastList.next
    lists[nullIndex] = lists[nullIndex].next
    if (lists[nullIndex] === null) {
      lists.splice(nullIndex, 1)}}return generateArray(newList.next)
}

var lists = [
  [1.3.5],
  [3.5.7],
  [1.2.3]]console.log(mergeKLists(lists))
/ / input [,3,5 [1], [3, 5, 7], [1, 2, 3]]
// Output [1, 1, 2, 3, 3, 3, 5, 5, 7]
Copy the code

Method 2

/ * * *@param {ListNode[]} lists
 * @return {ListNode}* /
var mergeKLists = function (lists) {
  // When an array is empty
  if(! lists.length) {return null;
  }
  // Merge two sorted lists
  const merge = (head1, head2) = > {
    let dummy = new ListNode(0);
    let cur = dummy;
    // New linked list, new value is small first pick whoever
    while (head1 && head2) {
      if (head1.val < head2.val) {
        cur.next = head1;
        head1 = head1.next;
      } else {
        cur.next = head2;
        head2 = head2.next;
      }
      cur = cur.next;
    }
    // If there is any left, connect the rest
    cur.next = head1 == null ? head2 : head1;
    return dummy.next;
  };
  const mergeLists = (lists, start, end) = > {
    if (start + 1 == end) {
      return lists[start];
    }
    // The input k sorted list can be divided into two parts, the first k/2 list and the last k/2 list
    // If the first and last k/2 lists are merged into two sorted lists, and the two sorted lists are merged, then all lists are merged
    let mid = (start + end) >> 1;
    let head1 = mergeLists(lists, start, mid);
    let head2 = mergeLists(lists, mid, end);
    return merge(head1, head2);
  };
  return mergeLists(lists, 0, lists.length);
};
Copy the code

Binary tree forward traversal

Power button link

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Input: root = [1,null,2,3] output: [1, 3]Copy the code
  • The recursive method
/** * 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) {
    let arr = []
    function qianxu(root){
        if(! root||! root.val)return
        arr.push(root.val)
        qianxu(root.left)
        qianxu(root.right)
    }
    qianxu(root)
    return arr
};
Copy the code
  • Iterative method
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
    const stack = [];
    const res = [];
    if (root) stack.push(root);
    while (stack.length) {
        const node = stack.pop();
        const left = node.left
        const right = node.right
        if(! node.left && ! node.right) { res.push(node.val);continue;
        }
        if (right) stack.push(node.right); / / right
        if (left) stack.push(node.left); / / left
        node.left = null
        node.right = null
        stack.push(node); / /
    };
    return res;
};

Copy the code