JZ1. Lookup of two-dimensional arrays

  • In a two-dimensional array (each one-dimensional array is the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.
  • Input: 7, [,2,8,9 [1], [2,4,9,12],,7,10,13 [4], [6,8,11,15]]
  • Output: true,
function Find(target, array){
    const n = array.length // Store the length of a two-dimensional array
    const m = array[0].length // The length of each one-dimensional array in a two-dimensional array
    let row = 0, col = m - 1
    
    if (n == 0 || m == 0) return false
    
    while (row <= n - 1 && col >= 0) {
        if (target < array[row][col]) { col -= 1 }
        else if (target > array[row][col]) { row += 1 }
        else if (target == array[row][col]) { return true}}return false
}
Copy the code

JZ2. Replace Spaces

  • Description: Replace each space in string S with “%20”
  • Enter: s = “We are happy.”
  • Output: “We % 20 are % 20 happy.”
// Method 1: regular
var replaceSpaceFn1 = function (s) {
     return s.replace(/\s/g.'% 20');
};

// Method 2: loop
var replaceSpaceFn2 = function (s) {
    let sb = ' '
    let c = ' '
    let len = s.length
    for (let i = 0; i < len; i++) {
        c = s.charAt(i);
        if (c == ' ') sb += "% 20";
        else sb += c
    }
    return sb
};
Copy the code

JZ3. Print the linked list from end to end

  • Enter a linked list and return an array in the order from end to end
  • Enter: head = [1,3,2]
  • Output:,3,1 [2]
/*function ListNode(x){ this.val = x; this.next = null; } * /
function printListFromTailToHead(head){
    var arr = []
    while(head! =null){
        arr.push(head.val)
        head = head.next
    }
    return arr.reverse()
}
Copy the code

JZ4. Rebuild the binary tree

  • Description: Input the results of the preceding and middle order traversal of a binary tree, please reconstruct the binary tree.
  • Input:,2,3,4,5,6,7 [1], [3,2,4,1,6,5,7]
  • Output:,2,5,3,4,6,7 {1}
/* Algorithm idea: determine the root node (root) by [preorder traversal list] split the nodes of [middle order traversal list] into [left branch node] and [right branch node] recursively find the root node in [left branch node] and the root node in [right branch node] */
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
/ / recursion
function reConstructBinaryTree(pre, vin){
    if(pre.length == 0||vin.length==0)return null
    var index = vin.indexOf(pre[0])
    var left = vin.slice(0,index)
    var right = vin.slice(index+1)
    return {
        val:pre[0].left:reConstructBinaryTree(pre.slice(1,index+1),left),
        right:reConstructBinaryTree(pre.slice(index+1),right)
    }
}
Copy the code

JZ5. Implement queues with two stacks

  • Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)
  • Input:
    • [“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
    • [[], [3], [], []]
  • Output: [null, null, 3-1]
var CQueue = function () {
    this.stack1 = []
    this.stack2 = []
};

/ * * *@param {number} value
 * @return {void}* /
CQueue.prototype.appendTail = function (value) {
    this.stack1.push(value) / / into the stack
};

/ * * *@return {number}* /
CQueue.prototype.deleteHead = function () {
    if (!this.stack2.length) {
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop()) / / flare stack}}return this.stack2.pop() || -1
};
Copy the code

Jz6. rotate the smallest number in the array

  • Input a rotation of a non-decrement array, output the smallest element of the rotation array. NOTE: All elements given are greater than 0. If array size is 0, return 0.
  • Input:,4,5,1,2 [3]
  • Output: 1.
function minNumberInRotateArray(rotateArray){
    if(! rotateArray){return 0
    }
    / / sorting
    rotateArray.sort(function(a,b){
        if(a<b) return -1;
        else return 1;
    });
    return rotateArray[0];
}

Copy the code

JZ7. Fibonacci series

F (0) = 0, F (1) = 1, F (N) = F (N – 1) + F (N – 2), where N > 1, the N 39 or less

  • Input: 4
  • Output: 3
function Fibonacci(n){
    if(n == 0)return 0
    if(n == 1)return 1
    let first = 1,second = 0,cur = 0
    for(let i = 1; i<n; i++){ cur=first+second second = first first = cur }return cur
}
Copy the code

JZ8. Dance steps

A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps.

  • Input: 7
  • Output: 21
function jumpFloor(number){
    if (number < 2) return 1
    let a = 1, b = 1
    for (let i = 2; i <= number; i++) {
        a = a + b
        b = a - b
        a = a >= 1000000007 ? (a - 1000000007) : a;
    }
    return a
}
Copy the code