两数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> rem = new HashMap<>();
int l = nums.length;
for (int i = 0; i < l; i++) {
rem.put(nums[i], i);
}
for (int i = 0; i < l; i++) {
int left = target - nums[i];
if (rem.containsKey(left) && rem.get(left) != i) {
return new int[] {i,rem.get(left)};
}
}
return null;
}
}
|
- 数组越界问题，注意遍历时不能取等
- 返回值是int数组，new int[]{}即可
- 注意循环判断时要判断rem.get(left) != i，确认不是同一个索引
优化成一遍遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> rem = new HashMap<>();
int l = nums.length;
for(int i = 0;i < l;i++)
{
int complement = target - nums[i];
if(rem.containsKey(complement)){
return new int[]{rem.get(complement),i};
}
rem.put(nums[i],i);
}
return new int[0];
}
}
|
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
排序
把每个单词按照字母序排序，把排序后的字符串作为key，列表为值，原字符串为列表的一部分。显然字母异位词key相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String word : strs) {
char[] charArray = word.toCharArray();
Arrays.sort(charArray);
String sortedString = new String(charArray);
if (map.containsKey(sortedString)) {
map.get(sortedString).add(word);
} else {
List<String> temp = new ArrayList<>();
temp.add(word);
map.put(sortedString,temp);
}
}
return new ArrayList<>(map.values());
}
}
|
时间复杂度O(nklogk),n个字符串，字符串最大长度k
空间复杂度O(nk)
注意；
- List列表是个接口，ArrayList和LinkedList(双向链表)是他的实现类
- ？是通配符，？extends E代表E以及子类
- collection也是个接口，定义了add，remove,size,isEmpty,contains等方法。List,Set,Queue，都是实现类
- Java中String和字符数组不同（c中没有string，只有字符数组实际上）。Java中String是个对象，内部实现封装了一个字符数组（或者byte[])，有不可变性（一旦创建不可改变），和chat[]可以通过方法互相转换
计数
key代表表示字母频率的唯一标识，将频率数组转换成特殊的字符串。
遍历输入的字符串数组中的每一个字符串，每个字符串创建一个长度26的整型数组，遍历每个字符串创建一个整型数组记录频率，之后转换成频率字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String word : strs) {
int[] count = new int[26];
for (char c : word.toCharArray()) {
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
sb.append((char) ('a' + i));
sb.append(count[i]);
}
}
String key = sb.toString();
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(word);
}
return new ArrayList<>(map.values());
}
}
|
时间复杂度O(nk),k是最长字符串长度
空间复杂度O(nk)
注意：
StringBuilder类（非线程安全）
- 可变
- 频繁修改字符串性能高与string
- 丰富方法：添加插入删除反转等
Java的String也可以进行加法运算（实际上是字符串拼接），但实际上是创建了新的对象
最长连续序列
自己想法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| import java.util.HashSet;
import java.util.Set;
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length <= 1)
{
return nums.length;
}
Set<Integer> integerSet = new HashSet<>();
int min = nums[0];
int max = nums[0];
for (int i : nums) {
if(!integerSet.contains(i))
{
integerSet.add(i);
}
if(i < min)
{
min = i;
}
if(i > max)
{
max = i;
}
}
if(max == min)
{
return 1;
}
int[] counts = new int[max - min];
int j = 0;
for (int i = min; i < max ; i++) {
if(integerSet.contains(i+1))
{
counts[j]++;
}else {
j++;
}
}
int maxNum = counts[0];
for (int i : counts) {
if(maxNum < i)
{
maxNum = i;
}
}
return maxNum + 1;
}
}
|
上面 不太对，尤其是[1,100]无法通过，而且复杂度过高,下面优化
- 对原数组的元素进行遍历即可。每个num先看看num-1是否在，不在的话是个起点，开始遍历+1+2+3……。如果在的话跳过
- 每次得到一个长度直接和当前长度比较，取最大的，不必建立数组储存全部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.HashSet;
import java.util.Set;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> integers = new HashSet<>();
for (int i : nums) {
integers.add(i);
}
int result = 0;
for (int num : nums) {
if(!integers.contains(num - 1)) {
int curnum = num;
int resultThisLoop = 1;
while (integers.contains(curnum + 1)) {
resultThisLoop++;
curnum++;
}
result = Math.max(result,resultThisLoop);
}
}
return result;
}
}
|
实际上来说直接遍历哈希集合就行，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.util.HashSet;
import java.util.Set;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> integers = new HashSet<>();
for (int i : nums) {
integers.add(i);
}
int result = 0;
for (int num : integers) {
if(!integers.contains(num - 1)) {
int curnum = num;
int resultThisLoop = 1;
while (integers.contains(curnum + 1)) {
resultThisLoop++;
curnum++;
}
result = Math.max(result,resultThisLoop);
}
}
return result;
}
}
|
关于遍历哈希表
1. 使用 for-each 循环遍历 entrySet() (推荐)
这是最常用且推荐的遍历方式，因为它可以同时访问键和值，并且代码简洁易读。entrySet() 方法返回一个包含哈希表中所有键值对（Map.Entry）的 Set 视图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| import java.util.HashMap;
import java.util.Map;
public class TraverseHashMap {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("一", 1);
map.put("二", 2);
map.put("三", 3);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("键: " + key + ", 值: " + value);
}
}
}
|
2. 使用 for-each 循环遍历 keySet()
如果你只需要遍历哈希表的键，可以使用 keySet() 方法。如果需要根据键获取值，可以再调用 get() 方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| import java.util.HashMap;
import java.util.Map;
public class TraverseHashMapKeys {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("一", 1);
map.put("二", 2);
map.put("三", 3);
for (String key : map.keySet()) {
Integer value = map.get(key);
System.out.println("键: " + key + ", 值: " + value);
}
}
}
|
3. 使用迭代器 (Iterator)
你也可以使用迭代器来遍历 entrySet() 或 keySet()。这种方式在需要在遍历过程中从哈希表中安全地删除元素时特别有用。
遍历 entrySet()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class TraverseWithIterator {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("一", 1);
map.put("二", 2);
map.put("三", 3);
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("键: " + key + ", 值: " + value);
}
}
}
|
4. 使用 Java 8 的 forEach 方法和 Lambda 表达式
从 Java 8 开始，你可以使用 forEach 方法和 lambda 表达式来遍历哈希表，这使得代码更加简洁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import java.util.HashMap;
import java.util.Map;
public class TraverseWithLambda {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("一", 1);
map.put("二", 2);
map.put("三", 3);
map.forEach((key, value) -> {
System.out.println("键: " + key + ", 值: " + value);
});
}
}
|
5. 遍历 values()
如果你只关心哈希表中的值，可以只遍历 values() 集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import java.util.HashMap;
import java.util.Map;
public class TraverseValues {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("一", 1);
map.put("二", 2);
map.put("三", 3);
for (Integer value : map.values()) {
System.out.println("值: " + value);
}
}
}
|
Hashtable 的特有方法：Enumeration
Hashtable 是一个较旧的类，它还提供了一个名为 elements() 和 keys() 的方法，分别返回一个 Enumeration 对象来遍历值和键。不过，现在更推荐使用 Iterator。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.Enumeration;
import java.util.Hashtable;
public class TraverseHashtable {
public static void main(String[] args) {
Hashtable<String, Integer> hashtable = new Hashtable<>();
hashtable.put("一", 1);
hashtable.put("二", 2);
hashtable.put("三", 3);
Enumeration<String> keys = hashtable.keys();
while (keys.hasMoreElements()) {
String key = keys.nextElement();
Integer value = hashtable.get(key);
System.out.println("键: " + key + ", 值: " + value);
}
}
}
|
总结
| 方法 |
优点 |
缺点 |
for-each 循环 entrySet() |
代码最简洁，效率高，可同时访问键和值 |
无法在遍历时安全地修改哈希表（除了通过 entry.setValue()） |
for-each 循环 keySet() |
代码简洁，适用于只需要键的场景 |
如果需要值，需要额外调用 get()，效率稍低 |
| 迭代器 (Iterator) |
可以在遍历时安全地删除元素 |
代码相对 for-each 循环稍显繁琐 |
Java 8 forEach |
代码非常简洁，函数式编程风格 |
需要 Java 8 或更高版本 |
for-each 循环 values() |
适用于只需要值的场景 |
无法直接访问键 |
Enumeration (仅 Hashtable) |
Hashtable 的传统方法 |
已被 Iterator 取代，不推荐在新代码中使用 |
