面试中常见算法问题详解

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 Specification

2# Leetcode 270 Closest Binary Search Tree Value

阐释下 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;
    }
}

阐述下 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;
    }
}

表明下什么是 伊夫nt Bubbling 以及怎样幸免

Event 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;
        }
    }
}

== 与 === 的区别是怎么着

=== 也正是所谓的严谨比较,关键的区分在于===
会相同的时候比较类型与值,并非仅相比较值。

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;
    }
}

解释下 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;
    }
}

解释下 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]));
    }
}

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

给定三个含有整数的冬日数组,供给找寻乘积最大的七个数。

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;
    }
}

招来两次三番数组中的缺点和失误数

给定某冬日数组,其蕴藉了 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];
        }
    }
}

数组瓜时素最大差值计算

给定某冬天数组,求取大肆多个要素之间的最大差值,注意,这里需要差值总结中十分的小的成分下标必得低于非常的大因素的下标。譬喻[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]永利澳门游戏网址304, <= 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];
    }
}

数组桐月素乘积

给定某冬季数组,供给回到新数组 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;
    }
}

字符串

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;
    }
}

颠倒字符串

加以有些字符串,须求将里面单词倒转之后然后输出,举个例子”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;
    }
}

会问字符串

判别有个别字符串是还是不是为回文字符串,例如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

发表评论

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