2020_java蓝桥_暑假训练_分治与动态规划

发表于 | 分类于 ， | 热度: ℃
字数统计: 3.2k | 阅读时长 ≈ 14

🌸分治与动态规划训练

贴在前面，想了解什么是分治，可查看我的这篇文章二分查找

🍁有序列表搜索位置

已知有序的序列,比如：
2,3,3,5,9,9,9,12,12,13,15,22,22,22,22,23,25,25,91,95
有整数x，比如： x=23
要求找到一个刚好比x稍微大一点的元素位置

当数组较大的时候，需要二分查找加快速度。

🍂分析

一看此题，直接暴力（不要求复杂度的话），题中说明利用二分查找，就直接二分模板上吧

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
public class Location_Search {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
//		int n = input.nextInt();
//		int[] a = new int[n];
//		for(int i = 0; i < a.length; i++) {
//			a[i] = input.nextInt();
//		}
		int x = input.nextInt();
		System.out.println(search(new int[]{2,3,3,5,9,9,9,12,12,13,15,22,22,22,22,23,25,25,91,95}, x));
		input.close();

	}

	private static int search(int[] a, int x) {
		// TODO Auto-generated method stub
		int left = 0;
		int right = a.length - 1;
		while(left < right) {
			int mid = left + (right - left) / 2; //寻找中位数
			if(x >= a[mid]) {//中位数比目标值小或者等于，显然目标值的位置在右边，下一段搜索[mid + 1, right]
				left = mid + 1;
			}else {//同理
				right = mid;
			}
		}
		return left;
	}
}

🍁最大子序和

数组中整数有正有负

求一连续子段，使得和最大化

例如：

2,4,-7,5,2,-1,2,-4,3

最大连续段：

5,2,-1,2

其最大和为8

🍂分析

💥暴力

解题一步一步的来，首先先写好暴力解法，双层循环遍历判断最大和

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
public class Max_sum_of_subsequences {
	public static void main(String[] args) {
		//int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int[] nums = {2,4,-7,5,2,-1,2,-4,3};
		System.out.println(maxSubArray(nums));
	}
	private static int maxSubArray(int[] nums) {
		int res = Integer.MIN_VALUE;
		for(int i = 0; i < nums.length; i++) {
			for(int j = 0; j <= i; j++) {
				int sum = sumOfArray(nums, j, i);
				res = Math.max(res, sum);
			}
		}
		return res;
	}
    private static int sumOfArray(int[] nums, int left, int right) {
		// TODO Auto-generated method stub
		int sum = 0;
		for(int i = left; i <= right; i++) {
			sum += nums[i];
		}
		return sum;
	}
}
💥暴力优化

优化：事实上，上面的代码有一些重复计算。这是因为相同前缀的区间求和，可以通过类似“状态转移”的方法得到。

例如：计算子区间 [1, 4] 的和可以在计算子区间 [1, 3] 的基础上，再加上 nums[4] 得到。 因此，只需要枚举子序的左端点，然后再扫描右端点，就可以减少一个级别的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Max_sum_of_subsequences {
	public static void main(String[] args) {
		//int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int[] nums = {2,4,-7,5,2,-1,2,-4,3};
		System.out.println(maxSubArray1(nums));
	}
	private static int maxSubArray1(int[] nums) {
		int res = Integer.MIN_VALUE;
		for(int i = 0; i < nums.length; i++) {
			int sum = 0;
			for(int j = i; j < nums.length; j++) {
				sum += nums[j];
				res = Math.max(sum, res);
			}
		}
		return res;
	}
}
💥动态规划

  • 第 1 步：定义状态 既然一个连续子数组一定要以一个数作为结尾，那么我们就将状态定义成如下。

    • dp[i]：表示以 nums[i] 结尾的连续子数组的最大和。

  • 那么为什么这么定义呢？这是因为这样定义状态转移方程容易得到。

    • 第2 步：思考状态转移方程 根据状态的定义，由于 nums[i] 一定会被选取，并且 dp[i] 所表示的连续子序列与 dp[i - 1]所表示的连续子序列（有可能）就差一个 nums[i] 。假设数组 nums 全是正数，那么一定有 dp[i] = dp[i - 1] + nums[i]。

    在一般情况下 dp[i - 1] 有可能是负数，例如前几个数都是负数，突然来了一个正数。

    • 于是分类讨论：

  • 如果 dp[i - 1] >= 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面。

  • 如果 dp[i - 1] < 0，那么加上前面的数反而越来越小了，于是“另起炉灶”，单独的一个 nums[i]，就是 dp[i]。

  • 以上两种情况的最大值就是 dp[i] 的值，写出如下状态转移方程：

    1
    2
    3
    dp[i] = dp[i - 1] + nums[i],  if dp[i - 1] >= 0 

    dp[i] = nums[i],  if  dp[i - 1] < 0
  • 记为“状态转移方程 1”。
  • 状态转移方程还可以这样写，反正求的是最大值，也不用分类讨论了，就这两种情况，取最大即可（即贪心思想，使每一步都能达到最优解），因此还可以写出状态转移方程如下：
1
dp[i] = max{nums[i], dp[i - 1] + nums[i]}

  • 记为“状态转移方程 2”。

  • 动态规划的问题经常要分类讨论，这是因为动态规划的问题本来就有最优子结构的特征，即大问题的最优解通常由小问题的最优解得到，那么我们就需要通过分类讨论，得到大问题的小问题究竟是哪些。

  • 第 3 步：思考初始值 dp[0] 根据定义，一定以 nums[0] 结尾，因此 dp[0] = nums[0]。
  • 第 4 步：思考输出 这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去。
  • 输出应该是把所有的 dp[0]、dp[1]、……、dp[n - 1] 都看一遍，取最大值。

状态方程一代码：

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
public class Max_sum_of_subsequences {
	public static void main(String[] args) {
		//int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int[] nums = {2,4,-7,5,2,-1,2,-4,3};
		System.out.println(maxSubArray2(nums));

	}
	private static int maxSubArray2(int[] nums) {
		int len = nums.length;
		if(len == 0) {
			return 0;
		}
		int[] dp = new int[len];
		dp[0] = nums[0];
		
		for(int i = 1; i < len; i++) {
			if(dp[i - 1] >= 0) {
				dp[i] = dp[i - 1] + nums[i];
			}else {
				dp[i] = nums[i];
			}
		}
		//最后寻找最大值
		int res = dp[0];
		for(int i = 1; i < len; i++) {
			res = Math.max(res, dp[i]);
		}
		return res;
	}
}

💥状态方程2（贪心解法）

贪心 使用单个数组作为输入来查找最大（或最小）元素（或总和）的问题，

贪心算法是可以在线性时间解决的方法之一。

每一步都选择最佳方案，到最后就是全局最优的方案。 

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
public class Max_sum_of_subsequences {
	public static void main(String[] args) {
		//int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int[] nums = {2,4,-7,5,2,-1,2,-4,3};
		System.out.println(maxSubArray3(nums));
        System.out.println(maxSubArray4(nums));

	}
	private static int maxSubArray3(int[] nums) {
		int len = nums.length;
		if(len == 0) {
			return 0;
		}
		int[] dp = new int[len];
		dp[0] = nums[0];
		
		for(int i = 1; i < len; i++) {
			dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
		}
		int res = dp[0];
		for(int i = 1; i < len; i++) {
			res = Math.max(res, dp[i]);
		}
		return res;
	}
	private static int maxSubArray4(int[] nums) {
		int len = nums.length;
		if(len == 0) {
			return 0;
		}
		int pre = nums[0]; // 代表上一个状态的值
		int res = pre;
		
		for(int i = 1; i < len; i++) {
			pre = Math.max(pre + nums[i], nums[i]);
			res = Math.max(res, pre);
		}
		return res;
	}
}
💥分治

这个是使用分治法解决问题的典型的例子，并且可以用与合并排序相似的算法求解。

分治法的思路是这样的，其实也是分类讨论。 将问题分解为子问题并递归地解决它们。 合并子问题的解以获得原始问题的解

连续子序列的最大和主要由这三部分子区间里元素的最大和得到：

  • 第 1 部分：子区间 [left, mid]；

  • 第 2 部分：子区间 [mid + 1, right]；

  • 第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。

    对它们三者求最大值即可。

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
public class Max_sum_of_subsequences {
	public static void main(String[] args) {
		//int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int[] nums = {2,4,-7,5,2,-1,2,-4,3};
        System.out.println(maxSubArray5(nums));

	}
	private static int maxSubArray5(int[] nums) {
		int len = nums.length;
		if(len == 0) {
			return 0;
		}
		
		return maxSubArraySum(nums, 0, len - 1);
	}
	private static int maxSubArraySum(int[] nums, int left, int right) {
		// TODO Auto-generated method stub
		if(left == right) {
			return nums[left];
		}
		int mid = (left + right) >>> 1;
		return max3(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid + 1, right), maxCrossingSum(nums, left, mid, right));
	}
	private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
		// TODO Auto-generated method stub
		//一定会包含nums[mid]这个元素
		int sum = 0;
		int leftSum = Integer.MIN_VALUE;
		//左半边包含nums[mid]元素，最多可以到什么地方
		//走到最边界，看看最值是什么
		//计算一mid结尾的最大的子数组的和
		for(int i = mid; i >= left; i--) {
			sum += nums[i];
			if(sum > leftSum) {
				leftSum = sum;
			}
		}
		sum = 0;
		int rightSum = Integer.MIN_VALUE;
		//右半边不包含nums[mid]元素，最多可以到什么地方
		//计算以mid+1开始的最大的子数组的和
		for(int i = mid + 1; i <= right; i++) {
			sum += nums[i];
			if(sum > rightSum) {
				rightSum = sum;
			}
		}
		return leftSum + rightSum;
	}
	private static int max3(int n1, int n2, int n3) {
		return Math.max(n1, Math.max(n2, n3));
	}
}

注：

  • 此分治解法需要仔细推磨想想原理

🍁大数相乘

用串的形式表示大数的乘法。
即求类似：
“23234845847839461464158174814792” * “6457847285617487843234535”
要求结果返回一个串。

🍂分析

这道题既然写在分治里，那必然跟分治脱不了干系，当然一开始也还是想不到分治是怎么分治的（确实好难）。所谓万物皆暴力，一切能暴力出来就先暴力出来，在进行一步步优化升级。好在这道题没有要求不能使用乘法，要是那样的话就整个人都不好了

💥利用大数类BigDecimal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class String_Multiple {
	public static void main(String[] args) {
		System.out.println(multiply("23234845847839461464158174814792", "6457847285617487843234535"));
	}
	/**
	 * 利用大数类
	 * @param num1
	 * @param num2
	 * @return
	 */
	private static String multiply(String num1, String num2) {
		return new BigDecimal(num1).multiply(new BigDecimal(num2)).toString();
	}
}
💥模拟人工乘法

人工乘法在座的各位没有谁不会吧？？？手写的过程利用计算机去一步步实现罢了（对于大数不建议使用，复杂度较高）

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
public class String_Multiple {
	public static void main(String[] args) {
		System.out.println(multiply1("23234845847839461464158174814792", "6457847285617487843234535"));
	}
	private static String multiply1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        // 保存计算结果
        String res = "0";
        
        // num2 逐位与 num1 相乘
        for (int i = num2.length() - 1; i >= 0; i--) {
            int carry = 0;
            // 保存 num2 第i位数字与 num1 相乘的结果
            StringBuilder temp = new StringBuilder();
            // 补 0 
            for (int j = 0; j < num2.length() - 1 - i; j++) {
                temp.append(0);
            }
            int n2 = num2.charAt(i) - '0';
            
            // num2 的第 i 位数字 n2 与 num1 相乘
            for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) {
                int n1 = j < 0 ? 0 : num1.charAt(j) - '0';
                int product = (n1 * n2 + carry) % 10;
                temp.append(product);
                carry = (n1 * n2 + carry) / 10;
            }
            // 将当前结果与新计算的结果求和作为新的结果
            res = addStrings(res, temp.reverse().toString());
        }
        return res;
	}
    /**
     * 对两个字符串数字进行相加，返回字符串形式的和
     */
    private static String addStrings(String num1, String num2) {
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        for (int i = num1.length() - 1, j = num2.length() - 1;
             i >= 0 || j >= 0 || carry != 0;
             i--, j--) {
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            int sum = (x + y + carry) % 10;
            builder.append(sum);
            carry = (x + y + carry) / 10;
        }
        return builder.reverse().toString();
    }
}
💥分治

对于大整数的乘法，我们可以利用分治法将其两个字符串从中间截断，将两字符串的后半部分，进行相乘

子串a1和子串a2，然后结果就是a1+0…000+a2。递归的边界条件就是当每个子串的长度都小于等于4的时候，就可以通过直接乘法运算返回结果。

大数乘法中必须用到大数加法（这里不用上面已经实现的字符串相加函数），而大数加法的思路和大数乘法也是大同小异的，将串a和串b的末尾都切出一段长度为8的子串出来，a从左到右子串分别是a1和a2，b亦然。之后就是考虑t=a2+b2的不同情况，有可能t.size<8，那么这个时候我们就要通过补0的方式)凑够8位。

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
public class String_Multiple {
	public static void main(String[] args) {
		System.out.println(multiply2("23234845847839461464158174814792", "6457847285617487843234535"));
	}
    private static String multiply2(String num1, String num2) {
    	if(num1.length() <= 4 && num2.length() <= 4) {
    		return Integer.parseInt(num1) * Integer.parseInt(num2) + "";
    	}
    	if(num1.length() > 4) {
    		int mid = num1.length() / 2;
    		String s1 = num1.substring(0, mid);
    		String s2 = num1.substring(mid);
    		return add(multiply2(s1, num2) + add_zero(s2.length()), multiply2(s2, num2));
    	}
    	return multiply2(num2, num1);
    }
    //补0
    private static String add_zero(int x) {
    	if(x == 0) {
    		return "";
    	}
    	if(x == 1) {
    		return "0";
    	}
    	return add_zero(x / 2) + add_zero(x / 2) + add_zero(x % 2);
    }
    /**
    *大数相加
    */
    private static String add(String num1, String num2) {
    	if(num1.length() <= 8 && num2.length() <= 8) {
    		return Integer.parseInt(num1) + Integer.parseInt(num2) + "";
    	}
    	String a1 = "0";
    	String a2 = num1;
    	if(num1.length() > 8) { //将num1的低八位分离
    		a1 = num1.substring(0, num1.length() - 8);
    		a2 = num1.substring(num1.length() - 8);
    	}
    	String b1 = "0";
    	String b2 = num2;
    	if(num2.length() > 8) {
    		b1 = num2.substring(0, num2.length() - 8);
    		b2 = num2.substring(num2.length() - 8);
    	}
    	String k = add(a2, b2);
    	if(k.length() > 8) {
    		return add(add(a1, b1), "1") + k.substring(1);
    	}
    	if(k.length() < 8) {
    		return add(a1, b1) + add_zero(8 - k.length()) + k;
    	}
    	return add(a1, b1) + k;
    }
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%