一刷 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;
}
}
