LeetCode解题思路,JavaScript初学者必要理解13个小本领

By admin in 4858美高梅 on 2019年9月23日

JavaScript 面试中常见算法难题详解

2017/02/20 · JavaScript
· 1 评论 ·
算法

原稿出处:
王下邀月熊_Chevalier   

JavaScript
面试中常见算法难题详解 翻译自
Interview Algorithm Questions in Javascript()
{…}
从属于我的 Web
前端入门与工程进行。下文提到的非常多标题从算法角度并不必供给么困难,但是用
JavaScript 内置的 API 来达成大概须要一番勘测的。

1# Leetcode 367. Valid Perfect Square

Given a positive integer num, write a function which returns True if
num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:
Input: 16
Returns: True

Example 2:
Input: 14
Returns: False

思路:
以256举例
mid = 128 => 128 * 128 > 256 => end = mid = 128;
mid = 64 => 64 * 64 > 256 => end = mid = 64;
mid = 32 => 32 * 32 > 256 => end = mid = 32;
mid = 16 => 16 * 16 = 256 => return true;

以15举例
mid = 8 => 8 * 8 > 15 => end = mid = 8;
mid = 4 => 4 * 4 > 15 => end = mid = 4;
mid = 2 => 2 * 2 < 15 => start = mid = 2; end = 4;
mid = 3 => 3 * 3 < 15 => start = mid = 3; end = 4;
start + 1 = 3 + 1 = 4 = end, while loop end;
start = 3, 3 * 3 != 15 and end = 4, 4 * 4 != 15;
so return false;

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) {
            return false;
        }
        long start = 1;
        long end = num;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (mid * mid == num) {
                return true;
            } else if (mid * mid < num) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (start * start == num || end * end == num) {
            return true;
        }
        return false;
    }
}

做的片段题的解题思路

因为超越二分一的浏览器都和它非凡,你可以在这几个浏览器中采用它。JavaScript被接受的一对一快,因为它是这么的简约,况且使用限制特别广泛。大多技术员过去时断时续以为JavaScript是一门“玩具语言”,不过,AJAX步向商场后表现出了一心相反的一端,它让JavaScript表现出了完全两样的力量和法力。
出于这么些发明的产出,技士以后早已得以成立带有桌面应用程序效果的Web应用程序了,那是很有利润的,因为数量能够越来越快地改成。那是一些娇小玲珑才具,它们能够协理初学者越来越好地行使JavaScript。JavaScript的行使限制十分常见,况且还应该有那样多的风格,所以它能够有为数十分的多的手艺。别的,就算它相当多的编制程序方法,但是自身只选择了十三个才能,笔者认为这一个本领对初学者明白JavaScript来讲是很好的的源点。
1,在多少个数组的末段增添多个要素
其一本领可以让你使用Length属性在多少个数组的末段增多二个要素,因为Length属性比数组的末梢多少个成分的下标多1。那些办法和“push”方法是平等的。举例:

JavaScript Specification

2# Leetcode 270 Closest Binary Search Tree Value

Product of Array Except Self

除自己之外的数组之积
Given an array of n integers where n > 1, nums, return an array
output such that output[i] is equal to the product of all the elements
of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].

解题思路:拆分法
[A_234 , A_134 , A_124 , A_123 ]=
[1 , A_1 , A_12 , A_123 ]*
[A_234 , A_34 , A_4 , 1 ]

/**
 * Created by Administrator on 2017/5/8.
 */
public class LeetCode {

    public static void main(String[] args) {
        // int [] nums={5, 7, 1, 8,3, 10};  //测试
        int[] nums = {1, 3, 5, 6};
        int k = 5;
        int [] res = productExceptSelf(nums);
        for (int i=0;i<res.length;i++) {
            System.out.print(res[i]+" ");
        }
    }

    public static int[] productExceptSelf(int[] nums) {
        final int [] result = new int [nums.length];
        final int [] right = new int [nums.length];
        final int [] left = new int [nums.length];
        left[0]=1;
        for(int i=1;i<nums.length;i++){
            left[i]=left[i-1]*nums[i-1];
        }
        right[nums.length-1]=1;
        for(int i=nums.length-2;i>=0;i--){
            right[i]=right[i+1]*nums[i+1];
        }

        for (int i=0;i<nums.length;i++){
            result[i]=right[i]*left[i];
        }
        return  result;
    }
}

复制代码 代码如下:

解说下 JavaScript 中的变量升高

所谓提高,顾名思义正是 JavaScript
会将具备的扬言升高到当下功能域的最上端。那也就表示我们得以在有个别变量证明前就动用该变量,可是固然如此
JavaScript 会将宣示进步到最上端,然而并不会进行真的开始化进度。

3# Leetcode 167 Two Sum II – Input array is sorted

/** 
 *  Method one: Two points 一刷
 *    时间复杂度为O(n), 空间复杂度为O(1)。
 */
public int[] twoSum(int[] numbers, int target) {
    int start = 0;
    int end = numbers.length - 1;
    while (start < end) {
        if (numbers[start] + numbers[end] < target) {
            start ++;
        }
        else if(numbers[start] + numbers[end] > target) {
            end --;
        }
        else {
            break;
        }
    }
    return new int[]{start + 1, end + 1};
}

/**
 *     Method 2: Binary Search 一刷
 *     时间复杂度为O(logn), 空间复杂度为O(1)。
 */
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = {0,0};
        int index1 = 0;
        int index2 = 0;

        for(int i = 0; i < numbers.length - 1; i++ ){
            index1 = i + 1;
            if(numbers[i] > target) {
                return result;
            }

            int gap = target - numbers[i];
            int start = i + 1;
            int end = numbers.length - 1;

            while(start + 1 < end){
                int mid = start + (end - start) / 2;
                if(numbers[mid] == gap) {
                    index2 = mid + 1;
                    result[0] = index1;
                    result[1] = index2;
                    return result;
                }
                if (numbers[mid] > gap) {
                    end = mid;
                }
                if (numbers[mid] < gap) {
                    start = mid;
                }
            }
            if (numbers[start] == gap) {
                result[0] = index1;
                result[1] = start + 1;
            }
            if (numbers[end] == gap) {
                result[0] = index1;
                result[1] = end + 1;
            }
        }
       return result;
    }
}

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of
length 3 exists or not in the array.

Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k
≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space
complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.
用整数最大值去比较,x1记录第一个数,x2记录第二大的数,当出现第三大的数,则return true。

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int x1=Integer.MAX_VALUE;
        int x2=Integer.MAX_VALUE;

        for(int x: nums){
            if(x<=x1) x1=x;
            else if(x<=x2) x2=x;
            else return true;
        }
        return false;
    }
}

var myArray = [];
myArray[myArray.length] = ‘New Element’;

阐述下 use strict; 的作用

use strict; 断章取义也正是 JavaScript
会在所谓严谨形式下实践,其贰个至关心重视要的优势在于能够强制开荒者制止使用未注脚的变量。对于老版本的浏览器照旧实行引擎则会自行忽略该指令。

JavaScript

// Example of strict mode “use strict”; catchThemAll(); function
catchThemAll() { x = 3.14; // Error will be thrown return x * x; }

1
2
3
4
5
6
7
8
// Example of strict mode
"use strict";
 
catchThemAll();
function catchThemAll() {
  x = 3.14; // Error will be thrown
  return x * x;
}

4# Leetcode 441. Arranging Coins

You have a total of n coins that you want to form in a staircase
shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be
formed.

n is a non-negative integer and fits within the range of a 32-bit
signed integer.

Example 1: n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.

Example 2: n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

思路:

1 + 2 + 3 + … + k <= n
=>
(k * ( k + 1)) / 2 <= n

public class Solution {
    public int arrangeCoins(int n) {
        int start = 0;
        int end = n;
        int mid = 0;
        while (start <= end){
            mid = start + (end - start) / 2 ;
            if ((0.5 * mid * mid + 0.5 * mid ) <= n){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        return start - 1;
    }
}

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are
two distinct indices i and j in the array such that nums[i] =
nums[j] and the absolute difference between i and j is at most k.

维护一个HashMap,key为整数,value为下标,将数组中的元素不断添加到这个Hashmap中,遇到重复时,计算下标距离;
用Integer.MAX_VALUE 设置为比较的初始值;
学会用HashMap是非常关键的。

public class LeetCode {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 1,6};
        int k=3;
        System.out.print(containsNearbyDuplicate(nums,k));
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        final Map<Integer,Integer> map = new HashMap<>();
        int min=Integer.MAX_VALUE;

        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                final int preIndex=map.get(nums[i]);
                final int gap = i-preIndex;
                min = Math.min(min,gap);
            }
            map.put(nums[i],i);
        }
        return min<=k;
    }
}

2,调治一个数组的长度
Length属性不是只读的,所以您能够设置Length属性的值。并且,你能够运用它增大或裁减数组的长短。举例:

批注下什么是 伊夫nt Bubbling 以及哪些幸免

伊夫nt Bubbling
即指某些事件不独有会接触当前成分,还有恐怕会以嵌套顺序传递到父成分中。直观来说便是对此有些子成分的点击事件同样会被父成分的点击事件管理器捕获。防止Event Bubbling 的不二秘诀得以使用event.stopPropagation() 可能 IE 9
以下使用event.cancelBubble

5# Leetcode 35. Search Insert Position

Given a sorted array and a target value, return the index if the
target is found. If not, return the index where it would be if it were
inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (nums[start] >= target) {
            return start;
        }
        else if (nums[end] >= target) {
            return end;
        }
        else {
            return end + 1;
        }
    }
}

Add Two Numbers

You are given two non-empty linked lists representing two non-negative
integers. The digits are stored in reverse order and each of their nodes
contain a single digit. Add the two numbers and return it as a linked
list.

You may assume the two numbers do not contain any leading zero, except
the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
主要学习怎么创建链表,怎么定义链表

public class LeetCode {
    public static void main(String[] args) {
        int[] inputl1=new int[]{2,4,3};
        int[] inputl2=new int[]{5,6,4};
        ListNode l1=buildListNode(inputl1);
        ListNode l2=buildListNode(inputl2);
        ListNode listNode =addTwoNumbers(l1,l2);
        while(listNode!=null){
            System.out.println("val "+listNode.val);
            listNode=listNode.next;
        }
    }
    //定义链表
   public static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }
    //创建链表
    private static ListNode buildListNode(int[] input){
        ListNode first = null,last = null,newNode;
        int num;
        if(input.length>0){
            for(int i=0;i<input.length;i++){
                newNode=new ListNode(input[i]);
                newNode.next=null;
                if(first==null){
                    first=newNode;
                    last=newNode;
                }
                else{
                    last.next=newNode;
                    last=newNode;
                }
            }
        }
        return first;
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
        public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           ListNode dummy =new ListNode(-1);
           int carry = 0;
           ListNode prev = dummy;
           for(ListNode pa=l1 ,  pb=l2 ; pa!=null || pb!=null ;
            pa=pa==null?null : pa.next,
            pb=pb==null ? null : pb.next,
            prev=prev.next){
               final int ai=pa==null?0:pa.val;
               final int bi=pb==null?0:pb.val;
               final int value=(ai+bi+carry)%10;
               carry=(ai+bi+carry)/10;
               prev.next=new ListNode (value);
            }

            if(carry>0)
                prev.next=new ListNode (carry);
            return dummy.next;
    }
}

复制代码 代码如下:

== 与 === 的分裂是怎么

=== 也等于所谓的从严比较,关键的分别在于===
会同期相比较类型与值,实际不是仅比较值。

JavaScript

// Example of comparators 0 == false; // true 0 === false; // false 2 ==
‘2’; // true 2 === ‘2’; // false

1
2
3
4
5
6
// Example of comparators
0 == false; // true
0 === false; // false
 
2 == ‘2’; // true
2 === ‘2’; // false

6# Leetcode 374. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher
or lower.

You call a pre-defined API guess(int num) which returns 3 possible
results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!

Example:
n = 10, I pick 6.
Return 6.

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1, end = n;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(guess(mid) == 0) {
                return mid;
            } else if(guess(mid) == 1) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if(guess(start) == 1) {
            return end;
        }
        return start;
    }
}

Evaluate Reverse Polish Notation

算算逆波兰共和国表明式(又叫后缀表明式)的值

” 2 ”,” 1 ”,” + ”, ”3”, ”* ” –>(2+1)*3–>9

用仓库境遇运算符则把后面五个拿出去运算

public class Main {
    public static void main(String[] args) {
       String []tokens={"2", "1", "+", "3", "*"};
        System.out.print(evalRPN(tokens));
    }

    public static int evalRPN(String [] tokens){
        Stack<String> s = new Stack<>();
        if(tokens.length==1){
            return Integer.parseInt(tokens[0]);
        }
        for(String token:tokens){
            if(!isOperator(token)){
                s.push(token);
            }else {
                int y=Integer.parseInt(s.pop());
                int x=Integer.parseInt(s.pop());
                switch (token.charAt(0)){
                    case '+':x+=y;break;
                    case '-':x-=y;break;
                    case '*':x*=y;break;
                    case '/':x/=y;break;
                }
                s.push(String.valueOf(x));
            }
        }
        return Integer.parseInt(s.peek());
    }

    private static boolean isOperator(final String op){
        return op.length() == 1 && OPS.indexOf(op)!=-1;
    }

    private static String OPS = new String("+-*/");
}

var myArray = [1,2,3];
myArray.length // 3
myArray.length = 2; //Delete the last element
myArray.length = 20 // add 18 elements to the array; the elements have
the undefined value.

解释下 null 与 undefined 的区别

JavaScript 中,null 是多个可以被分配的值,设置为 null
的变量意味着其无值。而 undefined
则代表着某些变量即使声称理解则未有实行过任何赋值。

7# Leetcode 69. Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

public class Solution {
    public int mySqrt(int x) {
        long start = 1;
        long end = x;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if(mid * mid <= x) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if(end * end <= x) {
            return (int)end;
        }
        return (int)start;
    }
}

3,使用“!!”把自由数据类型调换到Boolean
其一技艺能够令你使用“!!”把自由数据类型(举个例子string,
number或integer)转换来Boolean。举例:

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

在类承袭中,类是不可变的,分化的语言中对于多接二连三的支撑也不一样等,有个别语言中还扶助接口、final、abstract
的概念。而原型承继则更上一层楼灵活,原型本人是足以可变的,並且对象恐怕继续自八个原型。

8# Leetcode 278. First Bad Version

You are a product manager and currently leading a team to develop a
new product. Unfortunately, the latest version of your product fails
the quality check. Since each version is developed based on the
previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out
the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return
whether version is bad. Implement a function to find the first bad
version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if(isBadVersion(start)) {
            return start;
        }
        return end;
    }
}

复制代码 代码如下:

数组

9# Leetcode 475. Heaters

Winter is coming! Your first job during the contest is to design a
standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal
line, find out the minimum radius of heaters so that all houses could
be covered by those heaters.

So, your input will be the positions of houses and heaters separately,
and your expected output will be the minimum radius standard of
heaters.

Note:
Numbers of houses and heaters you are given are non-negative and will
not exceed 25000.

Positions of houses and heaters you are given are non-negative and
will not exceed 10^9.

As long as a house is in the heaters’ warm radius range, it can be
warmed.

All the heaters follow your radius standard and the warm radius will
the same.

Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we
use the radius 1 standard, then all the houses can be warmed.

Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We
need to use radius 1 standard, then all the houses can be warmed.

升序排列加热器的坐标heaters
遍历房子houses,记当前房子坐标为house:
接纳二分查找,分别找到不超越house的最大加热器坐标left,以及相当大于house的矮小加热器坐标right(即左右以来的heater),
则当前屋企所需的小不点儿加热器半径radius = min(house – left, right –
house)。利用radius更新最后答案。

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        //sort
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int radius = 0;
        for( int house: houses) {
            int local = binarySearch(heaters, house);
            radius = Math.max(radius, local);
        }
        return radius;
    }

    private int binarySearch(int[] heaters, int target) {
        int start = 0;
        int end = heaters.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (heaters[mid] == target) {
                return 0;
            } else if (heaters[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return Math.min (Math.abs(target - heaters[start]),
                        Math.abs(target - heaters[end]));
    }
}

var myString = ‘23255’;
typeof myString; //String
myString = !!myString;
typeof myString //Boolean

寻觅整型数组中乘积最大的八个数

给定三个含有整数的严节数组,供给寻觅乘积最大的四个数。

JavaScript

var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
computeProduct(unsorted_array); // 21000 function sortIntegers(a, b) {
return a – b; } // greatest product is either (min1 * min2 * max1 ||
max1 * max2 * max3) function computeProduct(unsorted) { var
sorted_array = unsorted.sort(sortIntegers), product1 = 1, product2 = 1,
array_n_element = sorted_array.length – 1; // Get the product of
three largest integers in sorted array for (var x = array_n_LeetCode解题思路,JavaScript初学者必要理解13个小本领。element; x
> array_n_element – 3; x–) { product1 = product1 *
sorted_array[x]; } product2 = sorted_array[0] *
sorted_array[1] * sorted_array[array_n_element]; if (product1
> product2) return product1; return product2 };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
 
computeProduct(unsorted_array); // 21000
 
function sortIntegers(a, b) {
  return a – b;
}
 
// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
  var sorted_array = unsorted.sort(sortIntegers),
    product1 = 1,
    product2 = 1,
    array_n_element = sorted_array.length – 1;
 
  // Get the product of three largest integers in sorted array
  for (var x = array_n_element; x > array_n_element – 3; x–) {
      product1 = product1 * sorted_array[x];
  }
  product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];
 
  if (product1 > product2) return product1;
 
  return product2
};

10# Leetcode 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) {
            return null;
        }

        HashSet<Integer> set = new HashSet<>();
        Arrays.sort(nums1);

        for (int i = 0; i < nums2.length; i++) {
            if(set.contains(nums2[i])){
                continue;
            }
            if(binarySearch(num1, nums2[i])) {
                set.add(nums2[i]);
            }
        }

        int[] result = new int[set.size()];
        int index = 0;
        for (Integer num : set) {
            result[index++] = num;
        }
        return result;
    }

    private boolean binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            else if (nums[mid] < target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }

        if(nums[start] == target || nums[end] == target) {
            return true;
        }
        return false;
    }
}

4,把Number转换成String
这些技术能够让你在number的末梢加多三个空的string来把number调换来string,举例:

探求接二连三数组中的缺点和失误数

给定某冬天数组,其富含了 n 个接二连三数字中的 n – 1
个,已知上上面界,须求以O(n)的复杂度搜索缺点和失误的数字。

JavaScript

// The output of the function should be 8 var array_of_integers = [2,
5, 1, 4, 9, 6, 3, 7]; var upper_bound = 9; var lower_bound = 1;
findMissingNumber(array_of_integers, upper_bound, lower_bound); //8
function findMissingNumber(array_of_integers, upper_bound,
lower_bound) { // Iterate through array to find the sum of the numbers
var sum_of_integers = 0; for (var i = 0; i <
array_of_integers.length; i++) { sum_of_integers +=
array_of_integers[i]; } // 以高斯求和公式计算理论上的数组和 //
Formula: [(N * (N + 1)) / 2] – [(M * (M – 1)) / 2]; // N is the
upper bound and M is the lower bound upper_limit_sum = (upper_bound
* (upper_bound + 1)) / 2; lower_limit_sum = (lower_bound *
(lower_bound – 1)) / 2; theoretical_sum = upper_limit_sum –
lower_limit_sum; // return (theoretical_sum – sum_of_integers) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// The output of the function should be 8
var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7];
var upper_bound = 9;
var lower_bound = 1;
 
findMissingNumber(array_of_integers, upper_bound, lower_bound); //8
 
function findMissingNumber(array_of_integers, upper_bound, lower_bound) {
 
  // Iterate through array to find the sum of the numbers
  var sum_of_integers = 0;
  for (var i = 0; i < array_of_integers.length; i++) {
    sum_of_integers += array_of_integers[i];
  }
 
  // 以高斯求和公式计算理论上的数组和
  // Formula: [(N * (N + 1)) / 2] – [(M * (M – 1)) / 2];
  // N is the upper bound and M is the lower bound
 
  upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;
  lower_limit_sum = (lower_bound * (lower_bound – 1)) / 2;
 
  theoretical_sum = upper_limit_sum – lower_limit_sum;
 
  //
  return (theoretical_sum – sum_of_integers)
}

11# Leetcode 350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in
both arrays.
The result can be in any order.
Follow up:
What if the given array is already sorted? How would you optimize your
algorithm?
What if nums1’s size is small compared to nums2’s size? Which
algorithm is better?
What if elements of nums2 are stored on disk, and the memory is
limited such that you cannot load all elements into the memory at
once?

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index1 = 0;
        int index2 = 0;
        List<Integer> list = new ArrayList<>();
        while(index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                list.add(nums1[index1]);
                index1++;
                index2++;
            } else if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            }
        }
        int[] result = new int[list.size()];
        int index = 0;
        for (int element: list) {
            result[index++] = element;
        }
        return result;
    }
}

复制代码 代码如下:

数组去重

给定某冬季数组,须求删减数组中的重复数字还要重回新的无重复数组。

JavaScript

// ES6 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8] // ES5
Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
uniqueArray(array); // [1, 2, 3, 5, 9, 8] function uniqueArray(array)
{ var hashmap = {}; var unique = []; for(var i = 0; i <
array.length; i++) { // If key returns null (unique), it is evaluated as
false. if(!hashmap.hasOwnProperty([array[i]])) {
hashmap[array[i]] = 1; unique.push(array[i]); } } return unique; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ES6 Implementation
var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
 
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]
 
 
// ES5 Implementation
var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
 
uniqueArray(array); // [1, 2, 3, 5, 9, 8]
 
function uniqueArray(array) {
  var hashmap = {};
  var unique = [];
  for(var i = 0; i < array.length; i++) {
    // If key returns null (unique), it is evaluated as false.
    if(!hashmap.hasOwnProperty([array[i]])) {
      hashmap[array[i]] = 1;
      unique.push(array[i]);
    }
  }
  return unique;
}

12# Leetcode 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot
unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0
1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int target = nums[nums.length - 1];

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (nums[start] <= target) {
            return nums[start];
        } else {
            return nums[end];
        }
    }
}

var mynumber = 234;
typeof mynumber; //Number
mynumber += ”;
typeof mynumber; //String

数组霜月素最大差值总括

给定某冬辰数组,求取任意多少个要素之间的最大差值,注意,这里要求差值总括中十分的小的因素下标必得低于一点都不小意素的下标。例如[7, 8, 4, 9, 9, 15, 3, 1, 10]这几个数组的总括值是
11( 15 – 4 ) 实际不是 14(15 – 1),因为 15 的下标小于 1。

JavaScript

var array = [7, 8, 4, 9, 9, 15, 3, 1, 10]; // [7, 8, 4, 9, 9, 15, 3,
1, 10] would return `11` based on the difference between `4` and
`15` // Notice: It is not `14` from the difference between `15`
and `1` because 15 comes before 1. findLargestDifference(array);
function findLargestDifference(array) { //
要是数组唯有一个因素,则直接回到 -1 if (array.length <= 1) return -1;
// current_min 指向当前的小小值 var current_min = array[0]; var
current_max_difference = 0; //
遍历整个数组以求取当前最大差值,要是发现某些最大差值,则将新的值覆盖
current_max_difference // 同期也会跟踪当前数组中的最小值,进而确定保障
`largest value in future` – `smallest value before it` for (var i =
1; i < array.length; i++) { if (array[i] > current_min &&
(array[i] – current_min > current_max_difference)) {
current_max_difference = array[i] – current_min; } else if
(array[i] <= current_min) { current_min = array[i]; } } // If
negative or 0, there is no largest difference if
(current_max_difference <= 0) return -1; return
current_max_difference; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
// [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15`
// Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.
 
findLargestDifference(array);
 
function findLargestDifference(array) {
 
  // 如果数组仅有一个元素,则直接返回 -1
 
  if (array.length <= 1) return -1;
 
  // current_min 指向当前的最小值
 
  var current_min = array[0];
  var current_max_difference = 0;
  
  // 遍历整个数组以求取当前最大差值,如果发现某个最大差值,则将新的值覆盖 current_max_difference
  // 同时也会追踪当前数组中的最小值,从而保证 `largest value in future` – `smallest value before it`
 
  for (var i = 1; i < array.length; i++) {
    if (array[i] > current_min && (array[i] – current_min > current_max_difference)) {
      current_max_difference = array[i] – current_min;
    } else if (array[i] <= current_min) {
      current_min = array[i];
    }
  }
 
  // If negative or 0, there is no largest difference
  if (current_max_difference <= 0) return -1;
 
  return current_max_difference;
}

13# Leetcode 154. Find Minimum in Rotated Sorted Array II

// version 1: just for loop is enough
public class Solution {
    public int findMin(int[] nums) {
        //  这道题目在面试中不会让写完整的程序
        //  只需要知道最坏情况下 [1,1,1....,1] 里有一个0
        //  这种情况使得时间复杂度必须是 O(n)
        //  因此写一个for循环就好了。
        //  如果你觉得,不是每个情况都是最坏情况,你想用二分法解决不是最坏情况的情况,那你就写一个二分吧。
        //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < min)
                min = nums[i];
        }
        return min;
    }
}

// version 2: use *fake* binary-search
public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == nums[end]) {
                // if mid equals to end, that means it's fine to remove end
                // the smallest element won't be removed
                end--;
            } else if (nums[mid] < nums[end]) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (nums[start] <= nums[end]) {
            return nums[start];
        }
        return nums[end];
    }
}

5,领会叁个函数需求有个别个变量
那是二个高大的技术,能够让你正确地了解二个函数供给多少个变量。比方:

数组凉月素乘积

给定某冬辰数组,需求回到新数组 output ,在那之中 output[i]
为原数组中除去下标为 i 的因素之外的要素乘积,必要以 O(n) 复杂度实现:

JavaScript

var firstArray = [2, 2, 4, 1]; var secondArray = [0, 0, 0, 2]; var
thirdArray = [-2, -2, -3, 2]; productExceptSelf(firstArray); // [8,
8, 4, 16] productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12] function
productExceptSelf(numArray) { var product = 1; var size =
numArray.length; var output = []; // From first array: [1, 2, 4, 16]
// The last number in this case is already in the right spot (allows for
us) // to just multiply by 1 in the next step. // This step essentially
gets the product to the left of the index at index + 1 for (var x = 0; x
< size; x++) { output.push(product); product = product *
numArray[x]; } // From the back, we multiply the current output
element (which represents the product // on the left of the index, and
multiplies it by the product on the right of the element) var product =
1; for (var i = size – 1; i > -1; i–) { output[i] = output[i] *
product; product = product * numArray[i]; } return output; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];
 
productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]
 
function productExceptSelf(numArray) {
  var product = 1;
  var size = numArray.length;
  var output = [];
 
  // From first array: [1, 2, 4, 16]
  // The last number in this case is already in the right spot (allows for us)
  // to just multiply by 1 in the next step.
  // This step essentially gets the product to the left of the index at index + 1
  for (var x = 0; x < size; x++) {
      output.push(product);
      product = product * numArray[x];
  }
 
  // From the back, we multiply the current output element (which represents the product
  // on the left of the index, and multiplies it by the product on the right of the element)
  var product = 1;
  for (var i = size – 1; i > -1; i–) {
      output[i] = output[i] * product;
      product = product * numArray[i];
  }
 
  return output;
}

14# Leetcode 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot
unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return
its index, otherwise return -1.

You may assume no duplicate exists in the array.

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[start] < nums[mid]) {
                if (nums[start] <= target && target <= nums[mid]) {
                    end = mid;
                } else {
                    start = mid;
                } 
            }
            else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                }
                else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] ==  target) {
            return end;
        }
        return -1;
    }
}

复制代码 代码如下:

数组交集

给定七个数组,供给求出多个数组的混杂,注意,交集中的成分应该是唯一的。

JavaScript

var firstArray = [2, 2, 4, 1]; var secondArray = [1, 2, 0, 2];
intersection(firstArray, secondArray); // [2, 1] function
intersection(firstArray, secondArray) { // The logic here is to create a
hashmap with the elements of the firstArray as the keys. // After that,
you can use the hashmap’s O(1) look up time to check if the element
exists in the hash // If it does exist, add that element to the new
array. var hashmap = {}; var intersectionArray = [];
firstArray.forEach(function(element) { hashmap[element] = 1; }); //
Since we only want to push unique elements in our case… we can
implement a counter to keep track of what we already added
secondArray.forEach(function(element) { if (hashmap[element] === 1) {
intersectionArray.push(element); hashmap[element]++; } }); return
intersectionArray; // Time complexity O(n), Space complexity O(n) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var firstArray = [2, 2, 4, 1];
var secondArray = [1, 2, 0, 2];
 
intersection(firstArray, secondArray); // [2, 1]
 
function intersection(firstArray, secondArray) {
  // The logic here is to create a hashmap with the elements of the firstArray as the keys.
  // After that, you can use the hashmap’s O(1) look up time to check if the element exists in the hash
  // If it does exist, add that element to the new array.
 
  var hashmap = {};
  var intersectionArray = [];
 
  firstArray.forEach(function(element) {
    hashmap[element] = 1;
  });
 
  // Since we only want to push unique elements in our case… we can implement a counter to keep track of what we already added
  secondArray.forEach(function(element) {
    if (hashmap[element] === 1) {
      intersectionArray.push(element);
      hashmap[element]++;
    }
  });
 
  return intersectionArray;
 
  // Time complexity O(n), Space complexity O(n)
}

15# Leetcode 81. Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot
unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0
1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

public class Solution {
    // 这个问题在面试中不会让实现完整程序
    // 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。
    // 在这种情况下是无法使用二分法的,复杂度是O(n)
    // 因此写个for循环最坏也是O(n),那就写个for循环就好了
    //  如果你觉得,不是每个情况都是最坏情况,你想用二分法解决不是最坏情况的情况,那你就写一个二分吧。
    //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
    public boolean search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }
}

function add_nums(num1, num2){
return num1 + num2;
}
add_nums.length // 2 is the amount of parameters expected by the
function add_nums

字符串

16# Leetcode 34. Search for a Range

Given an array of integers sorted in ascending order, find the
starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

public class Solution {
    public int[] searchRange(int[] nums, int target) {
       if (nums.length == 0) {
            return new int[]{-1,-1};
        }
        int[] bound = new int[2];
        // search for left bound
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) {
            bound[0] = start;
        } else if (nums[end] == target) {
            bound[0] = end;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        //search for right bound
        start = 0;
        end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                start = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            bound[1] = end;
        } else if (nums[start] == target) {
            bound[1] = start;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        return bound;
    }
}

6,使用“arguments”对象来理解多少个函数接收到了稍稍个参数
其一才具能够让您使用“arguments”对象来询问二个函数接收到了略微个参数。譬喻:

颠倒字符串

加以有些字符串,须要将内部单词倒转之后然后输出,比方”Welcome to this
Javascript Guide!” 应该出口为 “emocleW ot siht tpircsavaJ !ediuG”。

JavaScript

var string = “Welcome to this Javascript Guide!”; // Output becomes
!ediuG tpircsavaJ siht ot emocleW var reverseEntireSentence =
reverseBySeparator(string, “”); // Output becomes emocleW ot siht
tpircsavaJ !ediuG var reverseEachWord =
reverseBySeparator(reverseEntireSentence, ” “); function
reverseBySeparator(string, separator) { return
string.split(separator).reverse().join(separator); }

1
2
3
4
5
6
7
8
9
10
11
var string = "Welcome to this Javascript Guide!";
 
// Output becomes !ediuG tpircsavaJ siht ot emocleW
var reverseEntireSentence = reverseBySeparator(string, "");
 
// Output becomes emocleW ot siht tpircsavaJ !ediuG
var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");
 
function reverseBySeparator(string, separator) {
  return string.split(separator).reverse().join(separator);
}

17# Leetcode 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n
matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the
previous row.

For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int row = matrix.length;
        int column = matrix[0].length;
        int start = 0;
        int end = row * column - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int number = matrix[mid / column][mid % column];
            if (number == target) {
                return true;
            } else if (number < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[start / column][start % column] == target) {
            return true;
        } else if (matrix[end / column][end % column] == target) {
            return true;
        }
        return false;
    }
}

复制代码 代码如下:

乱序同字母字符串

给定多个字符串,判别是不是颠倒字母而成的字符串,举个例子MaryArmy固然同字母而一一颠倒:

JavaScript

var firstWord = “Mary”; var secondWord = “Army”; isAnagram(firstWord,
secondWord); // true function isAnagram(first, second) { // For case
insensitivity, change both words to lowercase. var a =
first.toLowerCase(); var b = second.toLowerCase(); // Sort the strings,
and join the resulting array to a string. Compare the results a =
a.split(“”).sort().join(“”); b = b.split(“”).sort().join(“”); return a
=== b; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var firstWord = "Mary";
var secondWord = "Army";
 
isAnagram(firstWord, secondWord); // true
 
function isAnagram(first, second) {
  // For case insensitivity, change both words to lowercase.
  var a = first.toLowerCase();
  var b = second.toLowerCase();
 
  // Sort the strings, and join the resulting array to a string. Compare the results
  a = a.split("").sort().join("");
  b = b.split("").sort().join("");
 
  return a === b;
}

18# Leetcode 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n
matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = 0;
        int col = matrix[0].length - 1;
        while (col >= 0 && row <= matrix.length - 1) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                col--;
            } else if (target > matrix[row][col]) {
                row ++;
            }
        }
        return false;
    }
}

function add_nums(){
return arguments.length;
}
add_nums(23,11,32,56,89,89,89,44,6); //this return the number 9

会问字符串

决断有些字符串是不是为回文字符串,举个例子racecarrace car都以回文字符串:

JavaScript

isPalindrome(“racecar”); // true isPalindrome(“race Car”); // true
function isPalindrome(word) { // Replace all non-letter chars with “”
and change to lowercase var lettersOnly =
word.toLowerCase().replace(/\s/g, “”); // Compare the string with the
reversed version of the string return lettersOnly ===
lettersOnly.split(“”).reverse().join(“”); }

1
2
3
4
5
6
7
8
9
10
isPalindrome("racecar"); // true
isPalindrome("race Car"); // true
 
function isPalindrome(word) {
  // Replace all non-letter chars with "" and change to lowercase
  var lettersOnly = word.toLowerCase().replace(/\s/g, "");
 
  // Compare the string with the reversed version of the string
  return lettersOnly === lettersOnly.split("").reverse().join("");
}

19# Leetcode 230. Kth Smallest Element in a BST

当您供给检讨参数个数的管事的时候,或然当您需求创设一个不分明参数个数的函数的时候,那个技巧是很有用的。

栈与队列

20# Leetcode 378. Kth Smallest Element in a Sorted Matrix

复制代码 代码如下:

运用三个栈达成入队与出队

JavaScript

var inputStack = []; // First stack var outputStack = []; // Second
stack // For enqueue, just push the item into the first stack function
enqueue(stackInput, item) { return stackInput.push(item); } function
dequeue(stackInput, stackOutput) { // Reverse the stack such that the
first element of the output stack is the // last element of the input
stack. After that, pop the top of the output to // get the first element
that was ever pushed into the input stack if (stackOutput.length <=
0) { while(stackInput.length > 0) { var elementToOutput =
stackInput.pop(); stackOutput.push(elementToOutput); } } return
stackOutput.pop(); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var inputStack = []; // First stack
var outputStack = []; // Second stack
 
// For enqueue, just push the item into the first stack
function enqueue(stackInput, item) {
  return stackInput.push(item);
}
 
function dequeue(stackInput, stackOutput) {
  // Reverse the stack such that the first element of the output stack is the
  // last element of the input stack. After that, pop the top of the output to
  // get the first element that was ever pushed into the input stack
  if (stackOutput.length <= 0) {
    while(stackInput.length > 0) {
      var elementToOutput = stackInput.pop();
      stackOutput.push(elementToOutput);
    }
  }
 
  return stackOutput.pop();
}

21# Leetcode 162. Find Peak Element

function sum_three_nums( ){
if(arguments.length!=3) throw new Error(‘received ‘ + arguments.length +
‘ parameters and should work with 3’);
}
sum_three_nums(23,43); //Return the error message
function sum_num(){
var total = 0;
for(var i=0;i<arguments .length;i++){
total+=arguments[i];
}
return total;
}
sum_num(2,34,45,56,56);

判别大括号是还是不是关闭

创办一个函数来剖断给定的说明式中的大括号是或不是关闭:

JavaScript

var expression = “{{}}{}{}” var expressionFalse = “{}{{}”;
isBalanced(expression); // true isBalanced(expressionFalse); // false
isBalanced(“”); // true function isBalanced(expression) { var
checkString = expression; var stack = []; // If empty, parentheses are
technically balanced if (checkString.length <= 0) return true; for
(var i = 0; i < checkString.length; i++) { if(checkString[i] ===
‘{‘) { stack.push(checkString[i]); } else if (checkString[i] ===
‘}’) { // Pop on an empty array is undefined if (stack.length > 0) {
stack.pop(); } else { return false; } } } // If the array is not empty,
it is not balanced if (stack.pop()) return false; return true; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var expression = "{{}}{}{}"
var expressionFalse = "{}{{}";
 
isBalanced(expression); // true
isBalanced(expressionFalse); // false
isBalanced(""); // true
 
function isBalanced(expression) {
  var checkString = expression;
  var stack = [];
 
  // If empty, parentheses are technically balanced
  if (checkString.length <= 0) return true;
 
  for (var i = 0; i < checkString.length; i++) {
    if(checkString[i] === ‘{‘) {
      stack.push(checkString[i]);
    } else if (checkString[i] === ‘}’) {
      // Pop on an empty array is undefined
      if (stack.length > 0) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
 
  // If the array is not empty, it is not balanced
  if (stack.pop()) return false;
  return true;
}

22# Leetcode 454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples
(i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is
zero.

To make problem a bit easier, all A, B, C, D have same length of N
where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1
and the result is guaranteed to be at most 231 – 1.

Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) +
    (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) +
    (-1) + 0 = 0

7,把对象正是参数,来集团和改革函数
在今世Web开辟中,对象最广大的二个用处是把它们当成函数的参数。要铭记在心函数参数的那个准则总是很拮据的;但是,使用一个对象是非常有补益的,因为咱们无需再想不开参数的准绳了。况且,它更有组织性,能够让客户更加好的通晓我们要做什么样。那几个格局能够令你把对象就是参数,来公司和修正函数。举例:

递归

23# Leetcode 436. Find Right Interval

Given a set of intervals, for each of the interval i, check if there
exists an interval j whose start point is bigger than or equal to the
end point of the interval i, which can be called that j is on the
“right” of i.

For any interval i, you need to store the minimum interval j’s index,
which means that the interval j has the minimum start point to build
the “right” relationship for interval i. If the interval j doesn’t
exist, store -1 for the interval i. Finally, you need output the
stored value of each interval as an array.

Note:
You may assume the interval’s end point is always bigger than its
start point.
You may assume none of these intervals have the same start point.
Example 1:
Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it
outputs -1.

Example 2:
Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied “right” interval for [3,4].
For [2,3], the interval [3,4] has minimum-“right” start point;
For [1,2], the interval [2,3] has minimum-“right” start point.

Example 3:
Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied “right” interval for [1,4] and
[3,4].
For [2,3], the interval [3,4] has minimum-“right” start point.

复制代码 代码如下:

二进制调换

通过有些递归函数将输入的数字转化为二进制字符串:

JavaScript

decimalToBinary(3); // 11 decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000 function decimalToBinary(digit) {
if(digit >= 1) { // If digit is not divisible by 2 then recursively
return proceeding // binary of the digit minus 1, 1 is added for the
leftover 1 digit if (digit % 2) { return decimalToBinary((digit – 1) /
2) + 1; } else { // Recursively return proceeding binary digits return
decimalToBinary(digit / 2) + 0; } } else { // Exit condition return ”;
} }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
decimalToBinary(3); // 11
decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000
 
function decimalToBinary(digit) {
  if(digit >= 1) {
    // If digit is not divisible by 2 then recursively return proceeding
    // binary of the digit minus 1, 1 is added for the leftover 1 digit
    if (digit % 2) {
      return decimalToBinary((digit – 1) / 2) + 1;
    } else {
      // Recursively return proceeding binary digits
      return decimalToBinary(digit / 2) + 0;
    }
  } else {
    // Exit condition
    return ”;
  }
}

24# Leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest
increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the
length is 4. Note that there may be more than one LIS combination, it
is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

function insertData(name,lastName,phone,address){
code here;
}

二分查找

JavaScript

function recursiveBinarySearch(array, value, leftPosition,
rightPosition) { // Value DNE if (leftPosition > rightPosition)
return -1; var middlePivot = Math.floor((leftPosition + rightPosition) /
2); if (array[middlePivot] === value) { return middlePivot; } else if
(array[middlePivot] > value) { return recursiveBinarySearch(array,
value, leftPosition, middlePivot – 1); } else { return
recursiveBinarySearch(array, value, middlePivot + 1, rightPosition); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
function recursiveBinarySearch(array, value, leftPosition, rightPosition) {
  // Value DNE
  if (leftPosition > rightPosition) return -1;
 
  var middlePivot = Math.floor((leftPosition + rightPosition) / 2);
  if (array[middlePivot] === value) {
    return middlePivot;
  } else if (array[middlePivot] > value) {
    return recursiveBinarySearch(array, value, leftPosition, middlePivot – 1);
  } else {
    return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);
  }
}

25# Leetcode 287. Find the Duplicate Number

重构以往的代码是那样的:

数字

26# Leetcode 275. H-Index II

复制代码 代码如下:

看清是还是不是为 2 的指数值

JavaScript

isPowerOfTwo(4); // true isPowerOfTwo(64); // true isPowerOfTwo(1); //
true isPowerOfTwo(0); // false isPowerOfTwo(-1); // false // For the
non-zero case: function isPowerOfTwo(number) { // `&` uses the bitwise
n. // In the case of number = 4; the expression would be identical to:
// `return (4 & 3 === 0)` // In bitwise, 4 is 100, and 3 is 011. Using
&, if two values at the same // spot is 1, then result is 1, else 0. In
this case, it would return 000, // and thus, 4 satisfies are expression.
// In turn, if the expression is `return (5 & 4 === 0)`, it would be
false // since it returns 101 & 100 = 100 (NOT === 0) return number &
(number – 1) === 0; } // For zero-case: function
isPowerOfTwoZeroCase(number) { return (number !== 0) && ((number &
(number – 1)) === 0); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
isPowerOfTwo(4); // true
isPowerOfTwo(64); // true
isPowerOfTwo(1); // true
isPowerOfTwo(0); // false
isPowerOfTwo(-1); // false
 
// For the non-zero case:
function isPowerOfTwo(number) {
  // `&` uses the bitwise n.
  // In the case of number = 4; the expression would be identical to:
  // `return (4 & 3 === 0)`
  // In bitwise, 4 is 100, and 3 is 011. Using &, if two values at the same
  // spot is 1, then result is 1, else 0. In this case, it would return 000,
  // and thus, 4 satisfies are expression.
  // In turn, if the expression is `return (5 & 4 === 0)`, it would be false
  // since it returns 101 & 100 = 100 (NOT === 0)
 
  return number & (number – 1) === 0;
}
 
// For zero-case:
function isPowerOfTwoZeroCase(number) {
  return (number !== 0) && ((number & (number – 1)) === 0);
}

 

3 赞 12 收藏 1
评论

4858美高梅 1

27# Leetcode 50. Pow(x, n)

function insertData(parameters){
var name = parameters.name;
var lastName = parameters.lastName;
var phone = parameters.phone;
var address = parameters.address;
}

28# Leetcode 29. Divide Two Integers

当您要动用私下认可值的时候,它也是丰硕实用的。比如:

29# Leetcode 222. Count Complete Tree Nodes

复制代码 代码如下:

30# Leetcode 209. Minimum Size Subarray Sum

function insertData(parameters){
var name = parameters.name;
var lastName = parameters.lastName;
var phone = parameters.phone;
var address = parameters.address;
var status = parameters.status || ‘single’ //If status is not defined as
a property
//in the object the variable status take single as value
}

31# Leetcode 392. Is Subsequence

现行反革命,要利用那一个函数十三分的简便;大家得以用二种格局来发送数据:

32# Leetcode 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n
respectively.

Find the median of the two sorted arrays. The overall run time
complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3], nums2 = [2]
The median is 2.0

Example 2:
nums1 = [1, 2], nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

复制代码 代码如下:

33# Leetcode 363. Max Sum of Rectangle No Larger Than K

//Example 1
insertData({name:’Mike’, lastName:’Rogers’,
phone:’555-555-5555′,address:’the address’, status:’married’});

34# Leetcode 354. Russian Doll Envelopes

//Example 2
var myData = { name:’Mike’,
lastName:’Rogers’,
phone:’555-555-5555′,
address:’the address’,
status:’married’
};
insertData(myData);

35# Leetcode 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer
m, you can split the array into m non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m
subarrays.

Note:
If n is the length of array, assume the following constraints are
satisfied:

1 ≤ n ≤ 1000

1 ≤ m ≤ min(50, n)
Examples:

Input:
nums = [7,2,5,10,8]
m = 2
Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

8,函数正是多少
函数正是像strings或numbers那样的数码,大家可以把它们便是函数参数来传递它们,那可以创立丰裕令人惊叹而又“英姿勃勃”的Web应用程序。这么些办法是十二分有效的,差十分的少全体的主流框架都使用了那个措施。比如:

36# Leetcode 302.Smallest Rectangle Enclosing Black Pixels

复制代码 代码如下:

37# Leetcode 174. Dungeon Game

The demons had captured the princess (P) and imprisoned her in the
bottom-right corner of a dungeon. The dungeon consists of M x N rooms
laid out in a 2D grid. Our valiant knight (K) was initially positioned
in the top-left room and must fight his way through the dungeon to
rescue the princess.

The knight has an initial health point represented by a positive
integer. If at any point his health point drops to 0 or below, he dies
immediately.

Some of the rooms are guarded by demons, so the knight loses health
(negative integers) upon entering these rooms; other rooms are either
empty (0’s) or contain magic orbs that increase the knight’s health
(positive integers).

In order to reach the princess as quickly as possible, the knight
decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so
that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight
must be at least 7 if he follows the optimal path RIGHT-> RIGHT
-> DOWN -> DOWN.

-2(K) -3 3
-5 -10 1
10 30 -5(P)

Notes:

The knight’s health has no upper bound.
Any room can contain threats or power-ups, even the first room the
knight enters and the bottom-right room where the princess is
imprisoned.

function byId(element, event, f){
Document.getElementById(element).[‘on’+event] = f; //f is the function
that we pass as parameter
}
byId(‘myBtn’,’click’,function(){alert(‘Hello World’)});
Another example of functions as data:
//Example 1
function msg(m){
Alert(m);
}
//Example 2
var msg = function(m){ alert(m);}
这个函数大约是千篇一律的。独一的分别是应用它们的秘籍。比如:第叁个函数,在你注解它原先,你就足以行使它了;可是第4个函数独有扬言以往技术接纳:
//Example 1
msg(‘Hello world’); //This will work
function msg(m){
alert(m);
4858美高梅,}
//Example 2
msg(‘Hello world’); //Does not work because JavaScript cannot find the
function msg because is used before is been declared.
var msg = function(m){ alert(m)}

38# Leetcode 483. Smallest Good Base

9,增加当地对象
虽说有的JavaScript的首脑不推荐这些本事,然而它曾经被一些框架使用了。它能够让您针对JavaScript
API来创立一些协理性的办法。

39# LintCode: Last Position of Target

Find the last position of a target number in a sorted array. Return -1
if target does not exist.
Example
Given [1, 2, 2, 4, 5, 5].
For target = 2, return 2.
For target = 5, return 5.
For target = 6, return -1.

public int lastPosition(int[] nums, int target) {
    // Write your code here
    if (nums.length == 0 || nums == null) {
        return -1;
    }
    int start = 0;
    int end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid]==target) {
            start = mid;
        } else if (nums[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    if (nums[end] == target) {
        return end;
    }
    if (nums[start] == target) {
        return start;
    }
    return -1;
}

复制代码 代码如下:

40# LintCode: Maximum Number in Mountain Sequence

Given a mountain sequence of n integers which increase firstly and then
decrease, find the mountain top.

Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10

public int mountainSequence(int[] nums) {
    if (nums.length == 0 || nums == null) {
        return -1;
    }
    int start = 0;
    int end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > nums[mid + 1]) {
            end = mid;
        } else {
            start = mid;
        }
    }
    return Math.max(nums[start], nums[end]);
}

//We create the method prototype for our arrays
//It only sums numeric elements
Array.prototype.sum = function(){
var len = this.length;
total = 0;
for(var i=0;i<len ;i++){
if(typeof this[i]!= ‘number’) continue;
total += this[i];
}
return total;
}
var myArray = [1,2,3,’hola’];
myArray.sum();

Array.prototype.max = function(){
return Math.max.apply(”,this);
}

10,Boolean
注意它们中间的区分,因为这会节约你调节和测验脚本的日子。

复制代码 代码如下:

” == ‘0’ // false
0 == ” // true
0 == ‘0’ // true
false == ‘false’ // false
false == ‘0’ // true
false == undefined // false
false == null // false
null == undefined // true
true == 1 // true
” == null // false
false == ” // true

假诺你在任哪个地点方看过这几个本子,那么这个技巧能够帮忙您闻一知十。那个本领还是还未有JavaScript全数功用的冰山一角,可是那是多个开始!请不要客气,留下您的评论和介绍,难题,额外的技术或疑虑吧,不过请牢记,这是一篇针对初学者的稿子!!作者期待能接收部分开辟者同行的通讯!Enjoy!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有