ARTS-WEEK10

#ARTS #Leetcode

本周ARTS

本周ARTS打卡内容：

Algorithm 来源 LeetCode26，LeetCode27，LeetCode28，LeetCode29
Review 分享 WHAT IS IDEMPOTENCE?
Tip 分享五种服务发现的对比
Share 分享一致性Hash算法

Algorithm

LeetCode26

移除排序数组中的重复数字：

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

解法：

定义两个整数i，j表示数组a的序列，i初始值为0，j从i+1开始依次增加，如果a[i]!=a[j]，则表示数字不重复，i加1，否则数字重复，i不增加，最后返回i的值即为数组长度，代码如下：

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var  i int
	for k := 1; k <len(nums); k++ {
		if nums[k] != nums[i] {
			i++
			nums[i] = nums[k]
		}
	}

	return i+1
}

LeetCode27

移除元素：

https://leetcode.com/problems/remove-element/

对于给定数据a，和给定数组value，从数组a中移除所有的value，要求空间复杂度为O(1)

解法：

空间复杂度为O(1)，也就是不能新建一个数组，只能在当前数组上进行修改。延续之前26题的思路，定义两个整数i，j表示数组a的序列，i，j初始值为0，j依次增加，如果a[j]!=value，则表示数字不需要去掉，a[i]=a[j]，同时i，j同时增加，否则，该数字需要去掉，j增加，i不变，代码如下：

func removeElement(nums []int, val int) int {
	l := len(nums)
	if l == 0 {
		return 0
	}
	var i int
	for k:=0; k < l; k++ {
		if nums[k] != val {
			nums[i] = nums[k]
			i++
		}
	}
	return i
}

LeetCode28

实现strStc()：

https://leetcode.com/problems/implement-strstr/

给定字符串haystack和needle，返回needle在haystack中的位置，若haystack中不包含needle则返回-1

解法：

轮询haystack的每个元素，判断其是否等于needle的第一个元素，不等则下一个元素，相等再则依次比较后续的每个元素，实现如下：

func strStr(haystack string, needle string) int {
    l := len(haystack)
	n := len(needle)
    if n == 0 {
		return 0
	}
	if l == 0 || l < n {
		return -1
	}
	for i:=0;i<l-n+1;i++{
		if haystack[i] == needle[0] {
			j:=0
			for ;j<n;j++{
				if haystack[i+j] != needle[j] {
					break
				}
			}
			if j == n {
				return i
			}
		}
	}
	return -1
}

LeetCode29

两个整数相除：

https://leetcode.com/problems/divide-two-integers/

给定两个整数dividend和divisor，不使用乘法、除法、取模操作，计算出这两个数的商。

解法：

不使用除法，可以考虑使用减法，先判断整数是否同号，再取绝对值进行计算。使用for循环，将||dividend||减到小于||divisor||，循环的次数即为我们需要的结果。对于dividend等于MaxInt32，divisor等于1的情况，需要MaxInt32的循环次数，时间太长，可以考虑优化for循环，每次循环后将divisor加倍:

func divide(dividend int, divisor int) int {
	var ret, nege int
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	if dividend == 0 {
		return 0
	}
	if dividend * divisor > 0 {
		nege = 1
	} else {
		nege = -1
	}
	dv1 := absolute(dividend)
	dv2 := absolute(divisor)
	for dv1 >= dv2 {
		i := 1
		for dv1 >= i * dv2 {
			dv1 = dv1 - i * dv2
			ret+=i
			i++
		}
	}
	return nege * ret
}

func absolute(i int) int{
	if i < 0 {
		return i * (-1)
	}
	return i
}

Review

本周内容： WHAT IS IDEMPOTENCE?

本文主要介绍了幂等。幂等意味着重复操作不会产生影响。就像按电梯的按钮，按两次并不会叫来两辆电梯。分布式系统中特别强调幂等，因为信号可能丢失，就会需要安全的重复发信号。

要实现幂等，首先在请求中需要加入标识，其次使用具有幂等操作的数据结构，比如set，当我们把key、value加两次时，不会有影响，就像一个数加上0一样。以邮件程序发送为例，我们可以查询set是否含有该ID，没有，我们发送出邮件，并将ID写入set，若set中有，说明已经发送过。

Tip

几种服务发现应用的对比：
Feature | Consul | zookeeper | etcd | euerka
—|—|—|—|—
服务健康检查 | 服务状态，内存，硬盘等 | (弱)长连接，keepalive | 连接心跳 | 可配支持
多数据中心 | 支持 | — | — | —
kv存储服务 | 支持 | 支持 | 支持 | —
一致性 | raft | paxos | raft | —
cap | cp | cp | cp | ap
使用接口(多语言能力) | 支持http和dns | 客户端 | http/grpc | http（sidecar）
watch支持 | 全量/支持long polling | 支持 | 支持 | long polling | 支持 long polling/大部分增量
自身监控 | metrics | — | metrics | metrics
安全 | acl /https | acl | https支持（弱） | —
spring cloud集成 | 已支持 | 已支持 | 已支持 | 已支持

一致性Hash算法：

https://www.cnblogs.com/lpfuture/p/5796398.html