美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 你知道麻、木吗?学问可大了
  • 中国第一颗卫星东方红一号:现在是太空垃圾吗?
  • 这种布能自动修复 再也不用担心划破衣服
  • 英国大狗重如小象:每月吃千元狗粮 还很瘦
  • 气象台主持人遭雷击:火花四溅 险些殉职
  • 中华神箭!长征五号火箭二次起航
  • 中国女游客南非突遭猎豹袭击:跪地尖叫
  • 公司被曝剽窃创意?黄磊:不清楚细节 有错会认
  • 台湾女孩6岁骑行千里丝路 9年来横越亚非、北美多国
  • 霸气!朱婷率瓦基弗夺留洋首冠 荣膺欧冠MVP
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3029|回复: 4

    内推面经 -问一个Anagram的参考程序- 唐人社区|北美华人论坛

    [复制链接]

    19

    主题

    405

    帖子

    447

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    447
    QQ
    发表于 2016-9-21 19:12:58 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-问一个Anagram的参考程序


      JobHunting
    标 题: 问一个Anagram的参考程序


    Given an array of strings, return all groups of strings that are anagrams.

    All inputs will be in lower-case

    Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

    Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

    9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
    成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
    有没有对应同一个hashcode的可能 (考虑int overflow的情况下).

    public class Solution {
    private int getHash(int[] count) {
    int hash = 0;
    int a = 378551;
    int b = 63689;
    for (int num : count) {
    hash = hash * a + num;
    a = a * b;
    }
    return hash;
    }

    public ArrayList anagrams(String[] strs) {
    ArrayList result = new ArrayList();
    HashMap map = new HashMap();

    for (String str : strs) {
    int[] count = new int[26];
    for (int i = 0; i < str.length(); i++) {
    count[str.charAt(i) - 'a']++;
    }

    int hash = getHash(count);
    if (!map.containsKey(hash)) {
    map.put(hash, new ArrayList());
    }

    map.get(hash).add(str);
    }

    for (ArrayList tmp : map.values()) {
    if (tmp.size() > 1) {
    result.addAll(tmp);
    }
    }

    return result;
    }
    }
    --

    新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    25

    主题

    102

    帖子

    158

    积分

    注册会员

    Rank: 2

    积分
    158
    QQ
    发表于 2016-9-21 20:41:19 | 显示全部楼层
    JobHunting
    标  题: 问一个Anagram的参考程序


    Given an array of strings, return all groups of strings that are anagrams.

    All inputs will be in lower-case

    Given [&quot;lint&quot;, &quot;intl&quot;, &quot;inlt&quot;, &quot;code&quot;], return [&quot;lint&quot;, &quot;inlt&quot;, &quot;intl&quot;].

    Given [&quot;ab&quot;, &quot;ba&quot;, &quot;cd&quot;, &quot;dc&quot;, &quot;e&quot;], return [&quot;ab&quot;, &quot;ba&quot;, &quot;cd&quot;, &quot;dc&quot;].

    9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
    成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
    有没有对应同一个hashcode的可能 (考虑int overflow的情况下).

    public class Solution {
        private int getHash(int[] count) {
            int hash = 0;
            int a = 378551;
            int b = 63689;
            for (int num : count) {
                hash = hash * a + num;
                a = a * b;
            }
            return hash;
        }
       
        public ArrayList<String> anagrams(String[] strs) {
            ArrayList<String> result = new ArrayList<String>();
            HashMap<Integer, ArrayList<String>> map = new HashMap<Integer,
    ArrayList<String>>();

            for (String str : strs) {
                int[] count = new int[26];
                for (int i = 0; i < str.length(); i++) {
                    count[str.charAt(i) - 'a']++;
                }

                int hash = getHash(count);
                if (!map.containsKey(hash)) {
                    map.put(hash, new ArrayList<String>());
                }

                map.get(hash).add(str);
            }

            for (ArrayList<String> tmp : map.values()) {
                if (tmp.size() > 1) {
                    result.addAll(tmp);
                }
            }

            return result;
        }
    }
    --

    30

    主题

    95

    帖子

    156

    积分

    注册会员

    Rank: 2

    积分
    156
    QQ
    发表于 2016-9-21 21:11:20 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个Anagram的参考程序


    代码看着有点奇怪,既然已经设置了int[] count, 每次将str的每一个字母放进去之后
    ,然后从0到26依次搜集这些字母,遍组成了一个hash code,这样互为anagram的两个
    字符串将拥有相同的hash code. 上面求解hash的 a *= b 存在溢出的风险。
    --

    24

    主题

    90

    帖子

    136

    积分

    注册会员

    Rank: 2

    积分
    136
    QQ
    发表于 2016-9-21 21:15:03 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个Anagram的参考程序


    我也觉得 理论上是不能保证的溢出了还能保证unique.
    一个26长度的int数组有INT_MAX^26种组合方式
    远远超出int的范围.

    就算每个int的范围是0~2 3^26也超出int的范围了.

    我发现他们家贴的好多答案都简单粗暴的不负责任啊.

    【 在 Yanjun (yanjun) 的大作中提到: 】
    : 代码看着有点奇怪,既然已经设置了int[] count, 每次将str的每一个字母放进去之后
    : ,然后从0到26依次搜集这些字母,遍组成了一个hash code,这样互为anagram的两个
    : 字符串将拥有相同的hash code. 上面求解hash的 a *= b 存在溢出的风险。



    --

    17

    主题

    1137

    帖子

    2261

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    2261
    QQ
    发表于 2016-10-5 11:41:56 | 显示全部楼层
    啊啊啊啊啊啊啊啊啊啊啊
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -问一个Anagram的参考程序- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -问一个Anagram的参考程序- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

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