shortest indices must be next to each other
40.87 %
class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
if (words == null || words.length < 2) {
return -1;
}
int p1 = -1;
int p2 = -1;
int min = words.length;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p1 = i;
}
if (words[i].equals(word2)) {
p2 = i;
}
if (p1 != -1 && p2 != -1) {
min = Math.min(min, Math.abs(p1 - p2));
}
}
return min;
}
}
Sunday, October 7, 2018
167. Two Sum II - Input array is sorted
二刷 06/2022
Time O(N)
Space O(1)
Runtime: 2 ms, faster than 68.16% of Java online submissions for Two Sum II - Input Array Is Sorted.
Memory Usage: 49.8 MB, less than 61.71% of Java online submissions for Two Sum II - Input Array Is Sorted.
class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return new int[0];
}
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}
Sorted -> Time O(N)
100.00 %
class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
return new int[0];
}
int left = 0;
int right = numbers.length - 1;
int sum = 0;
while (left < right) {
sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}
259. 3Sum Smaller
二刷 06/2022
Version #1 Two Pointers
写了一个bug就是以为nums[i] > target就可以终止，但是实际上如果nums[i]是负数，那么再加上一个比它略大的负数，sum还是可以继续变小的
所以正确的判断是nums[i] > 0 && nums[i] >= target再停止
Time O(N^2)
Space O(1)
Runtime: 6 ms, faster than 97.74% of Java online submissions for 3Sum Smaller.
Memory Usage: 43.3 MB, less than 46.03% of Java online submissions for 3Sum Smaller.
class Solution {
public int threeSumSmaller(int[] nums, int target) {
// 1 2 3 4 5
// l r
// when we are seeing that nums[l] + nums[r] < target, we know for current l pointer, all indicies between (i, j] could sum up to a smaller than target number
// so that we add (j - i) to the final result and increment l pointer by 1
Arrays.sort(nums);
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0 && nums[i] >= target) {
return cnt;
}
int left = i + 1, right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
cnt += right - left;
left++;
} else {
right--;
}
}
}
return cnt;
}
}
一刷
Version #1 Two PointerTime O(n^2)
在two pointer的时候，如果以左指针为判断条件，left++的话，终止条件是sum >= target是一个不符合的条件，就很容易写错
相反以right指针向左扫，停下的时候就是符合条件的，所以就是正确的
(left, right]都是right的valid值
一共有right - left个
class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}
Arrays.sort(nums);
int count = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
int left = i + 1;
int right = len - 1;
while (left < right) {
while (left < right && nums[i] + nums[left] + nums[right] >= target) {
right--;
}
count += right - left;
// i l r
// [-2,0,1,3]
left++;
}
}
return count;
}
}
917. Reverse Only Letters
Version #1 Two Pointers
class Solution {
public String reverseOnlyLetters(String S) {
if (S == null || S.length() == 0) {
return S;
}
char[] chars = S.toCharArray();
int left = 0;
int right = S.length() - 1;
while (left < right) {
while (left < right && !Character.isLetter(chars[left])) {
left++;
}
while (left < right && !Character.isLetter(chars[right])) {
right--;
}
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}
}
Saturday, October 6, 2018
86. Partition List
三刷 07/2022
和一刷一样，又一次写出了cycle的bug
原因是larger half的最后一个点有可能是指向smaller half的某个点的
这样连接起来就会成环
所以要不然是向二刷的做法每一次都把后面的pointer切断，要么是一刷的做法把larger point.next设置为null
Time O(N)
Space O(1)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Partition List.
Memory Usage: 42 MB, less than 83.95% of Java online submissions for Partition List.
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallHead = new ListNode(0);
ListNode pSmall = smallHead;
ListNode largeHead = new ListNode(0);
ListNode pLarge = largeHead;
ListNode curr = head;
while (curr != null) {
if (curr.val < x) {
pSmall.next = curr;
pSmall = pSmall.next;
} else {
pLarge.next = curr;
pLarge = pLarge.next;
}
curr = curr.next;
}
pLarge.next = null;
pSmall.next = largeHead.next;
return smallHead.next;
}
}
二刷 05/2022
Runtime: 0 ms, faster than 100.00% of Java online submissions for Partition List.
Memory Usage: 43.2 MB, less than 13.90% of Java online submissions for Partition 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 partition(ListNode head, int x) {
if (head == null) {
return head;
}
ListNode less = new ListNode();
ListNode greaterOrEqual = new ListNode();
ListNode curr = head, lp = less, gp = greaterOrEqual;
while (curr != null) {
if (curr.val < x) {
lp.next = curr;
lp = lp.next;
curr = curr.next;
lp.next = null;
} else {
gp.next = curr;
gp = gp.next;
curr = curr.next;
gp.next = null;
}
}
lp.next = greaterOrEqual.next;
return less.next;
}
}
一刷
Bug 最后largerCurr.next = null否则会有cycle
100.00 %
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode curr = head;
head = new ListNode(0);
ListNode largerHead = new ListNode(0);
ListNode smallerCurr = head;
ListNode largerCurr = largerHead;
while (curr != null) {
if (curr.val < x) {
smallerCurr.next = curr;
smallerCurr = smallerCurr.next;
} else {
largerCurr.next = curr;
largerCurr = largerCurr.next;
}
curr = curr.next;
}
largerCurr.next = null;
smallerCurr.next = largerHead.next;
return head.next;
}
}
Tuesday, October 2, 2018
707. Design Linked List
95.67 %
class MyLinkedList {
class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
}
private Node head;
private Node tail;
private int size;
/** Initialize your data structure here. */
public MyLinkedList() {
this.head = new Node(0);
this.tail = new Node(0);
head.next = tail;
tail.prev = head;
this.size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if (index >= this.size) {
return -1;
}
Node curr = head;
while (index >= 0) {
curr = curr.next;
index--;
}
return curr.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
addAtIndex(0, val);
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
addAtIndex(size, val);
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
// index = 1
Node prevNode = head;
while (index > 0) {
prevNode = prevNode.next;
index--;
}
Node nextNode = prevNode.next;
Node curr = new Node(val);
prevNode.next = curr;
curr.prev = prevNode;
curr.next = nextNode;
nextNode.prev = curr;
size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if (index >= size) {
return;
}
Node prevNode = head;
while (index > 0) {
prevNode = prevNode.next;
index--;
}
Node nextNode = prevNode.next.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
size--;
}
}
Monday, October 1, 2018
57. Insert Interval
二刷 06/2022
Version #1 Scan the Array
因为bottle neck是scan the array所以不需要用到binary search
思路就是先把前面不overlap的加上，然后计算overlap的，最后再把后面不overlap的加上
看起来不难但是自己竟然写不出来
Time O(N)
Space O(1)
Runtime: 1 ms, faster than 99.71% of Java online submissions for Insert Interval.
Memory Usage: 44.5 MB, less than 90.60% of Java online submissions for Insert Interval.
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int index = 0;
int start = newInterval[0], end = newInterval[1];
while (index < intervals.length && intervals[index][1] < start) {
result.add(intervals[index++]);
}
while (index < intervals.length && intervals[index][0] <= end) {
start = Math.min(start, intervals[index][0]);
end = Math.max(end, intervals[index][1]);
index++;
}
result.add(new int[]{start, end});
while (index < intervals.length) {
result.add(intervals[index++]);
}
return result.toArray(new int[0][]);
}
}
一刷
一万个edge case
[first]
[newInterval]
[first]
[newInterval]
[second]
[newInterval]
[second]
[newInterval]
left = 1
right = 0
[[3,5],[12,15]] [6,6]100.00 %
class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
result.add(newInterval);
return result;
}
// 1 find the first interval whose end >= newInterval.start
// 2 find the last interval whose start <= newInterval.end
int start = 0;
int end = intervals.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (intervals.get(mid).end < newInterval.start) {
start = mid + 1;
} else {
end = mid;
}
}
Interval first = intervals.get(start);
int left = start;
if (newInterval.end < first.start) {
left--;
} else if (first.end < newInterval.start) {
left++;
}
start = 0;
end = intervals.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (intervals.get(mid).start > newInterval.end) {
end = mid - 1;
} else {
start = mid;
}
}
int right = end;
Interval second = intervals.get(end);
if (second.start > newInterval.end) {
second = intervals.get(start);
right = start;
}
if (newInterval.end < second.start) {
right--;
} else if (second.end < newInterval.start) {
right++;
}
int i = 0;
while (i < left) {
result.add(intervals.get(i));
i++;
}
if (left >= 0 && left < intervals.size()) {
if (intervals.get(left).end >= newInterval.start) {
newInterval.start = Math.min(intervals.get(left).start, newInterval.start);
} else {
result.add(intervals.get(left));
}
}
result.add(newInterval);
if (right >= 0 && right < intervals.size()) {
if (intervals.get(right).start <= newInterval.end) {
newInterval.end = Math.max(intervals.get(right).end, newInterval.end);
} else {
result.add(intervals.get(right));
}
}
i = right + 1;
while (i < intervals.size()) {
result.add(intervals.get(i));
i++;
}
return result;
}
}
Subscribe to:
Posts (Atom)