书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Coin Change 2

给一个amount给一个coin数组, 问从coin中组成amount的多少种可能. 这个是典型的dp题, 设dp[i]是i块钱的找零个数. 那么我们就可以推断出, dp[i] += dp[i-coin[j]], 但是dp的初始值怎么设计? 我们设dp[0] = 1, 这意味着当, 当前的coin的和等于amount的时候, 算作一种找零方法.

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i = 0 ; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]]; 
            }
        }
        return dp[amount];
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

class Solution {

public int change(int amount, int[] coins) {

int[] dp = new int[amount+1];

dp[0] = 1;

for(int i = 0 ; i < coins.length; i++) {

for(int j = coins[i]; j <= amount; j++) {

dp[j] += dp[j - coins[i]];

}

return dp[amount];

}

Date October 15, 2019
Category Leetcode
Comments No Comments

Perfect Number

一个数是Perfect number就是他的factor的和等于这个数. 那么先求factor, 然后求和就可以了.

class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num <= 0)
            return false;
        int sum = 0;
        for(int i = 1; i <= Math.sqrt(num); i++) {
            if(num % i == 0) { // if it is a factor
                sum += i;
                if (i * i != num) { // adding num / i
                    sum += num / i;
                }
            }
        }
        System.out.println(sum);
        return sum - num == num;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public boolean checkPerfectNumber(int num) {

if(num <= 0)

return false;

int sum = 0;

for(int i = 1; i <= Math.sqrt(num); i++) {

if(num % i == 0) { // if it is a factor

sum += i;

if (i * i != num) { // adding num / i

sum += num / i;

}

System.out.println(sum);

return sum - num == num;

}

Date October 15, 2019
Category Leetcode
Comments No Comments

Find Largest Value in Each Tree Row

给一个二叉树, 找每层最大的值. 直接层序扫描.

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                max = Math.max(max, node.val);
                if(node.left != null)
                    q.offer(node.left);
                if(node.right != null)
                    q.offer(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution {

public List<Integer> largestValues(TreeNode root) {

List<Integer> res = new ArrayList<>();

if(root == null)

return res;

Queue<TreeNode> q = new LinkedList<>();

q.offer(root);

while(!q.isEmpty()) {

int size = q.size();

int max = Integer.MIN_VALUE;

for(int i = 0; i < size; i++) {

TreeNode node = q.poll();

max = Math.max(max, node.val);

if(node.left != null)

q.offer(node.left);

if(node.right != null)

q.offer(node.right);

}

res.add(max);

}

return res;

}

Date October 15, 2019
Category Leetcode
Comments No Comments

Longest Palindromic Subsequence

最长回文子序列, 首先这个子序列就是substring, 这题用dp做, dp[i][j]表示在substring(s, i, j)的最长回文子序列. 这时,有一下集中情况:

i==j, 这时候就是一个字符,当前最长回文子序列是1
i>j, 这时候越界了, 返回0
i<j时, 我们需要判断i和j的字符是不是相同,
- 如果相同, 继续探索i+1和j-1的答案并且加上i和j作为答案,即+2
- 如果不同, 则当前的i和j无法构成回文, 因为我们需要的是longest,所以选择i+1和j-1之间较大的那个.

public class Solution {
    public int longestPalindromeSubseq(String s) {
        return rec(s,0,s.length() - 1, new Integer[s.length()][s.length()]);
    }
    private int rec(String s, int i, int j, Integer[][] memo) {
        if(memo[i][j] != null)
            return memo[i][j];
        if(i > j)
            return 0;
        if(i == j)
            return 1;
        if(s.charAt(i) == s.charAt(j))
            memo[i][j] = rec(s,i+1,j-1,memo)+2;
        else
            memo[i][j] = Math.max(rec(s,i+1,j,memo),rec(s,i,j-1,memo));
        return memo[i][j];
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

public class Solution {

public int longestPalindromeSubseq(String s) {

return rec(s,0,s.length() - 1, new Integer[s.length()][s.length()]);

}

private int rec(String s, int i, int j, Integer[][] memo) {

if(memo[i][j] != null)

return memo[i][j];

if(i > j)

return 0;

if(i == j)

return 1;

if(s.charAt(i) == s.charAt(j))

memo[i][j] = rec(s,i+1,j-1,memo)+2;

else

memo[i][j] = Math.max(rec(s,i+1,j,memo),rec(s,i,j-1,memo));

return memo[i][j];

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Find Bottom Left Tree Value

给一个二叉树, 返回左下的节点的值, 直接层序扫描, 然后最后一层的第一个值肯定就是啦.

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> q = new ArrayList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                if(i == 0) {
                    res = q.
                }
            }
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

public int findBottomLeftValue(TreeNode root) {

int res = 0;

Queue<TreeNode> q = new ArrayList<>();

q.offer(root);

while(!q.isEmpty()) {

int size = q.size();

for(int i = 0; i < size; i++) {

if(i == 0) {

res = q.

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Fibonacci Number

Fib数, 当前数等于前两个数的和, 需要记录一下前两个数即可.

class Solution {
    public int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int first = 0;
        int second = 1;
        int current = 1;
        for(int i = 2; i <= n; i++) {
            current = first + second;
            first = second;
            second = current;
        }
        return current;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public int fib(int n) {

if(n == 0)

return 0;

if(n == 1)

return 1;

int first = 0;

int second = 1;

int current = 1;

for(int i = 2; i <= n; i++) {

current = first + second;

first = second;

second = current;

}

return current;

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Minesweeper

扫雷游戏, 给一个board给一个操作, 问操作过后的board什么样子. 这个就是dfs, 注意一点如果周围有雷, 需要用count记录一下雷数, 然后把count写入board.

public class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length;
        int n = board[0].length;
        int row = click[0];
        int col = click[1];
        int[][] dirs = new int[][]{
            {-1,-1},
            {-1,0},
             {1,0},
              {-1, 1},
               {1, -1}, 
                {1,1}, 
                 {0,1},
                  {0, -1}
        };
        
        if (board[row][col] == 'M') { // Mine
            board[row][col] = 'X';
        }
        else { // Empty
            // Get number of mines first.
            int count = 0;
            for (int[] d : dirs) {
                    int r = row + d[0], c = col + d[1];
                    if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) 
                        continue;
                    if (board[r][c] == 'M' ) 
                        count++;
            }
            
            if (count > 0) { // If it is not a 'B', stop further DFS.
                board[row][col] = (char)(count + '0');
            }
            else { // Continue DFS to adjacent cells.
                board[row][col] = 'B';
                for (int[] d : dirs) {
                        int r = row + d[0], c = col + d[1];
                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) 
                            continue;
                        if (board[r][c] == 'E') 
                            updateBoard(board, new int[] {r, c});
                    }
                }
            }        
        return board;
    }
}

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

public class Solution {

public char[][] updateBoard(char[][] board, int[] click) {

int m = board.length;

int n = board[0].length;

int row = click[0];

int col = click[1];

int[][] dirs = new int[][]{

{-1,-1},

{-1,0},

{1,0},

{-1, 1},

{1, -1},

{1,1},

{0,1},

{0, -1}

};

if (board[row][col] == 'M') { // Mine

board[row][col] = 'X';

}

else { // Empty

// Get number of mines first.

int count = 0;

for (int[] d : dirs) {

int r = row + d[0], c = col + d[1];

if (r < 0 || r >= m || c < 0 || c < 0 || c >= n)

continue;

if (board[r][c] == 'M' )

count++;

}

if (count > 0) { // If it is not a 'B', stop further DFS.

board[row][col] = (char)(count + '0');

}

else { // Continue DFS to adjacent cells.

board[row][col] = 'B';

for (int[] d : dirs) {

int r = row + d[0], c = col + d[1];

if (r < 0 || r >= m || c < 0 || c < 0 || c >= n)

continue;

if (board[r][c] == 'E')

updateBoard(board, new int[] {r, c});

}

return board;

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Diameter of Binary Tree

二叉树周长, 找到最长的一条路径在二叉树上. 这个路径不一定过root, 也不一定在某节点两侧. 所以我先要写一个找到depth的方法. 然后找每个节点的左边和右边. 最后把所有的结果取max.

/**
 * 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 diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        res = Math.max(left+right, res); // current
        res = Math.max(diameterOfBinaryTree(root.left), res); //current's left
        res = Math.max(diameterOfBinaryTree(root.right), res); //current's right
        return res;
    }
    public int depth(TreeNode root){
        if(root == null){
            return 0; 
        }
        int left = 1 + depth(root.left);
        int right = 1 + depth(root.right);
        
        return Math.max(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

/**

* 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 diameterOfBinaryTree(TreeNode root) {

if(root == null)

return 0;

int left = depth(root.left);

int right = depth(root.right);

res = Math.max(left+right, res); // current

res = Math.max(diameterOfBinaryTree(root.left), res); //current's left

res = Math.max(diameterOfBinaryTree(root.right), res); //current's right

return res;

}

public int depth(TreeNode root){

if(root == null){

return 0;

}

int left = 1 + depth(root.left);

int right = 1 + depth(root.right);

return Math.max(left, right);

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Student Attendance Record I

给一个string, 问有没有连续三个L或者超过一个A. 超过一个A用boolean判断, 连续三个L用一个counter和prev, prev记录前一个字符, counter记录几次重复.

class Solution {
    public boolean checkRecord(String s) {
        boolean absent = false;
        int countOfL = 0;
        char prev = 'C';
        for(char c : s.toCharArray()) {
            if(c == 'A') {
                if(!absent)
                    absent = true;
                else
                    return false;
            }
            else if(c == 'L' && prev == 'L'){
                countOfL++;
                if(countOfL == 2)
                    return false;
            }else{
                countOfL = 0;
            }
            prev = c;
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution {

public boolean checkRecord(String s) {

boolean absent = false;

int countOfL = 0;

char prev = 'C';

for(char c : s.toCharArray()) {

if(c == 'A') {

if(!absent)

absent = true;

else

return false;

}

else if(c == 'L' && prev == 'L'){

countOfL++;

if(countOfL == 2)

return false;

}else{

countOfL = 0;

}

prev = c;

}

return true;

}

Date October 14, 2019
Category Leetcode
Comments No Comments

Delete Node in a BST

BST中删除节点, 经典算法: 先BST搜到节点, 然后: 1. 如果左子树是空, 返回右子树. 2. 如果右子树是空, 返回左子树. 3. 两个都不是空的, 找到右子树最左的节点, 赋值给root, 然后继续删除右子树root的当前值.

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return root;
        if(root.val < key)
            root.right = deleteNode(root.right,key);
        else if(root.val > key)
            root.left = deleteNode(root.left, key);
        else{
            if(root.left == null)
                return root.right;
            else if(root.right == null)
                return root.left;
            else{
                TreeNode min = root.right;
                while(min.left != null)
                    min = min.left;
                root.val = min.val;
                root.right = deleteNode(root.right, root.val);
            }
        }
        return root;
    }
}

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 TreeNode deleteNode(TreeNode root, int key) {

if(root == null)

return root;

if(root.val < key)

root.right = deleteNode(root.right,key);

else if(root.val > key)

root.left = deleteNode(root.left, key);

else{

if(root.left == null)

return root.right;

else if(root.right == null)

return root.left;

else{

TreeNode min = root.right;

while(min.left != null)

min = min.left;

root.val = min.val;

root.right = deleteNode(root.right, root.val);

}

return root;

}

Date October 12, 2019
Category Leetcode
Comments No Comments

Coin Change 2

Perfect Number

Find Largest Value in Each Tree Row

Longest Palindromic Subsequence

Find Bottom Left Tree Value

Fibonacci Number

Minesweeper

Diameter of Binary Tree

Student Attendance Record I

Delete Node in a BST

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags

Links

October 2019
M	T	W	T	F	S	S
« Sep
	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