2025.10.17

哈希

补充知识： https://javaguidepro.com/blog/hash-table-java/

哈希表是根据key直接访问存储位置的暑假结构，key–>hash函数–>存储桶，每个存储桶可以存储一个或多个键值对。（哈希冲突即不同的键映射到同一个存储桶中）

1.Hashtable 是 Java 中最早提供的哈希表实现，它是线程安全的，不允许键或值为 null

2.HashMap 是 Java 中最常用的哈希表实现，它不是线程安全的，允许键和值为 null

3.LinkedHashMap 是 HashMap 的子类，它维护了一个双向链表，用于记录键值对的插入顺序或访问顺序

当需要查询一个元素是否出现过，或者一个元素是否在集合里—>哈希法。用空间换时间，可以用数组、set、map…做哈希法

两数之和 题解1. 双重循环 题解2. 哈希法 Map（key，value） （我想的一个是双重循环，一个是排序比较，但是注意审题，排序之后下标都变了肯定不对！） a + b = target， 当指针指到a时，可以去map中找b是否存在。key存放值，value存放下标

参考题解: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.md

代码： class Solution { public int[] twoSum(int[] nums, int target) { // 创建一个返回数组 int[] res = new int[2]; // 当传入的数组为空 直接返回[ , ] //数组为null是空引用，并没有创建这个数组对象 数组长度为0是有这个数组对象但数组元素为空 if(nums == null || nums.length == 0){ return res; } Map<Integer,Integer> indexMap = new HashMap<>(); // 遍历到某个a元素的时候，去map中找是否有满足target - a = b的b元素 有则将两者下标返回 没有则加入map // nums[i]当作key, i当作value for(int i = 0; i < nums.length; i++){ if(indexMap.containsKey(target - nums[i])){ res[0] = i; res[1] = indexMap.get(target - nums[i]); return res; } indexMap.put(nums[i],i); // haspMap插入key-value键值对 } return res; } }

移动零

class Solution { public void moveZeroes(int[] nums) { int[] res = new int[]; if(nums == null || nums.length == 0){ return res; }

}

}

2025.10.22

普通数组：

53.最大子数组和

1.我首先想的是双指针 但是最大子数组和不具备单调性，无法使用常规的“滑动窗口”技巧（即不能通过移动左右指针来收缩或扩展窗口以逼近答案）–方法选用不当 不知道什么算法应该解决什么问题 2.前缀和 用数组来保存前缀和 这里又有几个坑 比如不能让fix_num += num[i] 因为fix_num中的元素初始化都为0 这相当于 fix_num = num[i]。 求前缀和可以用sum+=num[i],然后让fix_num[i] = sum; 而且要注意，不能简单的用最大前缀和-最小前缀和，要满足这个最大前缀和在最小前缀和的右边 否则不能计算。

1
2
3
4
5
6
7
8
9

// 生成前缀和数组
   int sum = 0;
        int[] fix = new int[nums.length];
        int index = 0；
        for(int x : nums){ // 这里的x是数组的元素 不是下标
            sum += x;
            fix[index] = sum;
            index++；
        }

最大区间和 = fix[j] - fix[i-1]，其中 i <= j 要使这个差值最大，就要让 fix[j] 尽可能大，fix[i-1] 尽可能小，且 i-1 < j.【为什么是减去fix[i-1]???】 3.动态规划DP

二分查找：

力扣35 搜索插入位置

 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

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 可能出现的情况四种1.找到nums[mid] = target
        // 2.没出现 目标值在最前面 
        // 3.没出现 目标值在最后面
        // 4.没出现 目标值在某个区间
        //  2 3 4 要保证统一返回
        int low = 0;
        int high = nums.length - 1;
        int mid = (high + low)/2;
        while(low <= high){
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                high = mid - 1;
                mid = (high + low)/2;
            }else{
                low = mid + 1;
                mid = (high + low)/2;
            }
            
        }
        return high + 1;
    }
}

74.搜索二维矩阵

我的想法就是将二维矩阵变成一维数组 然后再使用二分查找 因为这个题目中的数组都是m行n列的。别人的题解说可以用两次二分查找，之后记得看看！

1.如何遍历二维数组并将其转换为一维数组？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int m = matrix.length;        // 行数
int n = matrix[0].length;  // 第一行的列数  matrix[i].length表示第i行的列数
int[] nums = new int[m*n];
int index = 0;
for(int i = 0;i<m;i++){
    for(int j = 0;j<n;j++){
        nums[index] = matrix[i][j];
            index++;
        }
            
}

 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

// 完整代码
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;        // 行数
        int n = matrix[0].length;  // 第一行的列数
        int[] nums = new int[m*n];
        int index = 0;
        boolean flag = false;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                nums[index] = matrix[i][j];
                index++;
            }
            
        }
       
        int i = 0;
        int j = nums.length - 1;
        
        while( i <= j){
            int mid = i + (j-i)/2;
            if(target > nums[mid]){
                i = mid+1;
            }else if(target < nums[mid]){
                j = mid -1;
            }else{
                flag = true;
                return flag;
            }
        }
        return flag;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

寻找左边界（不含target）和右边界（不含target） 主要还是要考虑清楚返回值是什么 要考虑target 存在和不存在的情况？？？？

33. 搜索旋转排序数组

我想的是让这个旋转后的数组变成一个有序数组 然后进行二分查找 找到target 即新建一个数组存放原始未旋转的数组 然后找到在这个数组中target的下标 再去求旋转后数组的下标 但是有个问题 找旋转点的过程需要遍历整个数组O(N)

为什么情况是这么多种？？？？ 1.二分后，左边的数组是升序的(nums[0]<nums[mid]) 1.1 target>nums[mid]：应该往右边搜索 1.2 target<nums[mid]并且target<nums[0]：应该往右边搜索 1.3 target<nums[mid]并且target>=nums[0]：应该往左边搜索

2.二分后，左边的数组是存在翻转点的(nums[0]>nums[mid]) 2.1 target<nums[mid]并且target>=nums[0]：应该往左边搜索 2.2 target<nums[mid]并且target<nums[0]：应该往左边搜索 2.3 target>nums[mid]并且target<nums[0]：应该往右边搜索 2.4 target>nums[mid]并且target>=nums[0]：应该往左边搜索

完成情况：（左右边界那题也不熟悉）

2025.10.23

今天换了一种刷题的策略 不按照分类做了 直接按照题单顺序来做 我觉得简单题其实难度还好 中等难度的题我就A不出来了 主要还是在于我的数据结构基础掌握的不是很牢固 今天刷题的时候遇到的问题：

1.hashmap怎么初始化 hashmap的操作 hashMap怎么遍历 怎么获得key 怎么获得value

2.动态数组ArrayList怎么创建 ArrayList的常见操作

3.位运算 异或运算符^，异或运算的性质 –相同为0，不同为1 任意数与0异或，结果仍是它本身。与运算 &

4.数组内置排序：Arrays.sort( )

5.Java支持十进制数字直接进行逻辑运算（计算的时候是按照二进制进行计算的）

2025.10.25

今天把之前写过的简单题回顾了一下 其中还是有一些题A不出来的 而且有的时候想法太多 一道题目把好几道题解想混了 就越想越多 反而做不出来 而且这些题解的时间复杂度和空间复杂度还有优化的可能 未来需要学习别人高阶的题解，还有一个问题是我对Java中内置的函数了解的不多 导致重复造轮子 写起来就比较吃力。 如果让我回顾一下简单题的知识点的话，首先是数据结构的实现：链表的数据结构（单链表），树的数据结构（二叉树）。主要涉及到的知识点：数组，动态数组ArrayList，HashMap（如何遍历HashMap），链表，位运算（异或，按位与），双指针，递归，二分查找。总体来说今天的状态还是满意的 写了16道题 想不出来实现方法/报错的有四五道 还可以接受。

今天没做出来的题目：反转链表，买卖股票的时机，移动零，删除链表倒数第N个节点 具体的实现代码我放在GitHub上面了，hot100 简单题回顾

2025.10.28

昨天公司派活了 在公司摸索一天 所以昨天就写了两道算法题 今天在公司依然在摸索 今天也写了两道题 不知道这种刷题策略有没有效果哦？ [hot100双指针](1parado_repo.github.io/leetcode1028.java at main · 1parado/1parado_repo.github.io) 今天写了移动零和盛水最多的边界 也就是快慢指针和首尾指针 三数之和那道题 大致意思看懂了 但是让我自己实现有一点麻烦 之后再复习。