首页 > 编程札记 > 编程

代码随想录——Java刷题记录

阅读：评论：0

代码随想录——Java刷题记录

数组（11.2-11.5）

定义：数组是存放在连续内存空间上的相同类型数据的集合，下标都是从0开始。

特点：连续 ==> 查找方便，新增/删除不方便【数组的元素是不能删的，只能覆盖】

1、二分查找

题目：704. 二分查找 - 力扣（LeetCode）

前提：数组为有序数组 + 数组中无重复元素

难点：对区间的定义想清楚 ==》保持不变量（在while寻找中每一次边界的处理都要坚持根据区间的定义来操作） ==》循环不变量规则

左闭右闭 [left, right]
- 范围包含right
- left = right 时是有意义的，也就是在中间只有一个数的时候 ==》 while (left <= right)
- 左右边界变的时候要多移一位
左开右闭 [left, right) ==> while (left < right)
- 范围不包含right
- left = right 时是没有意义的 ==》 while (left < right)
- left需要多移动一位，right不需要，因为反正也不包含
相当于[1，2，3]和[1，2，3）的区别

示例：Java左闭右闭区间

class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1])      return -1;int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid - 1;}return -1;}
}

时间复杂度：O(log n)
空间复杂度：O(1)

2、移除元素【快慢指针】

题目：27. 移除元素 - 力扣（LeetCode）

前提：数组中在保持基本顺序不变的前提下，删除指定元素（主要是减少空间复杂度）

难点：理解快慢指针的具体含义

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

示例：

class Solution {public int removeElement(int[] nums, int val) {// 快慢指针int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}

时间复杂度：O(n)
空间复杂度：O(1)

3、有序数组的平方【快慢指针】

题目： 977. 有序数组的平方 - 力扣（LeetCode）

前提： 非递减顺序 排序

难点：非递减 ==》平方大小两边向中间递减 ==》对向双指针移动的逻辑

实现：

class Solution {public int[] sortedSquares(int[] nums) {int p=nums.length-1;int[] arr=new int[nums.length];int left=0;int right=nums.length-1;while(left <= right){// 对向移动if(Math.abs(nums[left]) > Math.abs(nums[right])){arr[p]=nums[left] * nums[left];left++;}else{arr[p]=nums[right] * nums[right];right--;}p--;}return arr;}
}

时间复杂度：O(n)
空间复杂度：O(1)

4、长度最小的子数组【滑动窗口】

题目：209. 长度最小的子数组 - 力扣（LeetCode）

前提：问题涉及连续子数组或子字符串

难点：不断的调节子序列的起始位置和终止位置，注意for表示的是窗口的终止位置，每次for先确定终止位置再不断向前调整起始位置

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

示例：

class Solution {public int minSubArrayLen(int target, int[] nums) {int result = nums.length + 1;int sum = 0;int left = 0;
// 滑动窗口，移动的是终止位置for (int i = 0; i < nums.length; i++) {sum += nums[i];
while (sum >= target) {result = Math.min(result, i - left + 1);// 每次直接从确定的初始位置开始移动，因为是已经计算过的长度最短sum -= nums[left];left++;}}return result == nums.length + 1 ? 0 : result;}
}

5、螺旋矩阵Ⅱ【模拟】

题目：59. 螺旋矩阵 II - 力扣（LeetCode）

前提：好像没什么前提🤔

难点：模拟过程，边界处理，坚持循环不变量原则

示例：

class Solution {public int[][] generateMatrix(int n) {int[][] arr = new int[n][n];// 主要是定义的这四个变量对边界的处理int startx=0,starty=0;int endx=n-1,endy=n-1;int cnt=1;
while(cnt<=n*n){// 从左到右for(int i=startx;i<=endx;i++){arr[starty][i]=cnt++;}starty++;
// 从上到下for(int i = starty;i<=endy;i++)arr[i][endx]=cnt++;endx--;
// 从右到左for(int i = endx;i>=startx;i--)arr[endy][i]=cnt++;endy--;
// 从下到上for(int i =endy;i>=starty;i--)arr[i][startx]=cnt++;startx++;}return arr;}
}

相关题目推荐：【还没做完捏】

54. 螺旋矩阵 - 力扣（LeetCode）

LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）：思路很像，但注意跳出的时机，这里就不一定循环一整轮才跳出，必须每次遍历完就判断是否需要跳出，而且注意区别++i和i++的区别

class Solution {public int[] spiralArray(int[][] array) {// 添加特殊情况判断if (array == null || array.length == 0 || array[0].length == 0)return new int[0];int endy = array.length - 1, endx = array[0].length - 1;int startx = 0, starty = 0;int cnt = 0;int size = (endx + 1) * (endy + 1);int[] num = new int[size];// 首先注意跳出的时机，这里就不一定循环一整轮才跳出，必须每次遍历完就判断是否需要跳出while (true) {// 从左到右for (int i = startx; i <= endx; i++) num[cnt++] = array[starty][i];// 注意++starty和starty++的区别if(++starty > endy) break;// 从上到下for (int i = starty; i <= endy; i++) num[cnt++] = array[i][endx];if(--endx<startx)break;// 从右到左for (int i = endx; i >= startx; i--) num[cnt++] = array[endy][i];if(--endy<starty)break;// 从下到上for (int i = endy; i >= starty; i--) num[cnt++] = array[i][startx];if(++startx>endx)break;}return num;}
}

总结

链表

总结

1. 理解链表的结构

链表是由节点组成的，每个节点包含数据和指向下一个节点的指针。
理解头节点（head）和尾节点（tail）的概念，以及它们在链表中的角色。

2. 使用双指针

快慢指针：用于找到链表的中点、检测循环等。快指针每次移动两步，慢指针每次移动一步。
左右指针：用于反转链表、找到特定位置的节点等。左右指针一起向前移动。

3. 边界条件处理

检查链表是否为空。
注意处理链表的头部和尾部，特别是在添加或删除节点时。

4. 创建哑节点（Dummy Node）

在链表的头部创建一个哑节点可以简化一些操作，特别是在头节点可能改变的情况下。

5. 递归方法

递归特别适用于链表的一些问题，如反转链表的一部分、合并两个链表等。

6. 链表的合并与分割

学习如何合并两个链表，特别是在归并排序中。
了解如何分割链表，这在快速排序和一些其他问题中非常有用。

7. 修改时的注意事项

当修改链表时，特别注意不要丢失对节点的引用。
在删除或添加节点时，确保更新前后节点的指针。

8. 多重循环

在一些问题中，可能需要使用多重循环来遍历链表，如检查两个链表是否相交。

Hash

哈希表是根据关键码的值而直接进行访问的数据结构。

一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数：一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把数据映射为哈希表上的索引数字了。大于的话再进行取模

还极端的话就会出现哈希碰撞，解决办法：拉链法和线性探测法

拉链法：存在链表里面，注意要即不会因为数组空值而浪费内存，也不会因为链表过长再查找上浪费太多时间

线性探测法：往后再找空闲位置

常见的哈希结构：数组、set、map

map又分为HashMap、HashSet等

总结

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

array适用于限制了数值大小的（而且不要太大，像26个字母【两个part为序号+值】

HashSet：如果哈希值比较少、特别分散、跨度非常大，不考虑出现顺序，使用数组就造成空间的极大浪费，这个时候就用HashSet，有了值再放进去【只有一个part是值】【但是set又要比数组空间和时间复杂度要高一点】

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

1. 快速查找

用途：当你需要频繁检索特定元素是否存在于集合中时，哈希表是理想的数据结构。例如，在求解两个数组的交集或判断元素是否重复出现时。
实现：使用 HashSet 存储元素，实现常数时间复杂度的查找操作。

2. 计数和映射

用途：当你需要对元素进行计数或建立元素与其相关数据的映射时。例如，在计算元素频率或分组数据时。
实现：使用 HashMap 来映射元素到它们的计数或相关数据。

3. 去重

用途：在需要从数据中移除重复元素时。例如，在返回唯一元素集合的问题中。
实现：使用 HashSet 存储已经遇到的元素，自动处理重复项。

4. 子数组/子串问题

用途：在处理子数组或子串的问题，如找出具有特定特性的最长子串。
实现：使用 HashMap 记录字符及其在子串中的位置，帮助快速计算子串长度或验证其特性。

5. 避免双重循环

用途：在需要检查两个元素的组合是否满足特定条件时，如在数组中寻找和为特定值的一对数字。
实现：使用 HashMap 或 HashSet 存储已经遍历过的元素，避免使用嵌套循环。

6. 设计缓存机制

用途：在需要设计缓存机制，如 LRU (Least Recently Used) 缓存时。
实现：结合 HashMap 和双向链表实现高效的缓存机制。

注意事项

哈希冲突：了解哈希冲突及其解决方法（例如开放寻址法或链地址法）。
哈希函数的选择：哈希函数应当能够均匀分布键以减少冲突。
空间复杂度：虽然哈希表提供了优秀的时间性能，但可能会占用更多空间。

DIGITS	LARGEST	NEXT
1	9	81
2	99	162
3	999	243
4	9999	324
13	9999999999999	1053

字符串

总结

1. 双指针技巧

用途：解决如反转字符串、找到最长的不含重复字符的子串等问题。
技巧：使用两个指针（如左右指针）遍历字符串，根据条件移动这些指针。

2. 字符串匹配算法

用途：在一个文本中查找一个子串的出现位置。
技巧：使用高效的字符串匹配算法，如 KMP 算法、Rabin-Karp 算法。

3. 字符串分割与合并

用途：处理格式化数据，如日志文件或 CSV 文件。
技巧：使用字符串分割方法（如 split）来分解字符串，使用 join 或 StringBuilder 进行字符串合并。

双指针

其他

438.找到字符串中所有字母...

滑动窗口方法：

先统计父字符串和目标的hash字母数组频率

然后对这个父字符串数组进行滑动窗口，和目标数组比较

记得用arrays的equals比较方便

本文发布于:2024-01-28 00:02:18，感谢您对本站的认可！

本文链接：https://www.4u4v.net/it/17063713363436.html

上一篇：pt09文件处理

下一篇：java篇类的进阶0x0B：Class 类与反射

标签：题记代码随想录 Java

留言与评论（共有 0 条评论）

代码随想录——Java刷题记录