字符串子序列 & 数组的和

题目1:字符串子序列(算法课第八课)

求一个字符串的全部子序列。

思路

不是子字符串。

对于每一个位置,都有要和不要的两种情况,最后是一个树状的图。

子序列不包含 当前字符

  1. i作为String进行的哪里的做坐标,加1
  2. res 保持原来的值

printAllSubsquence(chs,i+1,res)

子序列包含 当前字符

  1. i作为String进行的哪里的做坐标,加1
  2. res 加上当前字符

printAllSubsquence(chs,i+1,res+chs[i])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class PrintAllSubsquences{
public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
printAllSubsquence(chs, 0,"");
}

public static void printAllSubsquence(char[] chs,int i,String res) {
if(i==chs.length) {
System.out.println(res);
return;
}
printAllSubsquence(chs,i+1,res);
printAllSubsquence(chs,i+1,res+chs[i]);
}

public static void main(String[] args) {
String test = "abc";
printAllSubsquence(test);
}
}

输出:(空字符串也是其子序列)

1
2
3
4
5
6
7
8

c
b
bc
a
ac
ab
abc

题目2:数组的和(算法课第八课)

给你一个数组arr,和一个整数aim。如果可以任意选择arr中的数字,能不能累加得到aim,返回true或者false

分析

每个数组位置的元素,都有选和不选两种情况。

没有累加i位置的元素

  1. i作为数组进行的哪里的做坐标,加1
  2. sum 保持原来的值

isSum(arr, i + 1, sum, aim)

累加了i位置的元素

  1. i作为数组进行的哪里的做坐标,加1
  2. sum 加上当前的 数组值

isSum(arr, i + 1, sum + arr[i], aim)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public class IsSum {
public static void main(String[] args) {
int[] arr = new int[] { 1, 4, 8 };
System.out.println(isSum(arr, 0, 0, 12));
}

public static boolean isSum(int[] arr, int i, int sum, int aim) {
if (i == arr.length) {
return sum == aim;
}
return isSum(arr, i + 1, sum, aim) || isSum(arr, i + 1, sum + arr[i], aim);
}
}

输出:

1
true
> >