76
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
HashMap<Character, Integer> hash1 = new HashMap<>();
HashMap<Character, Integer> hash2 = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c1 = t.charAt(i);
hash1.put(c1, hash1.getOrDefault(c1, 0) + 1);
}
int left = 0;
int right = 0;
int vaild = 0;
int window = Integer.MAX_VALUE;
int start = 0;
while (right < s.length()) {
char c2 = s.charAt(right);
right++;
hash2.put(c2, hash2.getOrDefault(c2, 0) + 1);
if (hash1.containsKey(c2) && hash1.get(c2).equals(hash2.get(c2))) {
vaild++;
}
while (vaild == hash1.size()) {
if(window!=Math.min(window,right-left)){
window=Math.min(window,right-left);
start = left;
}
char c3 = s.charAt(left);
if (hash1.containsKey(c3) && hash1.get(c3).equals(hash2.get(c3))) {
vaild--;
}
hash2.put(c3,hash2.get(c3)-1);//更新值
left++;
}
}
if (window == Integer.MAX_VALUE) {
return "";
} else {
return s.substring(start,start+window);
}
}
}36
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
class Solution {
public boolean isValidSudoku(char[][] board) {
HashSet<String> count = new HashSet<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
if (!count.add(c + "row" + i) || !count.add(c + "column" + j)
|| !count.add(c + "block" + i / 3 + "-" + j/3)) {// 通过字符对比判断是否重合
return false;
}
}
}
}
return true;
}
}或
class Solution {
public boolean isValidSudoku(char[][] board) {
int[] nums = new int[10];
//查行
//将数组初始化为全0，按行遍历，将board里的值当做数组下标
//若之前已经存在，则在数组中这个位置为1，否则为0
for(int x = 0 ;x < 9 ; x++){
setZero(nums);
for(int y = 0 ; y < 9 ; y++){
if(board[x][y] != '.'){
if(nums[board[x][y]-'0'] == 1){
return false;
}else{
nums[board[x][y]-'0'] = 1;
}
}
}
}
//test each column
for(int x = 0 ;x < 9 ; x++){
setZero(nums);
for(int y = 0 ; y < 9 ; y++){
if(board[y][x] != '.'){
if(nums[board[y][x]-'0'] == 1){
return false;
}else{
nums[board[y][x]-'0'] = 1;
}
}
}
}
//test each cube
for(int x = 0 ;x < 3 ; x++){
for(int y = 0 ; y < 3 ; y++){
setZero(nums);
for(int i = 0; i < 3 ; i++){
for(int j=0; j < 3; j++){
if(board[y*3+i][x*3+j] != '.'){
if(nums[board[y*3+i][x*3+j]-'0'] == 1){
return false;
}else{
nums[board[y*3+i][x*3+j]-'0'] = 1;
}
}
}
}
}
}
return true;
}
public void setZero(int[] nums){
for(int x = 0; x < nums.length ;x ++){
nums[x] = 0;
}
}
}54
提示
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int r=matrix.length;
int l=matrix[0].length;
int i=0,j=0;
boolean[][] visitd=new boolean[r][l];
ArrayList<Integer> list = new ArrayList<>();
while(list.size()<r*l){
//往右
while(i>=0&&j>=0&&i<r&&j<l&&!visitd[i][j]){
list.add(matrix[i][j]);
visitd[i][j]=true;
j++;
}
j--;
i++;
//往下
while(i>=0&&j>=0&&i<r&&j<l&&!visitd[i][j]){
list.add(matrix[i][j]);
visitd[i][j]=true;
i++;
}
i--;
j--;
//往左
while(i>=0&&j>=0&&i<r&&j<l&&!visitd[i][j]){
list.add(matrix[i][j]);
visitd[i][j]=true;
j--;
}
j++;
i--;
//往上
while(i>=0&&j>=0&&i<r&&j<l&&!visitd[i][j]){
list.add(matrix[i][j]);
visitd[i][j]=true;
i--;
}
i++;
j++;
}
return list;
}
}48
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution {
public void rotate(int[][] matrix) {
int temp = 0;
for(int i=0;i<matrix.length;i++){
for(int j=0;j<i;j++){
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//再镜像对称
for(int j =0;j<matrix.length/2;j++){
for(int i=0;i<matrix[0].length;i++){
temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length-j-1];
matrix[i][matrix.length-j-1] = temp;
}
}
}
}73
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
class Solution {
public void setZeroes(int[][] matrix) {
HashSet<Integer> rows = new HashSet<>();
HashSet<Integer> cols = new HashSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (rows.contains(i) || cols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}289
根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int count = 0;
if(i - 1 >= 0 && (board[i - 1][j] == 1 || board[i - 1][j] == -1)) count++;
if(i - 1 >= 0 && j - 1 >= 0 && (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == -1)) count++;
if(i - 1 >= 0 && j + 1 < n && (board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == -1)) count++;
if(j - 1 >= 0 && (board[i][j - 1] == 1 || board[i][j - 1] == -1)) count++;
if(j - 1 >= 0 && i + 1 < m && (board[i + 1][j - 1] == 1 || board[i + 1][j - 1] == -1)) count++;
if(j + 1 < n && (board[i][j + 1] == 1 || board[i][j + 1] == -1)) count++;
if(j + 1 < n && i + 1 < m && (board[i + 1][j + 1] == 1 || board[i + 1][j + 1] == -1)) count++;
if(i + 1 < m && (board[i + 1][j] == 1 || board[i + 1][j] == -1)) count++;
if((board[i][j] == 1 || board[i][j] == -1) && (count < 2 || count > 3)){
board[i][j] = -1;
} else if((board[i][j] == 0 || board[i][j] == -2) && count == 3){
board[i][j] = -2;
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == -1) board[i][j] = 0;
if(board[i][j] == -2) board[i][j] = 1;
}
}
}
}383
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> hash1 = new HashMap<>();
HashMap<Character, Integer> hash2 = new HashMap<>();
char[] c1 = ransomNote.toCharArray();
char[] c2 = magazine.toCharArray();
for (char s1 : c1) {
hash1.put(s1, hash1.getOrDefault(s1, 0) + 1);
}
for (char s2 : c2) {
hash2.put(s2, hash2.getOrDefault(s2, 0) + 1);
}
for(char s3 :hash1.keySet()){
int p1 = hash1.get(s3);
int p2 = hash2.getOrDefault(s3,0);
if(p1>p2){
return false;
}
}
return true;
}
}205
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> hash = new HashMap<>();
char[] c1 = s.toCharArray();
char[] c2 = t.toCharArray();
for(int i=0;i<c1.length;i++){
if(hash.containsKey(c1[i])){
if(hash.get(c1[i])!=c2[i]){
return false;
}
}else{
if(hash.containsValue(c2[i])){
return false;
}
hash.put(c1[i],c2[i]);
}
}
return true;
}
}
