ARTS （第65周）

认清目标,莫理琐事

Algorithm 算法

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

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

解法1 动态规划

比较简单的动态规划

class Solution {
  	public int maxSubArray(int[] nums) {
		if(nums==null||nums.length==0) return 0;
        int[] dp=new int[nums.length];   // dp[i]表示以nums[i]结尾的最大子序和
        dp[0] = nums[0];
        int maxSum = dp[0]; 
        for (int i = 1; i < nums.length; ++i){
            dp[i] = dp[i-1] > 0? nums[i]+dp[i-1]: nums[i];
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

解法2 分支法

这里的思想就是每个段都求出左半端最长值以中间为起点的最长值右半段的最长值然后比较其中的最大值。

class Solution {
  	public int maxSubArray(int[] nums) {
		if (nums.length == 1)
			return nums[0];
		return maxSubArray_help(nums, 0, nums.length-1);
	}

	int maxSubArray_help(int[] nums, int left, int right) {
		if (left == right)
			return nums[left];
		if (left > right)
			return Integer.MIN_VALUE;
		int mid = (left + right) / 2;
		int leftSum = maxSubArray_help(nums, left, mid - 1);
		int rightSum = maxSubArray_help(nums, mid + 1, right);

		// 计算穿过中间的最大子序和
		int midSumLeft = 0;
		int midSumRight = 0;
		int tmp = 0;
		for (int i = mid - 1; i >= left; --i) {
			tmp += nums[i];
			midSumLeft = Math.max(midSumLeft, tmp);
		}
		tmp = 0;
		for (int i = mid + 1; i <= right; ++i) {
			tmp += nums[i];
			midSumRight = Math.max(midSumRight, tmp);
		}

		return Math.max(Math.max(leftSum, rightSum), midSumLeft + midSumRight + nums[mid]);
	}
}

相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

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

解法递归

class Solution {
     public boolean isSameTree(TreeNode p, TreeNode q) {
		 if (p == null && q == null)
	            return true;
	        else if (p == null || q == null)
	            return false;
	        else
	            return (p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
	    }
}

Review 英文文章

https://spring.io/guides/gs/gateway/

构建gateway

Tip 技巧

IO多路复用

我自己的理解，用通俗的话来讲则是，每一个线程都可以处理多个IO操作。

IO复用：为了解释这个名词，首先来理解下复用这个概念，复用也就是共用的意思，这样理解还是有些抽象，为此，咱们来理解下复用在通信领域的使用，在通信领域中为了充分利用网络连接的物理介质，往往在同一条网络链路上采用时分复用或频分复用的技术使其在同一链路上传输多路信号，到这里我们就基本上理解了复用的含义，即公用某个“介质”来尽可能多的做同一类(性质)的事，那IO复用的“介质”是什么呢？为此我们首先来看看服务器编程的模型，客户端发来的请求服务端会产生一个进程来对其进行服务，每当来一个客户请求就产生一个进程来服务，然而进程不可能无限制的产生，因此为了解决大量客户端访问的问题，引入了IO复用技术，即：一个进程可以同时对多个客户请求进行服务。也就是说IO复用的“介质”是进程(准确的说复用的是select和poll，因为进程也是靠调用select和poll来实现的)，复用一个进程(select和poll)来对多个IO进行服务，虽然客户端发来的IO是并发的但是IO所需的读写数据多数情况下是没有准备好的，因此就可以利用一个函数(select和poll)来监听IO所需的这些数据的状态，一旦IO有数据可以进行读写了，进程就来对这样的IO进行服务。

select，poll，epoll都是IO多路复用的机制，I/O多路复用就是通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知应用程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

作者：可笑的黑耀斑链接：https://www.jianshu.com/p/545eb3403888来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。