LeetCode解题思路 (一)

作者:信息技术

二分搜索

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

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

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

数组

36# Leetcode 302.Smallest Rectangle Enclosing Black Pixels

做的一些题的解题思路

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

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

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

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("+-*/");
}

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

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

== 与 === 的区别是什么

=== 也就是所谓的严格比较,关键的区别在于=== 会同时比较类型与值,而不是仅比较值。

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

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

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

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

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

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

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

解释下 null 与 undefined 的区别

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

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

数字

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

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

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

39# LintCode: Last Position of Target

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

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

数组去重

给定某无序数组,要求去除数组中的重复数字并且返回新的无重复数组。

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

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

字符串

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.

乱序同字母字符串

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

38# Leetcode 483. Smallest Good Base

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

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

数组中元素最大差值计算

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

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

本文由杏彩发布,转载请注明来源

关键词: