全网最便宜的购物软件_高端网站设计报价_百度品牌广告_抖音广告

矩阵

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));}}}// 设置0for (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;// 向上置0for (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 -> sMap<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;}// 存储结果的mapMap<String, List<String>> map = new HashMap<>();for (int i = 0; i < strs.length; i++) {char[] charArray = strs[i].toCharArray();// 排序Arrays.sort(charArray);// 转换为StringString 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那么就是重复了直接返回falseif (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;}// 不满足要求就更新mapmap.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 200Arrays.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