一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1016|回复: 15
收起左侧

[算法题] 总结能用上HashMap的题

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-10 09:08:34 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-6-19 15:40 编辑

最近做题发现,google等公司很爱考HashMap的题。搜了一下互联网,好像还没有人总结leetcode/lintcode上能用HashMap的题。所以我开个贴,总结我遇到的能用HashMap的题,之后会不断更新。大家如有补充,请回复哈,我会一起更新在一楼方便你我。 能用HashMap的题解法会很清晰哈。感觉能用HashMap的题都是数据放在List里面的?
啥时用到hashmap呢? 其实,当我们需要计数时,往往可以用hashmap来做


1. Anagrams
2. Longest words
3. Valid parentheses
4. Two sum
5. Compare strings  (http://www.lintcode.com/en/problem/compare-strings/)
6. Contains duplicates ii
7. Single number(虽然题目不让用额外空间,但该题用hashmap计数也能过lc)8. Subarray sum:  http://www.lintcode.com/en/problem/subarray-sum/
9. Majority element: https://leetcode.com/problems/majority-element/
.....







57656929bb 发表于 2015-6-10 09:36:33 | 显示全部楼层
用HASHMAP的题很多,区别在于有的hashmap只是辅助,有的就是算法核心部分,并且绝大部分用hashmap解决的问题面试时都会要求不准用hash(额外空间)
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-10 09:45:20 | 显示全部楼层
57656929bb 发表于 2015-6-10 09:36
用HASHMAP的题很多,区别在于有的hashmap只是辅助,有的就是算法核心部分,并且绝大部分用hashmap解决的问 ...

不准用是一回事,但我们至少要把题解出来才有follow up啊
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-10 17:55:26 | 显示全部楼层
Valid Parentheses是怎么用HashMap解的呢?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-10 18:11:52 | 显示全部楼层
stellari 发表于 2015-6-10 17:55
Valid Parentheses是怎么用HashMap解的呢?
  1. public class Solution {
  2.     /**
  3.      * @param s A string
  4.      * [url=home.php?mod=space&uid=160137]@return[/url] whether the string is a valid parentheses
  5.      */
  6.     public boolean isValidParentheses(String s) {
  7.         // Write your code here
  8.         
  9.         if(s.length() == 1)
  10.         {
  11.             return false;
  12.         }
  13.         
  14.         HashMap<Character, Character> map = new HashMap<Character, Character>();
  15.         map.put('(', ')');
  16.         map.put('{', '}');
  17.         map.put('[', ']');
  18.         
  19.         LinkedList<Character> list = new LinkedList<Character>();
  20.         
  21.         for(int i = 0; i < s.length(); i++)
  22.         {
  23.             if(s.charAt(i) == '(' || s.charAt(i) =='{' || s.charAt(i) == '[')
  24.             {
  25.                 list.push(s.charAt(i));
  26.             }
  27.             else
  28.             {
  29.                 if(!list.isEmpty())
  30.                 {   char c = list.pop();
  31.                     if(map.get(c) == s.charAt(i))
  32.                     {
  33.                         continue;
  34.                     }
  35.                     else
  36.                     {
  37.                         return false;
  38.                     }
  39.                 }   
  40.                 else
  41.                 {
  42.                     return false;
  43.                 }
  44.             }
  45.         }
  46.         return list.isEmpty();
  47.         }
  48.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-11 19:59:09 | 显示全部楼层
stellari 发表于 2015-6-10 17:55
Valid Parentheses是怎么用HashMap解的呢?

感兴趣我的这个帖子的讨论不? http://www.1point3acres.com/bbs/thread-136147-1-1.html
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-11 21:24:15 | 显示全部楼层
Compare strings:
  1. public class Solution {
  2.     /**
  3.      * @param A : A string includes Upper Case letters
  4.      * @param B : A string includes Upper Case letter
  5.      * [url=home.php?mod=space&uid=160137]@return[/url] :  if string A contains all of the characters in B return true else return false
  6.      */
  7.     public boolean compareStrings(String A, String B) {
  8.         // write your code here
  9.         if(A == null && B == null || A.length() == 0 && B.length() == 0)
  10.         {
  11.             return true;
  12.         }
  13.         
  14.         if(A == null || A.length() == 0)
  15.         {
  16.             return false;
  17.         }
  18.         
  19.         
  20.         
  21.         HashMap<Character, Integer> mapA = new HashMap<Character, Integer>();
  22.         HashMap<Character, Integer> mapB = new HashMap<Character, Integer>();
  23.         
  24.         for(int i = 0; i < A.length(); i++)
  25.         {
  26.             if(mapA.containsKey(A.charAt(i)))
  27.             {
  28.                 mapA.put(A.charAt(i),mapA.get(A.charAt(i))+1);
  29.             }
  30.             else
  31.             {
  32.                 mapA.put(A.charAt(i), 1);
  33.             }
  34.         }
  35.         
  36.         for(int i = 0; i < B.length(); i++)
  37.         {
  38.             if(mapB.containsKey(B.charAt(i)))
  39.             {
  40.                 mapB.put(B.charAt(i),mapB.get(B.charAt(i))+1);
  41.             }
  42.             else
  43.             {
  44.                 mapB.put(B.charAt(i), 1);
  45.             }
  46.         }
  47.         
  48.         for(int i = 0; i < B.length(); i++)
  49.         {
  50.             if(mapA.containsKey(B.charAt(i)))
  51.             {   if(mapA.get(B.charAt(i)) >= mapB.get(B.charAt(i)))
  52.                 {
  53.                     continue;
  54.                 }
  55.                 else
  56.                 {
  57.                     return false;
  58.                 }
  59.             }
  60.             else
  61.             {
  62.                 return false;
  63.             }
  64.         }
  65.         return true;
  66.         
  67.     }
  68. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 17:18:40 | 显示全部楼层
Contains duplicates ii:
  1. public class Solution {
  2.     public boolean containsNearbyDuplicate(int[] nums, int k) {
  3.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         int min = Integer.MAX_VALUE;
  5.         
  6.         for(int i =0; i < nums.length; i++)
  7.         {
  8.             if(map.containsKey(nums[i]))
  9.             {
  10.                 int index = map.get(nums[i]);
  11.                 int diff = i - index;
  12.                 min = Math.min(min, diff);
  13.             }
  14.             map.put(nums[i], i);
  15.         }
  16.         if(min <= k)
  17.         {
  18.             return true;
  19.         }
  20.         else
  21.         {
  22.             return false;
  23.         }
  24.     }
  25. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 23:50:52 | 显示全部楼层
Single number(虽然题目不让用额外空间,但该题用hashmap计数也能过lc)
  1. public class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         for(int i = 0; i < nums.length; i++)
  5.         {
  6.             if(map.containsKey(nums[i]))
  7.             {
  8.                 map.put(nums[i], map.get(nums[i])+1);
  9.                
  10.             }
  11.             else
  12.             {
  13.                 map.put(nums[i], 1);
  14.             }
  15.         }
  16.         
  17.         for(int j = 0; j < nums.length; j++)
  18.         {
  19.             if(map.get(nums[j]) == 1)
  20.             {
  21.                 return nums[j];
  22.             }
  23.         }
  24.         return 0;
  25.     }
  26. }
复制代码
回复 支持 反对

使用道具 举报

adiggo 发表于 2015-6-13 02:27:51 | 显示全部楼层
love1point 发表于 2015-6-12 23:50
Single number(虽然题目不让用额外空间,但该题用hashmap计数也能过lc)

lc 应该不管空间的。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-13 09:09:47 | 显示全部楼层
adiggo 发表于 2015-6-13 02:27
lc 应该不管空间的。

嗯,lc不管空间,但lc note说 “Could you implement it without using extra memory?”
多谢回复
回复 支持 反对

使用道具 举报

jaly50 发表于 2015-6-19 05:17:05 | 显示全部楼层
第八题: 用hashmap: time o(n), space o(n)
  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: A list of integers includes the index of the first number
  5.      *          and the index of the last number
  6.      */
  7.     public ArrayList<Integer> subarraySum(int[] nums) {
  8.         // write your code here
  9.         // Store index and sum
  10.         Map<Integer,Integer> map = new HashMap<Integer, Integer>();
  11.         ArrayList<Integer> res = new ArrayList<Integer>();
  12.         int sum = 0;
  13.         map.put(0,-1);
  14.         for (int i=0; i<nums.length; i++) {
  15.             sum +=nums[i];
  16.             if (map.containsKey(sum)) {
  17.                 res.add(map.get(sum)+1);
  18.                 res.add(i);
  19.                 return res;
  20.             }
  21.             else
  22.             map.put(sum, i);
  23.         }
  24.         return res;
  25.     }
  26. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-19 08:39:30 | 显示全部楼层
jaly50 发表于 2015-6-19 05:17
第八题: 用hashmap: time o(n), space o(n)

是的哈。多谢参与哈
回复 支持 反对

使用道具 举报

mary小丸子 发表于 2015-9-2 22:13:31 | 显示全部楼层
谢谢分享。赞一个。。一起刷题努力!我也现在找工作。
回复 支持 反对

使用道具 举报

syjohnson 发表于 2015-9-12 05:10:44 | 显示全部楼层
回复 支持 反对

使用道具 举报

plich 发表于 2015-9-18 22:35:06 | 显示全部楼层
Single number用hash table会比直接xor快么?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 20:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表