Q1:leetcode 622
Q2:leetcode 259
Q3:leetcode 15
Q4:leetcode 18
Q5:leetcode merge interval
Q6:leetcode insert merge
Q7: leetcode 507
Q8: leetcode 1
Q9:leetcode 16
Q10:leetcode 454
class Solution {
public int triangleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums); //一定要sort
int n = nums.length;
int result = 0;
for (int k = n - 1; k >= 2; k--) {
int i = 0;
int j = k - 1;
while (i < j) { //没有去等 因为不重复用
if (nums[i] + nums[j] <= nums[k]) {
i++;
} else {
result += j - i;//j fixed, from i, i + 1, ...j - 1
j--; }
}
}
return result;
}
}
//Q2
class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int n = nums.length;
int count = 0;
for (int k = n - 1; k >= 2; k--) {
int i = 0;
int j = k - 1;
while (i < j) {
int sum = nums[i] + nums[j];
int temptarget = target - nums[k];
if (sum < temptarget) {
count += j - i;
i++;
} else {
j--;
}
}
}
return count;
}
}
//Q3
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int n = nums.length;
Arrays.sort(nums);
for (int k = n - 1; k >= 2; k--) {
int i = 0;
int j = k - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum < -nums[k]) {
i++;
} else if (sum > -nums[k]) {
j--;
} else {
List<Integer> oneSol = new ArrayList<>();
oneSol.add(nums[i]);
oneSol.add(nums[j]);
oneSol.add(nums[k]);
result.add(oneSol);
i++;
while (i < j && nums[i] == nums[i - 1]) {
//while (i+ 1 < j && nums[i] == nums[i + 1]) {
i++;
}
j--;
}
}
while (k - 1 > 0 && nums[k] == nums[k - 1]) {
k--;
}
}
return result;
}
}
//
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int n = nums.length;
Arrays.sort(nums);
for (int k = n - 1; k >= 3; k--) {
for (int m = k - 1; m >= 2; m--) {
int Ntarget = target - nums[k] - nums[m];
int i = 0;
int j = m - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum < Ntarget) {
i++;
} else if (sum > Ntarget) {
j--;
} else {
List<Integer> oneSol = new ArrayList<>();
oneSol.add(nums[i]);
oneSol.add(nums[a]);
oneSol.add(nums[m]);
oneSol.add(nums[k]);
result.add(oneSol);
i++;
while (i < j && nums[i] == nums[i - 1]) {
//while (i+ 1 < j && nums[i] == nums[i + 1]) {
i++;
}
j--;
}
}
while (m - 1 > 0 && nums[m] == nums[m - 1]) {
m--;
}
}
while (k - 1 > 0 && nums[k] == nums[k - 1]) {
k--;
}
}
return result;
}
}
//Q5
if (newInterval == null) return intervals;
boolean hasAdded = false;
for (int i = 0; i < n; i++) {
Interval cur = intervals.get(i);
if (newInterval.start > cur.end) {
results.add(cur);
} else if (cur.start > newInterval.end) {
if (!hasAdded) {
results.add(newInterval);
hasAdded = true;
}
results.add(cur);
} else {
newInterval.end = Math.max(cur.end, newInterval.end);
newInterval.start = Math.min(cur.start, newInterval.start);
}
}
if (!hasAdded) {
results.add(newInterval);
}
return results;
//Q6
class Solution {
public List<Interval> merge(List<Interval> intervals) {
//TODO: null check
Arrays.sort(intervals, new Comparator<Interval>(){
@override
public int compare(Interval o1, Interval o2) {
return o1.start.CompareTo(o2.start);//Use Integer.Compare
}
});
List<Interval> results = new ArrayList<>();
int n = intervals.size();
Interval temp = null;
for (int i = 0; i < n; i++) {
Interval cur = intervals.get(i);
if (temp == null) {
temp = new Interval(intervals.get(i).start, intervals.get(i).end);
}
if (i + 1 < n && intervals.get(i + 1).start <= temp.end) {
temp.end = Math.max(temp.end, intervals.get(i + 1).end);
i++;
} else {
results.add(temp);
temp == null;
}
}
//
public class Solution {
public boolean checkPerfectNumber(int num) {
if (num == 1) return false;
int sum = 0;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
sum++;
return sum == num;
}
}
//
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hashMap = new HashMap<>();
int diff;
int result[] = new int[2];
for(int i=0;i<nums.length;i++){
diff = target - nums[i];
if(hashMap.containsKey(diff)){
result[0] = hashMap.get(diff);
result[1] = i;
break;
}else {
hashMap.put(nums[i],i);
}
}
return result;
}
//private int threeSumClosestUsingTwoPointers(int[] nums, int target) {
// Sorting is essential for two pointer solution.
Arrays.sort(nums);
int closestThreeSum = Integer.MAX_VALUE;
int minDistance = Integer.MAX_VALUE;
boolean foundTarget = false;
for(int i=0; i<nums.length; i++) {
int beg=i+1;
int end=nums.length-1;
while(beg < end) {
int twoSum = nums[beg] + nums[end];
if(twoSum == target - nums[i]) {
closestThreeSum = target;
foundTarget = true;
break;
}
int possibleClosestTarget = twoSum + nums[i];
int distanceFromTarget = Math.abs(target - possibleClosestTarget);
if(distanceFromTarget < minDistance) {
minDistance = distanceFromTarget;
closestThreeSum = possibleClosestTarget;
}
if(twoSum < target - nums[i]) beg++;
else end--;
}
if(foundTarget) break;
}
return closestThreeSum;
}
//
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
/* sorting, O(n^2*log(n)) time, O(n^2) space, no map */
int nAB = A.length * B.length;
int[] sumAB = new int[nAB];
int i = 0;
for (int a : A) {
for (int b : B) {
sumAB[i++] = a + b;
}
}
Arrays.sort(sumAB);
int nCD = C.length * D.length;
int[] negSumCD = new int[nCD];
i = 0;
for (int c : C) {
for (int d : D) {
negSumCD[i++] = - (c + d);
}
}
Arrays.sort(negSumCD);
// if sumAB = negSumCD, then 4 sum = 0
i = 0;
int j = 0;
int res = 0;
while (i < nAB && j < nCD) {
if (sumAB[i] < negSumCD[j]) i++;
else if (sumAB[i] > negSumCD[j]) j++;
else {
// sumAB[i] == negSumCD[j]
// need to count number of same consecutive values, and multiply them
int countAB = 1, countCD = 1;
while (++i < nAB && sumAB[i-1] == sumAB[i]) countAB += 1;
while (++j < nCD && negSumCD[j-1] == negSumCD[j]) countCD += 1;
res += countAB * countCD;
}
}
return res;
}
