菜单

JavaScript初学者必要明白10个小技巧

2019年1月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的利用限制分外普遍,而且还有如此多的作风,所以它可以有好多的技术。其余,即使它很多的编程方法,可是本人只接纳了10个技巧,我觉得这个技巧对初学者领悟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
即指某个事件不仅会触发当前元素,还会以嵌套顺序传递到父元素中。直观而言就是对此某个子元素的点击事件相同会被父元素的点击事件处理器捕获。防止伊夫(Eve)nt 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_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

相关文章

发表评论

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

网站地图xml地图