字符串子序列 & 数组的和

发表于 | 分类于

题目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
> >