1. 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.

The input

7, [,2,8,9 [1], [2,4,9,12],,7,10,13 [4], [6,8,11,15]]Copy the code

The return value

true
Copy the code

solution

while(line=readline()){
    var index=line.indexOf(",");
    var left=parseInt(line.substring(0,index));
    var right=JSON.parse(line.substring(index+1));
    print(Find(left,right));
}

function Find(target, array)
{
    // write code here
    var arr = array;
    for(var i=0; i<arr.length; i++){for(var j=0; j<arr[i].length; j++){if(arr[i][j] == target){
                return true; }}}return false;
}    

Copy the code

2. Implement a function that replaces each space in a string with %20. For example, if the string is “We Are Happy.”, the replacement string is “We%20Are%20Happy”.

solution

/ / the first
function replaceSpace(str) {
  let temp = []
  for (let i = 0; i<str.length; i++) {
    if (str[i] === ' ') {
        temp.push('% 20')}else {
        temp.push(str[i])
    }
  }
  return temp.join(' ')}/ / the second
function replaceSpace(str){
    // write code here
     return str.replace(/ /g."% 20");
}

Copy the code

3. Enter a linked list and return an ArrayList from end to end.

The input

,0,24,58 {67}Copy the code

The return value

[58,24,0,67]
Copy the code

solution


function printListFromTailToHead(head)
{
    var arrayList = [];
    var node = head;
    while(node){
        arrayList.unshift(node.val);
        node = node.next;
    }
    return arrayList;

}

Copy the code

4. Input the results of preorder traversal and middle order traversal of a binary tree, and reconstruct the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. For example, input preorder traversal sequence {1,2,4,7,3,5,6,8} and intermediate order traversal sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return.

The input

,2,3,4,5,6,7 [1], [3,2,4,1,6,5,7]Copy the code

The return value

,2,5,3,4,6,7 {1}Copy the code

solution


 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    // write code here
    // Implement recursion where preStart represents the sequence of the subscript position of the first node traversed first
    function rebuild(preStart, preEnd, vinStart, vinEnd) {
        let node = new TreeNode(pre[preStart])
        If there is only one node, return the node itself
        if ((preStart == preEnd) && (vinStart == vinEnd)) {
            return node
        }
        let index = vin.indexOf(pre[preStart]) // Find the root node of the tree
        let leftLen = index - vinStart // The left subtree length
        let leftPrend = preStart + leftLen // Select all nodes of the left subtree traversed first
        if (leftLen > 0) {
            // This is equivalent to traversing the left subtree of the left subtree. Therefore, the node at the beginning of the traversal should be added by one, and the node at the end of the traversal should be subtracted by one
            node.left = rebuild(preStart + 1, leftPrend, vinStart, index - 1)}if (leftLen < preEnd - preStart) {
            node.right = rebuild(leftPrend + 1, preEnd, index + 1, vinEnd)
        }
        return node
    }
    let head = rebuild(0, pre.length - 1.0, vin.length - 1)
    return head
}

Copy the code

5, use two stacks to implement a queue, complete the queue Push and Pop operations. Elements in the queue are of type int.

solution


let inStack = []
let outStack = []

function push(node)
{
    inStack.push(node)
}
function pop()
{
    // write code here
    if(! outStack.length){while(inStack.length){
            outStack.push(inStack.pop())
        }
    }
    
    return outStack.pop()
}

Copy the code

6. Moving the beginning elements of an array to the end of the array is called array rotation. Take a rotation of a non-decrement array and print the smallest element of the rotation array. NOTE: All elements given are greater than 0. If array size is 0, return 0.

The input

,4,5,1,2 [3]Copy the code

The return value

1
Copy the code

solution


while(line=readline()){
    let arr = JSON.parse(line);
    print(minNumberInRotateArray(arr));
}
function minNumberInRotateArray(rotateArray) {
    // write code here
    if(rotateArray.length===0)return 0
    let left = 0,right = rotateArray.length-1;
    if(rotateArray[left]<rotateArray[right]){
        return rotateArray[left];
    }
    let mid;
    while(left<right){
        if(left+1===right){
            return rotateArray[right];
        }
        mid = (left+right)>>1;
        if(rotateArray[left]<rotateArray[mid]){
            left = mid;
        }else if(rotateArray[left]>rotateArray[mid]){
            right = mid;
        }else{
            if(rotateArray[right]===rotateArray[mid]){
                return Math.min(... rotateArray.slice(left,right+1)) } left = mid; }}}Copy the code

Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence = Fibonacci sequence

N 39 or less

solution

function Fibonacci(n){
    let f=0,g=1;
    while(n--){
        f=g+f;
        g=f-g;
    }
    return f;
}

Copy the code

A frog can jump up 1 step at a time, can also jump up 2 steps. Find out how many ways the frog can jump up a n step (different order counts different results).

The input

1
Copy the code

The return value

1
Copy the code

The input

4
Copy the code

The return value

5
Copy the code

solution

function jumpFloor(number)
{
    // write code here
    if(number==1) return 1;
    if(number==2) return 2;
    var pre1=1,pre2=2,cur=0;
    for(var i=3; i<=number; i++){ cur = pre1+pre2; pre1 = pre2; pre2 = cur; }return cur;
}

Copy the code

9, abnormal jump steps: a frog can jump up 1 step at a time, can also jump up 2 steps… It can also jump up n levels. Find out how many ways the frog can jump up n steps.

The input

3
Copy the code

The return value

4
Copy the code

solution

function jumpFloorII(number)
{
    if(number == 1) return 1
    return jumpFloorII(number - 1) * 2 
}

Copy the code

10. Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array. The relative positions between odd and odd numbers and even and even numbers remain the same.

solution

function reOrderArray(array)
{
    // write code here
    var arr1 = [];
    var arr2 = [];
    array.forEach(function(item){
        if(item % 2= = =0){
            arr2.push(item);
        }else{ arr1.push(item); }})return arr1.concat(arr2)
}

Copy the code