题目

原题在此
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 $\leq$ Node.val $\leq$ 9
• It is guaranteed that the list represents a number that does not have leading zeros.

解析

没啥好讲的, 按照题意做就好. 就相加, 进位.

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int val = 0;
        ListNode* holder = new ListNode(0);
        ListNode* onWork = holder;
        
        while(l1 || l2 || val){
            val += (l1 ? l1->val : 0);
            val += (l2 ? l2->val : 0);
            l1 = (l1 ? l1->next : l1);
            l2 = (l2 ? l2->next : l2);
            ListNode* node = new ListNode(val%10);
            val = val / 10;
            onWork->next = node;
            onWork = onWork->next;
        }
        return holder->next;
    }
};

题目

原题在此
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

• $0 <= n, m <= 200$
• $1 <= n + m <= 200$
• $nums_1.length == m + n$
• $nums_2.length == n$
• $-10^9 <= nums_1[i], nums_2[i] <= 10^9$

解析

根据题意, arr1足够大, 所以从arr1[m+n]开始倒着依次写入较大的数既可.

代码

C++

1
2
3
4
5
6

class Solution {
public:
    void merge(vector<int>& a, int m, vector<int>& b, int n) {
        while(n) a[m + n] = (m > 0 && a[m - 1] > b[n - 1])? a[--m] : b[--n];
    }
};

Golang

1
2
3
4
5
6
7
8
9
10
11

func merge(nums1 []int, m int, nums2 []int, n int) {
	for n > 0 {
		if m == 0 || nums2[n-1] > nums1[m-1] {
			nums1[m+n-1] = nums2[n-1]
			n--
		} else {
			nums1[m+n-1] = nums1[m-1]
			m--
		}
	}
}

题目

原题在此
Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:

The number of elements currently in nums that are strictly less than instructions[i].
The number of elements currently in nums that are strictly greater than instructions[i].
For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 109 + 7

Example 1:
Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:
Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:
Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

Constraints:

• $1 <= instructions.length <= 10^5$
• $1 <= instructions[i] <= 10^5$

解析

题目虽然标记为hard, 但其实和这道题 基本一样, 用到了树状数组
各大网站都有讲解, 在这儿就不多说了. 放几个链接就好.
论文原文
数据结构可视化

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#pragma clang optimize on
#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
static int __ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class BIT {
public:
    BIT(int _size): size(_size), tree(_size + 1){}
    
    void update(int x) {
        for(; x <= size; x += lowbit(x))
            ++tree[x];
    }
    
    int query(int x) {
        int sum = 0;
        for(; x > 0; x -= lowbit(x))
            sum += tree[x];
        return sum;
    }

private:
    int size;
    vector<long long> tree;
    static constexpr int lowbit(int x) {
        return x & (-x);
    }
};


class Solution {
public:
    int createSortedArray(const vector<int>& ins) {
        static const int M = 1e9 + 7;
        BIT bit(*max_element(ins.begin(), ins.end()));
        long long res = 0;
        for(int i = 0; i < static_cast<int>(ins.size()); ++i) {
            res += min(bit.query(ins[i] - 1), i - bit.query(ins[i]));
            bit.update(ins[i]);
        }
        return res % M;
    }
};

题目

原题在此
Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Return 0 if there is no such transformation sequence.

Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Constraints:

• 1 <= beginWord.length <= 100
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the strings in wordList are unique.

解析

根据题意,例如”hit”可以转变成”hot”, 在图(抽象数据结构)中称作节点hit和节点hot有一条边相连.
如何确定两个节点是不是邻居:

1. 把wordList 数组丢到 set 里方便快速查找.
2. 对word的每个字符用a-z替换并查看是否在set中(不包括自己),如果在就是邻居. 以hit为例: ait, bit, … zit, bat, bbt, … bzt, bia …

所以题目转化为根据数组构造一个图,然后搜索起点到终点的最短路径.
这时你就想到了BFS. BFS的要点:

1. 用queue(FIFO)的数据结构逐层遍历.
2. 图中可能有环, 需要用set或map之类的关联容器快速查找结点是否已经访问过. 访问过则不做处理, 否则会死循环.

在本题中, 由于起点终点已知, 只搜索最短路径, 可以使用双向BFS来优化. 双向BFS的要点:

1. bfs中使用的queue和set一分为二, 首尾各自保存. 循环终止判断变为当前元素是否在另一个集合里出现过.
2. 当前集合中有较多节点的集合, 在下一层的遍历中有更大的可能性遇到更多的节点. 所以根据当前集合的大小首尾交换.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* C++ BFS */
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int length = 1;
        while (!todo.empty()) {
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                string word = todo.front();
                todo.pop();
                if (word == endWord) {
                    return length;
                }
                dict.erase(word);
                for (int j = 0; j < word.size(); j++) {
                    char c = word[j];
                    for (int k = 0; k < 26; k++) {
                        word[j] = 'a' + k;
                        if (dict.find(word) != dict.end()) {
                            todo.push(word);
                        }
                     }
                    word[j] = c;
                }
            }
            length++;
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/* Golang Bidirectional BFS */
func ladderLength(beginWord string, endWord string, wordList []string) int {
    wordIdx := make(map[string]int)
    endUsed := make([]bool, len(wordList))
    
    for i, v := range wordList {
        wordIdx[v] = i
    }
    
    if idx, ok := wordIdx[endWord]; ok {
        endUsed[idx] = true;
    } else {
        return 0
    }
    
    var step int = 0
    startUsed := make([]bool, len(wordList))
    sq, eq := list.New(), list.New()
    
    sq.PushBack(beginWord)
    eq.PushBack(endWord)
    
    for sq.Len() > 0 {
        step++
        length := sq.Len()
        for i := 0; i < length; i++ {
            bytes := []byte(sq.Remove(sq.Front()).(string))
            for j := 0; j < len(bytes); j++ {
                b := bytes[j]
                for c := byte('a'); c <= 'z'; c++ {
                    if c != b {
                        bytes[j] = c
                        if idx, ok := wordIdx[string(bytes)]; ok {
                            if endUsed[idx] {
                                return step + 1
                            } else {
                                if !startUsed[idx] {
                                    sq.PushBack(wordList[idx])
                                    startUsed[idx] = true
                                }
                            }
                        }
                    }
                
                }
                bytes[j] = b
            }
        }
        if sq.Len() > eq.Len() {
            sq, eq = eq, sq
            startUsed, endUsed = endUsed, startUsed
        }
    }
    return 0
}

题目

原题在此
Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:
Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:
Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:
Input: word1 = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

• 1 <= word1.length, word2.length <= 103
• 1 <= word1[i].length, word2[i].length <= 103
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
• word1[i] and word2[i] consist of lowercase letters.

解析

把string拼起来再看它们是否相等是最简单的,但会使用额外空间.
也可以用4个指针遍历两个二维数组,达到$O(1)$空间复杂度.
甚至可以写一个Iterator,实现hasNext()和next().

代码

1
2
3

public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
    return (String.join("",  word1)).equals(String.join("",  word2));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        int wp1=0, wp2 = 0, sp1=0, sp2=0;
        while(wp1 < word1.size() && wp2 < word2.size() && word1[wp1][sp1] == word2[wp2][sp2]) {
            if(++sp1 == word1[wp1].size()) {
                wp1++;
                sp1 = 0;
            }
            if(++sp2 == word2[wp2].size()) {
                wp2++;
                sp2 = 0;
            }
        }
        return wp1 == word1.size() && wp2 == word2.size();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
    it1, it2 := iterator{words:word1}, iterator{words:word2}
    for it1.hasNext() && it2.hasNext() {
        if it1.next() != it2.next() {
            return false
        }
    }
    return it1.hasNext() == it2.hasNext()
}

type iterator struct {
    words []string
    currentWord int
    currentIndex int
}

func (i *iterator) hasNext() bool {
    if i.currentWord < len(i.words) {
        if i.currentIndex < len(i.words[i.currentWord]) {
            return true
        } else {
            i.currentWord++
            i.currentIndex = 0
            return i.hasNext()
        }
    }
    return false
}

func (i *iterator) next() byte {
    var result byte
    if !i.hasNext() {
        return result
    }
    result = i.words[i.currentWord][i.currentIndex]
    i.currentIndex++
    return result
}

题目

原题在此
Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Example 4:
Input: s = “”
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

解析

用map<char, int>储存每个字符最后出现的index。采用”滑动窗口”法, 指向子串尾端的指针持续扫描整个字符串,在遇到重复时将更新首指针指向重复字符的下一个。记录（更新）每个字符最后出现的index。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> m(256, -1);
        int res = 0, idx = -1;
        for(int i = 0; i < s.size(); ++i){
            if(m[s[i]] > idx) idx = m[s[i]];
            m[s[i]] = i;
            res = max(res, i - idx);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func lengthOfLongestSubstring(s string) int {
    
    m := make(map[rune]int)
    var res, idx = -1, 0
    for i,r := range s{
        if m[r] > idx {
            idx = m[r]
        }
        m[r] = i
        if(i - idx > res) {
            res = i - idx
        }
        m[r]++;
    }
    return res + 1
}

引

本章关键字：可靠、可拓展、可维护（的数据系统）。澄清它们的定义，概述考量这些目标的方法。
当今， 数据密集型（data-intensive） 应用多于 计算密集型（compute-intensive） 应用。CPU很少成为瓶颈，问题通常来自数据量、数据复杂性、以及数据的变更速度。

一些耳熟能详的组件：

• 存储数据，以便自己或其他应用程序之后能再次找到 （数据库（database））
• 记住开销昂贵操作的结果，加快读取速度（缓存（cache））
• 允许用户按关键字搜索数据，或以各种方式对数据进行过滤（搜索索引（search indexes））
• 向其他进程发送消息，进行异步处理（流处理（stream processing））
• 定期处理累积的大批量数据（批处理（batch processing））

大型应用程序有着各种严格而广泛的要求。这些数据存储工具与数据处理工具，它们针对不同应用场景进行优化，单个工具不足以满足所有的数据处理和存储需求。总体工作被拆分成一系列能被单个工具高效完成的任务，并通过应用代码将它们缝合起来。

在尝试将多个工具组合在一起提供服务时，设计者会重点讨论三个在大多数软件系统中都很重要的问题：

可靠性（Reliability）

​ 系统在困境（adversity）（硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）。

可拓展性（Scalability）

​ 有合理的办法应对系统的增长（数据量、流量、复杂性）

可维护性（Maintainability）

​ 许多不同的人（工程师、运维）在不同的生命周期，都能高效地在系统上工作（使系统保持现有行为，并适应新的应用场景）。

可靠性

可以把可靠性粗略理解为“即使出现问题，也能继续正确工作”。
造成错误的原因叫做故障（fault），能预料并应对故障的系统特性可称为容错（fault-tolerant）
故障（fault）不同于失效（failure）。故障通常定义为系统的一部分状态偏离其标准，而失效则是系统作为一个整体停止向用户提供服务。好的容错机制设计防止因故障而导致失效。

硬件故障

由众多机器组成的分布式系统中，硬件异常不再”异常”。硬件故障是随机的、相互独立的。通过增加单个硬件的冗余度来解决硬件异常可能带来的问题。
在硬件冗余的基础上引入软件容错，那么系统在容忍整个（单台）机器故障的道路上就更进一步了。运维上也有便利，例如：如果需要重启机器（例如应用操作系统安全补丁），单服务器系统就需要计划停机。而允许机器失效的系统则可以一次修复一个节点，无需整个系统停机。

软件错误

另一类错误是内部的系统性错误（systematic error）。这类错误难以预料，而且因为是跨节点相关的，所以比起不相关的硬件故障往往可能造成更多的系统失效。
软件BUG通常会潜伏很长时间，况意味着软件对其环境做出了某种假设——虽然这种假设通常来说是正确的，但由于某种原因最后不再成立了。
对策：

• 仔细考虑系统中的假设和交互；
• 彻底的测试。
• 进程隔离，允许进程崩溃并重启。
• 测量、监控并分析生产环境中的系统行为。如果系统能够提供一些保证（例如在一个消息队列中，进入与发出的消息数量相等），那么系统就可以在运行时不断自检，并在出现差异（discrepancy） 时报警。

人为错误

人类不可靠。
对策：

• 以最小化犯错机会的方式设计系统。
• 将人们最容易犯错的地方与可能导致失效的地方解耦（decouple）。沙箱（sandbox）。
• 在各个层次进行彻底的测试。
• 允许从人为错误中简单快速地恢复，以最大限度地减少失效情况带来的影响。 如快速回滚，分批发布。
• 配置详细和明确的监控，及时发现和日后分析问题。
• 良好的管理实践与充分的培训——一个复杂而重要的方面，但超出了本书的范围。

可拓展性

可拓展性（Scalability） 是用来描述系统应对负载增长能力的术语。讨论可拓展性意味着考虑诸如“如果系统以特定方式增长，有什么选项可以应对增长？”和“如何增加计算资源来处理额外的负载？”等问题。

描述负载

描述负载的参数的最佳选择取决于系统架构，它可能是每秒向Web服务器发出的请求、数据库中的读写比率、聊天室中同时活跃的用户数量、缓存命中率或其他东西。

描述性能

系统负载参数定义好后，就可以研究当负载增加会发生什么。两种角度：

• 增加负载参数并保持系统资源（CPU、内存、网络带宽等）不变时，系统性能将受到什么影响？
• 增加负载参数并希望保持性能不变时，需要增加多少系统资源？

如何描述性能(例)：

• 批处理系统：重要的是吞吐量（throughput）
• 在线系统：重要的是服务的响应时间（response time）

  延迟和响应时间

  延迟（latency） 和 响应时间（response time） 经常用作同义词，但实际上它们并不一样。响应时间是客户所看到的，除了实际处理请求的时间（ 服务时间（service time） ）之外，还包括网络延迟和排队延迟。延迟是某个请求等待处理的持续时长，在此期间它处于 休眠（latent） 状态，并等待服务。

单次服务的响应时间总会有差异，所以需要观测多次服务结果的分布（distribution）。
比起算数平均值，中位数有更好的说服力（或与中位数类似的，90%以上的请求可以在x毫秒之内响应）。
实践中，一个请求往往需要多个后端调用，如果其中一个响应较慢便会拖累整个请求的响应时间。

应对负载

垂直拓展（vertical scaling）：转向更强大的机器
水平拓展（horizontal scaling）：将负载分布到多台小机器上
如果负载极难预测（highly unpredictable），则检测到负载增加时自动增加计算资源的弹性（elastic）系统可能很有用
围绕假设（assumption） 建立良好的可拓展架构

可维护性

系统更新，代码会不再符合新的需求；人员更替，知识会流失。

可操作性（Operability）

​ 便于运维团队保持系统平稳运行。

简单性（Simplicity）

​ 消除尽可能多的复杂度（complexity），使新工程师易学。（和用户接口的简单性不一样。）

可演化性（evolability）

​ 使工程师在未来能轻松地对系统进行更改，当需求变化时为新应用场景做适配。也称为可拓展性（extensibility），可修改性（modifiability）或可塑性（plasticity）。
（extensibility是业务逻辑，服务范围方面的拓展性；Scalability是增加算力增加储存空间等性能方面的拓展性）

Developer Happiness

运维职责包括但不限：

• 监控系统的运行状况，并在服务状态不佳时快速恢复服务
• 跟踪问题的原因，例如系统故障或性能下降
• 及时更新软件和平台，比如安全补丁
• 了解系统间的相互作用，以便在异常变更造成损失前进行规避。
• 预测未来的问题，并在问题出现之前加以解决（例如，容量规划）
• 建立部署，配置、管理方面的良好实践，编写相应工具
• 执行复杂的维护任务，例如将应用程序从一个平台迁移到另一个平台
• 当配置变更时，维持系统的安全性
• 定义工作流程，使运维操作可预测，并保持生产环境稳定。
• 铁打的营盘流水的兵，维持组织对系统的了解。

实现幸福的方式：

• 通过良好的监控，提供对系统内部状态和运行时行为的可见性（visibility）
• 为自动化提供良好支持，将系统与标准化工具相集成
• 避免依赖单台机器（在整个系统继续不间断运行的情况下允许机器停机维护）
• 提供良好的文档和易于理解的操作模型（“如果做X，会发生Y”）
• 提供良好的默认行为，但需要时也允许管理员自由覆盖默认值
• 有条件时进行自我修复，但需要时也允许管理员手动控制系统状态
• 行为可预测，最大限度减少意外

用抽象消除额外复杂度，当状态空间激增、模块间紧密耦合、纠结的依赖关系、不一致的命名和术语、解决性能问题的Hack、需要绕开的特例等使复杂度激增的情况发生时。
可演化性（evolvability），系统不会一成不变，为添加各种奇怪的需求做好准备。

题目

原题在此
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.

Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,…]. The 5th missing positive integer is 9.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,…]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

解析

如果是一个没有missing数的数组,此时arr[i] == i + 1.
也就是说在一个missing了一些数的数组中,到下标i为止missing的个数为arr[i] - (i+1).
这个等式对于数组任意下标i都成立,所以可以用二分查找法快速检索.
当循环结束时 l == r,返回 l + k 即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12

func findKthPositive(arr []int, k int) int {
    var l, r, m int = 0, len(arr), 0
	for l < r {
        m = (l + r) / 2
        if(arr[m] - m - 1 < k) {
            l = m + 1
        } else {
            r = m
        }
	}
	return l + k
}

题目

原题在此
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

解析

1. 与Remove Duplicates from Sorted List I不同之处在于,这次要将重复值一个不留完全移除.
2. 有head的值会重复的情况,所以new一个值与head不一样的dummy指向head;
3. 声明两个指针, p1指向dummy, p2指向head;
4. 当p2不为空时,
   1. 当p2有next且next的值和p2相等时,p2指向next;
   2. 此时有两种情况,p1和p2挨着,两个指针分别指向自己的next. 否则p2指向自己的next,p1指向p2.此时便跳过了重复的值

      代码

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

      /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head) return head; ListNode dummy(head->val + 1, head); ListNode* p1 = &dummy, *p2 = head; while(p2) { while(p2 -> next && p2 -> val == p2 -> next -> val) { p2 = p2 -> next; } if(p1 -> next == p2) { p1 = p2; p2 = p2 -> next; } else { p2 = p2 -> next; p1 -> next = p2; } } return dummy.next; } };