[关闭]
@natsumi 2017-03-24T03:21:49.000000Z 字数 1076 阅读 850

无重复的数组分割方法

Algorithms


一个数组nums,每个元素都在1~9中的一个整数,将数组分成若干段,要求每段都没有重复的元素。(ps。可以不分或者再不必要分的地方瞎比分~满足要求即可)
给定数组长度n和数组nums,求分段方法有多少种。

思路

假设已知cut(n-1,nums),cut(n-2,nums)...cut(1,nums),也就是nums的前个(注意是前x个不是任意x个,分段的方法有多少中不止和数组长度有关)元素的分割方法有多少种,求cut(n,nums)就相对容易了。其实就是

cut(n,nums)=cut(n-1,nums)[最后1个不切]+cut(n-2,nums)[最后2个不切]+cut(n-3,nums)[最后3个不切]+...+cut(n-9,nums)[最后9个不切]+1[全部都不切]

所以我们只要从cut(3,nums)算起,然后一个一个增加元素,直到cut(n,nums)。不要忘了如果所有元素不同可以完全不切。

不切割的段要保证没有重复,所以一共九个颜色,至多9个一段,10个一段必会重复。而小于9的情况需要我们自己代码判断。如果最后5个出现重复,那么最后5、6、7、8、9个都会有重复,不可能不切割,无需重复判断。

另外在整个过程中需要注意下标不要越界。注意n<9的情况。

代码

  1. public class Solution {
  2. public int cut(int n, int[] nums) {
  3. //flag[i]表示nums的前i+1个元素组成的数组有多少种分段方法
  4. int[] flag = new int[n];
  5. flag[0] = 1;
  6. flag[1] = 2;
  7. for (int i = 2; i < n; i++) {
  8. boolean[] markSame = new boolean[9];
  9. int j;
  10. for (j = 0; j < i && j < 9; j++) {
  11. if (markSame[nums[i - j] - 1]) {
  12. break;
  13. } else {
  14. flag[i] += flag[i - j - 1];
  15. System.out.println("flag[i] = " + flag[i] + " " + "j = " + j);
  16. }
  17. }
  18. if (j == i) {//全部i个元素没有出现重复
  19. //那么还有一种切法是整个都不切
  20. flag[i]++;
  21. }
  22. }
  23. return flag[n - 1];
  24. }
  25. public static void main(String[] args) {
  26. Solution sol = new Solution();
  27. int n = 3;
  28. int[] nums = new int[]{1, 2, 3};
  29. System.out.println(sol.cut(n, nums));
  30. }
  31. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注