Skip to content

Latest commit

 

History

History
181 lines (145 loc) · 4.36 KB

arts-0006.md

File metadata and controls

181 lines (145 loc) · 4.36 KB

1.Algorithm

[4]  Median of Two Sorted Arrays

Hard    Array    Binary Search    Divide and Conquer

Given two sorted arrays nums1 and nums2 of size m and n respectively. Return the median of the two sorted arrays. Follow up: The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

解答 本题可以采用常规的方法和基于 hashtab 的方式进行处理(题目描述中已经定义不存在重复的数据)

(1).借助 hash 进行快速查找，避免双层 for 循环搜索，时间复杂度 O(n)
func lengthOfLongestSubstring(s string) int {
	count, begin := 0, 0
	hash := make(map[string]int)
	for i := 0; i < len(s); {
		val := string(s[i])
		if index, ok := hash[val]; ok {
			// 算起始位置
			if (i - begin) > count {
				count = i - begin
			}
			// 有2种方式处理，清空hash，重新从begin遍历，或者删除begin之前的在map中的值
			hash = make(map[string]int)
			begin, i = index+1, index+1
		} else {
			// 最后一位
			if i == len(s)-1 && (i-begin+1) > count {
				count = i - begin + 1
			}
			hash[val] = i
			i++
		}
	}
	return count
}
(2).对方法 1 进行了简化，滑动窗口，双指方式进行遍历，时间复杂度：O(2n)=O(n), 空间复杂度：O(min(m,n))
func lengthOfLongestSubstring2(s string) int {
	hash, length := make(map[byte]bool), len(s)
	begin, end, maxCount := 0, 0, 0
	for begin < length && end < length {
		// c := int(s[end] - 'a')
		c := s[end]
		if hash[c] {
			hash[s[begin]] = false
			begin++
		} else {
			hash[c] = true
			end++
			count := end - begin
			if count > maxCount {
				maxCount = count
			}
		}
	}
	return maxCount
}
(3).对方法 2 的滑动窗口方式进行优化
// if s[j] have a duplicate in the range [i, j) with index j' , we don't need to increase i little by little. We can skip all the elements in the range [i, j'] and let i to be j' + 1 directly.

func lengthOfLongestSubstring3(s string) int {
	hash, maxCount := make(map[byte]int), 0
	for begin, end := 0, 0; end < len(s); end++ {
		if index, ok := hash[s[end]]; ok { // check duplicate character, and skip to next index
			if index > begin { // test case: tmmzuxt
				begin = index
			}
		}
		count := end - begin + 1
		if count > maxCount {
			maxCount = count
		}
		hash[s[end]] = end + 1
	}
	return maxCount
}
(4).方法 3 的 C 语言版本
extern inline int max(int a, int b)
{
	return a > b ? a : b;
}

int lengthOfLongestSubstring(char *s)
{
	int hash[128] = {0};
	int maxCount = 0;
	int begin = 0;
	char ch;
	for (int i = 0; (ch = s[i]) != 0; i++)
	{
		begin = max(hash[ch], begin);
		maxCount = max(maxCount, i - begin + 1);
		hash[ch] = i + 1;
	}
	return maxCount;
}

2.Review

Why 0.1+0.2 != 0.3 IEEE 754 standard, float point number cannot be accurately represented according to IEEE 754 because:

  • No enough memory is allocated for representing the number
  • It needs a range to ensure the accuracy

IEEE Standard 754 Floating Point Numbers

How to break a Monolith into Microservices

  • Warm Up with a Simple and Fairly Decoupled Capability
  • Minimize Dependency Back to the Monolith
  • Split Sticky Capabilities Early
  • Decouple Vertically and Release the Data Early
  • Decouple What is Important to the Business and Changes Frequently
  • Decouple Capability and not Code
  • Go Macro First, then Micro
  • Migrate in Atomic Evolutionary Steps

3.Tip

todo: ThreadLocal 解析原理相关文章

4.Share

Microservices, martin flower 有关微服务的一篇基础文章