哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。
哈希表是使用 O(1)O(1) 时间进行数据的插入删除和查找，但是哈希表不保证表中数据的有序性，这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。
463. 岛屿的周长
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 :
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
题解：
class Solution {
public int islandPerimeter(int[][] grid) {
//思路：每个岛屿，如果四周都没有岛，那么它对周长的贡献就是4，
// 遍历二维数组，对每个岛查询上下左右相邻有没有岛屿，有岛屿对周长贡献-1，所有累加起来就是总周长
int totalEdge = 0;
for (int i = 0; i < grid.length; i++) {
int[] row = grid[i]; //当前行数组
//遍历当前行，值为1的为岛屿进行判断
for (int j = 0; j < row.length; j++) {
if (row[j] == 1) {
//当前点为岛屿，位置为 grid[i][j]
//上
if (i != 0) { //非第一行
if (grid[i - 1][j] != 1) {
//上一行对应位置没有岛屿，+1
totalEdge++;
}
} else {
totalEdge++;
}
//右
if (j != row.length-1) { //非该行最后一个位置
//不是最后一个
if (row[j+1] != 1) {
totalEdge++;
}
} else {
totalEdge++;
}
//下
if (i != grid.length-1) { //非最后一行
if (grid[i + 1][j] != 1) {
//下一行对应位置没有岛屿，+1
totalEdge++;
}
} else {
totalEdge++;
}
//左
if (j != 0) { //非该行第一个位置
//不是第一个
if (row[j-1] != 1) {
totalEdge++;
}
} else {
totalEdge++;
}
}
}
}
return totalEdge;
}
}
500. 键盘行
给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
示例：
输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]
题解：
class Solution {
public String[] findWords(String[] words) {
//思路：创建3个字符串，分别记录3行键盘所包含的字母字符
//遍历words数组，遍历单词字符，记录每个字符出现的键盘行数，用set存储各个行数值，如果最终只有一个值，那么表明在键盘的同一行
String[] enChar = new String[] {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
ArrayList<String> result = new ArrayList<>();
for (int i=0;i<words.length;i++) {
//遍历words
Set<Integer> record = new HashSet<>(); //用set存字符所在enchar位置，如果全部相等，最终set长度为1，否则大于1
for (int j=0;j<words[i].length();j++) {
//遍历每个单词
for (int k=0;k<enChar.length;k++) {
//遍历键盘每一行字符串
String wordChar = String.valueOf(words[i].charAt(j));
if (enChar[k].contains(wordChar)) {
record.add(k);
}
}
}
if (record.size() == 1) {
result.add(words[i]); //记录该满足条件字符串
}
}
return result.toArray(new String[result.size()]);
}
}
771. 宝石与石头
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
题解：
class Solution {
public int numJewelsInStones(String J, String S) {
int totalCount = 0;
//遍历J中的每种宝石，将S中有宝石的各种数量累加起来
for (int i=0;i<J.length();i++) {
Character jeuwls = J.charAt(i);
String restStr = S.replaceAll(String.valueOf(jeuwls), ""); //将珠宝字符替换掉
int count = S.length() - restStr.length(); //长度变短数为该字符出现在字符串中的次数
totalCount += count; //累加每种宝石数量
}
return totalCount;
}
}
349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
题解：
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> jiaoji = new HashSet<>();
for (int i=0;i<nums1.length;i++) {
for (int j=0;j<nums2.length;j++) {
if (nums1[i] == nums2[j]) {
jiaoji.add(nums1[i]);
break;
}
}
}
int[] jiaojiArray = new int[jiaoji.size()];
int pos = 0;
Iterator iterator = jiaoji.iterator();
while (iterator.hasNext()) {
jiaojiArray[pos] = (int) iterator.next();
pos++;
}
return jiaojiArray;
}
}
1207. 独一无二的出现次数
给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
示例 1：
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：
输入：arr = [1,2]
输出：false
示例 3：
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true
题解：
class Solution {
public boolean uniqueOccurrences(int[] arr) {
//思路：存储每一个数字出现的次数，判断这些次数是否都不相等
Map<Integer, Integer> record = new HashMap<>();
for (int num : arr) {
if (!record.containsKey(num)) {
record.put(num, 1);
} else {
record.put(num , record.get(num) + 1);
}
}
//遍历map，将value值存入set去判断是否有相同值，如果有，则false，否则返回true
Set<Map.Entry<Integer, Integer>> entries = record.entrySet();
Set<Integer> set = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : entries) {
if (!set.add(entry.getValue())) {
//添加失败，说明有相同值
return false;
}
}
return true;
}
}
1160. 拼写单词
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 ：
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
题解：
class Solution {
public int countCharacters(String[] words, String chars) {
int enLength = 26;
StringBuilder stringBuilder = new StringBuilder();
//解决方案：将每个字符串维护一张长度为26的int数组，存储a-z26个字母各自出现的次数
int[] charsArray = new int[enLength];
for (int i=0;i<chars.length();i++) {
charsArray[chars.charAt(i) - 'a'] += 1; //chars.char(i)-'a' 表示当前字符在a-z数组的序号，如c-'a'=2为c在字母表中序号
}
//给words数组中每个字符串创建一张字母表
a : for (String str : words) {
int[] strArray = new int[enLength];
for (int i=0;i<str.length();i++) {
strArray[str.charAt(i) - 'a'] += 1;
}
//核心判断：因为chars 中的每个字母都只能用一次，所有chars中每种字母次数不能比word中的小，不然就重复使用了
for (int i=0;i<enLength;i++) {
if (strArray[i] > charsArray[i]) {
continue a;
}
}
//顺利执行到此，表明满足条件，添加单词记录
stringBuilder.append(str);
}
return stringBuilder.length();
}
}
1002. 查找常用字符
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：
输入：["bella","label","roller"]
输出：["e","l","l"]
示例 2：
输入：["cool","lock","cook"]
输出：["c","o"]
题解：
class Solution {
public List<String> commonChars(String[] A) {
//思路：取出数组第一个字符串，遍历该字符串字符，遍历其他字符串，用indexof去找当前字符，如果没找到，则该字符为不常用
//如果找到了，删除该字符串，找到一轮遍历完成，那么该字符为常用字符
String compareStr = A[0];
List<String> strArray = new ArrayList<>();
a : for (int i=0;i<compareStr.length();i++) {
char ch = compareStr.charAt(i);
for (int j=1;j<A.length;j++) {
int pos = A[j].indexOf(ch);
if (pos == -1) {
//未找到
continue a;
} else {
//找到需要删去
A[j] = strRemoveChar(A[j], pos);
}
}
//ch字符在每个字符串都找到，属于常用字符串
strArray.add(String.valueOf(ch));
}
return strArray;
}
/**
* 删除字符串指定位置的字符
* @param string
* @param pos
* @return
*/
public String strRemoveChar(String string, int pos) {
return string.substring(0, pos) + string.substring(pos+1);
}
}
811. 子域名访问计数
一个网站域名，如"discuss.leetcode.com"，包含了多个子域名。作为顶级域名，常用的有"com"，下一级则有"leetcode.com"，最低的一级为"discuss.leetcode.com"。当我们访问域名"discuss.leetcode.com"时，也同时访问了其父域名"leetcode.com"以及顶级域名 "com"。
给定一个带访问次数和域名的组合，要求分别计算每个域名被访问的次数。其格式为访问次数+空格+地址，例如："9001 discuss.leetcode.com"。
接下来会给出一组访问次数和域名组合的列表cpdomains 。要求解析出所有域名的访问次数，输出格式和输入格式相同，不限定先后顺序。
示例 1:
输入:
["9001 discuss.leetcode.com"]
输出:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
说明:
例子中仅包含一个网站域名："discuss.leetcode.com"。按照前文假设，子域名"leetcode.com"和"com"都会被访问，所以它们都被访问了9001次。
题解：
class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
//思路：分别计算各种域名访问的次数，从三级域名到二级到一级，分别计算二级和一级访问的总数
//用Map来存各种域名访问的次数
Map<String, Integer> record = new HashMap<>();
for (String str : cpdomains) {
record(record, str);
}
ArrayList<String> datas = new ArrayList<>();
Set<Map.Entry<String, Integer>> entries = record.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
datas.add(entry.getValue() + " " + entry.getKey());
}
return datas;
}
private void record(Map<String, Integer> record, String ip) {
String[] data = ip.split(" ");
int count = Integer.parseInt(data[0]); //ip访问次数
String fullIp = data[1]; //ip全称
//从该ip获得所有个子ip地址
putValue(record, fullIp, count);
getSubIp(record, fullIp, count);
}
/**
* 递归获取所有子域名
* @param record
* @param fullIp
* @param count
*/
private void getSubIp(Map<String, Integer> record, String fullIp, int count) {
int pos = fullIp.indexOf(".");
if (pos != -1) {
//有子域名
fullIp = fullIp.substring(pos+1);
putValue(record, fullIp, count);
getSubIp(record, fullIp, count);
}
}
private void putValue(Map<String, Integer> record, String fullIp, int count) {
if (!record.containsKey(fullIp)) {
record.put(fullIp, count);
} else {
record.put(fullIp, record.get(fullIp)+count);
}
}
}
575. 分糖果
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:
输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
题解：
class Solution {
public int distributeCandies(int[] candies) {
//思路：遍历candies存入map中，判断map的长度，如果长度<=candies.length/2，则妹妹糖果种类为map长度，如果长度>candies.length/2，则为
//candies.length/2
Map<Integer, Integer> record = new HashMap<>();
for (int candy : candies) {
if (!record.containsKey(candy)) {
record.put(candy, 1);
} else {
record.put(candy, record.get(candy) + 1);
}
}
if (record.size() <= candies.length/2) {
return record.size();
} else {
return candies.length/2;
}
}
}
884. 两句话中的不常见单词
给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）
如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。
返回所有不常用单词的列表。
您可以按任何顺序返回列表。
示例 1：
输入：A = "this apple is sweet", B = "this apple is sour"
输出：["sweet","sour"]
题解：
class Solution {
public String[] uncommonFromSentences(String A, String B) {
String result = get(A, B) + get(B, A);
System.out.println(result);
if (result.length() == 0) {
return new String[]{};
} else {
return result.split(" ");
}
}
private String get(String A, String B) {
StringBuilder stringBuilder = new StringBuilder();
String[] arrayA = A.split(" ");
String[] arrayB = B.split(" ");
a : for (int i=0;i<arrayA.length;i++) {
//如果B中包含字符串，则不是不常见单词
for (String strB : arrayB) {
if (strB.equals(arrayA[i])) {
continue a;
}
}
//如果B中不包含，还需要判断arrayA中该字符串是否重复
for (int j=0;j<arrayA.length;j++) {
if (i != j) { //避免自己与自己再匹配
if (arrayA[j].equals(arrayA[i])) {
continue a;
}
}
}
stringBuilder.append(arrayA[i] + " ");
}
return stringBuilder.toString();
}
}
389. 找不同
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例:
输入：
s = "abcd"
t = "abcde"
输出：
e
解释：
'e' 是那个被添加的字母。
题解：
class Solution {
public char findTheDifference(String s, String t) {
//思路：将s、t字符串分别将字符存入map中，字符为key，存入次数为value，遍历t的map，如果存在t中key在s中不存在，则该key为被添加的字母
//如果t中的value与s中对应keyvalue不相等，则该key也为被添加的字母
Map<Character, Integer> mapS = record(s);
Map<Character, Integer> mapT = record(t);
Set<Map.Entry<Character, Integer>> entries = mapT.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
if (!mapS.containsKey(entry.getKey())) {
return entry.getKey();
}
if (entry.getValue() != mapS.get(entry.getKey())) {
return entry.getKey();
}
}
throw new IllegalArgumentException("不存在该字母");
}
private Map<Character, Integer> record(String s) {
Map<Character, Integer> mapS = new HashMap<>();
for (int i=0;i<s.length();i++) {
char ch = s.charAt(i);
if (!mapS.containsKey(ch)) {
mapS.put(ch, 1);
} else {
mapS.put(ch, mapS.get(ch)+1);
}
}
return mapS;
}
}
网友评论