题目

原题在此

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by 2.

  • For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].

• If the element is odd, multiply it by 2.

  • For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].
    The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

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

解析

先将奇数全部乘以2变成偶数, 然后sort. 因为会有频繁的删除插入操作, 使用优先队列节省时间.

代码

c++

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

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int res = INT_MAX, min_n = INT_MAX;
        priority_queue<int> pq;
        for (auto n : nums) {
            n = n % 2 ? n << 1 : n;
            pq.push(n);
            min_n = min(min_n, n); 
        }
        while (pq.top() % 2 == 0) {
            res = min(res, pq.top() - min_n);
            min_n = min(min_n, pq.top() >> 1);
            pq.push(pq.top() >> 1);
            pq.pop();
        }
        return min(res, pq.top() - min_n); 
    }
};

题目

原题在此

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (x, y), its left and right children will be at positions (x - 1, y - 1) and (x + 1, y - 1) respectively.

The vertical order traversal of a binary tree is a list of non-empty reports for each unique x-coordinate from left to right. Each report is a list of all nodes at a given x-coordinate. The report should be primarily sorted by y-coordinate from highest y-coordinate to lowest. If any two nodes have the same y-coordinate in the report, the node with the smaller value should appear earlier.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Explanation: Without loss of generality, we can assume the root node is at position (0, 0):
The node with value 9 occurs at position (-1, -1).
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2).
The node with value 20 occurs at position (1, -1).
The node with value 7 occurs at position (2, -2).

Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

Explanation: The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report [1,5,6], the node with value 5 comes first since 5 is smaller than 6.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 1000

解析

代码

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:    
    struct Foo {
        TreeNode* node;
        int x;
        int y;
    };
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, map<int, multiset<int>>> mp;
        queue<Foo> q;
        q.push({root, 0, 0});
        while (!q.empty()) {
            Foo tmp = q.front();
            q.pop();
            if(tmp.node -> left ) {q.push({tmp.node -> left , tmp.x - 1, tmp.y - 1});}
            if(tmp.node -> right) {q.push({tmp.node -> right, tmp.x + 1, tmp.y - 1});}
            mp[tmp.x][tmp.y].insert(tmp.node -> val);
        }
        vector<vector<int>> res;
        for (auto & [key, val] : mp) {
            vector<int> tmp;
            for (auto & [nonUsed, set] : val) {
                tmp.insert(tmp.begin(), set.begin(), set.end());
            }
            res.push_back(tmp);
        }
        return res;
    }
};

题目

原题在此

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:
Input: n = 5, k = 73
Output: "aaszz"

Constraints:

• 1 <= n <= $10^5$
• n <= k <= 26 * n

解析

先声明一个字符串长度为n, 全部填充’a’, 此时 k = k - n; 然后从字符串尾部开始逐个将 'a' 替换为 'z', 每替换一个 k -= 25; 直到 k < 25 时, 将 'a' 替换为 'a' + k;

代码

c++

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

class Solution {
public:
    string getSmallestString(int n, int k) {
        string s (n, 'a');
        k -= n;
        while (k > 0) {
            s[--n] += min(25, k);
            k -= min(25, k);
        }
        return s;
    }
};

题目

原题在此
Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: “1” in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to “1”, “10”, and “11”.
After concatenating them, we have “11011”, which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in “1101110010111011110001001101010111100”.
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

Constraints:

• 1 <= n <= $10^5$

解析

从$f(1) = 0b1 = 1$开始:

$ f(2) = 0b110 = 0b100 + 0b10 = f(1)<<2 + 0b10 = 1*4 + 2=6$

$f(3) = 0b11011 = 110 00 + 11 = f(2) << 2 + 3 = 24 + 3 = 27$

容易看出有以下递推公式:

$f(n) = f(n-1) <<[floor(log_2n)+1]+n = f(n-1) * 2^{\lfloor\log_2n\rfloor+1}+n$

这里的$\log_2n$是因为大于0的 k位2进制数 个数有$2^{k-1}个$, 等比数列求和得 小于k位的二进制数 共有$2^k$个.

k=1 1 : $2^0=1$

k=2 10, 11: $2^{1} = 2$

k=3 100, 101, 110, 111: $2^2 = 4$

所以递推公示的左移位数是$\log_2n$向下取整 + 1.

用矩阵形式来表示就是

然后只需要用结合律, 先考虑不同位数的二进制数生成的矩阵的$2^{k-1}$次乘方, 然后再去乘以向量$(f(1), 2,1)^T$.

另附英文讲解-and-O(log2-n)-fast-and-short-explained)一个.

代码

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

class Solution(object):
    def concatenatedBinary(self, n):
        """
        :type n: int
        :rtype: int
        """
        def multiply(X, Y):
            return [[sum(a*b for a,b in zip(X_row,Y_col)) % 1000000007 for Y_col in zip(*Y)] for X_row in X]
        
        ans, acc, level = [[1], [2], [1]], 1, 1
        while acc < n:
            M = 2 ** (level + 1)
			
			# number of matrix production in this level
            x = take = min(n, M - 1) - acc
            
			mat = [[M, 1, 0], [0, 1, 1], [0, 0, 1]]
			
			# for example
			# num^13 = num * num^4 * num^8
			# num^6 = num^2 * num^4
            while x > 0:
                if x & 1: ans = multiply(mat, ans)
                mat, x = multiply(mat, mat), x >> 1
            
			acc, level = acc + take, level + 1
        
        return ans[0][0]

题目

原题在此
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5]has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 106

解析

以graph的视角来看的话, 相邻node间的距离是node.val差的绝对值. 此时题目转化为求起点到终点的路径中单次距离最短的路径.
求路径就会想到Dijkstra算法. 但是在普通Dijkstra算法顺次计算距离的过程会造成TLE, 可以使用优先队列维护一个{effort, x, y}的三元组, 在必要的时候再搜索路径.

代码

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

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& m) {
        int row = m.size(), col = m[0].size();
        int dir[5] = {0, 1, 0, -1, 0};
        vector<vector<int>> efforts(row, vector<int>(col, INT_MAX));
        auto compare = [&](const array<int, 3> &p1, const array<int, 3> &p2) { return p1[0] >= p2[0]; };
        priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(compare)> pq(compare);
        pq.push({0, 0, 0});
        efforts[0][0] = 0;
        
        while(!pq.empty()) {
            auto [e, r, c] = pq.top();
            pq.pop();
            if(r == row - 1 && c == col - 1) break;
            
            for(int i = 0; i < 4; i++) {
                int x = r + dir[i], y = c + dir[i + 1];
                if(x >= 0 && y >= 0 && x < row && y < col) {
                    int effort = max(e, abs(m[r][c] - m[x][y]));
                    if (effort < efforts[x][y]) {
                        efforts[x][y] = effort;
                        pq.push({effort, x, y});
                    }
                }
            }
        }
        return efforts[row - 1][col - 1];
    }
};

题目

原题在此

解析

这题还用解析么? 是有人不会呢, 还是会有公司出这种面试题. 这个页面肯定没人看所以就写点儿垃圾话好了.

代码

c++

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

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int i = -1, n = nums.size();
        for (int j = 0; j < n; ++j) {
            if (nums[j] == 1) {
                if (i != -1 && j - i - 1 < k)
                    return false;
                i = j;
            }
        }
        return true;
    }
};

题目

原题在此

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won’t exceed $10^4$.

解析

做过TopK这道题的应该对最大堆,优先队列等数据结构有印象. 想看实现细节的可以自己百度.
将lists中的每个节点存入优先队列中, val最小的node出队, 出队node的next入队即可.

代码

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

/**
 * 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 Compare {
public:
    bool operator() (ListNode* foo, ListNode* bar) {
        return foo->val > bar->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        for(ListNode* node : lists)
            if(node) pq.push(node);
        ListNode* res = new ListNode();
        ListNode* foo = res;
        while(!pq.empty()) {
            foo->next = pq.top();
            pq.pop();
            foo = foo->next;
            if(foo->next) pq.push(foo->next);
        }
        return res->next;
    }
};

题目

原题在此

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Example 1:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100

解析

下标i - j相等的元素在一条斜线上, 装在一起排序再装回去就好. 用各种语言的标准库实现会很容易.

c++

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

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i - j].push(mat[i][j]);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = map[i - j].top(); map[i - j].pop();
            }
        }
        return mat;
    }
};

题目

原题在此

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
  • For example, abcde -> aecdb
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
  • For example, aacabb -> bbcbaa (all a’s turn into b’s, and all b’s turn into a’s)
    You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = “abc”, word2 = “bca”
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: “abc” -> “acb”
Apply Operation 1: “acb” -> “bca”

Example 2:

Input: word1 = “a”, word2 = “aa”
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = “cabbba”, word2 = “abbccc”
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: “cabbba” -> “caabbb”
Apply Operation 2: “caabbb” -> “baaccc”
Apply Operation 2: “baaccc” -> “abbccc”

Example 4:

Input: word1 = “cabbba”, word2 = “aabbss”
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

• 1 <= word1.length, word2.length <= $10^5$
• word1 and word2 contain only lowercase English letters.

解析

根据题意, close的条件如下:

1. 出现过的字符组成的集合(不重复)相同. 以例三为例: set<char> word1 = {a, b, c}, word2 = {a, b, c}
2. 统计每个字符出现过的次数所组成的集合(可重复)相同. 以例三为例: multiset<int> word1 = {2, 3, 1}, word2 = {1, 2, 3}
3. 因为题目指出输入字符串中只含有小写字母, 可使用数组替换集合.

代码

std::set使用

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

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        set<int> char1, char2;
        multiset<int> count1, count2;
        map<int, int> m1, m2;
        for(char c : word1) m1[c - 'a'] ++;
        for(char c : word2) m2[c - 'a'] ++;
        
        map<int, int>::iterator it;
        for (it = m1.begin(); it != m1.end(); it++) {
            char1.insert(it -> first);
            count1.insert(it -> second);
        }

        for (it = m2.begin(); it != m2.end(); it++) {
            char2.insert(it -> first);
            count2.insert(it -> second);
        }
        
        return char1 == char2 && count1 == count2;
    }
};

std::set不使用

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

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        array<int, 26> m1 {};
        array<int, 26> m2 {};
        for(char c : word1) m1[c - 'a'] ++;
        for(char c : word2) m2[c - 'a'] ++;
        
        if (!equal(begin(m1), end(m1), begin(m2), end(m2), [](int a, int b) { return bool (a) == bool (b); }))
            return false;
        // 此处sort数组长度为26和输入数据长度无关
        sort(begin(m1), end(m1));
        sort(begin(m2), end(m2));
        return m1 == m2;
    }
};

题目

原题在此
Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:
1 <= nums.length <= $10^5$
0 <= nums[i] <= $10^9$
1 <= k <= nums.length

解析

第一个数是从第0个到第size - k个中最小的那个.
第二个数是从上一个数的index开始到size - k - 1中最小的那个
如果已经不能再搜索,就只能按序填上所有元素

代码

golang

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

func mostCompetitive(nums []int, k int) []int {
    res := make([]int, k)
    idx, size := 0, len(nums)
    for i := 0; i < size; i++ {
        for idx > 0 && nums[i] < res[idx - 1] && size - i - 1 >= k - idx {
            idx--
        }
        
        if idx < k {
            res[idx] = nums[i]
            idx++
        }
    }
    return res;
}

c++

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

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> res(k);
        int c = 0, n = nums.size();
        for(int i = 0; i < n; i++) {
             while(c > 0 && res[c - 1] > nums[i] && n - i -1 >= k - c) c--;
             if(c < k) res[c++] = nums[i];
        }
        return res;
    }
};