k sum I II

Leave a comment

August 22, 2016 by oneOokay

k sum:

基本看到了两种解法:2 sum的递归和dp

2 sum的递归见此:http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html 好像不太适用与这个题目,因为引用参数以及返回参数都不一样。 (以后有空再研究一下吧,这个先放着做个参考)

所以还是先用dp from 九章:补充参考:http://www.cnblogs.com/yuzhangcmu/p/4279676.html

里面涉及了一个三维矩阵 int[][][],大概不用太去纠结它的具象吧。。。理解就好。

dp[i][j][t] 表示数组A的前i个数中,取j个数使其sum值为t的方案的个数

dp[i][0][0]: 数组A的前i个数,取0个数使其sum值为0的方案的个数为:1. (一个值都不取)

public int kSum(int A[], int k, int target) {
// write your code here
int len = A.length;
if (A == null || len < 1) {
return 0;
}

int[][][] dp = new int[len + 1][k + 1][target + 1]; //前i个数中找出j个数使得他们的sum = target
//initialization
for (int i = 0; i < len + 1; i ++) {
dp[i][0][0] = 1;
}

for (int i = 1; i <= len; i ++) {
for (int j = 1; j <= k; j ++) {
for (int t = 1; t <= target; c ++) {
dp[i][j][t] = 0; //先初始化为0
if (t >= A[i – 1]) { //这个t >= A[i] – 1 是把当前元素A[i-1]加入到方案集的条件。如果当前数的值比t小:那么此时前i个数中取j个数使其sum为t的方案集 等于 前i-1个数中取j-1个数使其sum为t-A[i] 的各个方案集再加上这个单独的{元素},所以方案的数量不变。
dp[i][j][t] = dp[i – 1][j – 1][t – A[i – 1]];
}
//不把当前元素A[i – 1] 加入方案集:如果当前数的值比t大,那么方案必然不取当前元素,所以此时“前i个数中取j个数使其sum为t的方案集”等于 “前i-1个数中,取j个数使其sum为t的方案集”。这里并不能用else。因为不是排他的选择而是两者均可,只不过前者需要有一定的if条件满足。所以进行累加。
dp[i][j][t] += dp[i – 1][j][t];
}}}
return dp[len][k][target];
}

90. k sum II:

从HC那里得到了启发,HC的思维方式特别好而且容易懂。九章上面的那个方法不好懂,不要看了。HC的方法比较好。

DFS搜索找出所有解:找到一个数为一层,找到这个数以后,加入oneResult。

对下一层要做的事情,k变成k-1了(接下来要找k-1个数),target变成了target – 找到的这个数,下一层的查找范围为从这个数的index + 1开始到最后一个数。

ArrayList<ArrayList<Integer>> ans;  //发现用这个的话在dfs里面能够少传一个参数,更加好。
public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
ans = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> oneResult = new ArrayList<Integer>();
if (k <= 0 || target <= 0 || A == null || A.length == 0) {
return ans;
}
dfs(oneResult, 0, target, k, A);
return ans;
}

private void dfs(ArrayList<Integer> oneResult, int index, int target, int k, int[] A) {
if (target == 0 && k == 0) {
ans.add(new ArrayList<Integer>(oneResult));
return;
}

if(target < 0 || index >= A.length || k <= 0) {
return;
}

for (int i = index; i < A.length; i ++) {
oneResult.add(A[i]);
dfs(oneResult, i + 1, target – A[i], k – 1, A); //这里i被我写成了index。。。
oneResult.remove(oneResult.size() – 1);
}
}

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: