Last active
March 29, 2023 18:13
-
-
Save sharunkumar/4efe7d55db9cf12eb2dfcbdc1f006e3d to your computer and use it in GitHub Desktop.
Hash Maps
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public List<List<String>> groupAnagrams(String[] strs) { | |
if (strs.length == 0) return new ArrayList(); | |
Map<String, List> ans = new HashMap<String, List>(); | |
for (String s : strs) { | |
char[] ca = s.toCharArray(); | |
Arrays.sort(ca); | |
String key = String.valueOf(ca); | |
if (!ans.containsKey(key)) ans.put(key, new ArrayList()); | |
ans.get(key).add(s); | |
} | |
return new ArrayList(ans.values()); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int longestConsecutive(int[] nums) { | |
Set<Integer> num_set = new HashSet<Integer>(); | |
for (int num : nums) { | |
num_set.add(num); | |
} | |
int longestStreak = 0; | |
for (int num : num_set) { | |
if (!num_set.contains(num-1)) { | |
int currentNum = num; | |
int currentStreak = 1; | |
while (num_set.contains(currentNum+1)) { | |
currentNum += 1; | |
currentStreak += 1; | |
} | |
longestStreak = Math.max(longestStreak, currentStreak); | |
} | |
} | |
return longestStreak; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Pair<U, V> { | |
public U first; | |
public V second; | |
public Pair(U first, V second) { | |
this.first = first; | |
this.second = second; | |
} | |
} | |
class Bucket { | |
private List<Pair<Integer, Integer>> bucket; | |
public Bucket() { | |
this.bucket = new LinkedList<Pair<Integer, Integer>>(); | |
} | |
public Integer get(Integer key) { | |
for (Pair<Integer, Integer> pair : this.bucket) { | |
if (pair.first.equals(key)) | |
return pair.second; | |
} | |
return -1; | |
} | |
public void update(Integer key, Integer value) { | |
boolean found = false; | |
for (Pair<Integer, Integer> pair : this.bucket) { | |
if (pair.first.equals(key)) { | |
pair.second = value; | |
found = true; | |
} | |
} | |
if (!found) | |
this.bucket.add(new Pair<Integer, Integer>(key, value)); | |
} | |
public void remove(Integer key) { | |
for (Pair<Integer, Integer> pair : this.bucket) { | |
if (pair.first.equals(key)) { | |
this.bucket.remove(pair); | |
break; | |
} | |
} | |
} | |
} | |
class MyHashMap { | |
private int key_space; | |
private List<Bucket> hash_table; | |
/** Initialize your data structure here. */ | |
public MyHashMap() { | |
this.key_space = 2069; | |
this.hash_table = new ArrayList<Bucket>(); | |
for (int i = 0; i < this.key_space; ++i) { | |
this.hash_table.add(new Bucket()); | |
} | |
} | |
/** value will always be non-negative. */ | |
public void put(int key, int value) { | |
int hash_key = key % this.key_space; | |
this.hash_table.get(hash_key).update(key, value); | |
} | |
/** | |
* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping | |
* for the key | |
*/ | |
public int get(int key) { | |
int hash_key = key % this.key_space; | |
return this.hash_table.get(hash_key).get(key); | |
} | |
/** Removes the mapping of the specified value key if this map contains a mapping for the key */ | |
public void remove(int key) { | |
int hash_key = key % this.key_space; | |
this.hash_table.get(hash_key).remove(key); | |
} | |
} | |
/** | |
* Your MyHashMap object will be instantiated and called as such: MyHashMap obj = new MyHashMap(); | |
* obj.put(key,value); int param_2 = obj.get(key); obj.remove(key); | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public int subarraySum(int[] nums, int k) { | |
int count = 0, sum = 0; | |
HashMap < Integer, Integer > map = new HashMap < > (); | |
map.put(0, 1); | |
for (int i = 0; i < nums.length; i++) { | |
sum += nums[i]; | |
if (map.containsKey(sum - k)) | |
count += map.get(sum - k); | |
map.put(sum, map.getOrDefault(sum, 0) + 1); | |
} | |
return count; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public boolean isValidSudoku(char[][] board) { | |
int N = 9; | |
// Use hash set to record the status | |
HashSet<Character>[] rows = new HashSet[N]; | |
HashSet<Character>[] cols = new HashSet[N]; | |
HashSet<Character>[] boxes = new HashSet[N]; | |
for (int r = 0; r < N; r++) { | |
rows[r] = new HashSet<Character>(); | |
cols[r] = new HashSet<Character>(); | |
boxes[r] = new HashSet<Character>(); | |
} | |
for (int r = 0; r < N; r++) { | |
for (int c = 0; c < N; c++) { | |
char val = board[r][c]; | |
// Check if the position is filled with number | |
if (val == '.') { | |
continue; | |
} | |
// Check the row | |
if (rows[r].contains(val)) { | |
return false; | |
} | |
rows[r].add(val); | |
// Check the column | |
if (cols[c].contains(val)) { | |
return false; | |
} | |
cols[c].add(val); | |
// Check the box | |
int idx = (r / 3) * 3 + c / 3; | |
if (boxes[idx].contains(val)) { | |
return false; | |
} | |
boxes[idx].add(val); | |
} | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment