显示标签为“Hashmap”的博文。显示所有博文
显示标签为“Hashmap”的博文。显示所有博文

2014年10月27日星期一

Anagrams

Problem:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Analysis:
基本没有会的题,从现在开始把参考人的链接发出来。也算是尊重别人的劳动成果。
Use hashmap to group the anagrams.
1. Pick up a string and sort it.
2. Compare the sorted string with existing keys.
3. If key is there, add the unsorted string to the keys values.
    If key is not there, create new hashmap item.
4. Return string groups have size greater than 1.

Solution:


1:            HashMap<String,ArrayList<String>> anagrams= new HashMap<String, ArrayList<String>>();  
2:            ArrayList<String> result=new ArrayList<String>();  
3:            for(String str: strs)  
4:            {  
5:                 char[] chars=str.toCharArray();  
6:                 Arrays.sort(chars);  
7:                 String key=new String(chars);  
8:                 if(anagrams.containsKey(key))  
9:                      anagrams.get(key).add(str);  
10:                 else  
11:                 {  
12:                      ArrayList<String> temp=new ArrayList<String>();  
13:                      temp.add(str);  
14:                      anagrams.put(key, temp);  
15:                 }  
16:            }  
17:            for(ArrayList<String> group:anagrams.values())  
18:            {  
19:                 if(group.size()>1)  
20:                      result.addAll(group);  
21:            }  
22:            return result;  
Reference:
https://github.com/ahmetalpbalkan/leetcode-solutions/blob/master/Anagrams.java

2014年9月17日星期三

Valid Parentheses

Problem:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Analysis:
Use stack and hashmap. Stack makes sure there is always "(" in front of ")", otherwise the string is not valid.

看了几天简单的算法看不懂。昨天找到一种笨方法,就是照着打,估计多打几遍就好了。

Solution:


1:  public class Solution {  
2:    public boolean isValid(String s) {  
3:      char[] chars=s.toCharArray();  
4:      HashMap<Character, Character> map=new HashMap<Character,Character>();  
5:      map.put('(', ')');  
6:          map.put('[', ']');  
7:         map.put('{', '}');  
8:         Stack<Character> stack = new Stack<Character>();  
9:         for(Character c: chars)  
10:         {  
11:           if(map.keySet().contains(c))  
12:            stack.push(c);  
13:           else if(map.values().contains(c))  
14:           {  
15:             if(!stack.isEmpty()&&map.get(stack.peek())==c)  
16:               stack.pop();  
17:             else   
18:             return false;  
19:           }  
20:         }  
21:         return stack.isEmpty();  
22:    }  
23:  }  

2014年7月14日星期一

Two Sum

Problem:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Solution:
1:  public class Solution {  
2:    public int[] twoSum(int[] numbers, int target) {  
3:      HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();  
4:      int[] result=new int[2];  
5:      for(int i=0;i<numbers.length;i++)  
6:        {  
7:          if(map.containsKey(numbers[i]))  
8:         {  
9:           int index=map.get(numbers[i]);  
10:           result[0]=index+1;  
11:           result[1]=i+1;  
12:           break;  
13:         }   
14:         else  
15:          map.put(target-numbers[i],i);  
16:        }  
17:       return result;  
18:    }  
19:  }