7.20号刷题

发表于 | 分类于 | 0 comments

第一题 51. N-Queens

题目描述

解决N 皇后问题

算法

主要利用回溯, 本题由于要求String格式进行输出，因此比较麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class solveNQueens51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n == 0) return res;
        char[][] board = inital(n);
        nQueens(board, 0, res);
        return res;
    }
    public char[][] inital(int n) {
        char[][] place = new char[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                place[i][j] = '.';
        return place;
    }
    public void nQueens(char[][] board, int colNumber, List<List<String>> res) {
        if (colNumber == board.length) {
            res.add(construct(board));
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (isValid(board, i, colNumber)) {
                board[i][colNumber] = 'Q';
                nQueens(board, colNumber + 1, res);
                board[i][colNumber] = '.';
            }
        }
    }
    public List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String s = new String(board[i]);
            res.add(s);
        }
        return res;
    }
    public boolean isValid(char[][] places, int row, int col) {
        for (int i = 0; i < places.length; i++) {
            if (places[row][i] == 'Q') return false;
            if (places[i][col] == 'Q') return false;
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (places[i][j] == 'Q') return false;
        }
        for (int i = row, j = col; i < places.length && j >= 0; i++, j--) {
            if (places[i][j] == 'Q') return false;
        }
        return true;
    }
}

第二题 52. N-Queens II

题目描述

与上题一样，只不过现在只需要统计出n皇后满足的数字即可

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class totalNQueens52 {
    public int totalNQueens(int n) {
        int[] res = new int[1];
        int[][] board = new int[n][n];
        solve(board, 0, res);
        return res[0];
    }
    public void solve(int[][] board, int colNum, int[] res) {
        if (colNum == board.length) {
            res[0]++;
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (isValid(board, i, colNum)) {
                board[i][colNum] = 1;
                solve(board, colNum + 1, res);
                board[i][colNum] = 0;
            }
        }
    }
    public boolean isValid(int[][] board, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 1) return false;
            if (board[row][i] == 1) return false;
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) return false;
        }
        for (int i = row, j = col; i < board.length && j >= 0; i++, j--) {
            if (board[i][j] == 1) return false;
        }
        return true;
    }
}

第三题 31. Next Permutation

题目描述

求下一个最大的数

算法

  1. 首先先找到从右边起的，往左边数的第一个打破逆序的数字num
  2. 然后找到右边起的第一个比num大的数字
  3. 交换他们的位置
  4. 之后交换所有从num的下一个数字起的所有的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class nextPermutation31 {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[i] >= nums[j]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums, int begin, int end) {
        int low = begin, high = end;
        while (low <= high) swap(nums, low++, high--);
    }
}

第四题 60. Permutation Sequence

题目描述

一个数字有很多种排列方式，求出对于1 - n组成的数字中，第k种排列方式

算法

对于n，如果拿去n，那么剩下有(n - 1)!种的排列方式。这样，比如对于1，2，3，4。我们需要第23种排列，那么22 / 3! = 3。我们可以知道，1 - 6对应位置0，即开头是1 剩下的所有组合是 {2，3，4}的排列。7 - 12对应位置1， 即开头是2，剩下对应的是{1，3，4}的排列。现在对应位置是3，那么即第一个数字是4，剩下{1，2，3}的排列。

根据这种方法，循环直到找到最后一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        
        StringBuilder res = new StringBuilder();
        k--;
        for (int i = n; i > 0; i--) {
            int index = k / factorial[i - 1];
            res.append(nums.get(index));
            k -= index * factorial[i - 1];
            nums.remove(index);
        }
        return res.toString();
    }
}

第五题 77. Combinations

题目描述

求一个1 ~ n的所有数字中，有所少种长度为n的组合方式

算法

还是基本的回溯的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class combine77 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k == 0) return res;
        backtrack(n, k, 1, new ArrayList<>(), res);
        return res;
    }
    public void backtrack(int n, int k, int start, List<Integer> cur, List<List<Integer>> res) {
       if (k == 0) {
           res.add(new ArrayList<>(cur));
           return;
       }
       for (int i = start; i <= n; i++) {
           cur.add(i);
           backtrack(n, k - 1, i + 1, cur, res);
           cur.remove(cur.size() - 1);
       }
    }
}

题目描述

在一个二维矩阵中，查看是否存在一个指定单词。规则是，只能在二维矩阵中上下左右移动，并进行寻找

算法

使用DFS进行搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class exist79 {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public boolean exist(char[][] board, String word) {
        if (word.length() == 0) return false;
        if (board.length == 0 || board[0].length == 0) return false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    char origin = board[i][j];
                    board[i][j] = '*';
                    if (DFS(board, word.substring(1), i, j)) return true;
                    else board[i][j] = origin;
                }
            }
        }
        return false;
    }
    public boolean DFS(char[][] board, String word, int x, int y) {
        if (word.length() == 0) return true;
        for (int[] dir : dirs) {
            int xx = x + dir[0];
            int yy = y + dir[1];
            if (xx >= 0 && yy >= 0 && xx < board.length && yy < board[0].length && board[xx][yy] == word.charAt(0)) {
                char origin = board[xx][yy];
                board[xx][yy] = '*';
                if (DFS(board, word.substring(1), xx, yy)) return true;
                else board[xx][yy] = origin;
            }
        }
        return false;
    }
}

第七题 212. Word Search II

题目描述

给定二维格板和一组单词，在格板中找出这些单词。

每一个单词必须通过顺序邻接的单元格中的字母构成，“邻接”是指水平或者竖直方向相邻。同一个单元格中的字母在构建某个单词时最多只能使用一次。

测试用例见题目描述。

注意：

你可以假设输入只包含小写字母a-z

你需要最优化你的回溯策略，以通过数据规模比较大的测试样例。能不能尽可能早的停止回溯？

提示：

如果当前的候选单词在所有的单词前缀中都不存在，就可以立即停止回溯。什么样的数据结构可以更加有效地响应这种查询？哈希表可以吗？为什么可以或者不行？字典树怎么样？如果要了解字典树的基础知识，可以先完成这道题目：Implement Trie (Prefix Tree) ，实现字典树（前缀树）

算法

利用字典树，进行DFS。 否则会timeout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(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 > 0) dfs(board, i - 1, j, p, res);
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res);
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
        board[i][j] = c;
    }
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode p = root;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
            }
            p.word = word;
        }
        return root;
    }
}

第八题 208. Implement Trie (Prefix Tree)

题目描述

实现字典树，包含插入，查找和前缀查找方法。

注意：

你可以假设所有的输入只包含小写字母a-z

算法

下面这个是自己的版本的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Trie {
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] chars = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (cur.next[index] == null) {
                cur.next[index] = new TrieNode();
            }
            cur = cur.next[index];
        }
        cur.word = word;
    }
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (cur.next[index] == null) return false;
            cur = cur.next[index];
        }
        return cur.word != null && cur.word.equals(word);
    }
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < chars.length - 1; i++) {
            int index = chars[i] - 'a';
            if (cur.next[index] == null) return false;
            cur = cur.next[index];
        }
        int index = chars[chars.length - 1] - 'a';
        return cur.next[index] == null ? false : true;
    }
}

第九题 211. Add and Search Word - Data structure design

题目描述

设计一个数据结构支持下列两种操作：

void addWord(word)
bool search(word)

search(word)可以搜索一个普通字符串或者一个只包含字母a-z或者.的正则表达式。符号.代表任意单个字母。

测试用例见题目描述。

注意：
你可以假设所有的单词只包含小写字母a-z

提示：
完成此题目之前，最好先做Implement Trie (Prefix Tree)

算法

还是使用Trie的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class WordDictionary {
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isword = false;
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        char[] chars = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (cur.next[index] == null) {
                cur.next[index] = new TrieNode();
            }
            cur = cur.next[index];
        }
        cur.isword = true;
    }
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        char[] wordChars = word.toCharArray();
        return backtrack(wordChars, 0, root);
    }
    public boolean backtrack(char[] word, int start, TrieNode cur) {
        if (start >= word.length)
            return false;
        char c = word[start];
        int index = c - 'a';
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (cur.next[i] != null) {
                    if (cur.next[i].isword && start + 1 == word.length)
                        return true;
                    boolean tag = backtrack(word, start + 1, cur.next[i]);
                    if (tag)
                        return true;
                }
            }
        }
        else if (c == word[start]) {
            if (cur.next[index] != null) {
                if (cur.next[index].isword && start + 1 == word.length)
                    return true;
                return backtrack(word, start + 1, cur.next[index]);
            }
        }
        return false;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */