Day1

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

实现思路：以长度最小的字符串为基准，遍历添加公共字符

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        
        StringBuilder rs = new StringBuilder();
        int minLen = 100001;
        //找到长度最小的元素
        for (int i = 0 ; i < strs.length; i ++)
            minLen = Math.min(strs[i].length(),minLen);
        //以长度最小的元素为基准
        for (int i = 0; i < minLen; i ++){
            char ch = 0;
            boolean flag = true;
            //遍历是否为公共字符
            for (int j = 0; j < strs.length; j ++){
                if (j == 0)   ch = strs[j].charAt(i);
                else if (ch != strs[j].charAt(i)){
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
            //若为公共字符，则添加
            rs.append(ch);
        }
        
        return rs.toString();
    }
}

微信红包

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
测试样例：
[1,2,3,2,2],5
返回：2

实现思路：使用哈希表来存储，以元素为key，元素出现的次数为value，最后再遍历哈希表，找出是否存在元素此时超过总数一半的元素。

public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        if (n == 0) return 0;
        Map<Integer,Integer> map = new HashMap<>();
        //添加到哈希表中
        for (int i = 0; i < n; i ++){
            Integer cur = map.get(gifts[i]);
            if (cur == null)
                map.put(gifts[i],1);
            else
                map.put(gifts[i],(++ cur));
        }
        //遍历哈希表，找出是否存在满足需求的元素
        int maxLen = 0;
        int pos = -1;
        for (Integer key : map.keySet()){
            if(map.get(key) > maxLen){
                pos = key;
                maxLen = map.get(key);
            }
        }
        
        return (maxLen > (n/2) ? pos : 0);
    }
}