14. Longest Common Prefix

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

實現(xiàn)思路：以長度最小的字符串為基準(zhǔn)，遍歷添加公共字符

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);
        //以長度最小的元素為基準(zhǔn)
        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();
    }
}

微信紅包

春節(jié)期間小明使用微信收到很多個紅包，非常開心。在查看領(lǐng)取紅包記錄時發(fā)現(xiàn)，某個紅包金額出現(xiàn)的次數(shù)超過了紅包總數(shù)的一半。請幫小明找到該紅包金額。寫出具體算法思路和代碼實現(xiàn)，要求算法盡可能高效。
給定一個紅包的金額數(shù)組gifts及它的大小n，請返回所求紅包的金額。
若沒有金額超過總數(shù)的一半，返回0。
測試樣例：
[1,2,3,2,2],5
返回：2

實現(xiàn)思路：使用哈希表來存儲，以元素為key，元素出現(xiàn)的次數(shù)為value，最后再遍歷哈希表，找出是否存在元素此時超過總數(shù)一半的元素。

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);
    }
}