LeetCode Two Sum

Java HashMap 基本操作在这题里

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // Constructor
        for(int i=nums.length-1; i>=0; i--){
            int adder = target-nums[i];
            if(map.containsKey(adder)){ // Check if map has the key
                return new int[] {i+1, map.get(adder)+1};  // Get the value from the key
            }
            else{
                map.put(nums[i], i);  // Add new key-value pair
            }
        }
        return new int[] {-1, -1};
    }
}

LeetCode Search Insert Position

二分插入

def searchInsert(self, nums, target):
        l, r, i = 0, len(nums)-1, 0
        while l<r:
            i = (l+r)/2
            if nums[i]<target:
                if l==i:
                    i += 1
                l = i
            elif nums[i]>target:
                r = i
            else:
                return i
        if nums[i]<target:
            return i+1
        return i

 

关注插入点 Most Voted Solution

public int searchInsert(int[] A, int target) {
        int low = 0, high = A.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(A[mid] == target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return low;
    }

LeetCode Product of Array Except Self

过早优化是万恶之源= =

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int[] output = new int[l];
        int[] a = new int[l];
        int[] b = new int[l];
        for(int i=0; i<l; i++){
            a[i] = 1;
            b[i] = 1;
        }
        for(int i=1; i<l; i++){
            int j = l-i-1;
            a[i] *= nums[i-1] * a[i-1];
            b[j] *= nums[j+1] * b[j+1];
        }
        for(int i=0; i<l; i++) output[i] = a[i] * b[i];
        return output;
    }
}

 

优化:用一个变量代替数组

public class Solution {
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

LeetCode Merge Sorted Array

心得:编程语言随机应变= =

 

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l = m + n - 1;
        int a = m-1;
        int b = n-1;
        int i=l;
        while(i>=0){
            if(a<0) nums1[i--] = nums2[b--];
            else if(b<0) nums1[i--] = nums1[a--];
            else if(nums1[a]>nums2[b]) nums1[i--] = nums1[a--];
            else nums1[i--] = nums2[b--];
        }
    }
}