题目

原题在此

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Example 4:

Input: s = “([)]”
Output: false

Example 5:

Input: s = “{[]}”
Output: true

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only ‘()[]{}’.

解析

学过Stack这种后进先出储存结构的就知道怎么做.左括号就入栈, 右括号就看栈顶元素是否匹配. 最后看栈是否为空.

代码

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

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> stack;
        for(auto c : s){
            if(c == '(' || c == '[' || c == '{') stack.push(c);
            
            if(c == ')'){
                if(!stack.empty() && stack.top() == '(') stack.pop();
                else return false;
            }

            if(c == ']'){
                if(!stack.empty() && stack.top() == '[') stack.pop();
                else return false;
            }
            
            if(c == '}'){
                if(!stack.empty() && stack.top() == '{') stack.pop();
                else return false;
            }
        }
        return stack.empty();
    }
};

题目

原题在此
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Example 3:

Input: s = “a”
Output: “a”

Example 4:

Input: s = “ac”
Output: “a”

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case).

解析

暴力解法

遍历所有可能的字符串,判断是否是回文串并记录长度.可能的优化有:

• 在子串长度大于已找到的最长字串时再判断是否是回文
• 长度为1的字串必为回文串无需访问

复杂度分析:对于长度为n的字符串,有$n^2$个字符串待检查(严格来说是$\frac{n(n+1)}{2}$), 每次检查是否为回文的消耗为O(n), 整体时间复杂度为$O(n^3)$. 原地检查不使用额外空间, 空间复杂度为$O(1)$.

动态规划

DP算法根据暴力解法优化而来. 回文串有如下属性: 一个回文串剪去首尾两个字符还是一个回文串.
用bool dp[i][j]记录字串s[i..j] // 闭区间, 包括i和j是否为回文串
根据回文串属性, 有状态转移方程dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]
边界条件既是长度为1的字串是回文串 -> dp[][]数组对角线全为true.

复杂度分析:对于长度为n的字符串,有$n^2$个dp状态,每次状态转移的时间为$O(1)$, 整体时间复杂度为$O(n^2)$. 空间复杂度即为存储dp状态所需的大小, $O(n^2)$.

中心扩散

中心扩散的思想和DP检查回文串的思路相反, 是以每一或两个字符为对称轴(回文串的奇偶,”aba”,”abba”)检查两侧最多有几个字符相同.
复杂度分析:对于长度为n的字符串, 有n个奇数回文中心和n-1个偶数回文中心, 每次检查消耗为$O(n)$, 整体时间复杂度为$O(n^2)$. 空间复杂度为$O(1).

Manacher

这个是个线性时间复杂度的算法, 光靠文字和公式理解起来比较抽象, 建议看视频讲解.

代码

暴力(java)

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

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxLen = 1;
        int begin = 0;
        
        char[] charArr = s.toCharArray();
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                if(j - i + 1 > maxLen && isPalindrome(charArr, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
    
    private boolean isPalindrome(char[] charArr, int i, int j) {
        while (i < j) {
            if (charArr[i] != charArr[j]) return false;
            i++;
            j--;
        }
        return true;
    }
}

DP(golang)

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

func longestPalindrome(s string) string {
    size, maxLen, begin := len(s), 1, 0
    dp := make([][]bool, size)
    for i := 0; i < size; i++ {
        dp[i] = make([]bool, size)
        dp[i][i] = true
    }
    
    for j := 1; j < size; j++ {
        for i := 0; i < j; i++ {
            if(s[i] != s[j]) {
                dp[i][j] = false
            } else {
                if (j - i < 3) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
            
            if(dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s[begin: begin + maxLen]
}

中心扩散(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Using global variables will cause inconsistent result between "Run" and "Submit"
func longestPalindrome(s string) string {
    var size, maxLen, begin int = len(s), 1, 0
    for i := 0; i < size - 1; i++ {
        begin, maxLen = isPalindrome(s, i, i, begin, maxLen)
        begin, maxLen = isPalindrome(s, i, i + 1, begin, maxLen)
    }
    return s[begin: begin + maxLen]
}

func isPalindrome(s string, i, j, begin, maxLen int) (int, int) {
    size := len(s)
    for i >= 0 && j < size && s[i] == s[j] {
        i--
        j++
    }
    if j - i - 1 > maxLen {
        begin = i + 1
        maxLen = j - i - 1
    }
    return begin, maxLen
}

Manacher(golang)

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

func longestPalindrome(s string) string {
    var maxLen, begin, maxRight, center int = 1, 0, 0, 0
    tmp := make([]rune, 0)
	tmp = append(tmp, '#')
	for _, c := range s {
		tmp = append(tmp, c)
		tmp = append(tmp, '#')
	}
    tsize := len(tmp)
    dp := make([]int, tsize)
    for i := 0; i < tsize; i++ {
        if i < maxRight {
            mirror := 2 * center - i;
            dp[i] = min(maxRight - i, dp[mirror])
        }
        
        left, right := i - (dp[i] + 1), i + (dp[i] + 1)
        for left >= 0 && right < tsize && tmp[left] == tmp[right] {
            dp[i]++
            left--
            right++
        }
        
        if i + dp[i] > maxRight {
            center, maxRight = i, dp[i] + i
        }
        
        if dp[i] > maxLen {
            maxLen = dp[i]
            begin = (i - maxLen) / 2
        }
    }
    return s[begin: begin + maxLen]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

题目

原题在此
You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:

• Remove numbers 1 and 4, then nums = [2,3]
• Remove numbers 2 and 3, then nums = []
  There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:

• Remove the first two 3’s, then nums = [1,4,3]
  There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

• 1 <= nums.length <= $10^5$
• 1 <= nums[i] <= $10^9$
• 1 <= k <= $10^9$

解析

思路一

这题和LeetCode第一题2Sum很像, 做过就会想到用空间换时间, 建立map来缩短查询时间.

1. 建立一个map<num, count>, 遍历数组, 记录每个数字出现的次数.
2. 遍历map, 如果有 map[k - key]存在, 则说明有可以相加等于k的两个数字存在, 此时有两种情况:
   1. key == k - key, 即两个相同数字相加等于k, 此时结果应该加上 map[key] / 2.
   2. key != k - key, 即两个不同数字相加等于k, 此时结果应该加上 min(map[key], map[k- key]), 即最多可以有两个count中较小值个数的pair. 且因为key != k - key, 之后还会遍历到一次相同的pair, 这里需要减去min值, 以便在第二次处理相同pair时 min()会返回0.

思路二

在理解了用map记录每个num的出现次数和查询 key 与 k - key的count关系后, 可以将算法改进. 将记录与查询过程放入一个循环, 一次搞定.

1. 建立一个map<num, count>, 遍历nums数组
   1. 若 num >= k, 即当前num不可能组成pair, 跳过本次循环.
   2. 若 map[k - num]有值且大于0, 则能组成pair, res++; map[k - num]--. 否则map[num]++.

代码

方法一(golang)

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

func maxOperations(nums []int, k int) int {
    m := make(map[int]int)
    res := 0
    for _, val := range nums {
        m[val]++
    }
    
    for key, val := range m {
        if v, ok := m[k - key]; ok {
            if(k - key == key) {
                res += val / 2;
            } else {
                less := min(val, v)
                res += less
                m[key] -= less
                m[k - key] -= less
            }
        }
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

方法二(golang)

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

func maxOperations(nums []int, k int) int {
    m := make(map[int]int)
    res := 0
    for _, num := range nums {
        if num >= k {
            continue
        }
        diff := k - num
        count := m[diff]
        if count > 0 {
            res++
            m[diff]--
        } else {
            m[num]++
        }
    }
    return res
}

题目

原题在此

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:
Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that “ea” is not a valid string since ‘e’ comes after ‘a’ in the alphabet.

Example 3:
Input: n = 33
Output: 66045

Constraints:

• 1 <= n <= 50

解析

一维的DP解不难, 就不多说了. 说说解析解.
这道题可以这样理解: 有5个盒子, 上面写着["a","e","i","o","u"], 有n个球放入5个盒子,盒子可以为空, 有多少种方法?
因为题目要求string为字典序,所以当组成字符串的所有字符确定了,顺序也就确定了.

盒子不为空的情况

把n个球放成一排, 插入4个隔板, 把n个小球分成5份, 板子有多少种插法?
因为盒子不为空,所以两个球之间和左右末端不能插入多个隔板. 所以有n - 1个位置插入隔板. 所以答案为 comb(n - 1 , 5 - 1)

盒子可为空的情况

先从n + 5个球中拿出5个, 在5个盒子里各放一个球, 然后再放原来的n个球. 等价于n个球放入5个盒子且盒子可以为空. 此时答案为comb(n + 5 - 1, 5 - 1)

排列组合公式

Permutation: $nP_k = \frac{n!}{(n-k)!}$
Combination: $nC_k = \frac{nP_k}{k!}$

代码

1
2
3
4
5
6

class Solution {
public:
    int countVowelStrings(int n) {
        return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;
    }
};

题目

原题在此
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解析

方法一: 最大堆

使用优先队列维护一个大小为k的最大堆, 遍历数组, 当发现比堆底元素更大的值时移除堆顶元素.

方法二: 优先选择

先复习下快速排序这个经典分治算法的步骤:

1. 随机选取区域中一个数字做pivot.
2. 遍历并交换元素使得pivot左侧元素全部小于a[pivot], 右侧全部大于等于a[pivot].
3. 对[left .. pivot-1], [pivot + 1 .. rigth] 重复上述操作.

也就是说, 每次”分组”操作后,一个数的最终位置就确定了. 在从小到大的排序过程中, 只要pivot在分组操作后落到了倒数第k个位置时, 答案就找到了.
否则, 如果pivot比k小, 就递归操作右区间, 如果pivot比k大就递归操作左区间. 因为这时两个区间已经按大小关系划分过, 总有一个区间是不需要再关心的.

代码

方法一

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

// std used
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
       priority_queue<int,vector<int>, greater<int>> pq;
        for(int n : nums) {
            pq.push(n);
            if(pq.size()>k) pq.pop();
        }
        return pq.top();
    }
};

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        buildHeap(nums, size);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --size;
            maxify(nums, 0, size);
        }
        return nums[0];
    }

private:
    void buildHeap(vector<int>& a, int size) {
        for(int i = size / 2; i >= 0; --i) {
            maxify(a, i, size);
        }
    }
    
    void maxify(vector<int>& a, int i, int size) {
        int l = i * 2 + 1, r = i * 2 + 2, max = i;
        if(l < size && a[l] > a[max]) max = l;
        if(r < size && a[r] > a[max]) max = r;
        if(max != i ) {
            swap(a[i], a[max]);
            maxify(a, max, 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

func findKthLargest(nums []int, k int) int {
    return partition(nums, 0, len(nums)-1, k)
}

func partition(nums []int, left int, right int, k int) int {
    if left == right {
        return nums[left]
    }
    
    p := right
    l := left
    r := right-1
    for l <= r {
        for (l <= r && nums[l] >= nums[p]) {
            l++
        }
        
        for (l <= r && nums[r] < nums[p]) {
            r--
        }
        
        if (l <= r) {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }
    nums[l], nums[p] = nums[p], nums[l]
    p = l
    
    if (p > k-1) {
        return partition(nums, left, p-1, k)
    } else if (p < k-1) {
        return partition(nums, p+1, right, k)
    }
    return nums[p];
}

题目

原题在此

You are given an integer n. An array nums of length n + 1 is generated in the following way:

• nums[0] = 0
• nums[1] = 1
• nums[2 i] = nums[i] when 2 <= 2 i <= n
• nums[2 i + 1] = nums[i] + nums[i + 1] when 2 <= 2 i + 1 <= n
  Return the maximum integer in the array nums​​​.

Example 1:

Input: n = 7
Output: 3
Explanation: According to the given rules:
nums[0] = 0
nums[1] = 1
nums[(1 2) = 2] = nums[1] = 1
nums[(1 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 2) = 4] = nums[2] = 1
nums[(2 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 2) = 6] = nums[3] = 2
nums[(3 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is 3.

Example 2:

Input: n = 2
Output: 1
Explanation: According to the given rules, the maximum between nums[0], nums[1], and nums[2] is 1.

Example 3:

Input: n = 3
Output: 2
Explanation: According to the given rules, the maximum between nums[0], nums[1], nums[2], and nums[3] is 2.

Constraints:

• 0 <= n <= 100

解析

根据题意生成数组,然后返回最大值即可.

代码

C++

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (!n) return 0;
        int arr[101] = {0, 1};
        for (int i = 2; i <= n; ++i)
            arr[i] = i % 2 ? arr[i / 2] + arr[i / 2 + 1] : arr[i / 2];
        int size = sizeof(arr) / sizeof(arr[0]);
        return *max_element(arr, arr + size);
    }
};

题目

原题在此

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

• 1 <= nums.length <= $10^5$
• 1 <= nums[i] <= $10^4$
• 1 <= x <= $10^9$

解析

设sum =$\sum\limits_{i = 0}^{i < n} {nums[i]}$, n = nums.size(). 此时, 原题等价于求最长的subarray使得subarray的各项元素和等于sum - x.
用和这道题一样的滑动窗口思路求解即可.

代码

c++

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

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        long long sum = -x;
        for(int num : nums)
            sum += num;
        int left = 0, right = 0, res = -1, n = nums.size();
        long long temp = 0; 
        while(left < n && right < n) {
            while(right < n && temp < sum) temp += nums[right++];
            res = (temp == sum) ? max(res, right - left) : res;
            do temp -= nums[left++]; while(left < n && temp > sum);
        }
        return res == -1 ? -1 : n - res;    
    }
};

引

本章关键字:

• 关系数据库，文档数据库，图形数据库等数据模型，讨论各类数据模型描述一对多、多对多关系的能力以及如何通过抽象来隐藏复杂度。
• 查询语言， 讨论如何基于数据模型做各种操作(例:添加新列，添加索引，结合查询，模拟其他数据模型等)以及执行操作的效率与难易度。

SQL与RDBMS

在关系模型中，数据被组织成关系（SQL中称作表），其中每个关系是元组（SQL中称作行)的无序集合。

NoSQL

NoSQL意味不仅是SQL（Not Only SQL）。它并非任何特定的技术，而泛指非关系型的数据模型。包括但不限：

• 列族数据库，按列存储数据。最大的特点是方便存储结构化和半结构化数据，方便做数据压缩等批量数据处理，对针对某一列或者某几列的查询有非常大的IO优势。如HBase， BigTable等。
• 文档数据库，将诸如JSON，XML等半结构化数据存储为文档。与传统关系数据库不同的是，每个 NoSQL 文档的架构是不同的（不限定数据模式），更加灵活地整理和存储应用程序数据并减少可选值所需的存储。如MongoDB，CouchDB等。
• 键值数据库，可以简单看作哈希表，数据仅可能通过主键访问，不能对Value进行索引和查询。适用于缓存等存在大量写入操作的场景。如Redis，Memcached等。
• 图数据库，描述节点和关系的抽象。主要应用于社交关系，知识图谱等关联分析的应用场景。如Neo4J等。

采用NoSQL数据库的背后有几个驱动因素，其中包括：

• 需要比关系数据库更好的可伸缩性，包括非常大的数据集或非常高的写入吞吐量。
• 相比商业数据库产品，免费和开源软件更受偏爱。
• 关系模型不能很好地支持一些特殊的查询操作。
• 受挫于关系模型的限制性，渴望一种更具多动态性与表现力的数据模型。

题目

原题在此

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

解析

方法一

将people排序, 然后判断情况上船:

1. 当前最轻的和最重的不能坐一起 $\Rightarrow$ 最重的不能和任何人共坐一条船 $\Rightarrow$ 最重的人单独上船 $\Rightarrow$ tailPointer--;
2. 当前最轻的和最重的能坐一起 $\Rightarrow$ 都上船 $\Rightarrow$ tailPointer--; headPointer++

重复上述过程直至 headPointer $\geq$ tailPointer

方法二

与方法一类似, 创建一个limit + 1长的数组当作map, 省去排序步骤.

代码

方法一(c++)

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

class Solution {
public:
    int numRescueBoats(vector<int>& people, int lim) {
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1;
        int res = 0;
        while(l <= r) {
            if (people[l] + people[r] <= lim) l++;
            r--;
            res++;
        }
        return res;
    }
};

方法二(c++)

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

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        vector<int> buckets(limit+1, 0); int n=people.size();
        for(int i=0; i<n; i++) buckets[people[i]]++;
        int l=0, r=limit, ans=0;
        while(l<=r) {
            while(l<=r && buckets[l]<=0) l++;
            while(l<=r && buckets[r]<=0) r--;
            if (buckets[l]<=0 && buckets[r]<=0) break;
            ans++;
            if (l+r<=limit) buckets[l]--;
            buckets[r]--;
        }
        return ans;
    }
};