LeetCode每日一题环形子数组的最大和 （中等）
考察动态规划,重点关注动态规划思想和代码实现。
total += nums[i]
currMax = max(currMax+nums[i], nums[i])
maxSum = max(maxSum, currMax)
题目描述：
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i – 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例
- 示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
- 示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
- 示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
解题思路
最开始的时候，思路：遍历num数组，获取最大的数，从此数开始。然后向左右俩边辐射，若是正数，直接相加。若是负数，则继续向左右俩边遍历。
然后代码写如下
func maxSubarraySumCircular(nums []int) int {
max := 0
index := 0
leng := len(nums)
for i:=0 ; i < leng ; i++{
if max < nums[i]{
max = nums[i]
index := i
}
}//找最大值，以及其所对应得下标
if nums[(index+1)%n] >0 {
max = max+ nums[(index+1)%n]
}
if nums[(index-1)%n] >0 {
max = max+ nums[(index-1)%n]
}//左右俩边大于0 ，就将其加入max中
//如果小于0，也不能直接舍弃，还要判断该负数的下一个是不是正数且大于该负数的绝对值。
//有个问题，如是不是应该全部用循环来遍历整个数组。
//不能这么做了，因为你不知道到底是不是满足大于0,。
//要不使用昨天的方法，
if nums[(index+1)%n] <=0 {
for k := 0 ; k < leng -1 ;k++{
k = (k+ index +1)%n//这个是负数的下标
}
}
}
很明显，由于你不确定到底后续还能不能获得一个大于0的数，所以这种方法肯定不可以。
然后换一种方法，能不能像昨天的题目一样，将数组中的每个数都差一个下标。然后进行排序。
如果这样做，思路就是：先将其从大到小排序？（坏，好像不一定从大的数开始就是正确的 ，比如 -7 7 -8 -9 1 2 -7这样，明显不能把-7包进去）
所以说，唔，还是先按从大到小排。然后读第一个数的时候，将其左右两边的数同加直到碰到下一个正数，
官方解答 （动态规划）
这题一共有两种情况
下面的这个子数组指最大和的子数组
第一种情况：这个子数组不是环状的，就是说首尾不相连。
第二种情况：这个子数组一部分在首部，一部分在尾部，我们可以将这第二种情况转换成第一种情况
如下图：
所以这最大的环形子数组和 = max(最大子数组和，数组总和-最小子数组和)
证明
证明一下第二种情况（最大子数组是环形的）
max(前缀数组+后缀数组)
= max(数组总和 – subarray) subarray指的是前缀数组和后缀数组中间的数组
= 数组总和 + max(-subarray) 数组总和是不变的，直接提出来
= 数组总和 – min(subarry) 。。。这个都懂吧，把负号提出来，max变成min
极端情况：如果说这数组的所有数都是负数，那么上面的公式还需要变一下，因为这种情况，对于上面的第一种情况sum会等于数组中的最大值，而对二种情况sum=0（最小的子数组就是本数组，total-total=0）。所以多加一个case，判断最大子数组和是否小于0，小于0，直接返回该maxSubArray
代码如下：
func maxSubarraySumCircular(nums []int) int {
total, maxSum, minSum, currMax, currMin := nums[0], nums[0], nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
total += nums[i]
currMax = max(currMax+nums[i], nums[i])
maxSum = max(maxSum, currMax)
currMin = min(currMin+nums[i], nums[i])
minSum = min(minSum, currMin)
}
//等价于if maxSum < 0
if total == minSum {
return maxSum
} else {
return max(maxSum, total - minSum)
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
作者：xing-you-ji
链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/solution/wo-hua-yi-bian-jiu-kan-dong-de-ti-jie-ni-892u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码解释
for i := 1; i < len(nums); i++ {
total += nums[i]
currMax = max(currMax+nums[i], nums[i])
maxSum = max(maxSum, currMax)
currMin = min(currMin+nums[i], nums[i])
minSum = min(minSum, currMin)
}
这段代码是使用Go语言编写的用于查找一个整数数组nums中的最大子数组和和最小子数组和的算法。代码使用了动态规划的思想来逐步更新当前的最大子数组和maxSum、当前的最小子数组和minSum、当前最大子数组和的累加值currMax和当前最小子数组和的累加值currMin。
（这一块代码是核心，动态规划来更新大小，如果我写的话，应该不会关注min的取值，只会写前三行，也就是我考虑的第二种情况是把他当成第一种情况相同，前面证明的变形太细了！）
if total == minSum
这是一个条件判断语句，用于检查数组的总和total是否等于最小子数组和minSum。
如果数组的总和等于最小子数组和，那么这意味着数组中的所有元素都是非正数（负数或零），
因为minSum是最小子数组和，而total是整个数组的总和。在这种情况下，数组中没有正数，因为如果有正数，将其加入到子数组和中，将会使得子数组和变得更大，而这与minSum相等是矛盾的。
LeetCode面试经典150题第4题：删除有序数组中的重复项 II（中等）
题目描述：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例
- 示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
- 示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素
解题思路
由于此题数组内已经按大小排序了，所以只需要设立一个检测量signal，然后去判断重复数是否超过2个即可。
唯一需要注意的点是，不能新建一个数组去存储，而是要在原有的数组上进行操作！
没有啥需要注意的，感觉像简单难度。
代码如下：
//此题数组内已经按大小排序了，所以只需要设立一个检测量signal=2，然后去判断重复数是否超过2个
func removeDuplicates(nums []int) int {
leng := len(nums)
signal := 1
j :=2
for i:=2 ; i< len(nums) ; i++{
if nums[i] == nums[j-1] && nums[i]==nums[j-2]{
signal =0
}
if signal ==0{
leng--
}else{
nums[j]= nums[i]
j++
}
signal = 1
}
return leng
}
我的解法，其实使用于较小位，如果保留k位，且k很大，我肯定不能列举完。
官方解答（双指针）
通用解法
为了让解法更具有一般性，我们将原问题的「保留 2 位」修改为「保留 k 位」。
因为给定数组是有序的，所以相同元素必然连续。我们可以使用双指针解决本题，遍历数组检查每一个元素是否应该被保留，如果应该被保留，就将其移动到指定位置。
具体地，我们定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即 nums[fast] 表示待检查的第一个元素，nums[slow−1] 为上一个应该被保留的元素所移动到的指定位置。
因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2] 是否和当前待检查元素 nums[fast] 相同。当且仅当 nums[slow−2]=nums[fast] 时，当前待检查元素nums[fast] 不应该被保留（因为此时必然有
nums[slow−2]=nums[slow−1]=nums[fast]）。最后，slow即为处理好的数组的长度。
特别地，数组的前两个数必然可以被保留，因此对于长度不超过 2 的数组，我们无需进行任何处理，对于长度超过 2的数组，我们直接将双指针的初始值设为 2 即可。
如果是保留k位nums[slow-2] != nums[fast]将2改为k即可。同时初值也跟着改。
func removeDuplicates(nums []int) int {
n := len(nums)
if n <= 2 {
return n
}
slow, fast := 2, 2
for fast < n {
if nums[slow-2] != nums[fast] {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-yec2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
唔，还是写复杂了很多，悲
正反向代理
docker搭建haproxy 四层代理，同时3个后端web服务器，暴露8000端口，做负载均衡，后端服务器采用RR的方式，任意一个Sever挂掉，不影响8000端口宿主机的访问
1.创建一个 Docker Compose 文件来定义 HAProxy 和三个后端 Web 服务器容器。我们将使用 Docker Hub 中的 haproxy 映像和 nginx 等简单 Web 服务器的三个实例来进行演示。docker-compose文件如下
services:
haproxy:
image: haproxy:latest
ports:
- "8000:8000"
volumes:
- ./haproxy.cfg:/usr/local/etc/haproxy/haproxy.cfg
networks:
- proxy_network
backend1:
image: python:3
command: python -m http.server 80
networks:
- proxy_network
backend2:
image: python:3
command: python -m http.server 80
networks:
- proxy_network
backend3:
image: python:3
command: python -m http.server 80
networks:
- proxy_network
networks:
proxy_network:
2.haproxy.cfg 如下
daemon
maxconn 256
defaults
mode tcp
timeout connect 5000ms
timeout client 50000ms
timeout server 50000ms
frontend http-in
bind *:8000
default_backend backend_servers
backend backend_servers
mode tcp
balance roundrobin
server backend1 backend1:80 check
server backend2 backend2:80 check
server backend3 backend3:80 check
