JavaScript 面试中常见算法问题详解网赌平台哪个信誉好

数组中元素乘积

给定某无序数组,要求返回新数组 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;
}

36# Leetcode 302.Smallest Rectangle Enclosing Black Pixels

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

在类继承中,类是不可变的,不同的语言中对于多继承的支持也不一样,有些语言中还支持接口、final、abstract
的概念。而原型继承则更为灵活,原型本身是可以可变的,并且对象可能继承自多个原型。

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

会问字符串

判断某个字符串是否为回文字符串,譬如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("");
}

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

寻找连续数组中的缺失数

给定某无序数组,其包含了 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)
}

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

数组中元素最大差值计算

给定某无序数组,求取任意两个元素之间的最大差值,注意,这里要求差值计算中较小的元素下标必须小于较大元素的下标。譬如[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;
}

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

递归

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

栈与队列

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

二分搜索

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

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

乱序同字母字符串

给定两个字符串,判断是否颠倒字母而成的字符串,譬如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;
}

28# Leetcode 29. Divide Two Integers

数组

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.

解释下什么是 Event Bubbling 以及如何避免

Event Bubbling
即指某个事件不仅会触发当前元素,还会以嵌套顺序传递到父元素中。直观而言就是对于某个子元素的点击事件同样会被父元素的点击事件处理器捕获。避免
Event Bubbling 的方式可以使用event.stopPropagation() 或者 IE 9
以下使用event.cancelBubble

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

数字

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.

JavaScript Specification

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

判断大括号是否闭合

创建一个函数来判断给定的表达式中的大括号是否闭合:

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

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

判断是否为 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
评论

网赌平台哪个信誉好 1

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

阐述下 JavaScript 中的变量提升

所谓提升,顾名思义即是 JavaScript
会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量,不过虽然
JavaScript 会将声明提升到顶部,但是并不会执行真的初始化过程。

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

字符串

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

找出整型数组中乘积最大的三个数

给定一个包含整数的无序数组,要求找出乘积最大的三个数。

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

34# Leetcode 354. Russian Doll Envelopes

使用两个栈实现入队与出队

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

38# Leetcode 483. Smallest Good Base

解释下 null 与 undefined 的区别

JavaScript 中,null 是一个可以被分配的值,设置为 null
的变量意味着其无值。而 undefined
则代表着某个变量虽然声明了但是尚未进行过任何赋值。

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]);
}
You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图