数组
2025年6月3日大约 25 分钟
数组
二分查找
- 明确区间，左闭右闭（包含left和right）还是左闭右开（不包含right）
- 左闭右闭：
- 循环条件：left <= right
- 更新条件：left = mid + 1, right = mid - 1
- 左闭右开：
- 循环条件：left < right
- 更新条件：left = mid + 1, right = mid
移除元素
- 快慢指针
- 快指针遍历数组，慢指针记录不重复的元素
- 快指针遍历完，慢指针就是不重复元素的个数
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
- 返回慢指针
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) { // 如果是val，则只移动快指针
if (nums[fast] != val) { // 不等于val，说明不是要移除的元素，同时移动快慢指针
nums[slow] = nums[fast]; // 将不等于val的元素赋值给慢指针位置
slow++;
}
}
return slow; // 返回新数组的长度
}有序数组的平方
- 双指针
- 从两端开始遍历，比较两端的平方大小，大的放在新数组末尾
- 最后返回新数组
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) { // 从后往前遍历，因为平方最大的数在两端
if (nums[left] * nums[left] > nums[right] * nums[right]) { // 如果左边的平方大于右边的平方
result[i] = nums[left] * nums[left]; // 将平方最大的数赋值给新数组
left++; // 左指针右移
} else {
result[i] = nums[right] * nums[right]; // 将平方最大的数赋值给新数组
right--; // 右指针左移
}
}
return result;
}字母异位词分组
- 排序完后的异位词都会相等
- 使用map，key为排序后的字符串，value为异位词列表
- 遍历strs，将排序后的字符串作为key，将原字符串作为value，加入map
- 最后返回map的value列表
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>(); // key 是排序后的字符串，value 是这些字母组成的所有原始字符串组成的列表。
for (String str : strs) {
char[] array = str.toCharArray(); // 将字符串转换为字符数组
Arrays.sort(array); // 对字符数组进行排序
String key = new String(array); // 将字符数组转换为字符串
List<String> list = map.getOrDefault(key, new ArrayList<String>()); // 获取key对应的value，如果key不存在，则返回new ArrayList<String>()
list.add(str); // 将字符串加入value列表
map.put(key, list); // 将key和value列表加入map
}
return new ArrayList<>(map.values()); // 返回map的value列表
}最长连续子序列
- 使用set因为set的查找时间复杂度为O(1)，将nums中的元素加入set
- 如果set中存在nums[i] - 1，则跳过，否则从nums[i]开始，使用while循环，判断set中是否存在nums[i] + 1，如果存在，则继续循环，否则结束循环
- 记录最长连续子序列的长度
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>(); // 使用set因为set的查找时间复杂度为O(1)，将nums中的元素加入set
for (int num : nums) {
num_set.add(num);
} // 将nums中的元素加入set 去重
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) { // 如果set中不存在nums[i] - 1，则从nums[i]开始
int currentNum = num; // 当前数字
int currentStreak = 1; // 当前连续子序列长度
while (num_set.contains(currentNum + 1)) { // 如果set中存在nums[i] + 1，则继续循环
currentNum += 1; // 当前数字加1
currentStreak += 1; // 当前连续子序列长度加1
}
longestStreak = Math.max(longestStreak, currentStreak); // 更新最长连续子序列长度
}
}
return longestStreak;
}移动零
- 快慢指针
- 快指针遍历数组，慢指针在元素不为0时，将快指针指向的元素赋值给慢指针
- 快指针遍历完，slowIndex之后都是移除元素0的冗余元素，把这些元素都赋值为0就可以了。
public void moveZeroes(int[] nums) {
int slow = 0; // 慢指针
for (int fast = 0; fast < nums.length; fast++) { // 快指针遍历数组
if (nums[fast] != 0) { // 如果快指针指向的元素不为0
nums[slow] = nums[fast]; // 将快指针指向的元素赋值给慢指针
slow++; // 慢指针右移
}
}
// 后面的元素全变成 0
for (int j = slow; j < nums.length; j++) { // 将慢指针之后的元素都赋值为0
nums[j] = 0; // 将慢指针之后的元素都赋值为0
}
}
}滑动窗口模版
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
//当前考虑的元素
while (l <= r && check()) {//区间[left,right]不符合题意
//扩展左边界
}
//区间[left,right]符合题意，统计相关信息
}长度最小的子数组
- 滑动窗口
public int minSubArrayLen(int s, int[] nums) {
int left = 0; // 滑动窗口左边界
int sum = 0; // 当前窗口的和
int result = Integer.MAX_VALUE; // 最小子数组长度，初始设为无限大
for (int right = 0; right < nums.length; right++) { // 右指针代表的是终止位置
sum += nums[right]; // 滑动窗口里元素的和 扩展右边界
// 只要窗口内的和 ≥ s，符合要求了，就收缩左边界以尝试得到更短的长度
while (sum >= s) {
result = Math.min(result, right - left + 1); // 更新最小长度 right - left + 1是当前窗口[left, right]的长度
sum -= nums[left]; // 收缩窗口
left++; // 移动左指针
}
}
// 如果 result 没被更新过，说明不存在满足条件的子数组
return result == Integer.MAX_VALUE ? 0 : result;
}无重复字符的最长子串
- 滑动窗口
- set负责快速判断和维护“当前窗口中字符的唯一性”
- 如果窗口内的字符重复，则移动左指针
- 如果窗口内的字符不重复，则移动右指针
- 返回最大长度
public int lengthOfLongestSubstring(String s) {
char[] ss = s.toCharArray(); // 将字符串转换为字符数组
Set<Character> set = new HashSet<>(); // 使用set记录窗口内的字符
int res = 0; //结果
for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个
char ch = ss[right];//right指向的元素，也是当前要考虑的元素
while(set.contains(ch)) {//set中有ch，则缩短左边界，同时从set集合出元素
set.remove(ss[left]); // 从set集合出元素
left++; // 移动左指针
}
set.add(ss[right]);//将当前元素加入
res = Math.max(res, right - left + 1);//计算当前不重复子串的长度
}
return res;
}最小覆盖子串
- 滑动窗口
- 在字符串 s 中找出最短的子串，它包含字符串 t 的所有字符（包括出现次数）。
public String minWindow(String s, String t) { // s是母串，t是子串
if (s.length() < t.length()) return ""; // 如果s的长度小于t的长度，则返回空字符串
Map<Character, Integer> need = new HashMap<>(); // 记录t中每个字符及其出现次数
Map<Character, Integer> window = new HashMap<>(); // 记录窗口中每个字符及其出现次数
for (char c : t.toCharArray()) { // 记录t中每个字符及其出现次数
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0; // 滑动窗口的左右指针
int valid = 0; // 满足 need 的字符数
int start = 0, len = Integer.MAX_VALUE; // 记录最小子串的起始位置和长度，最终的返回就是s.substring(start, start + len)
while (right < s.length()) {
char c = s.charAt(right); // 当前字符
right++; // 右指针右移
if (need.containsKey(c)) { // 如果t中包含当前字符
window.put(c, window.getOrDefault(c, 0) + 1); // 记录窗口中每个字符及其出现次数
if (window.get(c).equals(need.get(c))) { // 如果窗口中每个字符的出现次数等于t中每个字符的出现次数
valid++; // 满足 need 的字符数+1
}
}
while (valid == need.size()) { // 当窗口内已经包含了 t 中所有的字符，且每个字符出现次数都满足要求，就可以尝试收缩窗口了（即把左边界向右移，看看还能不能缩短窗口）
if (right - left < len) { // 如果当前窗口的长度小于最小子串的长度
start = left; // 更新最小子串的起始位置
len = right - left; // 更新最小子串的长度
}
char d = s.charAt(left); // 当前字符
left++; // 左指针右移
if (need.containsKey(d)) { // 如果t中包含当前字符
if (window.get(d).equals(need.get(d))) { // 如果窗口中每个字符的出现次数等于t中每个字符的出现次数
valid--; // 满足 need 的字符数-1
}
window.put(d, window.get(d) - 1); // 记录窗口中每个字符及其出现次数
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); // 如果最小子串的长度仍为无穷大，则返回空字符串，否则返回最小子串
}找到字符串中所有字母异位词
- 在s中找到所有p的异位词
- 因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量
- 如果两个字符串中每种字母的数量相同，则称这两个字符串互为字母异位词
- ascii
- 统计字符 'b' 的出现次数
char c = 'b';count[c - 'a']++; // 等价于 count[1]++
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] pCount = new int[26]; // 记录字符串 p 中每种字母的数量
int[] sCount = new int[26]; // 记录字符串 s 中每种字母的数量
for (char c : p.toCharArray()) { // 遍历字符串 p
pCount[c - 'a']++; // 记录字符串 p 中每种字母的数量
}
for (int i = 0; i < s.length(); i++) { // 遍历字符串 s
sCount[s.charAt(i) - 'a']++; // 记录字符串 s 中每种字母的数量
if (i >= p.length()) { // 如果窗口大小大于字符串 p 的长度
sCount[s.charAt(i - p.length()) - 'a']--; // 移除字符串 s 中第一个字母
}
if (Arrays.equals(pCount, sCount)) { // 如果两个字符串中每种字母的数量相同
res.add(i - p.length() + 1); // 记录字符串 s 中第一个字母异位词的起始位置
}
}
return res;
}合并两个有序数组
- 双指针
- 从后往前遍历
- 比较两个数组末尾元素，大的放在新数组末尾
- 最后返回新数组
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) { // 如果p1已经遍历完了，则直接将p2的元素赋值给新数组
cur = nums2[p2];
p2--;
} else if (p2 == -1) { // 如果p2已经遍历完了，则直接将p1的元素赋值给新数组
cur = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) { // 如果p1的元素大于p2的元素，则将p1的元素赋值给新数组
cur = nums1[p1];
p1--;
} else { // 如果p1的元素小于p2的元素，则将p2的元素赋值给新数组
cur = nums2[p2];
p2--;
}
nums1[tail] = cur; // 将cur赋值给新数组
tail--; // 新数组下标左移
}
}
}删除排序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int slow = 0; // 慢指针用于记录不重复元素的最后位置合法值的索引
for(int fast = 1; fast < nums.length; fast++){ // 快指针用于遍历数组
if(nums[fast] != nums[fast-1]){ // 如果当前元素与前一个元素不同
slow++; // 慢指针移动到下一个位置
nums[slow] = nums[fast]; // 将当前元素放到慢指针的位置
}
}
return slow + 1; // +1是因为slow是从0开始的 返回的是数组长度
}
}删除排序数组中的重复项II
- 快慢指针
- 慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度
- 如果当前数 != slow-2 位置的数，就可以保留
- 返回慢指针
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int slow = 2;
for (int fast = 2; fast < nums.length; fast++) {
// 如果当前数 != slow-2 位置的数，就可以保留
if (nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}多数元素
- 摩尔投票法
- 初始化一个候选元素candidate，初始化一个计数器count
- 遍历数组，如果当前元素等于candidate，则count加1，否则count减1
- 如果count为0，则将当前元素赋值给candidate
- 最后返回candidate
public int majorityElement(int[] nums) {
int count = 0; // 候选元素的计数
Integer candidate = null; // 当前候选多数元素 不能初始化为0 因为0也有可能成为多数元素
for (int num : nums) {
if (count == 0) { // 如果count为0，则将当前元素赋值给candidate
candidate = num;
}
count += (num == candidate) ? 1 : -1; // 如果当前元素等于candidate，则count加1，否则count减1
}
return candidate;
}旋转数组
- 创建一个新数组，将原数组中的元素按照旋转后的位置赋值给新数组
- 将新数组赋值给原数组
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i]; // %n是为了防止k大于n的情况
}
System.arraycopy(newArr, 0, nums, 0, n); // 参数1：源数组，参数2：源数组起始位置，参数3：目标数组，参数4：目标数组起始位置，参数5：复制长度
}
}O(1) 时间插入、删除和获取随机元素
class RandomizedSet {
List<Integer> nums;
Map<Integer, Integer> indices; // key: 元素值，value: 元素索引
Random random;
public RandomizedSet() {
nums = new ArrayList<Integer>();
indices = new HashMap<Integer, Integer>();
random = new Random();
}
public boolean insert(int val) {
if (indices.containsKey(val)) { // 如果val已经存在，则返回false
return false;
}
int index = nums.size(); // 获取当前数组长度
nums.add(val); // 将val添加到数组末尾
indices.put(val, index); // 将val和index添加到map中
return true;
}
// 正常地从 ArrayList 中间删除元素，时间复杂度是 O(n)，因为它需要移动所有后面的元素。
// 但我们想要 O(1) 删除，于是就用这个技巧：
// 把要删除的元素用最后一个元素覆盖，再把最后一个删掉（反正顺序不重要）
public boolean remove(int val) {
if (!indices.containsKey(val)) { // 如果val不存在，则返回false
return false;
}
int index = indices.get(val); // 获取val的索引
int last = nums.get(nums.size() - 1); // 获取数组最后一个元素
nums.set(index, last); // 将数组最后一个元素赋值给val的索引
indices.put(last, index); // 将数组最后一个元素和val的索引添加到map中
nums.remove(nums.size() - 1); // 删除数组最后一个元素
indices.remove(val); // 删除val的索引
return true;
}
public int getRandom() {
int randomIndex = random.nextInt(nums.size()); // 获取随机索引
return nums.get(randomIndex); // 返回随机索引的元素
}
}除自身以外数组的乘积
- 左边要记每个格子的乘积，要存进数组返回，所以你得一步步存（用 res[]）
- 右边只要实时算乘积，用一个变量乘上去就够了，不需要记历史（用 int right）
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
// 第一次遍历：从左往右，构建前缀积
res[0] = 1; // 初始化前缀乘积的第一步，表示第一个位置左边没有任何数，乘积为 1
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1]; // res[i-1]是i-1位置的前缀积 nums[i-1]是i-1位置的元素
}
// 第二次遍历：从右往左，乘上后缀积
int right = 1; // 初始化后缀乘积的第一步，表示最后一个位置右边没有任何数，乘积为 1
for (int i = n - 1; i >= 0; i--) {
res[i] = res[i] * right; // res[i]是i位置的元素 right是i位置的后缀积
right *= nums[i];
}
return res;
}
}接雨水
- 双指针
- 当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。
- 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。
- 当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
- 即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
- 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
- 按列计算 宽度是1
public int trap(int[] height) {
if (height.length <= 2) { // 如果数组长度小于等于2，则无法形成积水
return 0;
}
// 从两边向中间寻找最值
int maxLeft = height[0], maxRight = height[height.length - 1]; // 初始化左右两边的最高高度
int l = 1, r = height.length - 2; // 初始化左右两边的指针
int res = 0;
while (l <= r) {
// 不确定上一轮是左边移动还是右边移动，所以两边都需更新最值
maxLeft = Math.max(maxLeft, height[l]); // 更新左边的最高高度，maxLeft是左边的最高高度和当前高度（height[l]）的最大值
maxRight = Math.max(maxRight, height[r]); // 更新右边的最高高度，maxRight是右边的最高高度和当前高度（height[r]）的最大值
// 最值较小的一边所能装的水量已定，所以移动较小的一边。
if (maxLeft < maxRight) {
res += maxLeft - height[l]; // 计算当前列的雨水面积 maxLeft - height[l]是当前列的雨水高度 宽度是1 所以是maxLeft - height[l]
l++; // 左指针右移
} else {
res += maxRight - height[r]; // 计算当前列的雨水面积 maxRight - height[r]是当前列的雨水高度 宽度是1 所以是maxRight - height[r]
r--; // 右指针左移
}
}
return res;
}罗马数字转整数
- 当前位置的元素比下个位置的元素小，就减去当前值（比如IV，I小于V，所以减去I），否则加上当前值（比如VI，I小于V，所以加上I）
public int romanToInt(String s) {
Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};
int ans = 0;
int n = s.length();
for(int i = 0; i<n; i++){
int cur = symbolValues.get(s.charAt(i));
if(i<n-1 && cur<symbolValues.get(s.charAt(i+1))){ //i<n-1 是因为n-1是最后一个元素 所以i+1不会越界
ans -=cur; // 当前值比下个值小，减去当前值
} else{
ans +=cur; // 当前值比下个值大，加上当前值
}
}
return ans;
}整数转罗马数字
- 如果当前数字够大，可以减去 value（如 1000），就减掉，并追加 symbol（如 "M"）。
- 这样能优先使用较大的符号，符合罗马数字书写规则。
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public String intToRoman(int num) {
StringBuffer roman = new StringBuffer();
for (int i = 0; i < values.length; ++i) {
int value = values[i]; // 当前数字
String symbol = symbols[i]; // 当前符号
while (num >= value) { // 如果当前数字够大，可以减去 value（如 1000），就减掉，并追加 symbol（如 "M"）。
num -= value; // 减去 value（如 1000）
roman.append(symbol); // 追加 symbol（如 "M"）。
}
if (num == 0) { // 如果当前数字为0，则退出循环
break;
}
}
return roman.toString();
}最后一个单词的长度
- 从后往前遍历，找到第一个非空字符，然后从该字符开始，找到第一个空格，计算空格和该字符之间的长度
public int lengthOfLastWord(String s) {
int index = s.length() - 1;
while (s.charAt(index) == ' ') { // 从后往前遍历，找到第一个非空字符
index--;
}
int length = 0;
while (index >= 0 && s.charAt(index) != ' ') { // 从该字符开始，找到第一个空格，计算空格和该字符之间的长度
length++; // 最后一个单词的长度+1
index--; // 指针左移
}
return length;
}最长公共前缀
- 横向扫描
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
String prefix = strs[0]; // 初始化公共前缀为第一个字符串
int count = strs.length;
for (int i = 1; i < count; i++) {
prefix = longestCommonPrefix(prefix, strs[i]);
if (prefix.length() == 0) break; // 如果公共前缀为空，则返回空字符串
}
return prefix;
}
public String longestCommonPrefix(String str1, String str2) {
int length = Math.min(str1.length(), str2.length()); // 公共前缀肯定不会超过两个字符串中较短的那个
int index = 0; // 公共前缀的索引
while (index < length && str1.charAt(index) == str2.charAt(index)) { // 如果两个字符串的当前字符相同，则公共前缀长度+1
index++;
}
return str1.substring(0, index); // 返回公共前缀
}翻转字符串里的单词
- api战士
public String reverseWords(String s) {
// 除去开头和末尾的空白字符
s = s.trim();
// 正则匹配连续的空白字符作为分隔符分割
List<String> wordList = Arrays.asList(s.split("\\s+"));
// 翻转列表
Collections.reverse(wordList);
// 拼接为字符串并返回
return String.join(" ", wordList);
}
public String reverseWords(String s) {
//源字符数组
char[] initialArr = s.toCharArray();
//新字符数组
char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格最后会被处理掉
int newArrPos = 0;
//i来进行整体对源字符数组从后往前遍历
int i = initialArr.length-1;
while(i>=0){
while(i>=0 && initialArr[i] == ' ') i--; //跳过空格
//此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
int right = i;
while(i>=0 && initialArr[i] != ' ') i--;
//指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
for (int j = i+1; j <= right; j++) {
newArr[newArrPos++] = initialArr[j];
if(j == right){
newArr[newArrPos++] = ' ';//空格
}
}
}
//若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
if(newArrPos == 0){
return "";
}else{
return new String(newArr,0,newArrPos-1);
}
}Z字形变换
public String convert(String s, int numRows) {
if (numRows < 2) return s; // 如果行数小于2，则直接返回原字符串
StringBuilder[] rows = new StringBuilder[numRows]; // 创建一个StringBuilder数组，用于存储每一行的字符串
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder(); // 初始化每一行的StringBuilder
int i = 0, flag = -1; // i表示当前行，flag表示方向（向上还是向下，-1向上，1向下）
for (char c : s.toCharArray()) {
rows[i].append(c); // 将字符添加到当前行的StringBuilder中
if (i == 0 || i == numRows - 1) flag = -flag; // 如果当前行是第一行或最后一行，则改变方向
i += flag; // 更新当前行
}
StringBuilder res = new StringBuilder(); // 创建一个StringBuilder，用于存储最终结果
for (StringBuilder row : rows) res.append(row); // 将每一行的StringBuilder拼接起来
return res.toString();
}找出字符串中第一个匹配项的下标
- 暴力匹配
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) { // i 最多只能到 n - m，否则 i + j 会访问越界字符！
boolean flag = true;
for (int j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) { // 比较从主串 i 开始的第 j 个字符，是否和子串的第 j 个字符相等。不想等跳出循环
flag = false;
break;
}
}
if (flag) return i; // 相等，从 i 开始正好匹配了子串 → return i
}
return -1;
}有效的数独
- 使用三个数组来记录行、列和3x3小方块中每个数字的出现情况
public boolean isValidSudoku(char[][] board) {
int[][] rows = new int[9][9]; // 记录行中每个数字的出现次数
int[][] columns = new int[9][9]; // 记录列中每个数字的出现次数
int[][][] subboxes = new int[3][3][9]; // 记录3x3小方块中每个数字的出现次数
for (int i = 0; i < 9; i++) { // 遍历行
for (int j = 0; j < 9; j++) { // 遍历列
char c = board[i][j]; // 当前字符
if (c != '.') { // 如果当前字符有值
int index = c - '0' - 1; // 当前字符的索引 比如c是'5'，'5'-'0' = 5 (因为ASCII码，'0'的ASCII码是48，'5'的ASCII码是53)，5-1 = 4(再减一是因为索引从零开始），所以index = 4
rows[i][index]++; // 行中每个数字的出现次数 +1
columns[j][index]++; // 列中每个数字的出现次数 +1
subboxes[i / 3][j / 3][index]++; // 3x3小方块中每个数字的出现次数 +1
if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) { // 如果当前字符在行、列或3x3小方块中出现次数大于1，则返回false
return false;
}
}
}
}
return true;
}螺旋矩阵II
- 循环不变量：坚持左闭右开原则
- 循环圈数是n/2，n是矩阵的边长
- 如何n是奇数，则需要单独处理中心元素
public int[][] generateMatrix(int n) {
int[][] nums = new int[n][n];
int startX = 0, startY = 0; // 每一圈的起始点
int offset = 1; // 每一圈的偏移量
int count = 1; // 矩阵中需要填写的数字
int loop = 1; // 记录当前的圈数
int i, j; // j 代表列, i 代表行;
while (loop <= n / 2) { // 循环圈数是n/2，n是矩阵的边长
// 顶部
// 左闭右开，所以判断循环结束时， j 不能等于 n - offset
for (j = startY; j < n - offset; j++) {
nums[startX][j] = count++;
}
// 右列
// 左闭右开，所以判断循环结束时， i 不能等于 n - offset
for (i = startX; i < n - offset; i++) {
nums[i][j] = count++;
}
// 底部
// 左闭右开，所以判断循环结束时， j != startY
for (; j > startY; j--) {
nums[i][j] = count++;
}
// 左列
// 左闭右开，所以判断循环结束时， i != startX
for (; i > startX; i--) {
nums[i][j] = count++;
}
// 更新起始点 开始下一圈
startX++;
startY++;
offset++;
loop++;
}
if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
nums[startX][startY] = count;
}
return nums;
}螺旋矩阵
- 和上一题类似, 只是变成了读取矩阵的值
- 这里用的左闭右开原则（不包含右边最后一个元素）
- 不用处理中心元素，因为边界在遍历完一圈后会收缩
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0) return res;
int startRow = 0, endRow = matrix.length; // 左闭右开区间 [startRow, endRow)
int startCol = 0, endCol = matrix[0].length; // 左闭右开区间 [startCol, endCol)
while (startRow < endRow && startCol < endCol) {
// → 向右遍历，遍历[startCol, endCol)
for (int col = startCol; col < endCol; col++) {
res.add(matrix[startRow][col]);
}
startRow++; // 第一行遍历完，收缩上边界
// ↓ 向下遍历，遍历[startRow, endRow)
for (int row = startRow; row < endRow; row++) {
res.add(matrix[row][endCol - 1]);
}
endCol--; // 最右列遍历完，收缩右边界
// ← 向左遍历，遍历[startCol, endCol)
if (startRow < endRow) { // 还有行才遍历
for (int col = endCol - 1; col >= startCol; col--) {
res.add(matrix[endRow - 1][col]);
}
endRow--; // 最底行遍历完，收缩下边界
}
// ↑ 向上遍历，遍历[startRow, endRow)
if (startCol < endCol) { // 还有列才遍历
for (int row = endRow - 1; row >= startRow; row--) {
res.add(matrix[row][startCol]);
}
startCol++; // 最左列遍历完，收缩左边界
}
}
return res;
}旋转图像
- 原地旋转
public void rotate(int[][] matrix) {
int n = matrix.length; // 矩阵的边长（n×n）
// 外层循环控制旋转的“层数”，一共旋转 n/2 层
for (int i = 0; i < n / 2; i++) {
// 内层循环控制当前层每一组需要旋转的元素，列范围是 (n+1)/2
// (n+1)/2 保证奇数边长时，中心列被覆盖
for (int j = 0; j < (n + 1) / 2; j++) {
// 保存当前位置元素，准备交换
int temp = matrix[i][j];
// ① 左下 -> 左上
// 把左下角的元素赋值给当前元素位置
matrix[i][j] = matrix[n - j - 1][i];
// ② 左下角元素被替换，赋值为右下角元素
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
// ③ 右下角元素赋值为右上角元素
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
// ④ 右上角元素赋值为之前保存的当前元素（temp）
matrix[j][n - i - 1] = temp;
}
}
}矩阵置零
- 用两个标记数组分别记录每一行和每一列是否有零出现
public void setZeroes(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
boolean[] row = new boolean[n];
boolean[] col = new boolean[m];
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(matrix[i][j] == 0){
row[i] = col[j] = true; // 记录该行和该列有零出现
}
}
}
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(row[i] || col[j]){ // 如果该行或该列有零出现，则将该行或该列的所有元素置零
matrix[i][j] = 0;
}
}
}
}生命游戏
题目里 0 表示死细胞，1 表示活细胞
题目规则：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡
- 如果死细胞周围八个位置有三个活细胞，则该位置死细胞复活
原地修改的问题用状态编码解决，这里我们自定义了两个状态 | 当前编码值 | 原状态（上一代） | 新状态（下一代） | 含义 | | ----- | -------- | -------- | ----------- | |
0| 死（0） | 死（0） | 不变：死 → 死 | |1| 活（1） | 活（1） | 不变：活 → 活 | |2| 活（1） | 死（0） | 已死亡：活 → 死 ✅ | |3| 死（0） | 活（1） | 已复活：死 → 活 ✅ |最后再根据状态编码恢复原始状态
public void gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
// 方向数组，表示周围8个方向
int[][] directions = {
{-1, -1}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1}
};
// 第一步：根据旧状态判断，更新为编码状态
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int liveNeighbors = 0;
// 统计活邻居个数（看原始状态）
for (int[] dir : directions) {
int x = i + dir[0], y = j + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n) {
// 1和2的原始状态是1
if (board[x][y] == 1 || board[x][y] == 2) { // 如果当前1:细胞是活细胞 或者 2:活细胞变成死细胞
liveNeighbors++; // 活邻居个数+1
}
}
}
// 根据规则修改
if (board[i][j] == 1) {
// 活细胞死亡
if (liveNeighbors < 2 || liveNeighbors > 3) { // 活细胞周围八个位置的活细胞数少于两个 或者 活细胞周围八个位置有超过三个活细胞
board[i][j] = 2; // 1 -> 0
}
// 活细胞仍然存活(可以省略 因为实际上1还是1，没变)
if (liveNeighbors == 2 || liveNeighbors == 3) { // 活细胞周围八个位置有两个或三个活细胞
board[i][j] = 1; // 1 -> 1
}
} else {
// 死细胞变成活
if (liveNeighbors == 3) { // 死细胞周围八个位置有三个活细胞
board[i][j] = 3; // 0 -> 1
}
}
}
}
// 第二步：恢复编码状态为最终状态
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
board[i][j] %= 2; // 恢复编码状态为最终状态
}
}
}