JAVA算法题练习day1

开始前：

选择leetcode-hot100。要求每日1道，并且需要亲自二刷昨天的题目（每一种解法），要做解题笔记并发布CSDN，做完立刻二刷。做题时间为每日12：50起，不拖延，这是学习成长的机会，坚持下去就会变得很厉害很强。当然，学习是一个持续的过程，开学之后每日JAVA做的算法题就是leetcode面试经典150题。变强。努力提升算法和工程能力。

力扣hot100

哈希

1.两数之和

return new int[0] 表示返回一个长度为 0 的 int 类型数组

暴力枚举：

class Solution {

public int[] twoSum(int[] nums, int target) {

for(int i = 0;i<nums.length;i++){

for(int j=i+1;j<nums.length;j++){

if(nums[j]==(target-nums[i])){

int[] arr = new int[]{i,j};

return arr;

}

return new int[0];

}

哈希表：

复习代码随想录的哈希表理论基础

(代码随想录)

一般选择3种数据结构来做哈希：数组、set（集合）、map（映射）

C++：“当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。”

JAVA中哈希法涉及的数据结构：

1. HashMap（最常用的哈希表实现）

特点：基于哈希表实现，允许存储 null 键和 null 值，无序（键值对的存储顺序与插入顺序无关）。
底层结构：JDK 1.8 后采用「数组 + 链表 + 红黑树」结构：
- 数组（哈希桶）：每个索引对应一个链表或红黑树。
- 链表：解决哈希冲突（不同键映射到同一索引），当链表长度超过 8 时转为红黑树（提高查询效率）。
核心方法：
- put(key, value)：插入键值对（若键已存在则覆盖值）。
- get(key)：根据键获取值（不存在返回 null）。
- containsKey(key)：判断是否包含指定键。
- remove(key)：删除指定键的键值对。
适用场景：
- 需快速通过键查找值（如缓存、计数统计）。
- 解决两数之和、子数组和等算法问题（通过键存储目标值，值存储索引）。

2. HashSet（基于 HashMap 的集合）

特点：底层通过 HashMap 实现（将元素作为 HashMap 的键，值为固定常量），不允许重复元素，无序，允许 null 元素。
核心方法：
- add(element)：添加元素（若已存在则返回 false）。
- contains(element)：判断元素是否存在。
- remove(element)：删除元素。
适用场景：
- 需要去重或快速判断元素是否存在（如查找交集、判断是否包含重复元素）。
- 替代数组或链表做查找操作（时间复杂度从 O (n) 降至 O (1)）。

Map:因为要用元素值去找匹配的元素，最后返回的是下标，所以元素值作为key（用于哈希查找），下标作为value。

JAVA map,set学习链接：

(https://blog.csdn.net/qq_47980550/article/details/148064851)

(https://blog.csdn.net/qq_47980550/article/details/148085987)

哈希法：

class Solution {

public int[] twoSum(int[] nums, int target) {

Map<Integer,Integer> map = new HashMap<Integer,Integer>();

for(int i=0;i<nums.length;i++){

if(map.containsKey(target-nums[i])){

int[] arr = new int[]{i,map.get(target-nums[i])};

return arr;

}

else map.put(nums[i],i);

}

return new int[0];

}

MAP用于记录遍历过的。

2. 字母异位词分组

题意：要做的还是遍历一遍，过程中用MAP存遍历，找。题目返回的类型是List需要先学习List:

(https://blog.csdn.net/qq_47980550/article/details/148012216)

回顾做过的题：242.有效的字母异位词。

该题（242.有效的字母异位词）哈希：

class Solution {

public boolean isAnagram(String s, String t) {

// 首先判断长度是否相等，不等直接返回false

if (s.length() != t.length()) {

return false;

}

// 手动创建计数数组，存储每个字母的出现次数

int[] count = new int[26];

// 手动遍历字符串s，统计每个字符出现次数

for (int i = 0; i < s.length(); i++) {

// 手动计算字符对应的索引（'a'-'z'对应0-25）

char c = s.charAt(i);

int index = 0;

// 不使用减法运算，手动计算索引（锻炼基础逻辑）

for (char ch = 'a'; ch <= 'z'; ch++) {

if (ch == c) {

break;

}

index++;

}

count[index]++;

}

// 手动遍历字符串t，减少对应字符的计数

for (int i = 0; i < t.length(); i++) {

char c = t.charAt(i);

int index = 0;

for (char ch = 'a'; ch <= 'z'; ch++) {

if (ch == c) {

break;

}

index++;

}

count[index]--;

// 如果出现负数，说明t包含s没有的字符

if (count[index] < 0) {

return false;

}

// 检查所有计数是否为0

for (int i = 0; i < 26; i++) {

if (count[i] != 0) {

return false;

}

return true;

}

}
该题（242.有效的字母异位词）暴力解法：

public class AnagramChecker {

public static boolean isAnagram(String s, String t) {

// 首先检查长度是否相同

if (s.length() != t.length()) {

return false;

}

// 自定义方法将字符串转换为字符数组

char[] sChars = stringToCharArray(s);

char[] tChars = stringToCharArray(t);

// 使用冒泡排序对字符数组排序

bubbleSort(sChars);

bubbleSort(tChars);

// 比较排序后的字符数组

for (int i = 0; i < sChars.length; i++) {

if (sChars[i] != tChars[i]) {

return false;

}

return true;

}

// 自定义方法：将字符串转换为字符数组

private static char[] stringToCharArray(String str) {

// 创建与字符串长度相同的字符数组

char[] arr = new char[str.length()];

// 逐个提取字符并放入数组

for (int i = 0; i < str.length(); i++) {

arr[i] = str.charAt(i);

}

return arr;

}

// 冒泡排序实现

private static void bubbleSort(char[] arr) {

int n = arr.length;

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < n - i - 1; j++) {

if (arr[j] > arr[j + 1]) {

// 交换元素

char temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

public static void main(String[] args) {

// 测试示例

System.out.println(isAnagram("anagram", "nagaram")); // 输出: true

System.out.println(isAnagram("rat", "car")); // 输出: false

}

冒泡排序：核心逻辑是（重复地比较两个相邻的元素，如果他们是逆序，就交换他们，知道整个序列排序完成）

(三分钟学会冒泡排序_哔哩哔哩_bilibili)

private static void bubbleSort(char[] arr) {

int n = arr.length; // 获取数组长度

// 外层循环：控制需要进行多少轮比较

// 每一轮都会将当前未排序部分的最大元素"浮"到末尾

for (int i = 0; i < n - 1; i++) {

// 内层循环：进行每一轮的相邻元素比较

// n - i - 1：因为每轮结束后，最后i个元素已经排好序，不需要再比较

for (int j = 0; j < n - i - 1; j++) {

// 如果当前元素大于下一个元素，说明顺序错误，需要交换

if (arr[j] > arr[j + 1]) {

// 交换元素（借助临时变量temp）

char temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

接下来做49.字母异位词分组

把排序后的字符串作为键，将原字符串集合作为VALUE

JAVA ArrayList

(Java中ArrayList常用方法_java arraylist方法-CSDN博客)

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class AnagramGrouper {

// 主方法：将字符串数组中的异位词分组

public List<List<String>> groupAnagrams(String[] strs) {

// 创建一个HashMap，用于存储分组结果

// 键：字符串的特征编码（如"a3b2c1"）

// 值：具有相同特征编码的字符串列表（即异位词组）

Map<String, List<String>> groups = new HashMap<>();

// 遍历输入的每个字符串

for (String str : strs) {

// 1. 计算当前字符串的字符计数数组

int[] counter = new int[26]; // 26个位置对应a-z 26个字母

for (int i = 0; i < str.length(); i++) {

// 获取当前字符，计算它在数组中的索引（a->0, b->1, ..., z->25）

char c = str.charAt(i);

int index = c - 'a';

// 对应位置的计数加1

counter[index]++;

}

// 2. 将计数数组转换为字符串编码（如[0,2,1] -> "b2c1"）

StringBuilder sb = new StringBuilder();

for (int i = 0; i < 26; i++) {

// 只处理出现过的字符，减少编码长度

if (counter[i] != 0) {

// 添加字符（如i=0对应'a'，i=1对应'b'）

sb.append((char) ('a' + i));

// 添加该字符出现的次数

sb.append(counter[i]);

}

String code = sb.toString(); // 得到编码字符串

// 3. 将当前字符串添加到对应的分组中

// 如果该编码不存在于map中，先创建一个新列表

if (!groups.containsKey(code)) {

groups.put(code, new ArrayList<>());

}

// 将当前字符串添加到对应的列表中

groups.get(code).add(str);

}

// 4. 将map中的所有值（即分组列表）转换为List并返回

return new ArrayList<>(groups.values());

}

// 测试方法

public static void main(String[] args) {

AnagramGrouper solution = new AnagramGrouper();

String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

List<List<String>> result = solution.groupAnagrams(strs);

// 打印结果

for (List<String> group : result) {

System.out.println(group);

}

// 输出应该是：

// [eat, tea, ate]

// [tan, nat]

// [bat]

}

排序：由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

class Solution {

public List<List<String>> groupAnagrams(String[] strs) {

// 创建一个哈希表，用于存储分组结果

// 键：排序后的字符串（例如"aet"）

// 值：具有相同排序结果的字符串列表（即异位词分组）

Map<String, List<String>> map = new HashMap<String, List<String>>();

// 遍历数组中的每个字符串

for (String str : strs) {

// 1. 将字符串转换为字符数组

// 例如 "eat" 会变成 ['e', 'a', 't']

char[] array = str.toCharArray();

// 2. 对字符数组进行排序

// 排序后 ['e', 'a', 't'] 会变成 ['a', 'e', 't']

Arrays.sort(array);

// 3. 将排序后的字符数组转换回字符串

// 这里就是你不理解的 String key = new String(array);

// 作用：把排序后的字符数组['a', 'e', 't']变成字符串"aet"

// 互为异位词的字符串排序后会得到相同的key

String key = new String(array);

// 4. 这是你不理解的getOrDefault方法

// 作用：尝试从map中获取key对应的列表

// 如果存在，就直接使用这个列表；如果不存在，就创建一个新的空列表

List<String> list = map.getOrDefault(key, new ArrayList<String>());

map.getOrDefault(key, new ArrayList<String>())这是 Map 接口的一个便捷方法，等价于下面的代码：

List<String> list;

if (map.containsKey(key)) {

// 如果map中已经有这个key，就获取已有的列表

list = map.get(key);

} else {

// 如果map中没有这个key，就创建一个新的空列表

list = new ArrayList<String>();

}

// 5. 将当前字符串添加到对应的列表中

list.add(str);

// 6. 将更新后的列表放回map中

map.put(key, list);

}

// 7. 将map中所有的值（即所有分组）转换为List并返回

return new ArrayList<List<String>>(map.values());

}

3.最长连续序列

我想要做暴力法：冒泡排序+算法。但是有很多考虑不周全的地方，其实还要多练，加油。

问题分析

最后一段连续序列未被统计
循环结束后，最后一段连续序列的长度（cnt）没有与结果（res）比较，导致如果最长序列在数组末尾，会被遗漏。
flag变量的逻辑混乱
flag的存在使得重复元素的处理变得复杂，尤其是当重复元素出现在连续序列的起始位置时，会错误地重置计数。
重复元素处理不当
当遇到重复元素（nums[i] == nums[i+1]）时，无论是否在连续序列中，都应该直接跳过（不影响连续长度），但你的代码中flag的判断导致了错误的分支进入。

class Solution {

public int longestConsecutive(int[] nums) {

if (nums.length == 0) return 0;

// 先排序

mysort(nums);

int maxLen = 1; // 最长连续序列长度

int currentLen = 1; // 当前连续序列长度

for (int i = 0; i < nums.length - 1; i++) {

// 情况1：当前元素与下一个元素相等（重复元素），不影响连续长度，直接跳过

if (nums[i] == nums[i+1]) {

continue;

}