2020- 11 - 02: 349. Intersection of Two Arrays
Problem link.
Method 1: HashTable
Using two HashSet. put one array numbers in to a set, and check if numbers the other array are in the set.
Code
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
Set<Integer> result = new HashSet<>();
for (int num: nums2) {
if (set1.contains(num) && !result.contains(num)) {
result.add(num);
}
}
int[] intersection = new int[result.size()];
int idx =0;
for (int num: result){
intersection[idx++] = num;
}
return intersection;
}
}Method 2: Sort + Two pointer
Sort the array and use two pointer to find out the numbers that appear in both arrays. Move the pointer with smaller number.
Code
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int ptr1 = 0;
int ptr2 = 0;
List<Integer> intersection = new ArrayList<>();
while (ptr1 < nums1.length && ptr2 < nums2.length) {
int num1 = nums1[ptr1];
int num2 = nums2[ptr2];
if (num1 == num2) {
if (intersection.size() == 0 || intersection.get(intersection.size() -1) != num1) {
intersection.add(num1);
}
ptr1 += 1;
ptr2 += 1;
} else if (num1 > num2) {
ptr2 += 1;
} else {
// num1 < num2
ptr1 += 1;
}
}
return intersection.stream().mapToInt(Integer::intValue).toArray();
}
}2020-11-01 140. Word Break II
Problem link
Method: Recursion With Memorization
Given a string str, if its prefix is in the wordDict, we can recursivly find out the list of breaked words for the substringstr' with recursion. and combine the results.
Recursion Three key thing:
- boundary case: Once all
stris matched, this means we have another variable to record the starting point ,calledoffset - sub-problem: match the substring
- return value: list of word break string for an input string.
Code
class Solution {
private Map<String, List<String>> cache = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for (String word: wordDict) {
set.add(word);
}
return dfs(s, 0 , set);
}
private List<String> dfs(String s , int offset, Set<String> dict ) {
List<String> result = new ArrayList<>();
if (offset == s.length()) {
result.add("");
return result;
}
if (cache.containsKey(s.substring(offset))) {
return cache.get(s.substring(offset));
}
for (int idx = offset; idx < s.length(); idx++) {
String word = s.substring(offset, idx + 1);
if (dict.contains(word)) {
List<String> next = dfs(s, idx + 1, dict);
for (String nextStr: next) {
result.add((word + " " + nextStr).trim());
}
}
}
cache.put(s.substring(offset), result);
return result;
}
}2020-10-31 381. Insert Delete GetRandom O(1) - Duplicates allowed
Problem link
Method: HashTable + Design
The most challenge part is to get delete(int val) to be done in O(1) Time. We need to record not only how many time appears in the arraylist as well as their index. We need to get one of the index for the val, and swap with the last element. Update the indexMap first before remove the val from the arraylist. Be careful with the corner case.
Code
class RandomizedCollection {
private List<Integer> nums;
private Random random;
private Map<Integer, Set<Integer>> indexMap;
/** Initialize your data structure here. */
public RandomizedCollection() {
this.nums = new ArrayList<>();
this.indexMap = new HashMap<>();
this.random = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
nums.add(val);
int idx = nums.size() - 1;
indexMap.putIfAbsent(val, new HashSet<>());
indexMap.get(val).add(idx);
return indexMap.get(val).size() == 1;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!indexMap.containsKey(val)) {
return false;
}
Set<Integer> idxSet = indexMap.get(val);
int idx = idxSet.iterator().next(); // get one of the index of the val
int lastVal = nums.get(nums.size() - 1);
swap(nums, idx, nums.size() - 1); //swap the val with the lastVal
// remove `val` and `lastVal` indexin the indexMap
idxSet.remove(idx);
indexMap.get(lastVal).remove(this.nums.size() - 1);
// update`lastVal` index with new one if possible
// why this.nums.size() -1 here, becase after remove,the size decrease one.
if (idx < this.nums.size() -1) {
indexMap.get(lastVal).add(idx);
}
// update the lastVal index in this indexMap
if (idxSet.size() == 0) {
indexMap.remove(val);
}
nums.remove(nums.size() - 1);
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
int randIdx = random.nextInt(nums.size());
return nums.get(randIdx);
}
private void swap(List<Integer> nums, int idx1, int idx2) {
int temp = nums.get(idx1);
nums.set(idx1, nums.get(idx2));
nums.set(idx2, temp);
}
}
/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/2020-10-30 463. Island Perimeter
Problem link
Method: Math(Counting)
Very simple, if boundary overlap with its neighbour, minuteone.
Code
class Solution {
public int islandPerimeter(int[][] grid) {
int count = 0;
int rows = grid.length;
int cols = grid[0].length;
for (int r = 0; r < rows ; r++) {
for (int c = 0; c < cols; c++) {
if ( grid[r][c] == 0) {
continue;
}
count += 4;
if ( r > 0 && grid[r-1][c] == 1) {
count -= 1;
}
if ( c > 0 && grid[r][c-1] == 1) {
count -= 1;
}
if ( r < rows - 1 && grid[r+1][c] == 1) {
count -= 1;
}
if ( c < cols - 1 && grid[r][c+1] == 1) {
count -= 1;
}
}
}
return count;
}
}2020-10-29 129. Sum Root to Leaf Numbers
Problem link
Method 1： Breadth-first search (BFS)
We need to record the temp_sum along the way. So, we need to have a wrapper class of the TreeNode class. Add to result if this is a leaf Node.
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Element {
TreeNode node;
int sum;
Element (TreeNode node, int sum) {
this.node = node;
this.sum = sum;
}
}
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
int result = 0;
Deque<Element> queue = new LinkedList<>();
queue.add(new Element(root, root.val));
while (!queue.isEmpty()) {
Element cur = queue.poll();
if (cur.node.left == null && cur.node.right == null) {
result += cur.sum;
continue;
}
if (cur.node.left != null) {
queue.add(new Element(cur.node.left,
cur.sum * 10 + cur.node.left.val));
}
if (cur.node.right != null) {
queue.add(new Element(cur.node.right,
cur.sum * 10 + cur.node.right.val));
}
}
return result;
}
}Method 2: Depth-first Search (DFS)
Code
class Solution {
private int totalSum = 0;
public int sumNumbers(TreeNode root) {
if (root == null){
return 0;
}
dfs(root, 0);
return totalSum;
}
private void dfs(TreeNode root, int cur){
cur = cur * 10 + root.val;
if (root.left == null && root.right == null) {
totalSum += cur;
return;
}
if (root.left != null) {
dfs(root.left, cur);
}
if (root.right != null) {
dfs(root.right, cur);
}
}
}2020-10-28 1207. Unique Number of Occurrences
Problem link
Method: HashTable
Counting the numbers with one HashTable and counting the occurrency with another one.
Code
class Solution {
public boolean uniqueOccurrences(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int num: arr) {
map.put(num ,map.getOrDefault(num,0) + 1);
}
Set<Integer> occurrences = new HashSet<>();
for (int num: map.keySet()) {
if (occurrences.contains(map.get(num))){
return false;
}
occurrences.add(map.get(num));
}
return true;
}
}2020-10-27 144. Binary Tree Preorder Traversal
Method 1 : DFS with recursion
Code
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
dfs(root.left, result);
dfs(root.right,result );
}
}Method 2 : DFS with stack
Using stack can convert the recursion code into iterative one. Notice that Stack has the property of FILO,So when traverse the tree pre-order, we should add its right child to stack and then left child.
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
result.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
return result;
}
}2020-10-26 1365. How Many Numbers Are Smaller Than the Current Number
Problem link
Method 1: Bucket Sort + PreSum
Notice that the range of the element in the array is 0 <= nums[i] <= 100,So we could use a array with size 101 as the hashtable to count the number of occurency in the array ,and then pre-sum the bucket from the left to right, such that countMap[i] represents the number of numbers which are smaller than or equal to i.
Code
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] countMap = new int[101];
for (int num: nums) {
countMap[num] += 1;
}
for (int num = 1 ; num <= 100; num++) {
countMap[num] += countMap[num-1];
}
int[] result = new int[nums.length];
for (int idx = 0; idx < result.length; idx++) {
if (nums[idx] == 0) {
result[idx] = 0;
}else {
result[idx] = countMap[nums[idx] - 1];
}
}
return result;
}
}Method 2: Sort
We could sort with based on their val, but we also needs to carry their position information. After sorting, we could traverse from the left to right, and if the current val is larger than the preivous one, its val is just equal to idx, if its the same as the previous one, then they have the same result.
Code
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int len = nums.length;
int[][] tuples = new int[len][2];
for (int idx = 0 ; idx < nums.length; idx++ ){
tuples[idx] = new int[]{nums[idx], idx};
}
Arrays.sort(tuples, (a, b)->{
return a[0] - b[0];
});
int counter = 0;
int[] result = new int[len];
for (int idx = 0; idx < len; idx++) {
int curNum = tuples[idx][0];
int curPos = tuples[idx][1];
if (idx == 0) {
result[curPos] = 0;
} else{
int preNum = tuples[idx-1][0];
int prePos = tuples[idx-1][1];
// if the previous one is smaller than the current, assign by the counter,
// otherwise they have the same result;
result[curPos] = preNum < curNum ? counter: result[prePos];
}
counter += 1;
// counter represents how many number are smaller than or equal to the currentNum;
}
return result;
}
}
