发表于 | 分类于

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

1
2
3
4
5
6
7
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: “wertf”.

Example 2:
Given the following words in dictionary,

1
2
3
4
[
  "z",
  "x"
]

The correct order is: “zx”.

Example 3:
Given the following words in dictionary,

1
2
3
4
5
[
  "z",
  "x",
  "z"
]

The order is invalid, so return “”.

Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

解法1： Topological sort

此题的难点是看出来这是一题graph。
本质上这题的意思是不同的字符之间有顺序，而我们要找出来这个隐藏的顺序。
那么graph的node就是可能的字符,用一个26大小的array记录每一个字符的入度和出度。
然后遍历相邻的两个string，搜索直到两个字符不一样为止，然后用一个adjacent matrix记录两者之间的关系
同时增加后一个字符的入度。
等完成了之后只需要用一个queue做一个topological sort就可以了。

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
class Solution {
public String alienOrder(String[] words) {
    List<Set<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < 26; i++) {
        adj.add(new HashSet<Integer>());
    }
    int[] degree = new int[26];
    Arrays.fill(degree, -1);
    for (int i = 0; i < words.length; i++) {
        for (char c : words[i].toCharArray()) {
            if (degree[c - 'a'] < 0) {
                degree[c - 'a'] = 0;
            }
        }
        if (i > 0) {
            String w1 = words[i - 1], w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                int c1 = w1.charAt(j) - 'a', c2 = w2.charAt(j) - 'a';
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2]++;
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) { // "abcd" -> "ab"
                    return "";
                }
            }
        }
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < degree.length; i++) {
        if (degree[i] == 0) {
            q.add(i);       
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        int i = q.poll();
        sb.append((char) ('a'  + i));
        for (int j : adj.get(i)) {
            degree[j]--;
            if (degree[j] == 0) {
                q.add(j);        
            }
        }
    }
    for (int d : degree) {
        if (d > 0) {
            return "";
        }
    }
    return sb.toString();
}
}

发表于 | 分类于

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

1
2
3
4
5
6
7
8
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

img

Note:
The total number of elements of the given matrix will not exceed 10,000.

解法1：

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
class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return new int[0];
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] res = new int[m * n];
        int[][] dirs = new int[][]{{-1,1},{1,-1}};
        int d = 0;
        int row = 0, col = 0;
        for (int i = 0; i < m * n; i++) {
            res[i] = matrix[row][col];
            row += dirs[d][0];
            col += dirs[d][1];
            if (row >= m) {
                row = m - 1;
                col += 2;
                d = 1 - d;
            }
            if (col >= n) {
                col = n - 1;
                row += 2;
                d = 1 - d;
            }
            if (row < 0) {
                row = 0;
                d = 1 - d;
            }
            if (col < 0) {
                col = 0;
                d = 1 - d;
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

解法1： DP O(n^2) Time + O(n^2) Space

用一个二维数组pal[i][j]表示，子字符串s[i,j]是否为一个palindrome。
同时用一个dp数组dp[i]表示的是[0, i]的字符串的最小cut
那么我们可以不停的尝试每一个子字符串[j, i]，如果[j,i]为palindrom，那么他的最小cut
就是dp[j - 1] + 1, 不停的变换j就可以求的对应的dp[i]的最小值。

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
class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        int[] dp = new int[n];  // dp[i] is the min cut for str [0, i]
        for (int i = 0; i < n; i++) {
            dp[i] = i;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (i - j + 1 <= 2 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;
                    dp[i] = Math.min(dp[i], j == 0 ? 0 : dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

发表于 | 分类于

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

1
2
3
  1
 / \
2   3

Return 6.

解法1： Divide & Conquer O(N)

对于一个node有左右两边的path,经过这一点的path可以有的情况是,往左，往右，自己，或者从左往右。
如果以left或者right为顶点的maxPath为负数的话，那么包含当前点的maxPath一定不用包含负数的left或者right

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return res;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, helper(root.left));
        int right = Math.max(0, helper(root.right));
        res = Math.max(res, left + right + root.val);
        return Math.max(left, right) + root.val;        
    }
}

发表于 | 分类于

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解法1： In-order Traversal O(N)

BST的很重要的性质就是对他进行in order traversal的话，得到的是一个有序数组。
那么可以按照in order traversal,找到第一个node使得node.val >= node.successor.val和最后一个node使得node.predecessor.val >= node.val就可以了

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode prev = null;
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        inOrder(root);
        if (first == null || second == null) return;
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
        return;
    }
    private void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        if (prev != null && prev.val >= root.val) {
            if (first == null) {
                first = prev;
            }
            if (first != null) {
                second = root;
            }
        }
        prev = root;
        inOrder(root.right);
    }
}

发表于 | 分类于

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

解法1： DP O(len_s1 * len_s2) Time and space

拿到题目似乎就是用dp来做，其他没有比较好的办法可以套。
那么就从小问题开始。
如果一个string是空，那么s3必须和另一个string相等。
如果用dp[i][j] 表示的是前i个字符和前j个字符组成的string可以是前(i+j)的interleave，那么就可以知道
i+j上的字符一定要么等于s1的第i个字符或者是s2的第j个字符。同时，如果这个条件满足，则就考虑
dp[i -1][j]或者dp[i][j - 1]是否为真就可以了。

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
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (s3.length() != s1.length() + s2.length()) return false;
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for (int col = 1; col <= len2; col++) {
            dp[0][col] = s2.substring(0, col).equals(s3.substring(0, col));
        }
        for (int row = 1; row <= len1; row++) {
            dp[row][0] = s1.substring(0, row).equals(s3.substring(0,row));
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int len = i + j;
                if (s3.charAt(len - 1) == s1.charAt(i - 1) && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                if (s3.charAt(len - 1) == s2.charAt(j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[len1][len2];
    }
}

发表于 | 分类于

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

1
2
3
4
5
6
7
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

1
2
3
4
5
6
7
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

1
2
3
4
5
6
7
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

解法1： 递归　O(2^n)

尝试每一个可能的split point，然后查看对于某一个切口i,可能可以分成的４个substring是否是scramble string.
时间复杂度是O(2^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
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] chars = new int[256];
        for (int i = 0; i < s1.length(); i++) {
            chars[(int)s1.charAt(i)]++;
            chars[(int)s2.charAt(i)]--;
        }
        for (int i = 0; i < 256; i++) {
            if (chars[i] != 0) return false;
        }
        for (int i = 1; i < s1.length(); i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i))
                && isScramble(s1.substring(i), s2.substring(i)))
                return true;
            if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
               && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)))
                return true;
        }
        return false;
    }
}

解法２: DP

参考了[这篇][1]帖子的解法，　可以用dp的思想，dp是一个bottom up的想法。
用一个dp[i][j][k]表示两个string分别从i和j开始，长度为k + 1的两个子串是否为scramble 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
public boolean isScramble(String s1, String s2) {  
  int len = s1.length();  
  if (len != s2.length()) return false;  
  if (s1.equals(s2)) return true;  
  // a table of matches  
  // T[i][j][k] = true iff s2.substring(j,j+k+1) is a scambled string of s1.substring(i,i+k+1)  
  boolean[][][] scrambled = new boolean[len][len][len];  
  for (int i=0; i < len; ++i) {  
    for (int j=0; j < len; ++j) {  
      scrambled[i][j][0] = (s1.charAt(i) == s2.charAt(j));  
    }  
  }  
  // dynamically fill up the table  
  for (int k=1; k < len; ++k) { // k: length  
    for (int i=0; i < len - k; ++i) { // i: index in s1  
      for (int j=0; j < len - k; ++j) { // j: index in s2  
        scrambled[i][j][k] = false;  
        for (int p=0; p < k; ++p) { // p: split into [0..p] and [p+1..k]  
          if ((scrambled[i][j][p] && scrambled[i+p+1][j+p+1][k-p-1])  
              || (scrambled[i][j+k-p][p] && scrambled[i+p+1][j][k-p-1])) {  
            scrambled[i][j][k] = true;  
            break;  
          }  
        }  
      }  
    }  
  }  
  return scrambled[0][0][len-1];  
}

发表于 | 分类于

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

解法1： DFS

这题比要print所有的解法的一个可以优化的地方是，只需要不停的每行fill的同时check是否是valid,如果是就继续往下填。
在看是否是合法的时候用三个数组或者是set来保存当前fill的状态。

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
class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        Set<Integer> cols = new HashSet<>();
        Set<Integer> rightDiag = new HashSet<>();
        Set<Integer> leftDiag = new HashSet<>();
        solve(0, cols, rightDiag, leftDiag, n);
        return count;
    }
    private void solve(int row, Set<Integer> cols, Set<Integer> rightDiag, Set<Integer> leftDiag, int n) {
        if (row == n) {
            count++;
            return;
        }
        /*
            Fill in each row
            And check if it is valid  
        */
        for (int i = 0; i < n; i++) {
            if (cols.contains(i)) continue;
            if (rightDiag.contains(row - i)) continue;
            if (leftDiag.contains(row + i)) continue;
            cols.add(i);
            rightDiag.add(row - i);
            leftDiag.add(row + i);
            solve(row + 1, cols, rightDiag, leftDiag, n);
            cols.remove(i);
            leftDiag.remove(row + i);
            rightDiag.remove(row - i);
        }
        return;
    }
}

发表于 | 分类于

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

解法1： DFS, O(N^N )

每一行有Ｎ个位置可以尝试，一共有Ｎ个行，不同的摆放方法是N^N
要注意的是在存储一个特定的摆放时，一个list就能解决问题。每一个元素对应的是每一行的列的位置。
比较直接的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
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
66
67
68
69
70
71
72
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> board = new ArrayList<>();
        dfs(res, board, n);
        return res;
    }
    /*
        Create a board from the configuration
    */
    private List<String> draw(List<Integer> board) {
        List<String> res = new ArrayList<>();
        int n = board.size();
        for (int i = 0; i < board.size(); i++) {
            char[] chs = new char[n];
            Arrays.fill(chs, '.');
            chs[board.get(i)] = 'Q';
            res.add(new String(chs));
        }
        return res;
    }
    /*
        Check if a board is valid
    */
    private boolean isValid(List<Integer> board) {
        if (board.size() == 0) {
            return true;
        }
        for (int i = 0; i < board.size() - 1; i++) {
            for (int j = i + 1; j < board.size(); j++) {
                if (board.get(i) == board.get(j)) return false;
                if (i + board.get(i) == j + board.get(j)) return false;
                if (j - i == board.get(j) - board.get(i)) return false;
            }
        }
       return true;
    }
    private void dfs(List<List<String>> res, List<Integer> board, int n) {
        if (!isValid(board)) {
            return;
        }
        if (board.size() == n) {
            List<String> solution = draw(board);
            res.add(solution);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (board.contains(i)) {
                continue;
            }
            board.add(i);
            dfs(res, board, n);
            board.remove(board.size() - 1);
        }
    }
}

发表于 | 分类于

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

img1

A sudoku puzzle…
img2

…and its solution numbers marked in red.

解法1： DFS, O(9^N)

N是空格子的总数
就是一个比较直接的dfs的题。对于每一个空格子尝试从１到９，然后检查是否是valid，如果是则继续，如果不是就填回原来的数字。

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
class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        solve(board);
    }
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    // fill up 1 to 9
                    for (char ch = '1'; ch <= '9'; ch++) {
                        if (isValid(board, i, j, ch)) {
                            board[i][j] = ch;
                            boolean next = solve(board);
                            if (next) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == ch) return false;
            if (board[row][i] != '.' && board[row][i] == ch) return false;
            // check the small matrix
            int matrixRow = (row / 3) * 3 + i / 3;
            int matrixCol = (col / 3) * 3 + i % 3;
            if (board[matrixRow][matrixCol] != '.' && board[matrixRow][matrixCol] == ch) return false;
        }
        return true;
    }
}