Version #2 Sort
Version #1 HashSet
68.38 %
class Solution {
public boolean containsDuplicate(int[] nums) {
if (nums == null || nums.length <= 1) return false;
Set<Integer> visited = new HashSet<>();
for (int num : nums) {
if (!visited.add(num)) return true;
}
return false;
}
}
Saturday, September 30, 2017
Wednesday, September 27, 2017
19. Remove Nth Node From End of List
三刷 06/2022
Version #1 Two Passes - get length
Time O(N)
Space O(1)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 43.2 MB, less than 5.08% of Java online submissions for Remove Nth Node From End of List.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curr = head;
int cnt = 0;
// c
// 1
while (curr != null) {
cnt++;
curr = curr.next;
}
// m is zero based index of the node to be deleted
int m = cnt - n;
if (m == 0) {
return head.next;
}
curr = head;
// c
// 1 2 3 - m = 1
while (m-- > 1) {
curr = curr.next;
}
curr.next = curr.next.next;
return head;
}
}
Version #2 One Pass
Time O(N)
Space O(1)
Runtime: 1 ms, faster than 65.32% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 42.8 MB, less than 17.25% of Java online submissions for Remove Nth Node From End of List.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// s
// f
// 1 2 3 4 5
// s
// f
// 1
ListNode slow = head, fast = head;
while (n-- > 0 && fast != null) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
Two pointers
Find a node which is n nodes away from head -> curr
Define prev as the previous node of head
let curr go forward until it reaches tail, and prev also walk in the same pace
When curr reaches null, prev.next is n nodes away from curr -> we should remove prev.next
-> prev.next = prev.next.next
二刷
50.57 %
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//prev p c
//dummy -> 1->2->3->4->5->null
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode curr = head;
while (n > 0) {
curr = curr.next;
n--;
}
while (curr != null) {
prev = prev.next;
curr = curr.next;
}
prev.next = prev.next.next;
return dummy.next;
}
}
一刷
67.80 %
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || n == 0) return head;
// n = 1
//sf
// 1-> 2 -> null
ListNode fast = head;
ListNode slow = head;
while (n-- > 0 && fast != null) {
fast = fast.next;
}
if (fast == null) return head.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
Version #1 Two pass
二刷
99.83 %
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int len = 0;
ListNode curr = head;
while (curr != null) {
len++;
curr = curr.next;
}
// len = 5, target = 0
int target = len - n;
// p
// 1->2->3->4->5
ListNode prev = dummy;
while (target > 0) {
prev = prev.next;
target--;
}
prev.next = prev.next == null ? null : prev.next.next;
return dummy.next;
}
}
一刷
getLength
14.97 %
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || n == 0) return head;
int len = getLength(head);
// e.g. len = 5, n = 2 delete index (5 - 2) = 3
// i 0 1 2 3
// 1->2->null
ListNode curr = head;
if (n == len) return head.next;
for (int i = 0; i < len - n - 1; i++) {
curr = curr.next;
}
curr.next = curr.next.next;
return head;
}
private int getLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}
Friday, September 22, 2017
218. The Skyline Problem
[DONE] Write a int[2] version
四刷
38.16 %
class Solution {
public List<int[]> getSkyline(int[][] buildings) {
// check if the highest hight has changed or not
// int[] 0-represents the x, 0-represents height, minus if it is the end
List<int[]> heights = new ArrayList<>();
for (int[] building : buildings) {
// building[0] -> start
// building[1] -> end
// building[2] -> height
heights.add(new int[]{building[0], building[2]});
heights.add(new int[]{building[1], -building[2]});
}
// compare by x
// if 1 end and 1 start, start should come before end
// if both start, heigher one should come first
// if both end, lower one should come first
Collections.sort(heights, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return b[1] - a[1];
});
// all the points that are under consideration
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(0);
List<int[]> result = new ArrayList<>();
int currHeight = 0;
for (int[] height : heights) {
if (height[1] > 0) {
maxHeap.offer(height[1]);
} else {
maxHeap.remove(-height[1]);
}
if (maxHeap.peek() != currHeight) {
currHeight = maxHeap.peek();
result.add(new int[]{height[0], currHeight});
}
}
return result;
}
}
[3rd TRY]
1 bug -> should have checked if pq is empty before do pq.peek()
51.67 %
class Solution {
class Point {
int x;
int height;
int isEnd; // 0 for start, 1 for end
public Point(int x, int height, int isEnd) {
this.x = x;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
// we keep a list of heights -> if the highest point changes, then it should be added to skyline
// sort by their x positions, we need to know either it is a start point or a end point
// 4 kinds of ties
// if a ends and b starts, a < b, then we want to add b first and then remove a -> start 0, end 1
// if a ends and b starts, a > b, same
// if a,b ends at the same time, then we want to remove the lower one first
// if a,b stars at the same time, then we want to add the higher one first
List<Point> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new Point(building[0], building[2], 0));
list.add(new Point(building[1], building[2], 1));
}
Collections.sort(list, (a, b) -> {
if (a.x != b.x) {
return a.x - b.x;
}
if (a.isEnd != b.isEnd) {
return a.isEnd - b.isEnd; // Always return the start one first
} else if (a.isEnd == 0) {
return b.height - a.height;
} else {
return a.height - b.height;
}
});
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(16, Collections.reverseOrder());
int prevHeight = 0;
List<int[]> result = new ArrayList<>();
for (Point curr : list) {
if (curr.isEnd == 0) { // isStart
maxHeap.add(curr.height);
} else {
maxHeap.remove(curr.height);
}
int currHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
if (currHeight != prevHeight) {
prevHeight = currHeight;
result.add(new int[]{curr.x, currHeight});
}
}
return result;
}
}
二刷
Time O(n^2) -> linear time to remove
Space O(n)
class Solution {
// int[0] -> x, int[1] -> height, int[2] -> 0 start, 1 end
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) {
return result;
}
// buildings[i][0] -> start, buildings[i][1] -> end, buildings[i][2] -> height
List<int[]> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new int[]{building[0], building[2], 0});
list.add(new int[]{building[1], building[2], 1});
}
Collections.sort(list, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else if (a[2] != b[2]) {
// start before end
return a[2] - b[2];
} else if (a[2] == 0) {
// Two start, add the higher one first
return b[1] - a[1];
} else {
// Two end, remove the lower one first
return a[1] - b[1];
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
int currHeight = 0;
int[] curr = null;
for (int i = 0; i < list.size(); i++) {
curr = list.get(i);
if (curr[2] == 0) {
pq.add(curr[1]);
} else {
pq.remove(curr[1]);
}
if (pq.isEmpty()) {
result.add(new int[]{curr[0], 0});
currHeight = 0;
} else if (currHeight != pq.peek()){
result.add(new int[]{curr[0], pq.peek()});
currHeight = pq.peek();
}
}
return result;
}
}
一刷
上面的一个bug要注意如果second largest和之前pop出去的一样高，就不往结果里面加
还有一个是PriorityQueue remove(Object)
是remove single one
59.53 %
class Solution {
class Tuple {
int pos;
int height;
int isEnd; // 0 -> isStart, 1 -> isEnd
public Tuple(int pos, int height, int isEnd) {
this.pos = pos;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) return result;
List<Tuple> tuples = new ArrayList<>();
for (int[] building : buildings) {
// 0 1 2
// [Li, Ri, Hi]
tuples.add(new Tuple(building[0], building[2], 0));
tuples.add(new Tuple(building[1], building[2], 1));
}
// maxHeap
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
Collections.sort(tuples, new Comparator<Tuple>() {
@Override
public int compare(Tuple t1, Tuple t2) {
if (t1.pos != t2.pos) {
return t1.pos - t2.pos;
} else if (t1.isEnd != t2.isEnd) {
// start(0) befor end(1)
return t1.isEnd - t2.isEnd;
} else if (t1.isEnd == 0) {
// if both start, higher before lower
return t2.height - t1.height;
} else {
// if both end, lower before higher
return t1.height - t2.height;
}
}
});
// output [x1,y1] -> [pos, height]
for (int i = 0; i < tuples.size(); i++) {
Tuple curr = tuples.get(i);
// start -> add
if (curr.isEnd == 0) {
if (pq.isEmpty() || curr.height > pq.peek()) {
result.add(new int[]{curr.pos, curr.height});
}
pq.add(curr.height);
} else { // end -> delete
if (pq.peek() == curr.height) {
pq.poll();
if (pq.isEmpty()) {
result.add(new int[]{curr.pos, 0});
} else if (pq.peek() != curr.height){
result.add(new int[]{curr.pos, pq.peek()});
}
} else {
pq.remove(new Integer(curr.height));
}
}
}
return result;
}
}
四刷
38.16 %
class Solution {
public List<int[]> getSkyline(int[][] buildings) {
// check if the highest hight has changed or not
// int[] 0-represents the x, 0-represents height, minus if it is the end
List<int[]> heights = new ArrayList<>();
for (int[] building : buildings) {
// building[0] -> start
// building[1] -> end
// building[2] -> height
heights.add(new int[]{building[0], building[2]});
heights.add(new int[]{building[1], -building[2]});
}
// compare by x
// if 1 end and 1 start, start should come before end
// if both start, heigher one should come first
// if both end, lower one should come first
Collections.sort(heights, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return b[1] - a[1];
});
// all the points that are under consideration
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(0);
List<int[]> result = new ArrayList<>();
int currHeight = 0;
for (int[] height : heights) {
if (height[1] > 0) {
maxHeap.offer(height[1]);
} else {
maxHeap.remove(-height[1]);
}
if (maxHeap.peek() != currHeight) {
currHeight = maxHeap.peek();
result.add(new int[]{height[0], currHeight});
}
}
return result;
}
}
[3rd TRY]
1 bug -> should have checked if pq is empty before do pq.peek()
51.67 %
class Solution {
class Point {
int x;
int height;
int isEnd; // 0 for start, 1 for end
public Point(int x, int height, int isEnd) {
this.x = x;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
// we keep a list of heights -> if the highest point changes, then it should be added to skyline
// sort by their x positions, we need to know either it is a start point or a end point
// 4 kinds of ties
// if a ends and b starts, a < b, then we want to add b first and then remove a -> start 0, end 1
// if a ends and b starts, a > b, same
// if a,b ends at the same time, then we want to remove the lower one first
// if a,b stars at the same time, then we want to add the higher one first
List<Point> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new Point(building[0], building[2], 0));
list.add(new Point(building[1], building[2], 1));
}
Collections.sort(list, (a, b) -> {
if (a.x != b.x) {
return a.x - b.x;
}
if (a.isEnd != b.isEnd) {
return a.isEnd - b.isEnd; // Always return the start one first
} else if (a.isEnd == 0) {
return b.height - a.height;
} else {
return a.height - b.height;
}
});
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(16, Collections.reverseOrder());
int prevHeight = 0;
List<int[]> result = new ArrayList<>();
for (Point curr : list) {
if (curr.isEnd == 0) { // isStart
maxHeap.add(curr.height);
} else {
maxHeap.remove(curr.height);
}
int currHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
if (currHeight != prevHeight) {
prevHeight = currHeight;
result.add(new int[]{curr.x, currHeight});
}
}
return result;
}
}
二刷
Time O(n^2) -> linear time to remove
Space O(n)
class Solution {
// int[0] -> x, int[1] -> height, int[2] -> 0 start, 1 end
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) {
return result;
}
// buildings[i][0] -> start, buildings[i][1] -> end, buildings[i][2] -> height
List<int[]> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new int[]{building[0], building[2], 0});
list.add(new int[]{building[1], building[2], 1});
}
Collections.sort(list, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else if (a[2] != b[2]) {
// start before end
return a[2] - b[2];
} else if (a[2] == 0) {
// Two start, add the higher one first
return b[1] - a[1];
} else {
// Two end, remove the lower one first
return a[1] - b[1];
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
int currHeight = 0;
int[] curr = null;
for (int i = 0; i < list.size(); i++) {
curr = list.get(i);
if (curr[2] == 0) {
pq.add(curr[1]);
} else {
pq.remove(curr[1]);
}
if (pq.isEmpty()) {
result.add(new int[]{curr[0], 0});
currHeight = 0;
} else if (currHeight != pq.peek()){
result.add(new int[]{curr[0], pq.peek()});
currHeight = pq.peek();
}
}
return result;
}
}
一刷
Input:[[0,2,3],[2,5,3]]
Output:[[0,3],[2,3],[5,0]]
Expected:[[0,3],[5,0]]
有四种breaking tie的情况，决定了sort的顺序上面的一个bug要注意如果second largest和之前pop出去的一样高，就不往结果里面加
还有一个是PriorityQueue remove(Object)
是remove single one
59.53 %
class Solution {
class Tuple {
int pos;
int height;
int isEnd; // 0 -> isStart, 1 -> isEnd
public Tuple(int pos, int height, int isEnd) {
this.pos = pos;
this.height = height;
this.isEnd = isEnd;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) return result;
List<Tuple> tuples = new ArrayList<>();
for (int[] building : buildings) {
// 0 1 2
// [Li, Ri, Hi]
tuples.add(new Tuple(building[0], building[2], 0));
tuples.add(new Tuple(building[1], building[2], 1));
}
// maxHeap
PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
Collections.sort(tuples, new Comparator<Tuple>() {
@Override
public int compare(Tuple t1, Tuple t2) {
if (t1.pos != t2.pos) {
return t1.pos - t2.pos;
} else if (t1.isEnd != t2.isEnd) {
// start(0) befor end(1)
return t1.isEnd - t2.isEnd;
} else if (t1.isEnd == 0) {
// if both start, higher before lower
return t2.height - t1.height;
} else {
// if both end, lower before higher
return t1.height - t2.height;
}
}
});
// output [x1,y1] -> [pos, height]
for (int i = 0; i < tuples.size(); i++) {
Tuple curr = tuples.get(i);
// start -> add
if (curr.isEnd == 0) {
if (pq.isEmpty() || curr.height > pq.peek()) {
result.add(new int[]{curr.pos, curr.height});
}
pq.add(curr.height);
} else { // end -> delete
if (pq.peek() == curr.height) {
pq.poll();
if (pq.isEmpty()) {
result.add(new int[]{curr.pos, 0});
} else if (pq.peek() != curr.height){
result.add(new int[]{curr.pos, pq.peek()});
}
} else {
pq.remove(new Integer(curr.height));
}
}
}
return result;
}
}
Wednesday, September 20, 2017
393. UTF-8 Validation
报错的算是一个edge case
如果只有1byte，应该是0 开头
也就是说不存在只有一个1开头的meta data
Input:[145]
Output:true
Expected:false
1001000168.61 %
class Solution {
public boolean validUtf8(int[] data) {
if (data == null || data.length == 0) return false;
return helper(data, 0, 0);
}
private boolean helper(int[] data, int index, int toMatch) {
if (index == data.length) return toMatch == 0;
int curr = data[index];
if (toMatch != 0) {
if (curr >> 6 != 0b10) return false;
else return helper(data, index + 1, toMatch - 1);
}
// get the count of 1s
int count = 0;
int bit = 7;
while ((curr & (1 << bit--)) != 0) {
count++;
}
// can't be 1 since 1 byte is a special case
// can't be more than 4 bytes
if (count == 1 || count > 4) return false;
count = count == 0 ? 0 : count - 1;
return helper(data, index + 1, count);
}
}
Tuesday, September 19, 2017
219. Contains Duplicate II
二刷
Versuib #2 Sliding Window
14.63 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null) {
return false;
}
// sliding window of size k
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.size() > k) {
set.remove(nums[i - k - 1]);
}
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
}
return false;
}
}
Version #1 第一反应还是写了hashmap
Seems like this problem is actually a sliding window problem
81.40 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// key-> num, value -> index
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer index = map.get(nums[i]);
if (index != null && i - index <= k) {
return true;
}
map.put(nums[i], i);
}
return false;
}
}
一刷
Version #2 HashSet(Better)
82.57 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) return false;
// set of numbers in the sliding window
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
// i - j <= k -> j >= i - k
if (i - k > 0) {
set.remove(nums[i - k - 1]);
}
if (!set.add(nums[i])) return true;
}
return false;
}
}
Version #1 HashMap
看了答案发现自己这么写很烂
这个题有点像sliding window
只要用set看window里面有没有重复值就可以了
9.84 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) return false;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int prev = map.getOrDefault(nums[i], -1);
if (prev != -1 && i - prev <= k) {
return true;
} else {
map.put(nums[i], i);
}
}
return false;
}
}
Versuib #2 Sliding Window
14.63 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null) {
return false;
}
// sliding window of size k
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.size() > k) {
set.remove(nums[i - k - 1]);
}
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
}
return false;
}
}
Version #1 第一反应还是写了hashmap
Seems like this problem is actually a sliding window problem
81.40 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// key-> num, value -> index
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer index = map.get(nums[i]);
if (index != null && i - index <= k) {
return true;
}
map.put(nums[i], i);
}
return false;
}
}
一刷
Version #2 HashSet(Better)
82.57 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) return false;
// set of numbers in the sliding window
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
// i - j <= k -> j >= i - k
if (i - k > 0) {
set.remove(nums[i - k - 1]);
}
if (!set.add(nums[i])) return true;
}
return false;
}
}
Version #1 HashMap
看了答案发现自己这么写很烂
这个题有点像sliding window
只要用set看window里面有没有重复值就可以了
9.84 %
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) return false;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int prev = map.getOrDefault(nums[i], -1);
if (prev != -1 && i - prev <= k) {
return true;
} else {
map.put(nums[i], i);
}
}
return false;
}
}
253. Meeting Rooms II
三刷
Version #3 Sort start & end at the same time
3.68 %
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
List<int[]> list = new ArrayList<>();
for (Interval interval : intervals) {
list.add(new int[]{interval.start, 1});
list.add(new int[]{interval.end, -1});
}
Collections.sort(list, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1]; // end happens before start
return a[0] - b[0];
});
int count = 0;
int result = 0;
for (int i = 0; i < list.size(); i++) {
count += list.get(i)[1];
result = Math.max(result, count);
}
return result;
}
}
Version #2
sort start & end separately
用count表示现在有的meeting rooms的数量
如果有meeting结束 可以把后面的放进vacant的room
如果没有结束的meeting 就需要增加rooms的数量
81.05 %
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
int length = intervals.length;
int[] starts = new int[length];
int[] ends = new int[length];
for (int i = 0; i < length; i++) {
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
}
Arrays.sort(starts);
Arrays.sort(ends);
int count = 0;
int pEnd = 0;
for (int pStart = 0; pStart < length; pStart++) {
if (starts[pStart] < ends[pEnd]) {
count++;
} else {
pEnd++;
}
}
return count;
}
}
Version #1 Naive Sort Intervals Version
重点是breaking tie
看到discuss里面还有用heap和分别sort start&end的方法，懒得看了
49.06 %
class Solution {
class Tuple implements Comparable<Tuple> {
int time;
int isStart; //start -> 1, end -> 0
public Tuple(int time, int isStart) {
this.time = time;
this.isStart = isStart;
}
@Override
public int compareTo(Tuple that) {
if (this.time != that.time) {
return this.time - that.time;
} else {
return this.isStart - that.isStart;
}
}
}
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
List<Tuple> times = new ArrayList<>();
for (Interval i : intervals) {
times.add(new Tuple(i.start, 1));
times.add(new Tuple(i.end, 0));
}
Collections.sort(times);
int max = 0;
int count = 0;
for (Tuple tuple : times) {
if (tuple.isStart == 1) {
count++;
max = Math.max(count, max);
} else {
count--;
}
}
return max;
}
}
Version #3 Sort start & end at the same time
3.68 %
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
List<int[]> list = new ArrayList<>();
for (Interval interval : intervals) {
list.add(new int[]{interval.start, 1});
list.add(new int[]{interval.end, -1});
}
Collections.sort(list, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1]; // end happens before start
return a[0] - b[0];
});
int count = 0;
int result = 0;
for (int i = 0; i < list.size(); i++) {
count += list.get(i)[1];
result = Math.max(result, count);
}
return result;
}
}
Version #2
sort start & end separately
用count表示现在有的meeting rooms的数量
如果有meeting结束 可以把后面的放进vacant的room
如果没有结束的meeting 就需要增加rooms的数量
81.05 %
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
int length = intervals.length;
int[] starts = new int[length];
int[] ends = new int[length];
for (int i = 0; i < length; i++) {
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
}
Arrays.sort(starts);
Arrays.sort(ends);
int count = 0;
int pEnd = 0;
for (int pStart = 0; pStart < length; pStart++) {
if (starts[pStart] < ends[pEnd]) {
count++;
} else {
pEnd++;
}
}
return count;
}
}
Version #1 Naive Sort Intervals Version
重点是breaking tie
看到discuss里面还有用heap和分别sort start&end的方法，懒得看了
49.06 %
class Solution {
class Tuple implements Comparable<Tuple> {
int time;
int isStart; //start -> 1, end -> 0
public Tuple(int time, int isStart) {
this.time = time;
this.isStart = isStart;
}
@Override
public int compareTo(Tuple that) {
if (this.time != that.time) {
return this.time - that.time;
} else {
return this.isStart - that.isStart;
}
}
}
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
List<Tuple> times = new ArrayList<>();
for (Interval i : intervals) {
times.add(new Tuple(i.start, 1));
times.add(new Tuple(i.end, 0));
}
Collections.sort(times);
int max = 0;
int count = 0;
for (Tuple tuple : times) {
if (tuple.isStart == 1) {
count++;
max = Math.max(count, max);
} else {
count--;
}
}
return max;
}
}
416. Partition Equal Subset Sum
二刷 07/2022
Version #1 0/1 Knapsack
Time O(N * Sum)
Space O(N * Sum)
Runtime: 26 ms, faster than 91.77% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 43.5 MB, less than 75.86% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int target = 0;
for (int num : nums) {
target += num;
}
if (target % 2 != 0) {
return false;
}
target /= 2;
// dp[i][s] - [0, i) numbers can add up to s
boolean[][] dp = new boolean[nums.length + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= nums.length; i++) {
for (int j = target; j >= 0; j--) {
if (dp[i - 1][j] || (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]])) {
dp[i][j] = true;
}
}
if (dp[i][target]) {
return true;
}
}
return dp[nums.length][target];
}
}
Version #2 HashSet
Time O(N * Sum of all numbers)
Space O(Sum of all numbers)
Runtime: 410 ms, faster than 5.82% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 117.8 MB, less than 6.46% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int target = 0;
for (int num : nums) {
target += num;
}
if (target % 2 != 0) {
return false;
}
target /= 2;
Set<Integer> visited = new HashSet<>();
visited.add(0);
for (int num : nums) {
Set<Integer> newSum = new HashSet<>();
for (int prev : visited) {
if (prev + num == target) {
return true;
}
newSum.add(prev + num);
}
visited.addAll(newSum);
}
return false;
}
}
一刷 06/2022
Version #1 0/1 Knapsack DP
It could be optimized to 1d DP
Time O(N*Sum)
Space O(N*Sum)
Runtime: 51 ms, faster than 61.41% of Java online submissions for Partition Equal Subset Sum.
Memory Usage: 54.3 MB, less than 44.88% of Java online submissions for Partition Equal Subset Sum.
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum /= 2;
// System.out.printf("sum=%d\n", sum);
// The [0, i) numbers can sum up to j
boolean[][] dp = new boolean[nums.length + 1][sum + 1];
// The first 0 number can sum up to 0
dp[0][0] = true;
for (int i = 1; i <= nums.length; i++) {
// the nums[i - 1] item
int num = nums[i - 1];
for (int j = 0; j < sum + 1; j++) {
if (num <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
if (dp[i][sum]) {
return true;
}
}
return dp[nums.length][sum];
}
}
297. Serialize and Deserialize Binary Tree
参考 449. Serialize and Deserialize BST
Version #5 Byte Manipulation
这个方法是把Integer直接变成string给改成byte 表示法，可以压缩space
String ->
-2^31 = -2147483648 -> 11 chars
https://www.javamex.com/tutorials/memory/string_memory_usage.shtml
Byte -> 0xFFFFFFFF
4 bytes
No string-integer conversion needed
如果是 int -> byte[] -> char[] 的话，转换回来的时候
如果不
// return (int) ((data[0] & 0xff) << 24)
// | ((data[1] & 0xff) << 16)
// | ((data[2] & 0xff) << 8)
// | (data[3] & 0xff);
就会出错
然而如果直接 int -> char[]就不需要考虑这个问题，因为在int -> char[] 的时候已经
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
了
99.15 %
public class Codec {
private char NULL_VALUE = '0';
private char NOT_NULL_VALUE = '1';
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NULL_VALUE);
return;
}
char[] array = int2Bytes(node.val);
sb.append(NOT_NULL_VALUE).append(array[0]).append(array[1]).append(array[2]).append(array[3]);
seHelper(node.left, sb);
seHelper(node.right, sb);
}
private char[] int2Bytes(int x) {
return new char[]{
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
};
}
// Decodes your encoded data to tree.
private int index;
public TreeNode deserialize(String data) {
index = 0;
return deHelper(data.toCharArray());
}
private TreeNode deHelper(char[] data) {
if (data[index++] == NULL_VALUE) {
return null;
}
TreeNode node = new TreeNode(bytes2Int(new char[]{
data[index],
data[index + 1],
data[index + 2],
data[index + 3]
}));
index += 4;
node.left = deHelper(data);
node.right = deHelper(data);
return node;
}
private int bytes2Int(char[] data) {
return (int) (data[0] << 24)
| (data[1] << 16)
| (data[2] << 8)
| data[3];
}
}
Version #3 Iteration with Stack
二刷
看一刷的不知道自己在写什么。。。为什么需要一个boolean来判断是不是left？
Stack 加的时候注意是先左后右
Stack deserialize的时候，都是向左走到底，然后向右跳一个
39.88 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stack = new LinkedList<>();
stack.addFirst(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.removeFirst();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
stack.addFirst(curr.right);
stack.addFirst(curr.left);
}
}
System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Deque<TreeNode> stack = new LinkedList<>();
int pointer = 0;
if (strs.length == 0 || strs[pointer].equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
TreeNode curr = root;
stack.addFirst(root);
pointer++;
while (pointer < strs.length) {
while (curr != null) {
stack.addFirst(curr);
curr.left = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.left;
}
curr = stack.removeFirst();
curr.right = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.right;
}
return root;
}
}
一刷
Iteration desirialization 好难啊，写了好久好久好久
stack里面放的是已经连完左节点但是等待右subtree的点
curr代表的是当下等待连左节点的点
如果遇到null
1st -> 证明当前curr的left subtree是null
当前curr已经是Left most node
开始往外pop
2nd -> 在pop round，pop出的点是waiting for its right subtree
此时遇到null 证明当前点的right subtree是NULL
直接继续pop
37.48 %
public class Codec {
private static final String DIVIDER = "/";
private static final String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return null;
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
sb.append(curr.val);
sb.append(DIVIDER);
stack.push(curr);
curr = curr.left;
} else {
sb.append(NULL + DIVIDER);
curr = stack.pop();
curr = curr.right;
}
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) return null;
String[] strs = data.trim().split(DIVIDER);
int index = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[index++]));
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
stack.push(curr);
int n = strs.length;
// Nodes in stack -> waiting for their right subtree
// curr -> waiting for its left subtree
while (index < n) {
while (index < n && !strs[index].equals(NULL)) {
curr.left = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.left;
stack.push(curr);
}
// Top nodes left subtree is null, get the next candidate node
while (index < n && strs[index].equals(NULL)) {
curr = stack.pop();
index++;
}
// strs[index] is not NULL
if (index < n) {
curr.right = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.right;
stack.push(curr);
}
}
return root;
}
}
Version #4 Recursion DFS
Pre-Order Traversal
注意pointer是一个global变量，每一次recursion的当前层负责给pointer + 1
二刷
94.28 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
return;
}
sb.append(node.val + ",");
seHelper(node.left, sb);
seHelper(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
int[] pointer = new int[]{0};
return deHelper(strs, pointer);
}
private TreeNode deHelper(String[] strs, int[] pointer) {
if (strs[pointer[0]].equals("#")) {
pointer[0]++;
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(strs[pointer[0]]));
pointer[0]++;
node.left = deHelper(strs, pointer);
node.right = deHelper(strs, pointer);
return node;
}
}
Version #1 jiuzhang Version BFS with Queue
二刷
49.87 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return null;
}
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
que.offer(curr.left);
que.offer(curr.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
if (strs.length == 0) {
return null;
}
int pointer = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[pointer++]));
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
TreeNode left = null;
if (!strs[pointer].equals("#")) {
left = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(left);
}
pointer++;
curr.left = left;
TreeNode right = null;
if (!strs[pointer].equals("#")) {
right = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(right);
}
pointer++;
curr.right = right;
}
return root;
}
}
一刷
49.35 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "{}";
ArrayList<TreeNode> que = new ArrayList<>();
que.add(root);
TreeNode curr = null;
for (int i = 0; i < que.size(); i++) {
curr = que.get(i);
if (curr == null) continue;
que.add(curr.left);
que.add(curr.right);
}
StringBuilder sb = new StringBuilder();
sb.append("{");
curr = que.get(0);
int index = 1;
sb.append(String.valueOf(curr.val));
while (index < que.size()) {
curr = que.get(index);
index++;
sb.append(",");
if (curr == null) sb.append("#");
else sb.append(String.valueOf(curr.val));
}
sb.append("}");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("{}")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < vals.length; i++) {
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Version #2
57.60 %
自己改进了一下感觉比上个方法简洁一点 就是传统地用queue
上个方法里面用ArrayList作为Queue然后用get(index) 来代替queue.poll()感觉也挺有意思的
注意！string == "#"是不对的 必须string.equals("#");
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
TreeNode curr = null;
while (!que.isEmpty()) {
curr = que.poll();
if (curr == null) {
sb.append("#,");
continue;
} else {
sb.append(String.valueOf(curr.val));
sb.append(",");
}
que.add(curr.left);
que.add(curr.right);
}
char c = sb.charAt(sb.length() - 1);
do {
sb.deleteCharAt(sb.length() - 1);
c = sb.charAt(sb.length() - 1);
} while (c == '#' || c == ',');
//System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == "") return null;
String[] vals = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
que.add(root);
TreeNode curr = null;
boolean isLeft = true;
for (int index = 1; index < vals.length; index++) {
if (vals[index].equals("#")) {
curr = null;
} else {
curr = new TreeNode(Integer.valueOf(vals[index]));
que.add(curr);
}
if (isLeft) {
que.peek().left = curr;
} else {
que.poll().right = curr;
}
isLeft = !isLeft;
}
return root;
}
}
Version #5 Byte Manipulation
这个方法是把Integer直接变成string给改成byte 表示法，可以压缩space
String ->
-2^31 = -2147483648 -> 11 chars
https://www.javamex.com/tutorials/memory/string_memory_usage.shtml
Byte -> 0xFFFFFFFF
4 bytes
No string-integer conversion needed
如果是 int -> byte[] -> char[] 的话，转换回来的时候
如果不
// return (int) ((data[0] & 0xff) << 24)
// | ((data[1] & 0xff) << 16)
// | ((data[2] & 0xff) << 8)
// | (data[3] & 0xff);
就会出错
然而如果直接 int -> char[]就不需要考虑这个问题，因为在int -> char[] 的时候已经
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
了
99.15 %
public class Codec {
private char NULL_VALUE = '0';
private char NOT_NULL_VALUE = '1';
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NULL_VALUE);
return;
}
char[] array = int2Bytes(node.val);
sb.append(NOT_NULL_VALUE).append(array[0]).append(array[1]).append(array[2]).append(array[3]);
seHelper(node.left, sb);
seHelper(node.right, sb);
}
private char[] int2Bytes(int x) {
return new char[]{
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
};
}
// Decodes your encoded data to tree.
private int index;
public TreeNode deserialize(String data) {
index = 0;
return deHelper(data.toCharArray());
}
private TreeNode deHelper(char[] data) {
if (data[index++] == NULL_VALUE) {
return null;
}
TreeNode node = new TreeNode(bytes2Int(new char[]{
data[index],
data[index + 1],
data[index + 2],
data[index + 3]
}));
index += 4;
node.left = deHelper(data);
node.right = deHelper(data);
return node;
}
private int bytes2Int(char[] data) {
return (int) (data[0] << 24)
| (data[1] << 16)
| (data[2] << 8)
| data[3];
}
}
Version #3 Iteration with Stack
二刷
看一刷的不知道自己在写什么。。。为什么需要一个boolean来判断是不是left？
Stack 加的时候注意是先左后右
Stack deserialize的时候，都是向左走到底，然后向右跳一个
39.88 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stack = new LinkedList<>();
stack.addFirst(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.removeFirst();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
stack.addFirst(curr.right);
stack.addFirst(curr.left);
}
}
System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Deque<TreeNode> stack = new LinkedList<>();
int pointer = 0;
if (strs.length == 0 || strs[pointer].equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
TreeNode curr = root;
stack.addFirst(root);
pointer++;
while (pointer < strs.length) {
while (curr != null) {
stack.addFirst(curr);
curr.left = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.left;
}
curr = stack.removeFirst();
curr.right = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.right;
}
return root;
}
}
一刷
Iteration desirialization 好难啊，写了好久好久好久
stack里面放的是已经连完左节点但是等待右subtree的点
curr代表的是当下等待连左节点的点
如果遇到null
1st -> 证明当前curr的left subtree是null
当前curr已经是Left most node
开始往外pop
2nd -> 在pop round，pop出的点是waiting for its right subtree
此时遇到null 证明当前点的right subtree是NULL
直接继续pop
37.48 %
public class Codec {
private static final String DIVIDER = "/";
private static final String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return null;
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
sb.append(curr.val);
sb.append(DIVIDER);
stack.push(curr);
curr = curr.left;
} else {
sb.append(NULL + DIVIDER);
curr = stack.pop();
curr = curr.right;
}
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) return null;
String[] strs = data.trim().split(DIVIDER);
int index = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[index++]));
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
stack.push(curr);
int n = strs.length;
// Nodes in stack -> waiting for their right subtree
// curr -> waiting for its left subtree
while (index < n) {
while (index < n && !strs[index].equals(NULL)) {
curr.left = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.left;
stack.push(curr);
}
// Top nodes left subtree is null, get the next candidate node
while (index < n && strs[index].equals(NULL)) {
curr = stack.pop();
index++;
}
// strs[index] is not NULL
if (index < n) {
curr.right = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.right;
stack.push(curr);
}
}
return root;
}
}
Version #4 Recursion DFS
Pre-Order Traversal
注意pointer是一个global变量，每一次recursion的当前层负责给pointer + 1
二刷
94.28 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
return;
}
sb.append(node.val + ",");
seHelper(node.left, sb);
seHelper(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
int[] pointer = new int[]{0};
return deHelper(strs, pointer);
}
private TreeNode deHelper(String[] strs, int[] pointer) {
if (strs[pointer[0]].equals("#")) {
pointer[0]++;
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(strs[pointer[0]]));
pointer[0]++;
node.left = deHelper(strs, pointer);
node.right = deHelper(strs, pointer);
return node;
}
}
Version #1 jiuzhang Version BFS with Queue
二刷
49.87 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return null;
}
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
que.offer(curr.left);
que.offer(curr.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
if (strs.length == 0) {
return null;
}
int pointer = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[pointer++]));
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
TreeNode left = null;
if (!strs[pointer].equals("#")) {
left = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(left);
}
pointer++;
curr.left = left;
TreeNode right = null;
if (!strs[pointer].equals("#")) {
right = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(right);
}
pointer++;
curr.right = right;
}
return root;
}
}
一刷
49.35 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "{}";
ArrayList<TreeNode> que = new ArrayList<>();
que.add(root);
TreeNode curr = null;
for (int i = 0; i < que.size(); i++) {
curr = que.get(i);
if (curr == null) continue;
que.add(curr.left);
que.add(curr.right);
}
StringBuilder sb = new StringBuilder();
sb.append("{");
curr = que.get(0);
int index = 1;
sb.append(String.valueOf(curr.val));
while (index < que.size()) {
curr = que.get(index);
index++;
sb.append(",");
if (curr == null) sb.append("#");
else sb.append(String.valueOf(curr.val));
}
sb.append("}");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("{}")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < vals.length; i++) {
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Version #2
自己改进了一下感觉比上个方法简洁一点 就是传统地用queue
上个方法里面用ArrayList作为Queue然后用get(index) 来代替queue.poll()感觉也挺有意思的
注意！string == "#"是不对的 必须string.equals("#");
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
TreeNode curr = null;
while (!que.isEmpty()) {
curr = que.poll();
if (curr == null) {
sb.append("#,");
continue;
} else {
sb.append(String.valueOf(curr.val));
sb.append(",");
}
que.add(curr.left);
que.add(curr.right);
}
char c = sb.charAt(sb.length() - 1);
do {
sb.deleteCharAt(sb.length() - 1);
c = sb.charAt(sb.length() - 1);
} while (c == '#' || c == ',');
//System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == "") return null;
String[] vals = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
que.add(root);
TreeNode curr = null;
boolean isLeft = true;
for (int index = 1; index < vals.length; index++) {
if (vals[index].equals("#")) {
curr = null;
} else {
curr = new TreeNode(Integer.valueOf(vals[index]));
que.add(curr);
}
if (isLeft) {
que.peek().left = curr;
} else {
que.poll().right = curr;
}
isLeft = !isLeft;
}
return root;
}
}
373. Find K Pairs with Smallest Sums
Version #1 MinHeap with Lambda
41.23 %
class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<>();
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return result;
// minHeap -> always poll out the minimum sum and add its adjacent sums
PriorityQueue<int[]> minHeap = new PriorityQueue<>(10, (pairA, pairB) ->
(nums1[pairA[0]] + nums2[pairA[1]]) - (nums1[pairB[0]] + nums2[pairB[1]]));
minHeap.offer(new int[]{0, 0});
while (k-- > 0 && !minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int i1 = curr[0];
int i2 = curr[1];
result.add(new int[]{nums1[i1], nums2[i2]});
if (i1 == 0 && (i2 + 1 < nums2.length)) minHeap.offer(new int[]{i1, i2 + 1});
if (i1 + 1 < nums1.length) minHeap.offer(new int[]{i1 + 1, i2});
}
return result;
}
}
Version #2 Self-defined class -> Tuple with is own compareTo method
LC上看到的，拿过来做reference
如果lambda写不好可以参考这个方法
92.17 %
"public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(); int m = nums1.length, n = nums2.length; List<int[]> res = new ArrayList<int[]>(); if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res; for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j])); for(int i = 0; i < Math.min(k, m *n); i++) { Tuple t = pq.poll(); res.add(new int[]{nums1[t.x], nums2[t.y]}); if(t.x == m - 1) continue; pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y])); } return res; } } class Tuple implements Comparable<Tuple> { int x, y, val; public Tuple (int x, int y, int val) { this.x = x; this.y = y; this.val = val; } public int compareTo (Tuple that) { return this.val - that.val; } }"
41.23 %
class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<>();
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return result;
// minHeap -> always poll out the minimum sum and add its adjacent sums
PriorityQueue<int[]> minHeap = new PriorityQueue<>(10, (pairA, pairB) ->
(nums1[pairA[0]] + nums2[pairA[1]]) - (nums1[pairB[0]] + nums2[pairB[1]]));
minHeap.offer(new int[]{0, 0});
while (k-- > 0 && !minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int i1 = curr[0];
int i2 = curr[1];
result.add(new int[]{nums1[i1], nums2[i2]});
if (i1 == 0 && (i2 + 1 < nums2.length)) minHeap.offer(new int[]{i1, i2 + 1});
if (i1 + 1 < nums1.length) minHeap.offer(new int[]{i1 + 1, i2});
}
return result;
}
}
Version #2 Self-defined class -> Tuple with is own compareTo method
LC上看到的，拿过来做reference
如果lambda写不好可以参考这个方法
92.17 %
"public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(); int m = nums1.length, n = nums2.length; List<int[]> res = new ArrayList<int[]>(); if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res; for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j])); for(int i = 0; i < Math.min(k, m *n); i++) { Tuple t = pq.poll(); res.add(new int[]{nums1[t.x], nums2[t.y]}); if(t.x == m - 1) continue; pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y])); } return res; } } class Tuple implements Comparable<Tuple> { int x, y, val; public Tuple (int x, int y, int val) { this.x = x; this.y = y; this.val = val; } public int compareTo (Tuple that) { return this.val - that.val; } }"
Subscribe to:
Posts (Atom)