发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/unique-binary-search-trees-ii/

　　生成所有数量为n个节点的二叉查找树。

题目分析

　　思路参考了这里https://discuss.leetcode.com/topic/3079/a-simple-recursive-solution

　　主要是利用递归，不过这道题的tag是dp，还没有想清楚怎么用dp做。递归的思路不难理解，先把1-n每个数字作为二叉树的根，然后分别递归求左右子树的list，注意左子树的节点值范围是1~(i-1)，右子树的节点值范围是(i+1)-n,然后将求得的两个list进行两层遍历，组装成一棵树，加入list中。

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<TreeNode> gen(int start, int end) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > end) {
            list.add(null);//注意start>end不能直接返回null，而是返回带有null的list，这样能保证左/右子树的节点值为null，而且返回 null下面遍历也会抛异常。
            return list;
        }
        for(int i = start;i <= end; i++) {
            List<TreeNode> left = gen(start, i - 1);
            List<TreeNode> right = gen(i + 1, end);
            for(TreeNode l : left) {
                for(TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    list.add(root);
                }
            }
        }
        return list;
    }
    public List<TreeNode> generateTrees(int n) {
         if(n == 0) {//n＝0要特殊处理，不然返回[[]]是不正确的结果
             return new ArrayList<TreeNode>();
         }
         return gen(1, n);
    }
}

　　时间复杂度待分析

发表于   |   分类于 ，   |  

题目大意

　　http://poj.org/problem?id=1703

　　某个城市的罪犯分成两个帮派，给出一系列某两个罪犯是否是同一个帮派的信息，让你去推断某两个人是否是同一帮派。

题目分析

　　直接解感觉没思路，但是如果转换一下将每个罪犯属于帮派A，属于帮派B都作为数组的元素记录下来，那么

  • 当两个罪犯a和b属于相同帮派时，就讲a-A,b-A归在一起，将a-B,b-B归在一起。

  • 当两个罪犯a和b属于不同帮派时，就将a-B,b-A归在一起，将a-A,b-B归在一起。

    因此分析下来，有N个罪犯数组元素个数就是2N个，很自然的就用*并查集解就行了，注意最后判断如果罪犯a,b所对应的数组值相等则是同一个帮派，如果a跟b+N所对应的数组值相等，就不是一个帮派，否则的话就是不能确定。

    这个题如果拓展成3个帮派也是可以的，那么数组至少要有3*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
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
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 200010
int par[MAX_SIZE], rank2[MAX_SIZE];
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank2[i] = 0;
    }
}
int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);//路径压缩
    }
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) {
        return;
    }
    if(rank2[x] < rank2[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(rank2[x] == rank2[y]) {
           rank2[x]++;
        }
     }
    
}
bool same(int x, int y) {
    return find(x) == find(y);
}
void solve() {
    int T;
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        int N, K;
        scanf("%d%d", &N, &K);
        init(N * 2);
        
        for(int i = 0; i < K; i++) {
            int  x, y;
            char type;
            getchar();
            scanf("%c %d %d", &type, &x, &y);
            x = x - 1;
            y = y - 1;
            
            if(type == 'A') {
                if(same(x, y)) {
                    printf("In the same gang.\n");
                } else if (same(x, y + N)) {
                    printf("In different gangs.\n");
                } else {
                    printf("Not sure yet.\n");
                }
            } else { // 'D'
                unite(x, y + N);
                unite(x + N, y);
            }
        }
    }
}
int main() {
    solve();
    return 0;
}

时间复杂度待分析

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

　　leetcode买卖股票系列问题之一，不限次买入和卖出，但要求必须在卖出之后才能买入，另外买入和卖出之间至少间隔一个冷却天数。

题目分析

　　思路参考了这里：

　　https://discuss.leetcode.com/topic/30421/share-my-thinking-process/9

　　我们用两个数组sell和buy代表状态，sell[i]的含义是，第i 天之前包括第i天的所有以sell为结尾的序列所能得到的最大收益。buy[i]的含义是第i 天之前包括第i天的所有以buy为结尾的序列所能得到的最大收益。price[i]表示当天股票价格。leetcode的discuss区里有人还用了有限状态自动机画图直观的表示了出来sell，buy，cooldown三者转移关系，实际上，只需要两个数组保存状态就可以。

1
2
sell[i] = max(sell[i - 1], buy[i－1] + price[i]);
buy[i] = max(buy[i - 1], sell[i - 2] - price[i]);

　　有了转移方程以后，代码就比较好写了。注意一下sell[i]和buy[i]都依赖于前一项或者前两项的值，因此不需要保存所有的sell和buy值，额外空间复杂度为O(1)。但要注意buy初值设置成负数最小值，sell初值设置为0即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
    //buy[i] = max(sell[i-2]-price, buy[i-1])
    //sell[i] = max(buy[i-1]+price, sell[i-1])
    int buy = Integer.MIN_VALUE; //buy代表前一项buy值
    int prev_sell = 0; //pre_sell代表前前项的sell值
    int sell = 0; //sell代表前项的sell值
    for(int price : prices) {
        int prev_buy = buy;
        buy = Math.max(buy, prev_sell - price);
        prev_sell = sell;
        sell = Math.max(prev_buy + price, sell);
    }
    return sell;
}

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/decode-ways/

　　给你一个字符串，里边只含有数字0-9，而且0对应A，1对应B……26对应Z，问你这个字符串共有多少种解码方式，注意给的输入字符串有可能解码方案数为0，比如“90112”和“1212230”，输出就为0

题目分析

　　思路参考了这里。
https://github.com/haoel/leetcode/blob/master/algorithms/cpp/decodeWays/decodeWays.cpp

　　利用动态规划的思想，转移方程比较简单：

1
2
3
4
5
6
if(check(s.charAt(i)) == 1) {
    dp[i] = dp[i - 1];
}
if(check(s.charAt(i - 1), s.charAt(i)) == 1) {
	dp[i] += dp[i - 2];
}

　　由于dp[i]和dp[i-1],dp[i-2]有关，所以初始化时需要计算出dp[0]和dp[1]。计算dp[1]逻辑稍有点多，主要是因为需要考虑字符串前两位的各种情况，第一个位置分4种情况，0，1，2，3-9，第二个位置分五种情况，0，1，2，3-6，7-9。所以说计算dp[1]的if，else要把这4*5=20种情况都能覆盖到。

　　还要理解一点，dp数组并不是单调不减的，比如“120”。

阅读全文 »