【面试经典150】day 12

1.螺旋矩阵

2.旋转图像

3.矩阵置零

4.生命游戏

5. 赎金信

6.同构字符串

7.单词规律

1.螺旋矩阵

模拟

class Solution {public List<Integer> spiralOrder(int[][] matrix) {if(matrix.length==0)return new ArrayList<Integer>();int l=0,r=matrix[0].length-1,t=0,b=matrix.length-1,x=0;Integer[] ret=new Integer[(r+1)*(b+1)];while(true){//左到右for(int i=l;i<=r;i++){ret[x++]=matrix[t][i];}if(++t>b) break;//上到下for(int i=t;i<=b;i++){ret[x++]=matrix[i][r];}if(l>--r) break;//右到左for(int i=r;i>=l;i--){ret[x++]=matrix[b][i];}if(t>--b) break;//下到上for(int i=b;i>=t;i--){ret[x++]=matrix[i][l];}if(++l>r) break;}return Arrays.asList(ret);}
}

2.旋转图像

class Solution {public void rotate(int[][] matrix) {int n=matrix.length;//将matrix深拷贝到tmpint [][] tmp=new int[n][];for(int i=0;i<n;i++){tmp[i]=matrix[i].clone();}//按照元素旋转公式，遍历修改原矩阵matrix的各元素for(int i=0;i<n;i++){for(int j=0;j<n;j++){//旋转公式matrix[j][n-1-i]=tmp[i][j];}}}
}

ps：使用clone()函数进行二维矩阵克隆

3.矩阵置零

class Solution {public void setZeroes(int[][] matrix) {//逐步扩展法，如果一个元素为0，那么将整行和整列设置为0//实现：先遍历一遍元素，统计所有为0元素的i,j下标，再分别清除int m=matrix.length;int n=matrix[0].length;//使用列表List<Integer> toi=new ArrayList<>();List<Integer> toj=new ArrayList<>();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(matrix[i][j]==0){toi.add(i);toj.add(j);}}}//开始清除for(int seti:toi){for(int j=0;j<n;j++){matrix[seti][j]=0;}}for(int setj:toj){for(int i=0;i<m;i++){matrix[i][setj]=0;}}}
}

ps:数组列表的添加元素方式为add()

4.生命游戏

class Solution {public void gameOfLife(int[][] board) {//貌似需要新建一个二维数组//todo1: 在遍历二维数组的同时，统计活细胞的数目//todo2: 根据题目要求，活变死，死变活。//todo3: 需要原地操作，并且相互之间不能影响//0代表死细胞，1代表活细胞，2代表活转死，3代表死转活，这样后面恢复的时候能够%2简单操作int m=board.length;int n=board[0].length;for(int i=0;i<m;i++){for(int j=0;j<n;j++){//todo1,9个格子int count=0;for(int x=-1;x<=1;x++){for(int y=-1;y<=1;y++){//去掉自身情况以及越界情况if(x==0&&y==0||i+x<0||i+x>=m||j+y<0||j+y>=n) continue;//开始对活细胞计数,活着或者刚死（1或者2）if(board[i+x][j+y]==1||board[i+x][j+y]==2){count++;}}}//todo2if(board[i][j]==1&&(count<2||count>3)) board[i][j]=2;if(board[i][j]==0&&count==3) board[i][j]=3;}}//恢复数组，刚死或者复活都变为活或者死两种状态for(int i=0;i<m;i++){for(int j=0;j<n;j++){board[i][j]%=2;}}}
}

5. 赎金信

class Solution {public boolean canConstruct(String ransomNote, String magazine) {//就说判断第一个是不是第二个的子集//todo1:统计每个字符串中字符出现的次数//tip1:使用数组来存，int类型//tip2:不能使用for-each取值（字符串中），需要使用charAt//todo2:判断的逻辑为：遍历第一个counter结果，是否存在一个字符的统计次数高于第二个字符串//todo1int [] x=counter(ransomNote),y=counter(magazine);//todo2for(int i=0;i<x.length;i++){if(x[i]>y[i]){return false;}}return true;}//tip1private int[] counter(String s){int [] num=new int[26];for(int i=0;i<s.length();i++){num[s.charAt(i)-'a']++;}return num;}
}

6.同构字符串

class Solution {public boolean isIsomorphic(String s, String t) {//todo1:分别建立哈希表，建立a->b和b->a的映射//todo2:判断逻辑：存在a这个key，但a这个key的value不是b//        或者存在b这个key，但b这个key的value不是aMap<Character,Character> s2t=new HashMap<>(),t2s=new HashMap<>();for(int i=0;i<s.length();i++){//取出a和bchar a=s.charAt(i),b=t.charAt(i);if(s2t.containsKey(a)&&s2t.get(a)!=b||t2s.containsKey(b)&&t2s.get(b)!=a){return false;}//不管怎么样，都要存进去s2t.put(a,b);t2s.put(b,a);}return true;}
}

ps：

哈希表/字典常用

dict.containsKey(key);
dict.get(key);
dict.put(key,value);

7.单词规律

class Solution {public boolean wordPattern(String pattern, String s) {//思考：和上一题差不多，都是利用映射关系 a和bMap<Character,String> p2s=new HashMap<>();Map<String,Character> s2p=new HashMap<>();//todo1:需要根据空格将s转为列表String[] s1 = s.split(" ");if (pattern.length()!= s1.length) {return false;}for(int i=0;i<pattern.length();i++){//取出a和bchar a=pattern.charAt(i);String b=s1[i];//判断逻辑,和字符串比较需要用equals()if((p2s.containsKey(a)&&!p2s.get(a).equals(b))||(s2p.containsKey(b)&&s2p.get(b)!=a)){return false;}//不管怎样，都要添加进去p2s.put(a,b);s2p.put(b,a);}return true;}
}

ps:

Arrays.toList()操作