Q1: leetcode 653
Q2: leetcode 252
Q3: sorted, no dup, calculate how many pairs of i and j s.t arr[i] + arr[j] == target?
Q4: sorted array, w/ duplicates. calculate how many pairs of i and j s.t arr[i] + arr[j] == target?
We only calculate dup once.[1 1 2 2] target = 3: return 1
Q5:sorted array, w/ duplicates. calculate how many pairs of i and j s.t arr[i] + arr[j] == target?
We calculate dup as different.[1 1 2 2] target = 3: return 4 [1a 1b 2a 2b] 1a2a; 1b 2a; 1a 2b;
Q6: leetcode 1 sorted
Q7: leetcode 1: not sorte
Q8:leetcode 66 array
Q9: leetcode 66 as linked list
Q10: String add "123" + "12" =>"135" o(1) space,
//Q8
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; i--) {
if (digits[i] != 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0; //can we delete this? why not?
}
int[] results = new int[n + 1];
results[0] = 1;
return results;
}
}
//Q9
class Solution {
public Node plusOne(Node root) {
if (helper(root)) {
Node newN = new Node(1);
newN.next = root;
return newN;
}
return root;
}
private boolean helper(Node cur) {
if (cur == null) {
return true;
}
// if son returns T, means need to carry 1
if (helper(cur.next)) {
if (cur.val != 9) {
cur.val += 1;
return false;
}
cur.val = 0;
return true;
}
return false;
}
}
//
//Q leetcode 1, not sorted
public int[] twoSum(int[] nums, int target) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
List<Integer> sameVal = map.getOrDefault(nums[i], new ArrayList());
sameVal.add(i);
map.put(nums[i], sameVal);
}
Arrays.sort(nums);
int i = 0;
int j = nums.length - 1;
int[] result = new int[2];
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target ) {
List<Integer> sameVal = map.get(nums[i]);
result[0] = sameVal.get(sameVal.size() - 1);
sameVal.remove(sameVal.size() - 1);
List<Integer> sameVal2 = map.get(nums[j]);
result[1] =sameVal2.get(sameVal2.size() - 1);
sameVal2.remove(sameVal2.size() - 1);
return result;
} else if (sum < target) {
i++;
} else {
j--;
}
}
return result;
}
//Q
public int[] twoSum(int[] nums, int target) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
List<Integer> sameVal = map.getOrDefault(nums[i], new ArrayList());
sameVal.add(i);
map.put(nums[i], sameVal);
}
Arrays.sort(nums);
int i = 0;
int j = nums.length - 1;
int[] result = new int[2];
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target ) {
List<Integer> sameVal = map.get(nums[i]);
result[0] = sameVal.get(sameVal.size() - 1);
sameVal.remove(sameVal.size() - 1);
List<Integer> sameVal2 = map.get(nums[j]);
result[1] =sameVal2.get(sameVal2.size() - 1);
sameVal2.remove(sameVal2.size() - 1);
return result;
} else if (sum < target) {
i++;
} else {
j--;
}
}
return result;
}|
//Q1
class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return null;
}
Map<Integer,Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = map.get(target - nums[i]);
result[1] = i;
return result;
} else {
map.put(nums[i], i);
}
}
return result;
}}
//
int i = 0;
int j = n - 1;
int count = 0;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum < target) {
i++;
} else (if sum > target) {
j--;
} else {
if (arr[i] = arr[j]) {
int num = j - i + 1;
count += (num - 1) * num / 2;
} else {
int countI = 1;
int countJ = 1;
while (i + 1 < j && arr[i + 1] == arr[i]) {
//while (i + 1 < n && arr[i + 1] == arr[i]) {
i++; //容易漏
countI++;
}
while (j - 1 > i && arr[j - 1] == arr[i]) {
//while (j - 1 >= 0 && arr[j - 1] == arr[i]) {
j--;
countJ++;
}
count += countI * countJ;
i++; //容易漏
j--;
}
}
}
return count;
//int i = 0;
int j = n - 1;
int count = 0;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum < target) {
i++;
} else (if sum > target) {
j--;
} else {
count++;
while (i + 1 < j && arr[i + 1] == arr[i]) {
//while (i + 1 < n && arr[i + 1] == arr[i]) {
i++;
}
i++;
j--;
}
}
//Q3
int i = 0;
int j = n - 1;
int count = 0;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum < target) {
i++; //第一次写反了, j--
} else (if sum > target) {
j--;
} else {
count++;
i++;
j--;
}
}
//Q:653
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return helper(root, k, set);
}
private boolean helper(TreeNode root, int k, Set<Integer> set) {
if (root == null) {
return false;
}
if (set.contains(k - root.val)) {
return true;
}
set.add(root.val);
if (helper(root.left, k , set) || helper(root.right, k, set)) {
return true;
}
return false;
}
}
//Q252
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public boolean canAttendMeetings(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return true;
}
Arrays.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval o1, Interval o2) {
return Integer.compare(o1.start, o2.start);
}
});
Interval pre = intervals[0];
for (int i = 1; i < intervals.length; i++) {
Interval next = intervals[i];
if (next.start < pre.end) {
return false;
}
pre.end = Math.max(pre.end, next.end);
}
return true;
}
}
//Q10
int m = s1.size();
int n = s2.size();
int i = m - 1;
int j = n - 1;
StringBuilder sb = new StringBuilder();
int carry = 0;
while(i >= 0 && j >= 0) {
int tmp = carry + s1.charAt(i) + s1.charAt(j) - 2 * '0';
int cur = tmp % 10;
int carry = tmp >= 10 ? 1 : 0;
sb.append(cur.toChar());
}
addRemaining(i, j);
return sb.toString().reverse();
