文章目录
矩阵
1.有效的数独
1.答案
package com.sunxiansheng.classic150.g1;
/**
* Description: 36. 有效的数独
*
* @Author sun
* @Create 2024/12/22 10:02
* @Version 1.0
*/
public class t36 {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9];
boolean[][] cols = new boolean[9][9];
boolean[][] boxes = new boolean[9][9];
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 获取元素
char c = board[i][j];
// 跳过空格
if (c == '.') {
continue;
}
// 转换为索引，方便存入数组
int index = c - '1';
// 放入当前行
if (rows[i][index]) {
return false;
} else {
rows[i][index] = true;
}
// 放入当前列
if (cols[index][j]) {
return false;
} else {
cols[index][j] = true;
}
// 计算3x3子宫格的索引
int boxIndex = (i / 3) * 3 + j / 3;
if (boxes[boxIndex][index]) {
return false;
} else {
boxes[boxIndex][index] = true;
}
}
}
return true;
}
}
2.思路
记住这个公式：int boxIndex = (i / 3) * 3 + j / 3;
2.螺旋矩阵
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.ArrayList;
import java.util.List;
/**
* Description: 54. 螺旋矩阵
*
* @Author sun
* @Create 2024/12/22 10:43
* @Version 1.0
*/
public class t54 {
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int m = matrix.length;
int n = matrix[0].length;
// 定义上下左右边界
int top = 0;
int bottom = m - 1;
int left = 0;
int right = n - 1;
// 计算一共需要遍历的次数
int total = m * n;
int count = 0;
// 按照右下左上的顺序遍历
while (true) {
// 右
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
if (++count == total) {
return res;
}
}
// 上边界下移
top++;
// 下
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][right]);
if (++count == total) {
return res;
}
}
// 右边界左移
right--;
// 左
for (int i = right; i >= left; i--){
res.add(matrix[bottom][i]);
if (++count == total) {
return res;
}
}
// 下边界上移
bottom--;
// 上
for (int i = bottom; i >= top; i--) {
res.add(matrix[i][left]);
if (++count == total) {
return res;
}
}
// 左边界右移
left++;
}
}
}
2.思路
先定义四个边界，然后记录一共需要遍历的次数，最后在循环内按照顺序遍历，每次遍历完成都要移动边界
3.旋转图像
1.答案
package com.sunxiansheng.classic150.g1;
/**
* Description: 48. 旋转图像
*
* @Author sun
* @Create 2024/12/22 11:11
* @Version 1.0
*/
public class t48 {
public static void rotate(int[][] matrix) {
// 矩阵转置
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 将每一行都逆序
for (int i = 0; i < matrix.length; i++) {
reverse(matrix[i]);
}
}
/**
* 逆序数组
*
* @param arr
*/
private static void reverse(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
2.思路
转置后逆序即可
4.矩阵置零
1.答案
package com.sunxiansheng.classic150.g1;
import javafx.util.Pair;
import java.util.ArrayList;
import java.util.List;
/**
* Description: 73. 矩阵置零
*
* @Author sun
* @Create 2024/12/22 11:20
* @Version 1.0
*/
public class t73 {
public static void setZeroes(int[][] matrix) {
// 记录一下需要置0的下标
List<Pair<Integer, Integer>> list = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
list.add(new Pair<>(i, j));
}
}
}
// 设置0
for (int i = 0; i < list.size(); i++) {
setZero(matrix, list.get(i).getKey(), list.get(i).getValue());
}
}
private static void setZero(int[][] matrix, int row, int col) {
int top = 0;
int bottom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
// 向上置0
for (int i = row; i >= top; i--) {
matrix[i][col] = 0;
}
// 向下
for (int i = row; i <= bottom; i++) {
matrix[i][col] = 0;
}
// 向左
for (int i = left; i <= col; i++) {
matrix[row][i] = 0;
}
// 向右
for (int i = right; i >= col; i--) {
matrix[row][i] = 0;
}
}
}
2.思路
先要记录一下要置0的下标，然后遍历去置0即可
哈希表
1.赎金信
1.答案
package com.sunxiansheng.classic150.g1;
/**
* Description: 383. 赎金信
*
* @Author sun
* @Create 2024/12/22 13:27
* @Version 1.0
*/
public class t383 {
public static boolean canConstruct(String ransomNote, String magazine) {
// 统计字符频率
int[] mFreq = new int[26];
for (int i = 0; i < magazine.length(); i++) {
mFreq[magazine.charAt(i) - 'a'] ++;
}
// 遍历ransomNote看看够不够减
for (int i = 0; i < ransomNote.length(); i++) {
// 计算下标
int index = ransomNote.charAt(i) - 'a';
if (--mFreq[index] < 0) {
return false;
}
}
return true;
}
}
2.思路
先统计一下字符的频率，然后看看够不够减就可以
2.同构字符串
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.HashMap;
import java.util.Map;
/**
* Description: 205. 同构字符串
*
* @Author sun
* @Create 2024/12/22 13:44
* @Version 1.0
*/
public class t205 {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) {
return false;
}
// 双向映射：s -> t 和 t -> s
Map<Character, Character> mapS2T = new HashMap<>();
Map<Character, Character> mapT2S = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
// 获取元素
char charS = s.charAt(i);
char charT = t.charAt(i);
// 检查s到t是否有映射
if (mapS2T.containsKey(charS)) {
// 有映射就检查当前映射
if (mapS2T.get(charS) != charT) {
return false;
}
} else {
// 没有映射就建立映射
mapS2T.put(charS, charT);
}
// 检查t到s是否有映射
if (mapT2S.containsKey(charT)) {
// 有映射就检查当前映射
if (mapT2S.get(charT) != charS) {
return false;
}
} else {
// 没有映射就建立映射
mapT2S.put(charT, charS);
}
}
return true;
}
}
2.思路
就是检查双向映射，具体检查的过程就是：先判断有没有映射，如果有则检查，没有就建立映射
3.单词规律
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* Description: 290. 单词规律
*
* @Author sun
* @Create 2024/12/22 14:06
* @Version 1.0
*/
public class t290 {
public static boolean wordPattern(String pattern, String s) {
// s以空格分割
String[] split = s.split(" ");
if (split.length != pattern.length()) {
return false;
}
// 双向映射
Map<Character, String> map = new HashMap<>();
Map<String, Character> map2 = new HashMap<>();
for (int i = 0; i < pattern.length(); i++) {
// 取数
char left = pattern.charAt(i);
String right = split[i];
// 检查是否有映射
if (map.containsKey(left)) {
// 如果有，则检查映射
if (!map.get(left).equals(right)) {
return false;
}
} else {
// 如果没有，就添加映射
map.put(left, right);
}
// 检查是否有映射
if (map2.containsKey(right)) {
// 如果有，则检查映射
if (!map2.get(right).equals(left)) {
return false;
}
} else {
// 如果没有，就添加映射
map2.put(right, left);
}
}
return true;
}
}
2.思路
也是一个双向映射
4.有效的字母异位词
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.Arrays;
/**
* Description: 242. 有效的字母异位词
*
* @Author sun
* @Create 2024/12/22 14:22
* @Version 1.0
*/
public class t242 {
public static boolean isAnagram(String s, String t) {
// 计算频率，看频率是否相同
int[] sFeq = new int[26];
int[] tFeq = new int[26];
for (int i = 0; i < s.length(); i++) {
sFeq[s.charAt(i) - 'a']++;
}
for (int j = 0; j < t.length(); j++) {
tFeq[t.charAt(j) - 'a']++;
}
return Arrays.equals(sFeq, tFeq);
}
}
2.思路
就是转化为频率数组，判断两个数组是不是一样就可以
5.字母异位词分组
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.*;
/**
* Description: 49. 字母异位词分组
*
* @Author sun
* @Create 2024/12/22 14:29
* @Version 1.0
*/
public class t49 {
public static List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
if (strs == null || strs.length == 0) {
return res;
}
// 存储结果的map
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] charArray = strs[i].toCharArray();
// 排序
Arrays.sort(charArray);
// 转换为String
String key = String.valueOf(charArray);
// 判断map中是否有相同的
List<String> list = null;
if (map.containsKey(key)) {
list = map.get(key);
} else {
list = new ArrayList<>();
}
list.add(strs[i]);
map.put(key, list);
}
return new ArrayList<>(map.values());
}
}
2.思路
就是使用一个map，其中的key是排序后的字符串，value就是与排序后的字符串相同的元素，遍历去比较即可
6.两数之和
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.HashMap;
import java.util.Map;
/**
* Description: 1. 两数之和
*
* @Author sun
* @Create 2024/12/22 14:52
* @Version 1.0
*/
public class t1 {
public static int[] twoSum(int[] nums, int target) {
// 哈希表来记录
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 计算差
int diff = target - nums[i];
// 如果map中有这个差值对应的就返回结果
if (map.containsKey(diff)) {
return new int[]{i, map.get(diff)};
}
// 如果没有，就把自己放到map中
map.put(nums[i], i);
}
return null;
}
}
2.思路
就是使用哈希表来记录元素以及元素下标，然后遍历的时候先判断哈希表中有没有目标元素减去当前元素的差，如果有就直接返回，没有就将当前元素放到map中
7.快乐数
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.HashSet;
import java.util.Set;
/**
* Description: 202. 快乐数
*
* @Author sun
* @Create 2024/12/22 15:20
* @Version 1.0
*/
public class t202 {
public static boolean isHappy(int n) {
// 使用集合来记录结果，也可以判断是否重复
Set<Integer> set = new HashSet<>();
while (n != 1) {
int num = getNum(n);
// 只要set中出现了num那么就是重复了直接返回false
if (set.contains(num)) {
return false;
}
set.add(num);
n = num;
}
return true;
}
/**
* 获取这个数每个位置的平方和
*
* @return
*/
private static int getNum(int num) {
int res = 0;
while (num > 0) {
int cur = num % 10;
res += cur * cur;
num /= 10;
}
return res;
}
public static void main(String[] args) {
isHappy(19);
}
}
2.思路
使用set来记录计算后的结果，核心就是在加入之前先判断set中是否已经有这个结果了，如果有，就是开始重复了，表明不是快乐数
8.存在重复元素 II
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.HashMap;
import java.util.Map;
/**
* Description: 219. 存在重复元素 II
*
* @Author sun
* @Create 2024/12/22 15:36
* @Version 1.0
*/
public class t219 {
public static boolean containsNearbyDuplicate(int[] nums, int k) {
// map存储
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 如果map中有
if (map.containsKey(nums[i])) {
// 进一步判断是否满足要求
if (Math.abs(map.get(nums[i]) - i) <= k) {
// 如果满足要求就直接返回
return true;
}
// 不满足要求就更新map
map.put(nums[i], i);
} else {
// 没有就添加到map中
map.put(nums[i], i);
}
}
return false;
}
public static void main(String[] args) {
System.out.println("containsNearbyDuplicate(new int[]{1,0,1,1}, 1) = " + containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1));
}
}
2.思路
使用map来存储元素和下标，先判断map中有没有与当前元素相同的元素，如果没有就加入到map，如果有，就进一步判断是否能满足要求，如果满足就返回结果，如果不满足就更新map
9.最长连续序列
1.答案
package com.sunxiansheng.classic150.g1;
import java.util.Arrays;
/**
* Description: 128. 最长连续序列
*
* @Author sun
* @Create 2024/12/23 12:52
* @Version 1.0
*/
public class t128 {
public static int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 1;
// 1 2 3 3 4 100 200
Arrays.sort(nums);
// dp[i]：以i结尾的最长连续序列的长度
// 状态转移：当nums[i] == nums[i - 1] + 1 dp[i] = dp[i - 1] + 1
// 当nums[i] == nums[i - 1] dp[i] = dp[i - 1]
// 当nums[i] > nums[i - 1] + 1 dp[i] = 1
// 初始化
int[] dp = new int[nums.length];
dp[0] = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = 1;
if (nums[i] == nums[i - 1] + 1) {
dp[i] = dp[i - 1] + 1;
} else if (nums[i] == nums[i - 1]) {
dp[i] = dp[i - 1];
} else {
dp[i] = 1;
}
res = Math.max(res, dp[i]);
}
return res;
}
public static void main(String[] args) {
System.out.println("longestConsecutive(new int[]{1,2,3,3,4,100,200}) = " + longestConsecutive(new int[]{1, 2, 3, 3, 4, 100, 200}));
}
}
2.思路
首先对数组排序，然后使用动态规划，定义为dp[i]：以i结尾的最长连续序列的长度，分为三种情况，第一种是当前元素等于前一个元素加一，那么dp[i] = dp[i - 1] + 1，第二种是当前元素跟前一个元素相同，dp[i] = dp[i - 1] 最后一种情况就是当前元素比前一个元素加一还要大，就说明不是连续的，所以当前元素结尾的最长连续序列的长度就是1
标签：150,return,map,int,矩阵,++,length,哈希,public From： https://blog.csdn.net/m0_64637029/article/details/144919249