Leetcode1401 - 1500

Posted on Edited on

Leetcode1403. Minimum Subsequence in Non-Increasing Order

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.

If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.

Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Example 1:

1
2
3
Input: nums = [4,3,10,9,8]
Output: [10,9] 
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

找出这样的最小子序列，肯定从数组中最大数开始一个一个提取，直到子序列的和大于剩余在原数组的元素之和。关键在于怎么提取数组中的最大数。可以将数组排序。注意是严格大于！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        vector<int> res;
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(int i : nums)
            sum += i;
        sum /= 2;
        for(int i = nums.size()-1; i >= 0; i --) {
            if(sum < 0)
                break;
            sum -= nums[i];
            res.push_back(nums[i]);
        }
        return res;
    }
};

Leetcode1408. String Matching in an Array

Given an array of string words. Return all strings in words which is substring of another word in any order. String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

1
2
3
4
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

1
2
3
Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

找到字符串数组中哪些字符串是另一些字符串的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    
    static bool cmp(string a, string b) {
        return a.length() < b.length();
    }
    
    vector<string> stringMatching(vector<string>& words) {
        set<string> res;
        sort(words.begin(), words.end(), cmp);
        int len = words.size();
        for(int i = 0; i < len; i ++)
            for(int j = i + 1; j < len; j ++)
                if(words[j].find(words[i]) != -1)
                    res.insert(words[i]);
        return vector<string>(res.begin(), res.end());
    }
};

Leetcode1413. Minimum Value to Get Positive Step by Step Sum

Given an array of integers nums, you start with an initial positive value startValue. In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right). Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
                step by step sum
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:

1
2
3
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

求startValue使得从左到右加nums里的数的和不小于1，其实就是求个前缀和。从左往右依次累加nums的和，如果遇到和为负数的情况，只要保证 startValue = min(负数和） + 1 即可；如果全为正数，startValue = 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int minn = 99999, sum = 0;
        for(int i = 0; i < nums.size(); i ++) {
            sum += nums[i];
            minn = min(minn, sum);
        }
        if(minn < 0)
            return abs(minn) + 1;
        return 1;
    }
};

Leetcode1417. Reformat The String

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits). You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

1
2
3
Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

1
2
3
Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。如果letter的个数和digit的个数符合合并要求的话，我们要把长度较长的放在首位。比如说”111”和”aa”合并的话，结果一定是”1a1a1”，否则如果’a’打头的话，没有办法将所有的1分割开。

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
class Solution {
public:

    string reformat(string s) {
        string res;
        vector<char> a, b;
        for(int i = 0; i < s.length(); i ++) {
            if('0' <= s[i] && s[i] <= '9')
                a.push_back(s[i]);
            else
                b.push_back(s[i]);
        }
        int lena = a.size(), lenb = b.size();
        int abss = lena - lenb;
        cout<<abss<<endl;
        if(abs(abss) > 1) 
            return "";
        int k = 0;
        if(lena > lenb) {
            k = 0;
            for(char c : a) {
                s[k] = c;
                k += 2;
            }
            k = 1;
            for(char c : b) {
                s[k] = c;
                k += 2;
            }
        }
        else {
            k = 0;
            for(char c : b) {
                s[k] = c;
                k += 2;
            }
            k = 1;
            for(char c : a) {
                s[k] = c;
                k += 2;
            }
        }
            
        return s;
    }
};

Leetcode1418. Display Table of Food Orders in a Restaurant

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant’s “display table”. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito".

找到好的数据存储结构就行了。

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
class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        vector<vector<string> > res(1);
        map<int, map<string, int>> mp;

        for(vector<string> a : orders) {
            if(find(res[0].begin(), res[0].end(), a[2]) == res[0].end())
                res[0].push_back(a[2]);
            mp[stoi(a[1])][a[2]] ++;
        }
        sort(res[0].begin(), res[0].end());
        
        for(auto it = mp.begin(); it != mp.end(); it ++) {
            for(string a : res[0])
                if(it->second.find(a) == it->second.end())
                    it->second.insert(pair<string, int>(a, 0));
        }
        res[0].insert(res[0].begin(), "Table");
        
        for(auto it = mp.begin(); it != mp.end(); it ++) {
            vector<string> temp;
            temp.push_back(to_string(it->first));
            for(auto itt = it->second.begin(); itt != it->second.end(); itt ++) {
                temp.push_back(to_string(itt->second));
            }
            res.push_back(temp);
        }
        return res;
    }
};

Leetcode1422. Maximum Score After Splitting a String

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

1
2
3
4
5
6
7
8
9
Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

1
2
3
Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

1
2
Input: s = "1111"
Output: 3

求出左侧 0 数量和右侧 1 数量之和最多的情况，遍历一次，每次更新最大值，注意要保证字符串始终被切分为 2 个子字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxScore(string s) {
        int left = 0, right = 0, res = 0;
        for(int i = 0; i < s.length(); i ++)
            if(s[i] == '1')
                right ++;
        for(int i = 0; i < s.length()-1; i ++) {
            if(s[i] == '1') {
                res = max(res, left + right -1);
                right --;
            }
            else {
                res = max(res, left + right + 1);
                left ++;
            }
        }
        return res;
    }
};

Leetcode1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

1
2
Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

按照对角线的指引输出数字，这个题本来是按照模拟的方法做，但是特殊的case太多，所以参考大佬的做法，直接记下来这个数字在结果数组中的位置，用i+j表示，然后再排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    
    static bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
        if(a.first != b.first)
            return a.first < b.first;
        else
            return a.second.first > b.second.first;
    }

    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<int> res;
        vector<pair<int, pair<int, int>>> pa;
        for(int i = 0; i < nums.size(); i ++)
            for(int j = 0; j < nums[i].size(); j ++) {
                pa.push_back(make_pair(i+j, make_pair(i, nums[i][j])));
            }
        sort(pa.begin(), pa.end(), cmp);
        for(auto a : pa) {
            res.push_back(a.second.second);
        }
        return res;
    }
};

Leetcode1425. Constrained Subsequence Sum

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

1
2
3
Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

1
2
3
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

1
2
3
Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

思路：动态规划 dp[i] = Max(nums[i], nums[i] + dp[i + j]) 其中0 < j <= k，但是直接遍历dp[i + j]会超时，所以要维护一个能快速查找dp[i + j]中最大值的结构，可以使用单调栈。

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 constrainedSubsetSum(vector<int>& a, int k) {
        // 是一个结合了滑动窗口最大值的dp
        // 使用滑动窗口计算最大值，再使用dp求最大值
        int n = a.size();
        deque<int> d;
        int ret = -10000;
        
        vector<int> f(n);
        // f[i] 是考虑前i个元素且选中第i个元素时构造的最大子序列和
        for (int i = 0; i < n; i ++) {
            int l = i - k - 1; // 当前窗口的范围
            if (!d.empty() && d.front() == l)
                d.pop_front(); // 先把上一个窗口的左端点踢出来
            
            f[i] = a[i];
            if (!d.empty())
                f[i] = max(f[i], f[d.front()] + a[i]);
            
            while(!d.empty() && f[d.back()] <= f[i])
                d.pop_back();
            
            d.push_back(i);
            
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

Leetcode1431. Kids With the Greatest Number of Candies

Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has. For each kid check if there is a way to distribute extraCandies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.

Example 1:

1
2
3
4
5
6
7
8
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: 
Kid 1 has 2 candies and if he or she receives all extra candies (3) will have 5 candies --- the greatest number of candies among the kids. 
Kid 2 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids. 
Kid 3 has 5 candies and this is already the greatest number of candies among the kids. 
Kid 4 has 1 candy and even if he or she receives all extra candies will only have 4 candies. 
Kid 5 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有最多的糖果数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        vector<bool> res(candies.size(), false);
        int maxx = -1;
        for(int i = 0; i < candies.size(); i ++)
            if(maxx < candies[i])
                maxx = candies[i];
        for(int i = 0; i < candies.size(); i ++)
            if(candies[i] + extraCandies >= maxx)
                res[i] = true;
        return res;
    }
};

Leetcode1436. Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

1
2
3
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

得到特征：所有destination都出现一次且只出现在list的第二位，第一遍把独特的list第二个city找出来，第二遍遍历把独一无二的找出来就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        map<string, pair<int, int>> mp;
        for(int i = 0; i < paths.size(); i ++) {
            mp[paths[i][0]].first++;
            mp[paths[i][1]].second++;
        }
        for(auto it = mp.begin(); it != mp.end(); it ++) {
            if(it->second.first == 0 && it->second.second == 1)
                return it->first;
        }
        return "";
    }
};

Leetcode1441. Build an Array With Stack Operations

Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3…, n}. Build the target array using the following operations:

  • Push: Read a new element from the beginning list, and push it in the array.
  • Pop: delete the last element of the array.

If the target array is already built, stop reading more elements.
You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array. You are guaranteed that the answer is unique.

Example 1:

1
2
3
4
5
6
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

依次读取1~n之间的数字，如果数字等于target[0]，那么只要做Push操作，同时删掉target[0]；如果不相等，那么做Push和Pop操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> res;
        int j = 0, i;
        for(i = 1; i <= n && j < target.size(); i ++) {
            if(target[j] == i) {
                res.push_back("Push");
                j ++;
            }
            else {
                res.push_back("Push");
                res.push_back("Pop");
            }
        }
        return res;
    }
};

Leetcode1442. Count Triplets That Can Form Two Arrays of Equal XOR

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

  • a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

1
2
3
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

1
2
Input: arr = [1,1,1,1,1]
Output: 10

这个题利用到前段时间学到的新知识——前缀异或和，根据异或运算的性质——相等的数进行异或，结果为0。

从题意中可以得出，我们所要求的是满足条件的三元组的数量，其中三元组的范围为0 <= i < j <= k < arr.length，所以在得到前缀异或和之后，我们可以通过暴力方法获取所有的可能情况，然后依次进行对比，得到最终的结果。

根据上面i, j, k三者的关系，我们可以转化为如下代码，又因为判断条件为——区间[i, j-1]和[j, k]的异或和相等，所以枚举所有可能的区间，然后比较异或和是否相等即可：

为什么题目中是a=arr[i]^arr[i+1]^…^arr[j-1], b=arr[j]^arr[j+1]^…^arr[k]而代码中直接比较前k+1和前i和元素的异或和s[k+1] == s[i]呢？

因为当a==b时，满足arr[i]^arr[i+1]^…^arr[j-1] == arr[j]^arr[j+1]^…^arr[k]，也就是满足s[j]^s[i] == s[k+1]^s[j]，等价于s[k+1] == s[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int ret = 0;
        int n = arr.size();
        vector<int> dp(n, 0);
        
        dp[0] = arr[0];
        for (int i = 1; i < n; i ++)
            dp[i] = dp[i-1] ^ arr[i];
        
        int res = 0;
        for (int i = 0; i < n; i ++)
            for (int j = i+1; j < n; j ++) {
                int tmp = i > 0 ? (dp[i-1] ^ dp[j]) : dp[j];
                if (tmp == 0)
                    res += (j - i); 
            }
        return res;
    }
};

Leetcode1446. Consecutive Characters

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character. Return the power of the string.

Example 1:

1
2
3
Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:

1
2
3
Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

找到最长连续相同字母的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxPower(string s) {
        int count = 1;
        char c = s[0];
        int res = -1;
        for(int i = 1; i < s.length(); i ++) {
            if(c == s[i]) {
                count ++;
            }
            else {
                res = max(res, count);
                c = s[i];
                count = 1;
            }
        }
        res = max(res, count);
        return res;
    }
};

Leetcode1450. Number of Students Doing Homework at a Given Time

Given two integer arrays startTime and endTime and given an integer queryTime. The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

1
2
3
4
5
6
Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

简单题，无聊，找到在queryTime时写作业的人。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int res = 0;
        for(int i = 0; i < startTime.size(); i ++) {
            if(startTime[i] <= queryTime && queryTime <= endTime[i])
                res ++;
        }
        return res;
    }
};

Leetcode1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Given a sentence that consists of some words separated by a single space, and a searchWord. You have to check if searchWord is a prefix of any word in sentence. Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1. A prefix of a string S is any leading contiguous substring of S.

Example 1:

1
2
3
Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

1
2
3
Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

1
2
3
Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

1
2
Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

找给定字符串是句子中的哪个词的前缀，简单但是字符串的题要注意下标的自增。

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
class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int count = 1;
        for(int i = 0; i < sentence.length();) {
            if(sentence[i] == ' ') {
                count ++;
                i ++;
            }
            else {
                int j;
                for(j = 0; i < sentence.length() && j < searchWord.length() && sentence[i] != ' '; i ++) {
                    if(sentence[i] == searchWord[j]) {
                        j ++;  
                    }
                    else {
                        break;
                    }
                }
                if(j == searchWord.length()) {
                    return count;
                }
                for(; i < sentence.length(); i ++)
                    if(sentence[i] == ' ')
                        break;
            }
            
        }
        return -1;
    }
};

还能用流做，不过流能显示水平嘛

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 isPrefixOfWord(string sentence, string searchWord) {
        int n = int(sentence.length());
        int n1 = int(searchWord.length());
        int res = 0;
        int t = 0;
        for(int i = 0; i < n; i ++) {
            if(i == 0 || sentence[i - 1] == ' ') {   
                res ++;
                if(sentence[i] == searchWord[0]) { 
                    if(n1 == 1)
                        return res;
                    for(int j = 1; j < n1; j ++) {
                        i++;
                        if(sentence[i] != searchWord[j]) {
                            t = 0;
                            break;
                        }
                        else
                            t = 1;
                    }
                    if(t == 1)
                        return res;
                }
            } 
        }
        return -1;
    }
};

Leetcode1460. Make Two Arrays Equal by Reversing Sub-arrays

Given two integer arrays of equal length target and arr. In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps. Return True if you can make arr equal to target, or False otherwise.

Example 1:

1
2
3
4
5
6
7
Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

1
2
3
Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

1
2
Input: target = [1,12], arr = [12,1]
Output: true

判断一个数组能否通过翻转子串变成另一个数组，通过统计每个数字的个数判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        vector<int> res(1001, 0);
        for(int i = 0; i < arr.size(); i ++)
            res[arr[i]] ++;
        for(int i = 0; i < target.size(); i ++) {
            res[target[i]] --;
            if(res[target[i]] < 0)
                return false;
        }
        return true;
    }
};

Leetcode1464. Maximum Product of Two Elements in an Array

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Example 1:

1
2
3
Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

1
2
3
Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

返回最大的两个数之积，找到最大的两个数就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max1 = -1, max2 = -1;
        for(int i = 0; i < nums.size(); i ++) {
            if(nums[i] > max1) {
                max2 = max1;
                max1 = nums[i];
            }
            else if(nums[i] > max2) {
                max2 = nums[i];
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
};

Leetcode1470. Shuffle the Array

Given the array nums consisting of 2n elements in the form [x1,x2,…,xn,y1,y2,…,yn]. Return the array in the form [x1,y1,x2,y2,…,xn,yn].

Example 1:

1
2
3
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

Example 2:

1
2
Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

转换数组。。。。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> res;
        for(int i = 0; i < nums.size()/2; i ++) {
            res.push_back(nums[i]);
            res.push_back(nums[i+n]);
        }
        return res;
    }
};

Leetcode1475. Final Prices With a Special Discount in a Shop

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.

Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Example 1:

1
2
3
4
5
6
7
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. 
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. 
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. 
For items 3 and 4 you will not receive any discount at all.

对每个价格，从这个价格开始往后找第一个小于它的，这就是当前价格可以折扣的数量，当前价格减掉找到的这个价格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        for(int i = 0; i < prices.size(); i ++) {
            for(int j = i + 1; j < prices.size(); j ++){
                if(prices[j] <= prices[i]) {
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }
};

Leetcode1480. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums.

Example 1:

1
2
3
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

求前缀和

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i ++) {
            nums[i] = nums[i] + nums[i-1];
        }
        return nums;
    }
};

Leetcode1486. XOR Operation in an Array

Given an integer n and an integer start. Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length. Return the bitwise XOR of all elements of nums.

Example 1:

1
2
3
4
Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

求异或和。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int xorOperation(int n, int start) {
        int res = start;
        for(int i = 1; i < n; i ++)
            res = res ^ (start + i * 2);
        return res;
    }
};

Leetcode1491. Average Salary Excluding the Minimum and Maximum Salary

Given an array of unique integers salary where salary[i] is the salary of the employee i. Return the average salary of employees excluding the minimum and maximum salary.

Example 1:

1
2
3
4
Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500

去掉最值求平均。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double average(vector<int>& salary) {
        int minn = 1e7, maxx = -1;
        for(int i = 0; i < salary.size(); i ++) {
            if(salary[i] > maxx)
                maxx = salary[i];
            if(salary[i] < minn)
                minn = salary[i];
        }
        int sum = 0, count = 0;
        for(int i = 0; i < salary.size(); i ++)
            if(salary[i] != minn && salary[i] != maxx) {
                sum += salary[i];
                count ++;
            }
        return (double)sum / count;
    }
};

Leetcode1492. The kth Factor of n

Given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0. Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

1
2
3
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:

1
2
3
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

找一个数的第k个因子，简单。评测机不稳定，我提交了三次有两次是memory战胜100%。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int kthFactor(int n, int k) {
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(n % i == 0 && --k == 0) 
                return i;
        }
        return -1; 
    }
};

Leetcode1496. Path Crossing

Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return True if the path crosses itself at any point, that is, if at any time you are on a location you’ve previously visited. Return False otherwise.

Example 1:

1
2
3
Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

看路线有没有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isPathCrossing(string path) {
        int x = 0, y = 0;
        set<pair<int, int>> se;
        se.insert({x, y});
        for(char c : path) {
            switch(c){
                case 'N':   y++;    break;
                case 'S':   y--;    break;
                case 'E':   x++;    break;
                case 'W':   x--;    break;
            }
            if(se.find({x, y}) != se.end())
                return true;
            se.insert({x, y});
        }
        return false;
    }
};