-> 简要 一般先处理!containsKey
Use hashset to detect duplicate element
187. Repeated DNA Sequences
Time: O(N)
/** Solution 1
* Use two hashset here one is the result hashset the other is used
* to detect whether there are more than 1 string in the string. Swipe
* the string with a window of size 10 and put the result back to the
* arraylist */
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<String>();
if(s == null||s.length() == 0){
return res;
}
int n = s.length();
HashSet<String> result = new HashSet();
HashSet<String> set = new HashSet();
for(int i = 0;i <= n - 10;i++){
String cur = s.substring(i,i + 10);
if(set.contains(cur)){
result.add(cur);
}
else{
set.add(cur);
}
}
//Iterate over set
for(String str: result){
res.add(str);
}
return res;
}
}
Use hashmap to store the index
336. Palindrome Pairs
When will the two string construct a palindrome?
- (ababd)+(db) 有一部分是palindrome,剩下的部分在数组里可以找到reverse
整个string在数组里可以找到reverse
为了排除某些情况 比如这个string的reverse就是自己 我们需要建立HashMap 在判断的时候同时要加上判断index是不是同一个index
166. Fraction to Recurring Decimal
--> 分数变循环小数
按照正常的除法规则找到pattern就可以 这个题corner case挺多的。。主要一个是溢出
一个是符号的判断。还有一个算法怎么设计能让代码更加好写 比如怎么发现有重复的pattern?
怎么加括号？首先我们先计算出整数部分 如果没有余数就可以直接返回了 但如果有余数 则要继续
乘以10进行计算 然后用一个哈希表记录每个余数出现的index 这样如果有数字之前出现过了则说明
进行了循环。这时停止计算在相应的位置加上"(" 和 ")"就好 啦
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if(numerator == 0){
return "0";
}
StringBuilder bd = new StringBuilder();
if((numerator > 0) ^ (denominator > 0))bd.append('-');
//since when we compute the result we need positive values! so we need to use Math.abs but consider every
//possible overflow!!
long num = Math.abs((long)numerator);
long deno = Math.abs((long)denominator);
long v1 = num / deno;
bd.append(v1);
long r = num % deno;
//if no leftover just return right away
if(r == 0){
return bd.toString();
}
bd.append(".");
//continue to multiply by ten and detect the duplicate!
//<剩余的数，对应的index>
HashMap<Long,Integer> map = new HashMap<Long,Integer>();
map.put(r,bd.length());
while(r > 0){
r = r * 10;
long val = r / deno;
bd.append(val);
//the next round
r = r % deno;
if(map.containsKey(r)){
int idx = map.get(r);
bd.insert(idx,"(");
bd.append(")");
break;
}
else{
map.put(r,bd.length());
}
}
return bd.toString();
}
}
处理树的问题！
314. Binary Tree Vertical Order Traversal
结合BFS, 记录每个树节点的colomn index 同时记录colomn的range
以及有的时候BFS要记录很多信息
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* New Node class track the TreeNode and its revelant colomn index
* Perform BFS and put the related treenodes to the hashmap's colomn bucket
* Keep track of the range of the colomn index and retrieve the element to
* The final result
*/
public class Solution {
//each node and corresponding col number
class Node {
TreeNode node;
int col;
public Node(TreeNode node, int col) {
this.node = node;
this.col = col;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(root == null){
return result;
}
Queue<Node> q = new LinkedList<Node>();
//colomn num,the treenode's belong to this colomn
HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
q.add(new Node(root,0));
//the colomn's range to be computed
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//BFS and assign the colomn value to the index
while(!q.isEmpty()){
Node cur = q.poll();
TreeNode curNode = cur.node;
int idx = cur.col;
if(!map.containsKey(idx)){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(idx,list);
}
map.get(idx).add(curNode.val);
if(curNode.left != null){
q.add(new Node(curNode.left,idx - 1));
}
if(curNode.right != null){
q.add(new Node(curNode.right,idx + 1));
}
min = Math.min(idx,min);
max = Math.max(idx,max);
}
//retrieve the result
for(int i = min;i <= max;i++){
result.add(map.get(i));
}
return result;
}
}
Detect whether a number exist in the value set of hashmap
290. Word Pattern
双向的比较 一对一的关系
205. Isomorphic Strings
一一对应 不同的字符不能对应相同的字符 相同的字符对应的一定时相同的
public class Solution {
public boolean isIsomorphic(String s, String t) {
int len = s.length();
HashMap<Character,Character> map = new HashMap<Character,Character>();
for(int i = 0;i < len;i++){
char s1 = s.charAt(i);
char s2 = t.charAt(i);
//s1不存在 s2却存在则返回false
if(!map.containsKey(s1)){
if(map.containsValue(s2)){
return false;
}
map.put(s1,s2);
}
else{
//s1存在但是s1对应的s2不对
if(map.get(s1) != s2){
return false;
}
}
}
return true;
}
}
匹配
350. Intersection of Two Arrays II
要求返回的交叉元素是原来的原有个数
解法1 --> 用到HashMap匹配的思想 匹配一个就在原来的Map里面减去相应的值
380. Insert Delete GetRandom O(1)
考察了ArrayList的remove操作怎么才能最快达到O(1) 以及HashMap能达到的O(1) insert remove
方法就是把要移除的元素和List的最后一个元素交换并且更新HashMap里的相应元素 这
这样删除的时候只用删除最后一个元素就是O(1)的速度
381. Insert Delete GetRandom O(1) - Duplicates allowed
在380的基础上 如果插入的元素可以有重复怎么体现 相当于有Hash Collision这样我们用HashMap
对应的bucket里面放入HashSet记录当前元素可能存在的index 这样在删除一个值为val的元素时一个
一个移除index
怎么用Iterator一个一个access相同数字的index
Use HashSet to detect exisiting matching element in the Given Set
939 Minimum Area Rectangle
//问题转换很重要 矩形由四点确认 和subarray sum有点像
//存在(x1,y1) (x2,y2)互为对角的两个点 找另外两个对角点在不在(x2,y1) (x1,y2)
//write the hash function for new class object Node
//时间复杂度 O(N2)