实现Trie树
class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
public TrieNode() {}
TrieNode(char c){
TrieNode node = new TrieNode();
node.val = c;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
root.val = ' ';
}
public void insert(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null){
ws.children[c - 'a'] = new TrieNode(c);
}
ws = ws.children[c - 'a'];
}
ws.isWord = true;
}
public boolean search(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return ws.isWord;
}
public boolean startsWith(String prefix) {
TrieNode ws = root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return true;
}
}
二维字符矩阵中寻找字符串
public class Solution {
class TrieNode{
TrieNode[] next = new TrieNode[26];
String word;
}
public TrieNode buildTree(String[] words){
TrieNode root = new TrieNode();
for(String w : words){
TrieNode p = root;
for(char c : w.toCharArray()){
int i = c - 'a';
if(p.next[i] == null){
p.next[i] = new TrieNode();
}
p=p.next[i];
}
p.word = w;
}
return root;
}
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<String>();
TrieNode root = buildTree(words);
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
dfs(board,i,j,root,res);
}
}
return res;
}
public void dfs(char[][] board,int i,int j,TrieNode p,List<String> res){
char c = board[i][j];
if(c == '#' || p.next[c-'a']==null) return;
p = p.next[c-'a'];
if(p.word != null){
res.add(p.word);
p.word = null;
}
board[i][j] = '#';
if(i+1<board.length){dfs(board,i+1,j,p,res);}
if(i-1>=0){dfs(board,i-1,j,p,res);}
if(j+1<board[0].length){dfs(board,i,j+1,p,res);}
if(j-1>=0){dfs(board,i,j-1,p,res);}
board[i][j] = c;
}
}
课程表1(拓扑排序)
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] degree = new int[numCourses];
Queue queue = new LinkedList();
int count=0;
for(int i=0;i<numCourses;i++)
graph[i] = new ArrayList();
for(int i=0; i<prerequisites.length;i++){
degree[prerequisites[i][1]]++;
graph[prerequisites[i][0]].add(prerequisites[i][1]);
}
for(int i=0; i<degree.length;i++){
if(degree[i] == 0){
queue.add(i);
count++;
}
}
while(queue.size() != 0){
int course = (int)queue.poll();
for(int i=0; i<graph[course].size();i++){
int pointer = (int)graph[course].get(i);
degree[pointer]--;
if(degree[pointer] == 0){
queue.add(pointer);
count++;
}
}
}
if(count == numCourses)
return true;
else
return false;
}
}
课程表2(拓扑排序)
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] incLinkCounts = new int[numCourses];
List<List<Integer>> adjs = new ArrayList<>(numCourses);
initialiseGraph(incLinkCounts, adjs, prerequisites);
return solveByBFS(incLinkCounts, adjs);
// return solveByDFS(adjs);
}
private void initialiseGraph(int[] incLinkCounts, List<List<Integer>> adjs, int[][] prerequisites){
int n = incLinkCounts.length;
while (n-- > 0) adjs.add(new ArrayList<>());
for (int[] edge : prerequisites) {
incLinkCounts[edge[0]]++;
adjs.get(edge[1]).add(edge[0]);
}
}
private int[] solveByBFS(int[] incLinkCounts, List<List<Integer>> adjs){
int[] order = new int[incLinkCounts.length];
Queue<Integer> toVisit = new ArrayDeque<>();
for (int i = 0; i < incLinkCounts.length; i++) {
if (incLinkCounts[i] == 0) toVisit.offer(i);
}
int visited = 0;
while (!toVisit.isEmpty()) {
int from = toVisit.poll();
order[visited++] = from;
for (int to : adjs.get(from)) {
incLinkCounts[to]--;
if (incLinkCounts[to] == 0) toVisit.offer(to);
}
}
return visited == incLinkCounts.length ? order : new int[0];
}
}
N皇后问题1
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ret = new ArrayList<>();
if (n <= 0) return ret;
char[][] curr = new char[n][n];
for (char[] row : curr) {
Arrays.fill(row, '.');
}
boolean[] col_occupied = new boolean[n];
helper(ret, curr, col_occupied, 0, n);
return ret;
}
private void helper(List<List<String>> ret, char[][] curr, boolean[] col_occupied, int r, int n) {
if (r == n) {
List<String> list = new ArrayList<String>();
for (char[] row : curr) {
list.add(new String(row));
}
ret.add(list);
return;
}
for (int i=0; i<n; i++) {
if (isValid(curr, col_occupied, r, i, n)){
curr[r][i] = 'Q';
col_occupied[i] = true;
helper(ret, curr, col_occupied, r+1, n);
curr[r][i] = '.';
col_occupied[i] = false;
}
}
}
private boolean isValid(char[][]curr, boolean[] col_occupied, int row, int col, int n) {
if (col_occupied[col]) return false;
for (int i=1; row-i>=0 && col-i>=0; i++) {
if (curr[row-i][col-i] == 'Q') return false;
}
for (int i=1; row-i>=0 && col+i<n; i++) {
if (curr[row-i][col+i] == 'Q') return false;
}
return true;
}
}
N皇后问题2
public class Solution {
int count = 0;
public int totalNQueens(int n) {
boolean[] cols = new boolean[n]; // columns |
boolean[] d1 = new boolean[2 * n]; // diagonals \
boolean[] d2 = new boolean[2 * n]; // diagonals /
backtracking(0, cols, d1, d2, n);
return count;
}
public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
if(row == n) count++;
for(int col = 0; col < n; col++) {
int id1 = col - row + n;
int id2 = col + row;
if(cols[col] || d1[id1] || d2[id2]) continue;
cols[col] = true; d1[id1] = true; d2[id2] = true;
backtracking(row + 1, cols, d1, d2, n);
cols[col] = false; d1[id1] = false; d2[id2] = false;
}
}
}
有效的数独
public class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i=0; i<9; i++) {
if (!isParticallyValid(board,i,0,i,8)) return false;
if (!isParticallyValid(board,0,i,8,i)) return false;
}
for (int i=0;i<3;i++){
for(int j=0;j<3;j++){
if (!isParticallyValid(board,i*3,j*3,i*3+2,j*3+2)) return false;
}
}
return true;
}
private boolean isParticallyValid(char[][] board, int x1, int y1,int x2,int y2){
Set singleSet = new HashSet();
for (int i= x1; i<=x2; i++){
for (int j=y1;j<=y2; j++){
if (board[i][j]!='.') if(!singleSet.add(board[i][j])) return false;
}
}
return true;
}
}
数独解答
public class Solution {
int[] row = new int[9];
int[] col = new int[9];
int[] block = new int[9];
public void setSudoku(char[][] board) { // Set all the numbers given by the problem
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j] == '.') continue;
int temp = 1 << (board[i][j] - '0');
row[i] |= temp;
col[j] |= temp;
block[i/3*3+j/3] |= temp;
}
}
}
public boolean helpSolveSudoku(char[][] board) {
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j] != '.') continue; // already a valid number
for (int k=1; k<=9; k++) { // try from 1 to 9
int temp = 1 << k;
// The next line is a little bit long
if ((row[i] & temp)>0 || (col[j] & temp)>0 || (block[i/3*3+j/3] & temp)>0) continue; // not valid
board[i][j] = (char)(k + '0'); // valid, set the cell to be k
row[i] |= temp;
col[j] |= temp;
block[i/3*3+j/3] |= temp;
if (helpSolveSudoku(board)) return true;
board[i][j] = '.'; // set every changes back to last step
row[i] &= (~temp);
col[j] &= (~temp);
block[i/3*3+j/3] &= (~temp);
}
return false;
}
}
return true;
}
public void solveSudoku(char[][] board) {
setSudoku(board);
helpSolveSudoku(board);
}
}
全排列的下一个
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while(i >= 0 && nums[i] >= nums[i + 1]) i--; // Find 1st id i that breaks descending order
int j = nums.length - 1;
if(i >= 0) { // If not entirely descending
while(nums[j] <= nums[i]) j--; // Find rightmost first larger number j
swap(nums, i, j); // Switch i and j
}
reverse(nums, i + 1, nums.length - 1); // Reverse the descending sequence
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public void reverse(int[] nums, int i, int j) {
while(i < j) {
swap(nums, i, j);
i++; j--;
}
}
}
所有全排列(不含重复数字)
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutations = new ArrayList<>();
if (nums.length == 0) {
return permutations;
}
collectPermutations(nums, 0, new ArrayList<>(), permutations);
return permutations;
}
private void collectPermutations(int[] nums, int start, List<Integer> permutation,
List<List<Integer>> permutations) {
if (permutation.size() == nums.length) {
permutations.add(permutation);
return;
}
for (int i = 0; i <= permutation.size(); i++) {
List<Integer> newPermutation = new ArrayList<>(permutation);
newPermutation.add(i, nums[start]);
collectPermutations(nums, start + 1, newPermutation, permutations);
}
}
}
所有全排列(含重复数字)
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
LinkedList<Integer> list = new LinkedList<Integer>();
for (int num : nums) list.add(num);
permute(list, 0, res);
return res;
}
private void permute(LinkedList<Integer> nums, int start, List<List<Integer>> res){
if (start == nums.size() - 1){
res.add(new LinkedList<Integer>(nums));
return;
}
for (int i = start; i < nums.size(); i++){
if (i > start && nums.get(i) == nums.get(i - 1)) continue;
nums.add(start, nums.get(i));
nums.remove(i + 1);
permute(nums, start + 1, res);
nums.add(i + 1, nums.get(start));
nums.remove(start);
}
}
}
N个数全排列的第K个
public class Solution {
public String getPermutation(int n, int k) {
k--;
int fact = 1;
char[] result = new char[n];
result[n - 1] = '1';
for (int i = 2; i <= n; i++) {
fact *= i;
result[n - i] = (char) (k % fact * i / fact + '1');
for (int j = n - i + 1; j < n; j++) {
result[j] += result[j] >= result[n - i] ? 1 : 0;
}
k -= k % fact;
}
return new String(result);
}
}