14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
實(shí)現(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é)期間小明使用微信收到很多個(gè)紅包止状，非常開心巩趁。在查看領(lǐng)取紅包記錄時(shí)發(fā)現(xiàn)两嘴，某個(gè)紅包金額出現(xiàn)的次數(shù)超過了紅包總數(shù)的一半。請(qǐng)幫小明找到該紅包金額。寫出具體算法思路和代碼實(shí)現(xiàn)捌显，要求算法盡可能高效吠式。
給定一個(gè)紅包的金額數(shù)組gifts及它的大小n陡厘，請(qǐng)返回所求紅包的金額。
若沒有金額超過總數(shù)的一半奇徒，返回0雏亚。
測試樣例：
[1,2,3,2,2],5
返回：2
實(shí)現(xiàn)思路：使用哈希表來存儲(chǔ)，以元素為key摩钙，元素出現(xiàn)的次數(shù)為value罢低，最后再遍歷哈希表，找出是否存在元素此時(shí)超過總數(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);
}
}
