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;
}
// 情况2：下一个元素是当前元素+1，属于连续序列，长度+1
else if (nums[i+1] == nums[i] + 1) {
currentLen++;
}
// 情况3：不连续，更新最长长度，并重置当前长度
else {
maxLen = Math.max(maxLen, currentLen);
currentLen = 1;
}
}
// 最后一次比较（处理数组末尾的连续序列）
maxLen = Math.max(maxLen, currentLen);
return maxLen;
}
// 冒泡排序（保持不变）
private void mysort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
}
这样显然不符合题目o(n)的要求。下面学习哈希法：
哦其实不用排序，直接哈希查数一直查，是否有x,x+1,…。为什么不用排序：为了避开在子序列上找答案，只要保证该序列不是子序列，也就是要保证枚举的数x在原数组中一定不存在前驱的x-1。并且set是自动去重的。
import java.util.HashSet;
import java.util.Set;
class Solution {
public int longestConsecutive(int[] nums) {
// 1. 创建哈希集合存储所有数字，实现O(1)时间复杂度的查询
// 哈希集合的特性：自动去重，且查询元素是否存在时效率极高
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) {
numSet.add(num); // 将数组中所有数字添加到集合中
}
// 用于记录最长连续序列的长度，初始化为0
int longestStreak = 0;
// 2. 遍历集合中的每个数字
for (int num : numSet) {
// 关键判断：只有当当前数字是一个序列的起点时，才开始计算连续长度
// 什么是序列的起点？即当前数字的前一个数字（num-1）不在集合中
// 这样可以避免重复计算（例如序列1,2,3，只会从1开始计算，不会从2或3开始）
if (!numSet.contains(num - 1)) {
int currentNum = num; // 当前正在检查的数字
int currentStreak = 1; // 当前连续序列的长度，至少为1（包含自身）
// 3. 不断检查下一个数字是否存在于集合中，扩展连续序列
// 例如当前数字是1，检查2是否存在，存在则继续检查3，以此类推
while (numSet.contains(currentNum + 1)) {
currentNum += 1; // 移动到下一个数字
currentStreak += 1; // 连续长度加1
}
// 4. 更新最长连续序列的长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
// 返回最长连续序列的长度
return longestStreak;
}
}
明天一定要二刷，能力欠缺，需要多学多练，深入地练习掌握。