1. Two Sum
输入输出
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
答案一
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i + 1;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i + 1);
}
return result;
}
答案二
vector<int> twoSum(vector<int> &numbers, int target) {
//Key is the number and value is its index in the vector.
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];
//if numberToFind is found in map, return them
if (hash.find(numberToFind) != hash.end()) {
//+1 because indices are NOT zero based
result.push_back(hash[numberToFind] + 1);
result.push_back(i + 1);
return result;
}
//number was not found. Put it in the map.
hash[numbers[i]] = i;
}
return result;
}
参考
Accepted Java O(n) Solution Accepted C++ O(n) Solution
4. Median of Two Sorted Arrays
输入输出
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
答案一
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
答案二
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int N1 = nums1.size();
int N2 = nums2.size();
if (N1 < N2) return findMedianSortedArrays(nums2, nums1); // Make sure A2 is the shorter one.
if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2; // If A2 is empty
int lo = 0, hi = N2 * 2;
while (lo <= hi) {
int mid2 = (lo + hi) / 2; // Try Cut 2
int mid1 = N1 + N2 - mid2; // Calculate Cut 1 accordingly
double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2]; // Get L1, R1, L2, R2 respectively
double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
if (L1 > R2) lo = mid2 + 1; // A1's lower half is too big; need to move C1 left (C2 right)
else if (L2 > R1) hi = mid2 - 1; // A2's lower half too big; need to move C2 left.
else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
}
return -1;
}
参考
Share my O(log(min(m,n)) solution with explanation Very concise O(log(min(M,N))) iterative solution with detailed explanation
11. Container With Most Water
答案一
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
MAX = 0
x = len(height) - 1
y = 0
while x != y:
if height[x] > height[y]:
area = height[y] * (x - y)
y += 1
else:
area = height[x] * (x - y)
x -= 1
MAX = max(MAX, area)
return MAX
答案二
int maxArea(vector<int>& height) {
int water = 0;
int i = 0, j = height.size() - 1;
while (i < j) {
int h = min(height[i], height[j]);
water = max(water, (j - i) * h);
while (height[i] <= h && i < j) i++;
while (height[j] <= h && i < j) j--;
}
return water;
}
参考
Yet another way to see what happens in the O(n) algorithm Simple and fast C++/C with explanation
[TODO] 3Sum, 3Sum Closest, 4Sum
26. Remove Duplicates from Sorted Array
输入输出
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
答案一
class Solution {
public:
int removeDuplicates(int A[], int n) {
if(n < 2) return n;
int id = 1;
for(int i = 1; i < n; ++i)
if(A[i] != A[i-1]) A[id++] = A[i];
return id;
}
};
答案二
int count = 0;
for(int i = 1; i < n; i++){
if(A[i] == A[i-1]) count++;
else A[i-count] = A[i];
}
return n-count;