一刷 08/2022
Version #1 Divide by 3
Time O(logN)
Space O(1)
class Solution {
public boolean isPowerOfThree(int n) {
if (n == 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}
一刷 08/2022
Version #1 Divide by 4
Time O(logN)
Space O(1)
class Solution {
public boolean isPowerOfFour(int n) {
if (n == 0) {
return false;
}
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
}
一刷 08/2022
Version #1 HashMap + sorting
Time - N is array length, create the hash map O(N), sort the count worst case O(NlogN) - total O(NlogN)
Space - O(N)
class Solution {
public int minSetSize(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer> counts = new ArrayList<>(map.values());
Collections.sort(counts, Collections.reverseOrder());
// 0 1
int want = arr.length / 2 + arr.length % 2;
int i = 0;
while (want > 0) {
want -= counts.get(i++);
}
return i;
}
}
一刷 08/2022
Version #1 Sliding Window
感觉这个的重点是sliding window invalid的时候不skip而是一个一个地挪left
Time - word length W, word count N, string length L - outer loop W, inner loop L / W * W(for substring operation), N to initialize the word count map - total O (N + WL)
Space O(NL)
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words == null || words.length == 0) {
return result;
}
int wordL = words[0].length();
int totalL = wordL * words.length;
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (int i = 0; i < wordL; i++) {
// start using sliding window
int left = i, right = i;
int wordCount = words.length;
// count of words between [left, right)
Map<String, Integer> currMap = new HashMap<>();
while (right + wordL <= s.length()) {
// expand for one word
String currWord = s.substring(right, right + wordL);
right += wordL;
int currCount = currMap.getOrDefault(currWord, 0) + 1;
currMap.put(currWord, currCount);
if (currCount <= map.getOrDefault(currWord, 0)) {
wordCount--;
}
if (right - left > totalL) {
currWord = s.substring(left, left + wordL);
left += wordL;
currCount = currMap.getOrDefault(currWord, 0) - 1;
currMap.put(currWord, currCount);
if (currCount < map.getOrDefault(currWord, 0)) {
wordCount++;
}
}
if (wordCount == 0) {
result.add(left);
}
}
}
return result;
}
}
一刷 08/2022
Version #1 Two Pointers
Time O(N) - construction, O(N) - calculate product
Space O(N)
class SparseVector {
public List<Integer> indices;
public List<Integer> values;
SparseVector(int[] nums) {
indices = new ArrayList<>();
values = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
continue;
}
indices.add(i);
values.add(nums[i]);
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
int result = 0;
int p = 0, q = 0;
while (p < this.indices.size() && q < vec.indices.size()) {
if (this.indices.get(p) < vec.indices.get(q)) {
p++;
} else if (this.indices.get(p) > vec.indices.get(q)) {
q++;
} else {
result += this.values.get(p) * vec.values.get(q);
p++;
q++;
}
}
return result;
}
}
一刷 08/2022
Version #1 1D DP
Time O(N)
Space O(1)
class Solution {
private int MOD = (int)(1e9 + 7);
public int countVowelPermutation(int n) {
//0 a -> e
//1 e -> a, i
//2 i -> a, e, o, u
//3 o -> i, u
//4 u -> a
// number of combinations with length i and ending with char (a,e,i,o,u)
int[] dp = new int[5];
Arrays.fill(dp, 1);
for (int i = 2; i <= n; i++) {
int[] ndp = new int[5];
// a can follow e,i,u
ndp[0] = ((dp[1] + dp[2]) % MOD + dp[4]) % MOD;
// e can follow a,i
ndp[1] = (dp[0] + dp[2]) % MOD;
// i can follow e,o
ndp[2] = (dp[1] + dp[3]) % MOD;
// o can follow i
ndp[3] = dp[2];
// u can follow i,o
ndp[4] = (dp[2] + dp[3]) % MOD;
dp = ndp;
}
int sum = 0;
for (int i = 0; i < 5; i++) {
sum = (sum + dp[i]) % MOD;
}
return sum;
}
}
一刷 08/2022
Version #1 Stack
因为要保证最小，所以要reverse some subarray in the min array if we encountered a 'D'
因为在min array里面前面的element 永远是小于后面的element的，所以即使前面reverse，也一定满足I
我觉得难点在于'D''I'都是针对两个elements来说的，所以index的处理有点麻烦
Time O(N)
Space O(N)
class Solution {
public int[] findPermutation(String s) {
int[] result = new int[s.length() + 1];
int p = 0;
int num = 1;
Stack<Integer> stack = new Stack<>();
// "DI"
//
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'D') {
stack.push(num++);
continue;
}
stack.push(num++);
while (!stack.isEmpty()) {
result[p++] = stack.pop();
}
}
stack.push(num);
while (!stack.isEmpty()) {
result[p++] = stack.pop();
}
return result;
}
}
一刷 08/2022
Version #2 Merge Sort
看某一个prefix index后面有多少个prefix满足lower <= prefix[j]-prefix[i] <= upper
Time O(NlogN)
Space O(N)
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// find count of prefixSum on the right that lower <= prefixSum[j] - prefixSum[i] <= uppder
// [-2,5,-1,-4]
// [0, -2, 3, 2, -2]
// [-2, 0] [-2, 2, 3]
int[] count = new int[1];
mergeSort(prefixSum, new long[prefixSum.length], 0, prefixSum.length - 1, count, lower, upper);
return count[0];
}
private void mergeSort(long[] nums, long[] aux, int start, int end, int[] count, int lower, int upper) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(nums, aux, start, mid, count, lower, upper);
mergeSort(nums, aux, mid + 1, end, count, lower, upper);
// left is the first index that nums[left] - num[i] >= lower
// right is the first index that nums[right] - nums[i] > upper
int left = mid + 1, right = mid + 1;
// int i = mid + 1, j = mid + 1;
// for (int k = low; k <= mid; k++) {
// while (i <= high && pfxSum[i] - pfxSum[k] < lower) i++;
// while (j <= high && pfxSum[j] - pfxSum[k] <= upper) j++;
// count += j - i;
// }
// [0, -2, 3, 2]
// [-2, 0, 2, 3]
for (int i = start; i <= mid; i++) {
while (left <= end && nums[left] - nums[i] < lower) {
left++;
}
while (right <= end && nums[right] - nums[i] <= upper) {
right++;
}
count[0] += right - left;
}
for (int i = start; i <= end; i++) {
aux[i] = nums[i];
}
int pleft = start, pright = mid + 1;
int p = start;
while (pleft <= mid && pright <= end) {
if (aux[pleft] <= aux[pright]) {
nums[p++] = aux[pleft++];
} else {
nums[p++] = aux[pright++];
}
}
while (pleft <= mid) {
nums[p++] = aux[pleft++];
}
while (pright <= end) {
nums[p++] = aux[pright++];
}
}
}
Version #1 Segment Tree[TLE]
Time O(NlogN)
Space O(Range of all prefix sums)
class Solution {
class Node {
Node left, right;
int count;
int start, end;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
}
public int countRangeSum(int[] nums, int lower, int upper) {
int[] prefixSum = new int[nums.length + 1];
int min = 0, max = 0;
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
min = Math.min(min, prefixSum[i + 1]);
max = Math.max(max, prefixSum[i + 1]);
}
Node root = buildTree(min, max);
int count = 0;
for (int i = nums.length; i >= 0; i--) {
// prefixSum[i] - try to find the count of j that lower <= prefixSum[j] - prefixSum[i] <= upper
// lower + prefixSum[i] <= prefixSum[j] <= upper + prefixSum[j]
count += query(root, (long)lower + prefixSum[i], (long)upper + prefixSum[i]);
update(root, prefixSum[i]);
}
return count;
}
private void update(Node node, int num) {
if (node.start == num && node.end == num) {
node.count++;
return;
}
int mid = node.start + (node.end - node.start) / 2;
if (num <= mid) {
update(node.left, num);
} else {
update(node.right, num);
}
node.count = node.left.count + node.right.count;
}
private int query(Node node, long left, long right) {
// [start, end]
// [left, right]
if (left > node.end || right < node.start) {
return 0;
}
if (left <= node.start && right >= node.end) {
return node.count;
}
return query(node.left, left, right) + query(node.right, left, right);
}
private Node buildTree(int start, int end) {
Node n = new Node(start, end);
if (start == end) {
return n;
}
int mid = start + (end - start) / 2;
n.left = buildTree(start, mid);
n.right = buildTree(mid + 1, end);
return n;
}
}
一刷 08/2022
Version #1 Map of DoublyLinkedList
Time O(1) for all
Space O(N) - N is number of keys
class LFUCache {
// key-the counter, value-the most recent used node with this counter
Map<Integer, DList> counterToList;
Map<Integer, Node> keyToNode;
int cap;
int minCounter;
class Node {
Node prev, next;
int key;
int val;
int counter;
public Node(int key, int val) {
this.key = key;
this.val = val;
this.counter = 1;
}
}
class DList {
Node head, tail;
int size;
public DList() {
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
this.size = 0;
}
// add after head
public void add(Node node) {
Node next = head.next;
head.next = node;
node.next = next;
node.prev = head;
next.prev = node;
size++;
}
public void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
size--;
}
// remove the last element and returns its key
public int removeLast() {
if (size == 0) {
return 0;
}
size--;
Node last = tail.prev;
Node prev = last.prev;
prev.next = tail;
tail.prev = prev;
return last.key;
}
}
public LFUCache(int capacity) {
this.cap = capacity;
this.minCounter = 0;
counterToList = new HashMap<>();
keyToNode = new HashMap<>();
}
public int get(int key) {
if (!keyToNode.containsKey(key)) {
return -1;
}
Node curr = keyToNode.get(key);
DList list = counterToList.get(curr.counter);
list.remove(curr);
if (list.size == 0 && curr.counter == minCounter) {
minCounter++;
}
curr.counter++;
counterToList.putIfAbsent(curr.counter, new DList());
counterToList.get(curr.counter).add(curr);
return curr.val;
}
public void put(int key, int value) {
if (keyToNode.containsKey(key)) {
keyToNode.get(key).val = value;
get(key);
return;
}
if (cap == 0) {
if (minCounter == 0) {
return;
}
cap++;
DList list = counterToList.get(minCounter);
int removedKey = list.removeLast();
keyToNode.remove(removedKey);
}
minCounter = 1;
cap--;
Node curr = new Node(key, value);
counterToList.putIfAbsent(1, new DList());
counterToList.get(1).add(curr);
keyToNode.put(key, curr);
}
}
一刷 07/2022
Version #1 TreeMap
思路比较简单就是把interval用key-value pair的形式存在treemap里面，然后维持所有的invervals没有overlap
需要特别处理的case
exists [8, 9)
add [1,8)
这时候首先需要取floowKey(8)获得[8, 9)然后合并获得[1,9)
另外一个case就是
exists [1, 9)
add [9, 10)
取完floorKey获得[1, 9)这时候需要判断的是get(floorKey) >= start
Time Amortized O(logN) - N is number of intervals
Space O(N)
class RangeModule {
TreeMap<Integer, Integer> map;
public RangeModule() {
map = new TreeMap<>();
}
public void addRange(int left, int right) {
int start = left, end = right;
// System.out.printf("left=%d, right=%d\n", left, right);
Integer lk = map.floorKey(end);
while (lk != null && map.get(lk) >= left) {
start = Math.min(start, lk);
end = Math.max(end, map.get(lk));
map.remove(lk);
lk = map.floorKey(end);
// System.out.printf("start=%d, end=%d\n", start, end);
}
map.put(start, end);
}
public boolean queryRange(int left, int right) {
Integer lk = map.lowerKey(right);
if (lk == null) {
return false;
}
if (lk <= left && map.get(lk) >= right) {
return true;
}
return false;
}
public void removeRange(int left, int right) {
// [ ]
// [ ] [ ]
Integer lk = map.lowerKey(right);
while (lk != null && map.get(lk) > left) {
int prevLeft = lk;
int prevRight = map.get(lk);
//left right
// [ ]
// pl pr
// [ ]
map.remove(lk);
if (prevRight > right) {
map.put(right, prevRight);
}
if (prevLeft < left) {
map.put(prevLeft, left);
}
lk = map.lowerKey(right);
}
}
}
一刷 07/2022
Version #1 HashMap
Time O(1)
Space O(N^2 + P) - N is number of stations, P is number of passengers
class UndergroundSystem {
// key-startStation,endStation value-sum of all travel times, count of customers
Map<List<String>, Pair<Long, Integer>> timeMap;
// key-customer id, value-startStation,checkin time
Map<Integer, Pair<String, Integer>> checkinMap;
public UndergroundSystem() {
this.timeMap = new HashMap<>();
this.checkinMap = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
checkinMap.put(id, new Pair(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
if (!checkinMap.containsKey(id)) {
return;
}
Pair<String, Integer> checkinInfo = checkinMap.get(id);
List<String> stations = new ArrayList<>();
stations.add(checkinInfo.getKey());
stations.add(stationName);
int duration = t - checkinInfo.getValue();
Pair<Long, Integer> stationInfo = timeMap.getOrDefault(stations, new Pair(0l, 0));
Pair<Long, Integer> nInfo = new Pair(stationInfo.getKey() + duration, stationInfo.getValue() + 1);
timeMap.put(stations, nInfo);
}
public double getAverageTime(String startStation, String endStation) {
Pair<Long, Integer> stationInfo = timeMap.get(new ArrayList<>(Arrays.asList(new String[]{startStation, endStation})));
return (1.0 * stationInfo.getKey()) / stationInfo.getValue();
}
}
一刷 07/2022
Version #1 Sliding Window
感觉很难，照着答案写还是一知半解的感觉
Time O(N)
Space O(N)
class Solution {
public int minKBitFlips(int[] nums, int k) {
// number of flips in the sliding window
int flipCounter = 0;
int flips = 0;
boolean[] isFlipped = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i >= k && isFlipped[i - k]) {
flipCounter--;
}
// check if we need to flip current bit
if (flipCounter % 2 == nums[i]) {
if (i + k > nums.length) {
return -1;
}
isFlipped[i] = true;
flipCounter++;
flips++;
}
}
return flips;
}
}
