ARTS （第37周）

自我感想：BUG的出现，其实很多时候，都是因为分支情况的考虑不够周全。

Algorithm 算法

三角形最小路径和

https://leetcode-cn.com/problems/triangle/

leetcode 120

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 最简单的暴力搜索法

这里采用的是回溯的思路。(提交之后结果和我预料的一样是超时= =)

public int minimumTotal(List<List<Integer>> triangle) {
		if(triangle==null ||triangle.size()==0)
			return 0;
		return minimumTotalHelo(triangle, 0, 0, 0);
	}

	public int minimumTotalHelo(List<List<Integer>> triangle, int cur, int r, int c) {
		if (r >= triangle.size() || c >= triangle.get(r).size()) {
			return cur;
		}
		cur += triangle.get(r).get(c);
		return Math.min(minimumTotalHelo(triangle, cur, r + 1, c), minimumTotalHelo(triangle, cur, r + 1, c + 1));
	}

解法2 动态规划 自底向上的动态规划

这个题目其实只需要考虑底下的两个节点哪个更小即可。很简单的判断。

 	// 执行用时:4 ms,在所有java提交中击败了59.36%的用户
// 内存消耗:37.8 MB,在所有java提交中击败了57.43%的用户
   public int minimumTotal(List<List<Integer>> triangle) {
	if (triangle == null || triangle.size() == 0)
		return 0;
	int size = triangle.size();
	int[] dp = new int[size];
	for (int i = 0; i < size; i++) {
         //最底下一层的初始化
		dp[i] = triangle.get(size - 1).get(i);
	}
	for (int i = triangle.size() - 2; i >= 0; i--) {
		for (int j = 0; j < triangle.get(i).size(); j++) {
			int c = triangle.get(i).get(j);
             //只需要考虑底下的两个节点哪个更小即可
			c +=  Math.min(dp[j], dp[j + 1]);
			dp[j]=c;
		}
		//System.out.println(Arrays.toString(dp));
	}
	return dp[0];

}

解法3 备忘录模式

最初从暴力法自顶部向下进行备忘，然后发现不对，

才发现这种情况 其实也应该由底部向上做备忘，或者初始化好最后一层后再进行备忘

	// 备忘录
	// 执行用时:2 ms,在所有java提交中击败了97.54%的用户
	// 内存消耗:37.2 MB,在所有java提交中击败了76.43%的用户
	Integer[][] minimumTotalHeloMemo = null;// 备忘录
	Integer minimumTotalHeloMemoDefault = null;// 初始值
	public int minimumTotal_mem(List<List<Integer>> triangle) {
		if (triangle == null || triangle.size() == 0)
			return 0;
		// 初始化备忘录
		minimumTotalHeloMemo = new Integer[triangle.size()][];
		for (int i = 0; i < minimumTotalHeloMemo.length; i++) {
			minimumTotalHeloMemo[i] = new Integer[i + 1];
			for (int j = 0; j < minimumTotalHeloMemo[i].length; j++) {
				minimumTotalHeloMemo[i][j] = minimumTotalHeloMemoDefault;// 初始值
			}
		}
		// 初始化最后一行
		for (int i = 0; i < minimumTotalHeloMemo.length; i++) {
			minimumTotalHeloMemo[minimumTotalHeloMemo.length - 1][i] = triangle.get(minimumTotalHeloMemo.length - 1)
					.get(i);
		}
		int v = minimumTotalHelo_mem(triangle, 0, 0);
		return v;
	}

//
public int minimumTotalHelo_mem(List<List<Integer>> triangle, int r, int c) {
		if (minimumTotalHeloMemo[r][c] != minimumTotalHeloMemoDefault) {
			return minimumTotalHeloMemo[r][c];
		}
		int cur = triangle.get(r).get(c);
		int v = cur + Math.min(minimumTotalHelo_mem(triangle, r + 1, c), minimumTotalHelo_mem(triangle, r + 1, c + 1));
		minimumTotalHeloMemo[r][c] = v;
		// printArr(minimumTotalHeloMemo);
		return v;
	}

乘积最大子序列

https://leetcode-cn.com/problems/maximum-product-subarray/

leetcode 152

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1暴力搜索法

双重循环 时间复杂度n^2

结果是毫无意外的超时= =

//暴力搜索
	//超出时间限制
	public int maxProduct(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}
		if (nums.length == 1) {
			return nums[0];
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			for (int j = i ; j < nums.length; j++) {
				int val = nums[i];

				for (int s = i + 1; s <= j; s++) {
					val *= nums[s];
				}

				max = Math.max(max, val);
			}
		}
		return max;
	}

解法2 动态规划

因为需要考虑奇数个负数的情况

所以需要2个DP数组

这里是2种解法 思路是一致的。

// 执行用时:3ms,在所有java提交中击败了53.21%的用户
		// 内存消耗:37.3MB,在所有java提交中击败了38.15%的用户
		public int maxProduct_DP2(int[] nums) {
			if (nums == null || nums.length == 0)
				return 0;
			// 2个DP数组 到每个位置时候，最大和最小的乘积值
			int dpMax = nums[0];
			int dpMin = nums[0];
			int r = nums[0];
			int cMax = 0;
			int cMin = 0;
			for (int i = 1; i < nums.length; i++) {
				// 将当前数字和前一个最大和最小进行相乘
				cMax = nums[i] * dpMax;
				cMin = nums[i] * dpMin;
				// 核心思想：因为有负数的可能性 负负得正 如果之前的数字有负数 当前也是负数 那么就可能负负得正的值更大
				dpMax = Math.max(nums[i], Math.max(cMax, cMin));
				dpMin = Math.min(nums[i], Math.min(cMax, cMin));
				// 取更大的值
				r = Math.max(r, dpMax);
			}
			return r;
		}

		// 执行用时:3ms,在所有java提交中击败了53.21%的用户
		// 内存消耗:37.1MB,在所有java提交中击败了41.30%的用户
		public int maxProduct_dp(int[] nums) {
			if (nums == null || nums.length == 0)
				return 0;
			// 2个DP数组 到每个位置时候，最大和最小的乘积值
			int[] dpMax = new int[nums.length];
			dpMax[0] = nums[0];
			int[] dpMin = new int[nums.length];
			dpMin[0] = nums[0];
			int r = nums[0];
			for (int i = 1; i < nums.length; i++) {
				// 将当前数字和前一个最大和最小进行相乘
				int cMax = nums[i] * dpMax[i - 1];
				int cMin = nums[i] * dpMin[i - 1];
				// 核心思想：因为有负数的可能性 负负得正 如果之前的数字有负数 当前也是负数 那么就可能负负得正的值更大
				dpMax[i] = Math.max(nums[i], Math.max(cMax, cMin));
				dpMin[i] = Math.min(nums[i], Math.min(cMax, cMin));
				// 取更大的值
				r = Math.max(r, dpMax[i]);
			}
			return r;
		}

解法3 分段法

这里将这题的情况分支考虑的话就是如下

这里用0隔开做分段
第1种可能 分段里全是正数 或者有偶数个负数 ->将值全部相乘即可
第2种可能 分段里有奇数个负数
  ->舍弃末尾的奇数 从分段起始位置乘到最后一个奇数前面 情况A
  ->舍弃第一个奇数 第1个奇数后面的数字开始乘到分段末尾 情况B
根据上面的情况就可以写出代码了。

//执行用时:1ms,在所有java提交中击败了100.00%的用户
		//内存消耗:36.6MB,在所有java提交中击败了43.95%的用户
		public int maxProduct_(int[] nums) {
			if (nums == null || nums.length == 0)
				return 0;
			// 用0隔开做分段
			// 第1种可能 分段里全是正数 或者有偶数个负数 ->将值全部相乘即可
			// 第2种可能 分段里有奇数个负数
			// ->舍弃末尾的奇数 从分段起始位置乘到最后一个奇数前面 情况A
			// ->舍弃第一个奇数 第1个奇数后面的数字开始乘到分段末尾 情况B
			int r = nums[0];
			int m = 1;// 初始值 1
			// 情况A的循环
			for (int i = 0; i < nums.length; i++) {
				// 累乘判断
				m = m * nums[i];
				// 这里的max判断 情况如下
				// 1 分段里全是正数 或者有偶数个负数 ->将值全部相乘
				// 2 分段里有奇数个负数 ->舍弃末尾的奇数 从分段起始位置乘到最后一个奇数前面
				// 但是在这里无法考虑到舍弃首个奇数的情况 因此 需要再来一个循环 从后面向前循环即可
				r = Math.max(m, r);
				if (nums[i] == 0) {
					m = 1;// 回归初始值 即新的分段
				}
			}
			m = 1;// 初始值 1
			// 情况B的循环
			for (int i = nums.length-1; i >= 0; i--) {
				// 累乘判断
				m = m * nums[i];
				// 这里的max判断 情况如下
				// 1 分段里全是正数 或者有偶数个负数 ->将值全部相乘
				// 2 分段里有奇数个负数 ->舍弃第一个奇数 第1个奇数后面的数字开始乘到分段末尾
				// 这里的2个循环的逻辑一致 是为了考虑情况A和情况B
				r = Math.max(m, r);
				if (nums[i] == 0) {
					m = 1;// 回归初始值 即新的分段
				}
			}
			return r;
		}

Review 英文文章

https://spring.io/projects/spring-cloud

springcloud 简洁和各个组件的介绍

Tip 技巧

状态码

1 消息
100 Continue
101 Switching Protocols
102 Processing

2 成功
200 OK
201 Created
202 Accepted
203 Non-Authoritative Information
204 No Content
205 Reset Content
206 Partial Content
207 Multi-Status

3 重定向
300 Multiple Choices
301 Moved Permanently
302 Move Temporarily
303 See Other
304 Not Modified
305 Use Proxy
306 Switch Proxy
307 Temporary Redirect

4 请求错误
400 Bad Request
401 Unauthorized
402 Payment Required
403 Forbidden
404 Not Found
405 Method Not Allowed
406 Not Acceptable
407 Proxy Authentication Required
408 Request Timeout
409 Conflict
410 Gone
411 Length Required
412 Precondition Failed
413 Request Entity Too Large
414 Request-URI Too Long
415 Unsupported Media Type
416 Requested Range Not Satisfiable
417 Expectation Failed
418 I’m a teapot
421 Too Many Connections
422 Unprocessable Entity
423 Locked
424 Failed Dependency
425 Too Early
426 Upgrade Required
449 Retry With
451 Unavailable For Legal Reasons

5 服务器错误
500 Internal Server Error
501 Not Implemented
502 Bad Gateway
503 Service Unavailable
504 Gateway Timeout
505 HTTP Version Not Supported
506 Variant Also Negotiates
507 Insufficient Storage
509 Bandwidth Limit Exceeded
510 Not Extended
600 Unparseable Response Headers

Share 分享

因为最近项目可能需要使用vue 就简单的了解了一下。

https://www.jianshu.com/p/bb4a347b903a VueJS简明教程(二)之组件
https://www.jianshu.com/p/5d0d913d2453 VueJS简明教程(一)之基本使用方法

https://www.jianshu.com/p/1a7bbdd8ca4e 三十分钟学会使用VUE搭建单页应用(SPA) 上

https://www.jianshu.com/p/47a207618cbd 三十分钟学会使用VUE搭建单页应用(SPA) 下

知识储备：

https://blog.csdn.net/huoji555/article/details/79595533 JAVA百度OCR的调用