首页 > 代码库 > 完成得不是很仔细哦！

完成得不是很仔细哦！

2024-08-27 06:36:12   223人阅读

(1)Word Pattern

技术分享

解题思路一：使用HashMap,将字符串转化为字符串数组，并行遍历字符和字符串数组，比较它们上一次（最后一次）出现的位置，如果不相同返回false，遍历完成后返回true。

代码如下：

技术分享 
 1 public class Solution {
 2     public boolean wordPattern(String pattern, String str) {
 3         String[] words = str.split(" ");
 4         if (words.length != pattern.length()) {
 5             return false;
 6         }
 7         Map index = new HashMap();
 8         for (Integer i = 0; i < words.length; i++) {
 9             if (index.put(words[i], i) != index.put(pattern.charAt(i), i)){
10                 return false;
11             }
12         }
13         return true;
14     }
15 }
View Code

注意：字符串分割为字符数组string.split(" ")。pattern.put( , )返回的是上一次保存的位置。

int是基本数据类型。Integer是其包装类，注意是一个类，是对int的扩展，定义了很多转换方法。比如，现在int要转为String  int a=0; String result=Integer.toString(a);在java中，包装类比较多的用途是用在于各种数据类型的转化中。

解题思路二：依然使用HashMap,char和string一一对应，同时将string保存在set,避免多对一的情况。

代码如下：

技术分享 
 1 public class Solution {  
 2     public boolean wordPattern(String pattern, String str) {  
 3         //input check  
 4           
 5         String[] strs = str.split(" ");  
 6         if(pattern.length() != strs.length  ) return false;  
 7           
 8         Map<Character, String> map = new HashMap<>();  
 9         Set<String> unique = new HashSet<>();  
10           
11         for(int i=0; i<pattern.length(); i++) {  
12             char c = pattern.charAt(i);  
13             if(map.containsKey(c) ) {  
14                 if(!map.get(c).equals(strs[i])) return false;  
15             } else {  
16                 if(unique.contains(strs[i])) return false;  
17                 map.put(c, strs[i]);  
18                 unique.add(strs[i]);  
19             }  
20         }  
21         return true;  
22     }  
23 }
View Code

（2） Valid Sudoku

技术分享

题目本意：检查该九宫格中每行每列每个小九宫格中是否有重复元素。

难点在于表示第i个九宫格每个格子的坐标。

观察行号规律：

第0个九宫格：000111222; 第1个九宫格：000111222; 第2个九宫格：000111222;

第3个九宫格：333444555; 第4个九宫格：333444555; 第5个九宫格：333444555;

第6个九宫格：666777888; 第7个九宫格：666777888; 第8个九宫格：666777888;

可见对于每三个九宫格行号增3；对于单个九宫格，每三个格点行号增1。

因此第i个九宫格的第j个格点的行号可表示为i/3*3+j/3

观察列号规律：

第0个九宫格：012012012; 第1个九宫格：345345345; 第2个九宫格：678678678;

第3个九宫格：012012012; 第4个九宫格：345345345; 第5个九宫格：678678678;

第6个九宫格：012012012; 第7个九宫格：345345345; 第8个九宫格：678678678;

可见对于下个九宫格列号增3，循环周期为3；对于单个九宫格，每个格点行号增1，周期也为3。

周期的数学表示就是取模运算mod。

因此第i个九宫格的第j个格点的列号可表示为i%3*3+j%3

使用HashSet来进行操作，set.add()用来向Set集合添加对象。如果Set集合中不包含要添加的对象，则添加对象并返回true；如果Set集合中已经包含相同的对象，返回false。

代码如下：

技术分享 
 1 public class Solution {
 2     public boolean isValidSudoku(char[][] board) {
 3     for(int i = 0; i<9; i++){
 4         HashSet<Character> rows = new HashSet<Character>();
 5         HashSet<Character> columns = new HashSet<Character>();
 6         HashSet<Character> cube = new HashSet<Character>();
 7         for (int j = 0; j < 9;j++){
 8             //if(board[i][j]!=‘.‘ && rows.add(board[i][j]) !=true)
 9             if(board[i][j]!=‘.‘ && !rows.add(board[i][j]))
10                 return false;
11             if(board[j][i]!=‘.‘ && !columns.add(board[j][i]))
12                 return false;
13             int RowIndex = 3*(i/3);
14             int ColIndex = 3*(i%3);
15             if(board[RowIndex + j/3][ColIndex + j%3]!=‘.‘ && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
16                 return false;
17         }
18     }
19     return true;
20   }
21 }
View Code

 

完成得不是很仔细哦！


联系
我们