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}; } }
二分插入
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; }
过早优化是万恶之源= =
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; }
心得:编程语言随机应变= =
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--]; } } }