源代码地址：https://github.com/hopebo/hopelee
语言：C++
301. Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
- 第一遍采用正向遍历数组，将多余的')'去除。用stack来记录到当前位置的'('和')'的数量关系，当出现'('时加1，出现')'时减一。如果stack>=0继续循环，如果stack < 0时，说明到当前位置为止，')'的数量已经超过'('的数量了，需要立即处理，将当前位置之前的不用位置的')'删除，得到不同的字符串后进行递归，当前循环返回。用start_i存储遍历字符串开始的位置，说明之前的字符串都是经过处理后stack=0的；用start_j用来存储上一次删除')'的位置，确保下一次删除')'，是在start_j之后的位置，不会构成重复。
- 如果能正常遍历完字符串，说明当前的stack>=0，即'('的数量是大于等于')'的，此时需要将上述过程反过来，将多余的'('删除掉，因此我们将字符串反转后遍历，将函数带有的字符数组改换，原本是['(',')']，现在换成[')','(']，完成对'('的删除。由于经过了上一步的过程，所以stack一定不会>0，只有可能<0，即'('的数量大于')'的数量。通过循环后再将字符串反转后加入返回向量中。
刷题记录：
- 很重要的一题，NO BUG FREE.
303. Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
- You may assume that the array does not change.
- There are many calls to sumRange function.
解题思路：
- 定义一个数组记录sum从0~index的元素求和，那么如果要求i~j的元素和时等于0~j的元素和减去0~(i-1)的元素和。
304. Range Sum Query 2D - Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
] sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
解题思路：
- 构建一个二维数组用来存储当前位置到matrix左上角（即(0,0)）所组成的矩形内元素的和。注意添加第一行全为0，第一列全为0，实际构造的数组维度为(m+1)×(n+1)，m、n为matrix的维度，为了保持代码的一致性。
- 对于(row1,col1)到(row2,col2)的矩形内元素求和，可以等于sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1]。用大矩形减去两个小矩形再加上重复减去的矩形。
306. Additive Number
Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?
- 针对字符串表示的非常大的数字相加，为了防止出现溢出，可以定义一个函数直接实现字符串的相加，并返回结果字符串，完整的避开了变量所能表示范围有限的问题。
- 针对各种不同情况下的第一个数和第二个数进行讨论，看看是否满足题设的条件的规律，如果满足就直接返回true，否则继续循环，循环结束返回false。
307. Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5] sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
解题思路：
- 如果采用直接向数组中更改值和对范围内元素求和的方法，更改值的时间复杂度为O(1)，求和的时间复杂度为O(n)。执行m次操作，平均时间复杂度为O(mn)；但是如果使用数状数组(Binary Indexed Tree)来对数组中部分元素的和进行存储，将使修改的时间复杂度变为O(logn)，读取和的时间复杂度也变成O(logn)，达到一个均衡二者的效果，而将m次操作的时间复杂度变为O(mlogn)。
- 假设原数组为nums，长度为n，下标范围为0~(n-1)。那么定义一个长度为n+1的数组sum用来存储nums中特定元素的和，sum的数组是从1开始的，所以nums中的元素下标对应到sum中需要加1。sum存在这样的特点：下标的二进制码的最后连续0的个数决定了当前位置存储和的元素个数，假设当前下标尾数后有k个连续0，那么它存储的就是2^k个元素的和，sum中的下标为i的话，sum[i] = nums[i-1] + nums[i-2]+ ... + nums[i-2^k+1] + nums[i-2^k]。（将sum和nums中下标相差1考虑进去了）。因此每当更改nums中的一个元素时，只需要对包含其求和的那些位置的sum元素进行相应的更改即可，操作次数为logn。对应的位置末尾多一个零（加上一个末位1，即 i += i & -1;）。初始化时，对nums数组进行遍历，将每个元素添在sum中的对应位置。
- 在对nums数组中下标0~i范围内元素求解时，从sum数组的下标为(i+1)位置开始，每次将其对应下标多一个零的位置的和加上（减去最末位的1，具体操作为 i -= i & -i;），直到下标为0时停止。
刷题记录：
- 存储结构和思路很神奇，需要完全掌握，NO BUG FREE。
309. Best Time to Buy and Sell Stock with Cooldown
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
- 定义三个变量sell,buy,rest，分别存储到prices[i]之前（包括prices[i]）的三种最新状态下的最大收获。sell是指在下标为i的位置卖出股票，buy是指在i位置买入股票或者在i之前买入股票还没来得及卖（因为如果卖了，那么到i的最新状态就肯定是rest或者sell了），rest指的是在i-1之前已经卖掉然后一直到i都没买入所以最新状态仍然是rest或者在i-1位置时刚刚卖掉股票，所以i位置一定是rest。
- 动态规划的关键就是要找前后两种状态的关系式，上述关系通过表达式为:1 sell[i] = buy[i-1] + prices[i]; 2 buy[i] = max(buy[i-1], rest[i-1]-prices[i]); 3 rest[i] = max(rest[i-1], sell[i-1])。通过数学归纳法可以证明上述结论是正确的，最后求max(sell[n-1], res[n-1])的最大值即可，因为得到最大值的方式一定是最新状态为卖出股票或者冷冻日，而不可能是刚买入股票。
刷题记录：
- 思路很奇妙，将十分复杂的问题转化成了很简洁的算法，NO BUG FREE。
310. Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
- 此题通过不断删去外层的叶子结点，来得到最短的树的根结点，当所剩下的结点数量<=2时，为根结点返回。
- 利用map<int, set<int>>的数据结构来存储与每个结点相连的结点，将set的大小为1的结点加入到存储叶子结点的向量中，当n>2时，删除这个叶子结点，并将与这些叶子结点相连的结点的连接结点set中删除，如果删除后的size为1的话就将其加入到新的存储叶子结点的向量中。然后继续循环，直到n<=2，注意访问set中的元素用迭代器。
刷题记录：
- 思路和存储结构都很新颖，NO BUG FREE。
312. Burst Balloons
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8]
Return 167
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
- 时间复杂度极其高的问题一定要考虑是不是有很多重复计算的工作可以省略，DP算法就能很好的处理这些问题。本题的动态规划我们要逆向考虑，从短的长度延伸到长的序列；在一定长度（从start~end）的序列中，我们要考虑每一个元素作为最后一个元素的可能情况，比较其最大值，在求最后一个元素的coins时，用的是nums[i] * nums[start-1] * nums[end+1]，以方便于更大长度的动态引用，因为dp[start][end]=max(dp[start][end],nums[start-1]*nums[i]*nums[end+1]+dp[start][i-1]+dp[i+1][end])，因为dp[start][i-1]和dp[i+1][end]的值在计算时是依赖于nums[i]的值的，所以以上做法能方便之后的计算。
刷题记录：
- 动态规划的经典题目，需要熟练掌握思想与写法。NO BUG FREE。
313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
- 类似于Ugly NumII的思路，通过定义flag整型数，指示每个质因数的与现存的Ugly Num相乘得到最小数的下标index，每次都比较所有数的大小关系找到最小的Ugly Num加入到返回值向量中，并将其flag++。
- 为了缩减循环次数以及不必要的乘积计算，我们定义一个数组存储各自质因数对应的最小结果。在当前比较循环时，先将其与之间得到的Ugly Num比较，如果相同，就存入新的candidate，并将对应的flag++。
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1] To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
解题思路：
- 通过构建二叉排序树来提高比较的效率，降低在比较过程中的时间复杂度。二叉排序树的查找效率取决于树的形态，而构造一颗形态匀称的二叉排序树与结点插入次序有关。在最坏的情况下，时间复杂度为O(n)；最好的情况下为O(logn)。不过在本题中，我们并未对二叉排序树的形态多加干预，构造平衡树。
- 在树的结点中不光定义指向左子树和右子树的指针，还定义其val值，sum存储树结构中比它小的结点数量，dup存储该val值的重复次数。在构建二叉树的过程中，依次插入结点，如果当前指向的根结点为空，就new一个新结点；如果相同，就加上比当前结点小的结点数量sum；如果小于当前结点的val，就将其sum值加1，并递归调用插入到其left指针；如果大于当前的val，就将统计值加上当前结点的sum和dup，然后递归调用插入到right指针。
刷题记录：
- 学会自己定义合适的存储结构来降低时间复杂度的方法，NO BUG FREE。
316. Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given "bcabc"
Return "abc"
Given "cbacdcbc"
Return "acdb"
- 用一个map<char, int> dic结构存储原字符串s中所有字符最后出现的位置，优先选取最靠前的位置，说明到这个最靠前的位置前（包括该位置）一定至少出现一次该字符，否则该字符就不存在了。将begin初始化为0，end初始化为上述位置，在begin到end范围内寻找在dic里存在（也就是说还没有在返回字符串中出现）且ASCII码最小的字符，每当找到更小ASCII码的字符，就将begin改写为i+1，因为将最小的字符放置在最前面的话，它之前的字符都必须删掉。遍历完成后，将ASCII码最小的字符push_back到返回字符串中，然后从dic里删去该字符，如果该字符和end位置的字符相同，说明在end前(包括end)已经出现了目标字符有且只有一次，此时将end重置为下一个最后出现位置最近的字符的位置。
刷题记录：
- 使用合适的存储结构能够最大化的减少无谓的遍历，NO BUG FREE。
318. Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.
- 需要合适的存储结构来存放每个单词所包含的字母信息，还要方便之后的比较。我们选择一个int整型数来存放，整型数不同bit位上是否为'1'代表着是否包含对应的字母，最后一位代表'a'，倒数第二位代表'b'，...，倒数第26位代表'z'。用移位运算符和bit或运算来完成这一操作，word[i] |= 1 << (words[i][j] - 'a')；然后通过两层循环比较任意两个单词的int整型数来判断两个单词的字母是否存在重复，如果没有重复，两个int整型数按位与为0。
- 注意操作符之间的优先级顺序，==优先于位运算符&，^，|。
319. Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.
解题思路：
- 这一题需要观察规律和掌握一定的技巧，最后发现只有平方数经过1~n round后是on的状态。因为对于质数而言，在1和它本身round时会切换，次数为2，因此恢复到off的状态；对于非平方数的合数而言，任何相乘等于它本身的因子都是成对的，在它的因子处都会发生切换，成对的因子导致其切换次数一定是2的倍数，最后恢复到off的状态。但是对于平方数而言，存在两个相同的因子对，却只会发生一次切换，所以最后是on的状态。因此返回1~n有多少个平方数即可，return int(sqrt(double(n)))；
321. Create Maximum Number
Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]
- 通过找单个数组中一定长度为len的最大整型序列，然后将其与另一数组中对应k-len长度的最大整型序列合并得到的目标序列，将不同长度组合下得到的目标序列进行比较，得到最大的数。
- 在单个数组中找一定长度的最大整型序列时一定要注意算法的时间复杂度，不要每次都重复遍历数组找最大值，而是将当前的位置上的数依次与已经存入的数字进行比较，如果小于等于，直接加到返回向量尾部；如果比它大，就将j--，继续往前比较，直到j=0或者出现比它大的数，然后放置在其后就可以。
刷题记录：
- 很大的一个问题，但是如果合理的对其分解为很多小问题后，解决起来会方便很多。NO BUG FREE。
322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.
- 定义一个长度为amount+1的数组，位置i存储将i换零所需的最小coin数，可以用dp算法或者递归函数将这个数组填满。
- DP算法是依次往后遍历，用i减coins数组里的所有coin面额，然后用nums[i-coins[j]]+1，取最小值作为换零i所需的最少coins数。如果nums[i-coins[j]为INT_MAX，代表当前面额无法换算成几个硬币的和，跳过。直到循环至amount，将其结果返回。
- 递归算法时从大到小递归，然后从小到大依次返回，如果需要求amount的换算数，就递归调用求amount-coins[j]的换算数，循环求其最小值并返回。注意在求比amount小的钱数的coins换算数时，得到结果后将其写入到nums数组中，以便下一次再需要求这个数的最小换算硬币数时可以直接调用。我们用nums[i]的数值将两种状态区分开：如果nums[i]==INT_MAX，表示并未求其换算数，需要递归来求；如果nums[i]==-1，代表求其换算数的过程已经经历过了，它不存在任何换算组合；其他值就表示最小换算硬币数，直接返回。
刷题记录：
- 一个不是很难的问题，被你想复杂了，NO BUG FREE。
324. Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
- 使用nth_element(nums.begin(), nums.begin()+n/2, nums.end())函数找到向量的中位数（这个函数会将中位数放置在nums.begin()+n/2的位置，大于等于中位数的数排列在其前面，小于等于它的数排列在向量的后面，但其实这个排列对后面的程序没有意义）。我们通过nums.begin()+n/2迭代器就可以访问得到中位数。
- 通过index mapping的方法，将原本的下标i映射为(1+2*i) % (n | 1)，结合three-way partitioning的方法就可以实现大于等于median的数排列在1，3，5，7...的位置上，小于等于median的数排列在0，2，4，6...的位置上。
刷题记录：
- 采用了很巧妙的方法，难以有直观的理解，需要记住这种方法，NO BUG FREE。
326. Power of Three
Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?
- 由于3的次幂中的所有因子都是3，在整型数表示范围内，最大的3次幂数为3^19 = 1162261467，因此如果一个数能够被3^19整除，说明该数所有的因子都是3，即3的次方数。
327. Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
- 之前有一个问题是 count smaller number after self ，是求nums[j] - nums[i] < 0 (j > i)的j的数量。此题先计算出0~1,2,3,...,n-1的序列和向量sum之后，题中的S(i, j)相当于sum[j] - sum[i-1]，即求lower <= sum[j] - sum[i-1] <= upper (i <= j)的数量，可以类似于解决之前题目的方法来求解（归并排序法和二叉排序树法）。
- 本题使用归并排序法来做，在归并排序的过程中，对于前半部分的位置i，找出后半部分使sum[j] - sum[i]在lower和upper之间的j的范围，因此对于每一个i，都能找出使S(i, j)满足条件的j的数量（两个范围相减），然后再进行归并，把后半部分小于sum[i]的数优先加入到新定义的用来存储排好序的元素数组的前面，再放置nums[i]，继续循环。
- 通过一层一层的归并，我们就可以讨论清楚所有i <= j的情况下，满足条件的组合数量。从小范围到大范围，不管小范围内如何变更进行排序，但是在大范围下，后半部分的在原sum向量中的下标肯定是大于前半部分的，按序排列方便我们直接通过左右边界计算组合的数量。
刷题记录：
- 对于之前题目的方法还没有完全掌握，需要更熟练的运用和写归并排序。NO BUG FREE。
328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...
- 两种方法，一种是定义一个指针指向前段odd结点的尾部，一个指针指向经过排序好的even结点的尾部，然后将even指针的next指针指向的结点（即下一个待重排序的odd结点）转移到odd结点的尾部，然后将even结点的next指针指向下一个even结点，依次循环。
- 第二种方法是单独构造odd和even的两条链表，最后将odd链的尾结点的next指针指向even的头结点即可。
329. Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
解题思路：
- 遍历matrix中的每一个元素，寻找与它相邻并大于它的元素，然后递归求该元素为起点的最大增加序列长度。由于在每一步递归中都是寻找大于当前元素的近邻，所以在深层迭代中不可能重复访问到之前的元素，因为访问元素一定是越来越大的，因此不需要设立visited向量来指示哪些元素访问过，哪些元素没有访问过。注意定义一个cache数组来存储在递归过程中曾计算过的起点的最大长度，以方便之后重复访问时能直接调用。
刷题记录：
- NO BUG FREE。
330. Patching Array
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums = [1, 3], n = 6
Return 1.
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].
Example 3:
nums = [1, 2, 2], n = 5
Return 0.
- 找最小缺失值miss，证明[0, miss)范围内的数都可以通过数组已存在的元素求和得到，然而数组后面元素的值大于miss，因此加入后面的元素也无法填补miss的空白。需要加入一个小的数，[0, miss)范围内的数加上一个小数就能覆盖miss，那么加上一个什么样的数会带来最优的效果，使覆盖范围更广呢，答案是加入miss本身，导致之前数的组合sum范围达到[0, miss+miss)，然后再加上原数组中在这个范围以内的元素，以进一步扩充范围，找到下一个缺失值，再添加，直到缺失值>n为止。此时数组中数的组合sum一定覆盖了1~n，而且添加的元素数量最少。
刷题记录：
- 思路很巧妙，但是难以想到，NO BUG FREE。
331. Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:"1,#"
Return false
Example 3:"9,#,#,1"
Return false
- 可以类似于之前unserialize的递归方法去做，也可以统计入度和出度的方法去做。由于一颗正确的树所有结点的入度和出度和一定是相等的，而且不可能出现入度比出度大的情况(即degree > 0)，由于根结点没有入度，我们将degree初始化为-1，以保证代码的一致性。每当访问一个结点我们就将degree++，因为每个结点一定有一个入度；然后判断degree是否大于0，如果大于0，那么直接返回false；再根据结点的实际情况，对出度进行处理，如果结点非空（即不是"#"），那么存在两个出度，将degree -= 2，如果结点为空，则不予处理，因为空结点不存在出度。将所有结点遍历结束后，判断degree是否为0，如果为0返回true，如果不为0返回false。
332. Reconstruct Itinerary
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
- If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary
["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"]. - All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.
Example 1:tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
- 构建一个map<string, multiset<string>>结构用来存储票的信息，代表从每个机场出发，可以前往的下一个机场的信息，要注意map结构的value值必须是multiset类型，因为可能存在两次从某一个机场飞到另一个机场的情况，而且在用掉一次后erase时，只能用迭代器来进行擦除，不能用键值。（如果使用键值的话会将multiset中所有的键值全部擦除）。
- 用一个栈结构来（根据飞机票的ASCII码顺序）依次前往下一个城市，如果当前城市的multiset为空，说明该城市为目的地或者之前已经前往目的地城市后导致不剩下飞机票，就将该城市加入到结果向量中。因此结果向量中的城市顺序是逆序放入的，在将所有飞机票用光之后，也就是循环结束后，需要将返回向量重新反转一下返回。
334. Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
- 定义两个变量one和two，分别存储一个元素和两个元素组成的递增序列尾部的最小值。如果当前元素比one小，那么更新one为其和当前元素的较小值；如果当前元素比one大，再比较其和two的大小，如果比two也大，那么返回true，如果没有two大，说明组成了新的两个元素递增序列，将其值与two做比较，取其较小值更新为two的值。
335. Self Crossing
You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:
Given x =[2, 1, 1, 2],
┌───┐
│ │
└───┼──>
│ Return true (self crossing)
Example 2:
Given x =[1, 2, 3, 4],
┌──────┐
│ │
│
│
└────────────> Return false (not self crossing)
Example 3:
Given x =[1, 1, 1, 1],
┌───┐
│ │
└───┼> Return true (self crossing)
- 有几种情况，首先判断什么样的情况下，行走的圈会陷入之前的圈中，只能越来越小；如果没有陷入之前的圈中，什么样的情况会导致self crossing；如果不出现上述两种情况，说明圈还是在扩大的过程中，那么继续循环即可。
336. Palindrome Pairs
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
- 定义一个map<string, int>结构，存入单词的反转以及对应的下标，便于快速的查找向量中有没有所需要的string。便利向量中的每个词语，将词语进行分割（考虑其与其他单词组合后成为回文字符串中较长的单词考虑），如果分割后左边为回文字符串，那么判断右边的字符串部分在反转字典中是否存在；如果右边部分为回文字符串，那么判断左边的字符串在字典中是否存在。如果存在，那么就有相应的单词组合为回文字符串。注意在遍历时，如果右边部分为空字符串时，不予考虑，避免出现重复的情况，即两个单词，顺序颠倒都为回文字符串的情况。
刷题记录：
- 没有特别的技巧，只是定义了合适的数据结构和遍历的策略就大幅降低了时间复杂度。NO BUG FREE。
337. House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
解题思路：
- 自己之前的递归方法是单独计算下一层的某个子结点是否rob或者notrob的，造成递归函数调用的次数翻倍，而且这个翻倍随着递归函数的继续进行是呈指数性增长的，递归层数越大，增长越多。其实可以将递归函数定义为返回一个大小为2的int型向量，第一个元素存储子结点notrob时的最大收益，第二个元素存储子结点rob时的最大收益，然后在上层函数中再讨论根结点在rob与notrob情况下的最大收益。可使递归函数调用的次数减半。
刷题记录：
- NO BUG FREE。
338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
- 根据规律，以2^n个数为组合，后面一组的数等于前面对应的数的1的数量加1，因为后面一组数与前面对应数相比，相当于只是在最高位多了一个1。也可以用num[i] = num[i >> 1] + i & 1，根据前面数的求得结果来计算后面的数。
341. Flatten Nested List Iterator
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
- 定义一个栈，将向量中的元素，逆序存入，因此从栈顶往外读的顺序是正的。在hasnext()函数里，判断栈顶元素是否为整数，如果是则返回true；如果是链表，则将原栈顶元素出栈，且将链表内元素逆序入栈，继续循环。直到栈为空时，返回false。
- 在读取下一个元素时，直接返回栈顶元素即可，并将原栈顶元素出栈。
342. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example:
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
- 用num & (num-1) == 0可以判断num中是否只包含一个1（说明num为2的次方），由于2的次方与4的次方中的1出现的位置不一样，因此用num & 0x55555555 != 0可以排除掉2的奇数次方（不是4的次方）。
343. Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume that n is not less than 2 and not larger than 58.
- 复杂的方法是用动态规划，根据前面的数分割后得到的最大相乘的结果，来求当前数分割得到最大结果。其实可以观察到一个规律，当把一个整数分解时，分解的一部分小于等于4时，将其作为一整个因子是要比将这部分继续分解再相乘得到的结果大的；如果一部分大于4，那么将其分解后相乘是比原数作为一个整体要大的。
- 更简单的方法是观察其中的规律，当n>4时，尝试对其分解，如果第一步分解的一部分是2或者3，那么将其作为一个整体因子更大；如果另一部分也大于4，那么将其分解后得到的因子相乘的结果是大于其本身的，由于5，6分解得到最大数的因子均为2和3，所以依次类推后面所有数分解得到最大数的因子全是由2和3组成的。
- 再考虑一点，6 = 2+2+2 = 3+3，而3*3 > 2*2*2，所以只要因子中出现3个2，那么转化为2个3相乘一定更大，所以最大的因子分解后最后包含2个2。所以在循环里，我们优先提取3作为因子，直到n<=4，就乘以n本身就行了。
刷题记录：
- 思路很巧妙，NO BUG FREE。
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".
- 将原字符串中的字符倒序加入新的字符串中，或者将原字符串前后字符交换。
345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
- 定义一个字符集合存储所有的元音字母，使用i,j作为从前和从后遍历字符串的index下标，i循环递增直到找到元音字母，j循环递减直到当前字符为元音字母。然后将字符串中i和j位置的字符相交换。将i++,j--后继续循环，直到i>=j时循环停止。
347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
- 不要怕使用复杂的存储结构，很多时候优秀的时间复杂度都是用空间复杂度换来的，所以一定要敢于尝试。
- 本题首先就是用map<int, int>统计向量中每个元素出现的次数，然后就是根据他们的次数进行的一个排序问题，可以用Bucket Sort来解决，也可以用priorty_queue来解决都行。
349. Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
- 定义两个集合来降低算法的时间复杂度，一个集合来存储其中一个向量中出现的数，用来迅速判断另一向量中的元素在第一个向量中是否存在；另一个集合用来存储重复的数（也就是结果向量中的数）以避免结果中元素的重复。
350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
- 定义一个map<int, int>结构用来存储nums1向量中出现的元素及其出现次数，然后遍历Nums2向量，如果nums2中的元素在map中存在，且次数>0，就将其push_back到返回向量中，并且将其count次数--。
352. Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]
Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?
- 一个不是很难的问题，你一定要相信自己的判断，有的时候可能就只是基本的算法，而没有特别的trick。
- 本题就是一个根据二分查找确定插入的数在已有的间隔向量中的位置，然后判断插入数是否在已有间隔内。如果在间隔内，那么不用做任何操作；如果位于所有间隔的前面，那么判断是否比最左的间隔的start-1，如果是直接改写第一个间隔的start，不是则在第一个位置插入当前数组成的间隔；如果插入数为当前间隔的end+1，同时是下一个间隔的start-1，就合并前后两个间隔；如果只是当前间隔的end+1，直接改写当前间隔的end；如果只是下一间隔的start-1，那么改写下一间隔的start；如果都不是，则位于前面两个间隔之间，且各不相邻，此时插入当前数组成的间隔即可。
- 在本题中需要调用向量的insert和erase函数，虽然在理论上这些成员函数的时间复杂度都不低，但是也只能这么做了，是最优的解决方案。
354. Russian Doll Envelopes
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
- Naive DP: 首先将原向量按照width从小到大排序，那么对于每一个信封来说，它所能包裹的信封一定是在向量中它所在的位置前面，因此我们就可以用DP算法，求每个信封对应的前面height递增序列的长度；如果当前元素j的height > 前面某个元素i的height，那么其dp[j] = max(dp[j], dp[i]+1)。这样就可以求到最大可包裹信封数量。
- Binary Search DP: 将原向量安装width从小到大排序后，要求最大可包裹信封的数量，实际上就是求当前向量height呈递增子序列的最大长度。这就可以转化为我们之前做过的问题，将向量的下标作为子序列的长度，其值作为该长度下的最小末尾值，显然末尾值是递增的，我们就可以使用二分查找来寻找当前元素的height是大于哪个末尾值：如果height大于最后一个元素的末尾值，说明最大长度可以+1，直接将当前height加入到向量中；如果不是最后的值，那么对后一个长度的值进行更新，取最小值。要注意使用这种方法时要对向量排序的比较函数进行更改，当两个元素的width值相同时，我们将height由大到小排列，避免在后面求最大递增序列时，相同的width值情况下的height递增也算进去了。
- 注意只要是涉及到求最长递增子序列的问题，都要用上述二分法+DP算法解决。
解题思路：
- 十分巧妙的算法，温习了以前的算法，事实证明学过的东西还没能做到活学活用。NO BUG FREE。
355. Design Twitter
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:
- postTweet(userId, tweetId): Compose a new tweet.
- getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
- follow(followerId, followeeId): Follower follows a followee.
- unfollow(followerId, followeeId): Follower unfollows a followee.
Example:
Twitter twitter = new Twitter(); // User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1); // User 1 follows user 2.
twitter.follow(1, 2); // User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6); // User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1); // User 1 unfollows user 2.
twitter.unfollow(1, 2); // User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);
解题思路：
- 用时间戳来记录推特发布的时间，每发一个推特就将时间戳+1，保证每条推特的时间戳都不一样，而且按照先后顺序从小到大。用map<int, set<int>>来存储每个用户关注的用户集合，用map<int, priority_queue<int, int>>来存储每个用户发布的推特，pair<int, int>分别是推特发布的时间戳和推特id，用优先级队列存储会自动将这些推特按照时间戳从大到小排序，在取最新的推特列表时很方便。
- 在取最新的10条推特列表时，用一个优先级队列存储该用户和他所关注的其他用户的前10条推特信息，然后从队列输出前10条加入返回向量中即可。
- 要努力尝试和相信自己的想法和数据结构，任何事情完成的第一步就是去做。
357. Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
- 虽然由Unique Digits组成的数比较多，而非Unique的数比较少，但是寻找非Unique的数起来算法非常麻烦，而且计算量较大，代码不具有一致性。因此我们还是从正面直接寻找由Unique Digits组成的数，一位数有10个，二位数有9*9，三位数有9*9*8，四位数有9*9*8*7个，依次类推，利用这个规律循环来找。注意当位数太大，有10位数时，必然不存在每位数字都不相同的数，所以在循环时还需要加上一定的限制条件。
- 一定要注意思路的转换，当反面思路困难的时候，要尝试从正面去思考和解决问题。
363. Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
Example:
Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2
The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).
Note:
- The rectangle inside the matrix must have an area > 0.
- What if the number of rows is much larger than the number of columns?
- 本题是一个经典的问题，一定要熟练掌握，设m为matrix的行数，n为matrix的列数。本题对matrix的列进行双层遍历，确定子矩形的宽，时间复杂度为O(n^2)，然后在内部对矩形的行进行遍历，计算在当前列的情况下，哪些连续行的结果相加最接近于目标值k（可以认为是求数组的子数组的最大和问题，这里是小于等于k的最大值）。这样整个算法的时间复杂度就为O(m*n^2)。
- 在对行遍历时求行的子向量和最接近于k的问题时，可以将0~i行的sum结果加入到一个集合set<int>中，然后对于当前的curSum，我们在集合中找最小的大于等于curSum-k的数（即之前更小的矩形sum大于等于curSum-k，那么用curSum减去这个小矩形的sum就为当前行到之前行所组成的最接近于k的矩形的sum），这一点我们可以用集合的lower_bound()函数来快速实现。注意在set中事先插入一个0，避免curSum <= k时，还减去一个正数。
- 由于时间复杂度对于矩形的行和列来说不是对称的，所以我们优先选取n为较小的行或列能确保时间复杂度最优化。
刷题记录：
- 求数组的子数组的最大和问题一定要熟练掌握，本题也要熟练掌握，NO BUG FREE。
365. Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:
- Fill any of the jugs completely with water.
- Empty any of the jugs.
- Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
- 此题要理解题目的意思，不是说用x，y两桶运水将z装满的意思，而是用x和y现有的容量承载z的容量，因此当z > x+y时，明显是无法做到的，返回fasle。
- 根据贝祖定理，假设x，y为非零的整数，d为它们的最大公约数(greatest common divisor)，那么d是最小的正整数能被写成ax+by = d，其中a，b均为整数。所有能被写成ax+by的整数都是最大公约数d的整数倍。推论：如果存在a和b，使ax+by = 1，那么1就是x和y的最大公约数，即x和y互质。
367. Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
解题思路：
- 求一个数的平方根和判断一个数是否为平方数有多种方法：首先是1+3+5+...的方法，因为(n+1)^2-n^2 = 2*n+1，所以一个平方数可以写成这种形式，我们可以将要求的平方数依次-1，-3，-5直到结果为0或者小于0。如果结果为0，证明其是平方数，返回true；如果结果<0，证明其不是平方数，返回false。
- 第二种方法是二分查找法，找其平方根，因为一个数的平方根一定是在0~num（其本身）范围内的，所以我们初始化low = 0, high = num，根据mid * mid与num的大小比较可以对low和high进行修改，即可找到其平方根，如果循环结束high < low，说明平方根不存在，原数不是平方数。
- 另一种方法是用牛顿迭代法求平方根，对于f(x) = 0求其根，任意取一个起始位置x0，判断x0是否是方程的根（即使等式成立）。如果不是，那么过(x0, f(x0))作f(x)的切线，切线与横坐标相交的点x1一定是更接近于方程的根的，所以用x1继续循环...直到xn * xn与num的差值小于阈值时，我们认为xn即为方程的根。在本题中，问题具体化为f(x) = x^2 - num，所以迭代式也更加明亮，x(n+1) = [x(n) + num/x(n)] / 2。初始值可以设定为num本身，当x * x >= num时继续循环，当x * x < num时，显然说明num的平方根不为整数，因此返回false。
刷题记录：
- 虽然简单，但是很经典的问题，一定熟练掌握，NO BUG FREE。
368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3] Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8] Result: [1,2,4,8]
- 将原向量从小到大重新排列后，可以用DP算法求出符合条件序列的最大长度，因为如果nums[i] % nums[j] == 0(i > j)，那么比nums[j]小的能整除nums[j]的数一定也能整除nums[i]，所以到nums[i]为止的最大长度应该为j下标对应的最大长度+1。外层循环到i，就内层遍历0~i-1的数是否能被nums[i]整除即可，就能得到到nums[i]为止的最大符合条件的序列长度，循环结束我们就能知道最大的序列长度。
- 但是题目中不光要求我们求最长序列长度，还需输出这个序列是由哪些元素组成的，因此我们定义一个向量用来存储每个元素的前驱元素的下标，定义一个int型变量index用来存储最长序列的最后一个元素的下标。当输出结果使，循着index和其前驱push_back所有的元素即可。没有前驱（即序列中第一个元素的前驱为-1）。
刷题记录：
- 很好的思路，减少了无谓的空间存储，NO BUG FREE。
371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator +and -.
Example:
Given a = 1 and b = 2, return 3.
- 求两个整数的和，无论两个数是整数或者负数，在二进制中都是可以直接相加的，因为负数在计算机中也是用补码表示的，负数和负数相加就等于其补码相加。
- 用a^b来求两个数经过一部计算后各bit位上的结果，用a&b来表示各位上有没有进位，如果a&b != 0，那么继续循环，将进位信息左移一位（因为进位都是往高位+1的）后将得到的结果再和进位做同样的处理，循环直到进位为0，即得到了最终的结果。
372. Super Pow
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
a = 2
b = [3] Result: 8
Example2:
a = 2
b = [1,0] Result: 1024
- 这个题目的难点在于数很大，如果直接循环，可能会出现次幂数过大，超出int整型所能表示范围的问题。因此需要把大指数的乘方转化为小指数乘方，而且由于指数是用向量一位一位的表示的，需要用合理的方式将这些数位单独计算会比较方便。
- 利用恒等式(a*b)%k = ((a%k)*(b%k))%k，可以将向量的前面位和最后一位分割开，比如2^1234567%k = (2^1234560%k) * (2^7)%k = (2^123456%k)^10%k * (2^7)%k，因此将向量的前半部分和最后一位完全分隔开，前面部分可以用递归调用继续计算。
刷题记录：
- NO BUG FREE。
373. Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Example 1:
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence:
[1,3],[2,3]
- 迅速找到相加最小和的组合，合适的存储结构就是优先级队列，优先级队列按照和小的优先级高的顺序排列，定义一个数组用来存储nums1向量中每个元素在nums2对应候选pair<int, int>的下标，注意哪些组合能成为候补元素。如果当前最小的组合是nums1[i]+nums2[j]，那么当前nums1[i]+nums2[j+1]就是对应于nums1[i]的候补搭档，他们就是候补组合。而且如果i是当前nums1加入候补的最后一个元素的话，还需要将pair<int, int>(nums1[i+1], nums2[0])加入候补。循环直到k == 0或者队列为空。
- 另一种更简单的方法，可以避免多定义一个向量来存储对于nums1中每个元素在nums2中对应候补元素的下标，就是将[nums1[i], nums2[j], j]组合成一个数组作为优先级队列的元素，优先级队列的排列规则可以自定义，我们就自定义为数组前两个元素和较小的元素优先级较高，就可以达到所需要的效果。如果当前元素输出，就直接将[nums[i], nums[j+1], j+1]重新加入到队列中即可。
刷题记录：
- 要相信自己的判断和对数据结构的选择，去尝试就会发现是对的，注意优先级队列的灵活运用，NO BUG FREE。
374. Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6. Return 6.
解题思路：
- 基本的二分查找问题。
375. Guess Number Higher or Lower II
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
- 此题没有太多的技巧和固定的规律，只能通过dp算法迭代去求解。由于求长序列猜测数所需的最少金币数需要用到每个小序列，所以选择逆向的dp。序列长度从2延伸到n，对于每一个序列进行动态规划过程时，都需要对序列中的数进行遍历，每个数都将原序列分隔为左右两个子序列，然后分别求左右子序列所需的最少金币。左边的子序列在序列长度不断延伸的过程中已经求得，那么分割点就需要从右边往左边遍历，使得右边序列的长度越来越大，已经计算过的序列越来越多，为后面的分割点计算提供结果。
- 除此之外，也可以采用递归函数的方法，要求1~n的数序列猜测所需的最小金币，就等于i+max(0~i-1，i+1~n)，所以继续用递归求0~i-1和i+1~n的序列最小值，直到序列长度为1时返回0。记住在递归的过程中将已经求得过的子序列的需要金币数写入数组中，方便之后的递归需要使用时直接调用，避免重复计算。
刷题记录：
- 反向的DP和正向的递归的经典题目，需要牢牢掌握，NO BUG FREE。
376. Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence. Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8]. Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?
- 此题就是一个交替找大于或者小于前一个数的问题。在选择和前面的哪一个数进行比较时有一定的技巧，如果当前要从i+1位置开始找比i小的数，那么如果i+1位置上的数大于等于i位置上的数，其实我就只需要找比i+1位置上的数小的数就可以了。因为被比较的数越大，后面找比它小的数越容易，所以相当于任何情况下我都只需要和前一个位置上的数做比较就可以了，如果比前一个位置上的数小，那么跳出循环，将flag取反，继续找大于前一个位置上的数；如果比前一个位置上的数大，那么将当前位置上的值作为比较标准，在下一个循环里比较它就相当于比较前一个位置上的数。所以循环的形式变得相当简单。
刷题记录：
- 自己的思路和写法比讨论区post出来的解法都要简单高效，所以要相信自己去尝试，NO BUG FREE。
377. Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4 The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
- 由于本题对组成target的数的顺序不作要求，不用的顺序算作不同的组合，因此可以直接用DP算法解决这个问题，求出1~target所有组合的数目。
- 很多时候迭代算法出现TIME LIMIT EXCEEDED的时候都要考虑能否转化为DP问题。
378. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8, return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
- 如果一个序列是按照index呈线性有序的，那么我们可以对下标index做二分法查找；但是如果一个序列不是线性有序的，而是像题目中一样是两个方向递增的，我们只知道最大值和最小值，所以只能对元素的范围进行二分法查找。
- 每次确定mid值以后，对matrix数组进行遍历，根据数组中小于等于mid值的元素数量count与k做比较来对low和high进行调整，由于是整数，所以我们对low = mid+1的幅度递增，一定不会错过最后所需的数，只要mid不是我们最终寻找的数，比目标数要小，那么小于等于mid的数一定是小于k的，然后对low = mid+1慢慢递增。最后low = high时，即为目标值。
刷题记录：
- 本题和以前的二分法问题不同，本题是对范围进行二分法，不是对下标。NO BUG FREE。
380. Insert Delete GetRandom O(1)
Design a data structure that supports all following operations in average O(1) time.
-
insert(val): Inserts an item val to the set if not already present. -
remove(val): Removes an item val from the set if present. -
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1); // Returns false as 2 does not exist in the set.
randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2); // getRandom should return either 1 or 2 randomly.
randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1); // 2 was already in the set, so return false.
randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
解题思路：
- 由于集合或者map都是不存在顺序的，不是一个连续结构，所以其迭代器虽然可以通过自增依次访问其包含的所有元素，但是迭代器无法直接加上一个随机数。想要随机读取元素，只能采用顺序结构，也就是vector。我们定义一个map来存储集合中的所有元素和其在nums向量中对应的位置，添加元素数就将nums最末的位置写入。如果需要删除某个元素时，我们首先读取该元素在向量中位置，如果直接从该位置删除元素，那么后续元素都需要前移，时间复杂度为O(n)。为了避免这样，我们可以将待删除元素的位置写入当前向量的末位元素，修改末尾元素在向量中的位置，然后将末尾元素删除就可以将时间复杂度降至O(1)。
- 在随机读取向量中的元素时，我们需要生成在0~nums.size()-1范围内的随机下标，通过定义随机数种子，调用随机数函数rand()对向量的大小取余做到。
刷题记录：
- NO BUG FREE.
381. Insert Delete GetRandom O(1) - Duplicates allowed
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
-
insert(val): Inserts an item val to the collection. -
remove(val): Removes an item val from the collection if present. -
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1); // getRandom should return 1 and 2 both equally likely.
collection.getRandom();
解题思路：
- 与上题的思路类似，只不过map结构的value值变成了set<int>用来存储当前元素在向量中的多个位置。
382. Linked List Random Node
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
Example:
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head); // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
- 从前往后遍历链表，将元素的选择转化为一个概率论问题，当指针遍历到第i个元素(i下标是从0开始计数的)，有1/(i+1)的概率(这一点用随机数来实现，rand()%(i+1) == i)将结果改写为该结点的值，如果最终结果能保持这个值一直到最后的概率为1/(i+1) * (i+1)/(i+2) * (i+2)/(i+3) * …… * (len-2) / (len-1) * (len-1) / len = 1/len，因此每个元素被选中的概率都为1/len。所以这是一个随机选择。
刷题记录：
- 这是一个涉及概率论知识的问题，NO BUG FREE。
383. Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
解题思路：
- 用一个数组letter来存储每个字符的数量，可以先遍历magazine数组，来存储所有的可以用来组成ransom note字符串的字符以及其数量。然后遍历ransom note字符串，如果存在某个字符，letter中其数量已经<=0时，立即返回false。可以减少多一次对letter的遍历。
384. Shuffle an Array
Shuffle a set of numbers without duplicates.
Example:
// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle(); // Resets the array back to its original configuration [1,2,3].
solution.reset(); // Returns the random shuffling of array [1,2,3].
solution.shuffle();
解题思路：
- 重点在于打乱数组，一定要学会连续取随机数对对应位置上的数进行交换的方法，随着循环的进行位于j位置上的数交换到位置i上的概率为1 / (j+1) ,之后保持不变的概率为(j+1）/ （j+2) * (j+2) / (j+3) * (j+3) / (j+4) *... * (len-2) / (len-1) * (len-1) / len，所以总概率为1/len，所以每个元素出现在每个位置上的概率都相同，打乱为等概率的。
- 另外，对一个向量做处理时，如果需要删除向量中间位置的某个元素，可以将其与最末位置的元素相交换后pop_back()使得删除元素的时间复杂度降为O(1)，这样做的前提在于元素的排列顺序不影响问题的解决。
刷题记录：
- 概率论的思路很精妙，NO BUG FREE。
385. Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:
- String is non-empty.
- String does not contain white spaces.
- String contains only digits
0-9,[,-,,].
Example 1:
Given s = "324", You should return a NestedInteger object which contains a single integer 324.
Example 2:
Given s = "[123,[456,[789]]]", Return a NestedInteger object containing a nested list with 2 elements: 1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789.
解题思路：
- 如果给的字符串只包含数字，没有'['，说明这个类的对象只有一个integer，将这个字符串表示的数加入到当前对象中返回即可。但是只有存在'[',']'，那么里面的无论是数，还是嵌套的list都是作为新的NestedInteger存在的。因此需要用栈来存储之前的对象，具体的方法是遍历字符串，如果遇到'-'或'0'~'9'，就顺序读取这个数作为新的NestedInteger对象加入到当前对象中；如果当前字符为'['，如果当前指针不为空，就将当前指针指向的NestedInteger对象加入到栈顶，然后当前指针申请一个新的NestedInteger对象空间，用来存储嵌套对象；如果当前字符为']'，且栈非空，那么把当前对象加入到栈顶对象的元素中去。
- 要注意类对象的申请，也是要通过指针来申请的。
刷题记录：
- 对题目的意思不明，几种情况分别有什么差别不明。NO BUG FREE。
386. Lexicographical Numbers
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
解题思路：
- 这个题要将1-n的整数按ASCII码字典编纂的顺序排列，我们通过观察规律，可以使用循环加递归的方式。数字的首字符一定是1~9，后面的循环就是一样的了，优先什么都不加，将当前数字加入结果向量中。然后当前数字乘以10后依次加上0，1，2，...，9后调用原递归函数即可。
387. First Unique Character in a String
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0. s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
解题思路：
- 用一个大小为26的一维数组存储每个字符出现的次数，第一次遍历字符串对字符信息进行统计。第二次遍历数组，如果当前字符对应的出现数量为1的话，说明它是第一个Unique Character，返回其下标i，否则返回-1。
388. Longest Absolute File Path
Suppose we abstract our file system by a string in the following manner:
The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"represents:
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory dir contains two sub-directories subdir1 and subdir2. subdir1contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.
We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).
Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.
Note:
- The name of a file contains at least a
.and an extension. - The name of a directory or sub-directory will not contain a
..
Time complexity required: O(n) where n is the size of the input string.
Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
解题思路：
- 用一个栈或者数组来存储之前路径层的长度，以'\n'作为分割符，通过读取当前字符串的'\t'的数量来确定当前路径的层数，找到栈或者数组中对应截止到上一层路径的长度。如果当前层为子目录，那么将当前路径的长度加上上一层路径的长度的结果加入栈或者向量中；如果当前层为文件，那么用文件名的长度加上上一层的路径长度，与我们存储最长长度的向量作比较，取最大值。
- 用栈来存储的话，需要返回的出栈，来访问到其上一层的结果；如果使用数组的话可以避免这个问题，可以直接访问对应上一层的长度，并且对当前层直接做修改。在读取当前用'\n'分割的'\t'的个数时，可以不用流循环读取，直接调用string的成员函数find_last_of()即可。string结构的和查找有关的成员函数，如果找到返回其下标，如果没有找到，返回string::nops。
389. Find the Difference
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde" Output:
e Explanation:
'e' is the letter that was added.
解题思路：
- 用一个长为26的数组来存储每个字母的数量情况，如果在字符串s中出现，就--，如果在字符串t中出现，对应位置就++。完成对t和s的遍历之后，遍历数组，如果数组某一位置上的值不等于0，即大于0，那么返回当前位置对应的字母。
390. Elimination Game
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Find the last number that remains starting with a list of length n.
Example:
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6 Output:
6
解题思路：
- 定义一个变量用来存储剩下的元素个数n，head变量用来存储最左边的数，step变量用来存储当前消除的步长，每次循环step = 2*step。每当最左边的数在一次循环中能被消除时，就将head改写为head+step，为新的最左端的数。当循环从左往右消除时，或者从右往左消除且当前剩余数为奇数时，最左边的数会被消除，此时需要改写最左端的数。直到剩余数的数量为1时，返回当前最左边的数head即为返回结果。
刷题记录：
- 要学会定义相应的变量来确定当前数列消除的情况。NO BUG FREE。
391. Perfect Rectangle
Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).
Example 1:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
] Return true. All 5 rectangles together form an exact cover of a rectangular region.
Example 2:
rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
] Return false. Because there is a gap between the two rectangular regions.
Example 3:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
] Return false. Because there is a gap in the top center.
Example 4:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
] Return false. Because two of the rectangles overlap with each other.
解题思路：
- 这种表示比较复杂的问题，一定要想办法把问题进行转换，比如将原题中的是否能组成一个完美矩形转化为向量中的点或者其他信息满足什么条件时能组成完美矩形。发现需满足以下两个条件：1 首先所有小矩形的面积和与所有小矩形中由最右下角的点和最右上角的点所决定的大矩形的面积相等。2 小矩形在拼凑成整个大矩形的过程中，边界点是正好吻合的，也就是说，所有的内部四个角的点都出现两次，只有最外侧决定大矩形边界的四个角上的点只出现一次。
- 因此，我们对小矩形向量进行遍历，求出所以小矩形的面积和，将x1取所有矩形左下角点横坐标的最小值，y1为纵坐标的最小值，x2取所有矩形右上角点横坐标的最大值，y2为纵坐标的最大值。用一个集合来存放代表所有小矩形的四个角上的点，如果集合中已经存在这个点，那么将其从集合中删除，否则插入集合。用set.insert()函数的返回值，可以方便判断其在集合中是否存在，返回值为pair，第二个变量为bool，true代表不存在，false代表存在。那么最终所有的重复点都会删除，只留下外边界的四个点。
刷题记录：
- 注意思路和判断条件的转换。NO BUG FREE。
392. Is Subsequence
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
s = "abc", t = "ahbgdc"
Return true.
Example 2:
s = "axc", t = "ahbgdc"
Return false.
Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
- 定义一个变量pos用来指定模式串s需要比较的位置，遍历目标串t，如果t当前位置的字符与s[pos]相同，那么pos++，直到pos等于s.size()时，说明s中所有的字符都在目标串t中按顺序存在，返回true。否则返回false。
393. UTF-8 Validation
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
- For 1-byte character, the first bit is a 0, followed by its unicode code.
- For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001. Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100. Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.
解题思路：
- 利用按位与&运算符，对数值的高位依次进行讨论，如果出现多位的utf-8编码，就讨论后续的整型数是否为规定的10******，如果不是就返回false，如果是就继续循环。
394. Decode String
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
解题思路：
- 使用栈的方法，将当前的前缀字符串和需要重复的次数存入栈中。顺序读取输入字符串，如果是数字，那么在num*10的基础上加上这个数字；如果是'['，将当前数字和字符串都加入对应的栈中，然后将数字和字符串都重置；如果是']'那么将当前字符串重复栈顶的数字次，然后加上之前栈中存放的前缀字符串得到的结果赋给当前的字符串ans；如果是其他字符，那么直接加入到当前字符串的尾部即可。
- 与字符串相关的问题，一般都可以用顺序遍历的方式来解决，根据读取到的字符的不同有不同的处理方法。
395. Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3 Output:
3 The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2 Output:
5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
解题思路：
- 使用递归的方法很好的简化了算法的过程。首先对当前的字符串进行遍历，统计其中每个字符出现的次数，统计完成后重新遍历字符串。如果遍历到某个位置，对应字符的数目不为0，且小于要求的整数k，那么最长字符串中这个字符是一定不会加进来的。所以可以从这个字符的当前位置做个分段，调用原函数求当前位置的左子串和右子串的最长符合条件的字符串，然后取其较大值即可。
396. Rotate Function
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:
A = [4, 3, 2, 6] F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
解题思路：
- 要注意旋转前和旋转一次后得到的F函数直接的关系，假设sum为向量A中所有元素的和，那么F(n+1) = F(n) + sum - n*A[n-1]。A[n-1]代表当前旋转前向量的末尾元素。将其与最大值比较取较大即可。因此可以在O(n)的时间复杂度内解决这个问题。
397. Integer Replacement
Given a positive integer n and you can do operations as follow:
- If n is even, replace n with
n/2. - If n is odd, you can replace n with either
n + 1orn - 1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Input:
8 Output:
3 Explanation:
8 -> 4 -> 2 -> 1
Example 2:
Input:
7 Output:
4 Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1
解题思路：
- 要想一个正整数最快的减小到1，除以2当然是最好的方式。因此如果当前数为偶数，我们就直接将其除以2；如果当前数为奇数，即2k+1，那么将其加一或者减一得到的效果是不一样的。加一得到2k+2，除以2得到k+1；减一得到2k，除以2得到k，显然k和k+1一定有一个偶数和一个奇数，为了尽可能多的使当前数为偶数，方便直接除以2。我们选择对奇数加一或者减1的依据就在于除以2之后是否还是偶数，即数的倒数第二位是否为0，如果为0，那么减一后末尾至少有两个0；如果为1，那么加1后末尾至少有两个0。
398. Random Pick Index
Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
解题思路：
- 不使用过大的额外存储空间来完成目标数的下标的随机选择，需要对整个数组进行遍历，每当遇到一个当前目标数时，就将其总数count++，然后在count范围内生成随机数，当随机数为某一值时，将index改写为当前的元素下标。因此将index改写为当前元素下标的概率为1/count，保持到最后不被改写的概率为count/(count+1)*(count+1)/(count+2)*...*(n-2)/(n-1)*(n-1)/n。所以每个元素下标被选取的概率均为1/n。
399. Evaluate Division
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
解题思路：
- 用map结构来存储以某一字符串作为被除数时，已经求出的除数以及他们的结果。然后如果出现新的待求的除法算式，就用深度优先遍历去查找即可，用一个set<string>结构来存储已经寻找过的被除数，在深度优先遍历进行递归时，首先是判断当前字符串作为被除数是否已经遍寻过，而且要判断当前被除数除以除数是否有解，是否不等于-1，如果等于-1那么也没必要对此除数进行递归。
400. Nth Digit
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3 Output:
3
Example 2:
Input:
11 Output:
0 Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
解题思路：
- 循环减去不同长度的整数所能涵盖的数位数，以此来判断第n位数字是出现在多长的整数中。然后用剩下的n除以当前整数的位数，找出第n位数字是出现在哪一整数中，余数为当前整数的第几位。在求第几位整数的过程中，千万不要跟求二进制第几位搞混淆，不能用位运算符，可以将整数转换为字符串后直接读取来做。
- 注意当遇到比较大的整数相乘时，要考虑超出整型数表示范围的问题，所以要将需要的数提前表示为long long类型。
401. Binary Watch
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
For example, the above binary watch reads "3:25".
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
Note:
- The order of output does not matter.
- The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
- The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".
解题思路：
- 用排列组合的方式先寻找在10个灯中随机选取num个亮的不同情况，在这里我们使用一个整数的最后10个bit位来表示这些灯的亮灭情况。'1'代表亮，'0'代表灭。得到所有排列组合的整型向量后，再将这些整数转化为对应的string，取整数的后6位为minutes，往后将后6位移出后为hour，当hour>11或者minutes>59时，跳过当前数。
402. Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
解题思路：
- 自己的方法是用递归，将前k个字符中最小的数字进行保留，然后对后面的字符串进行递归调用，将其得到的字符串加到之前保留的数字后面。
- 也可以使用顺序存储的方式，遍历原字符串，如果当前字符比结果向量尾部的字符小，且k>0，即还可以继续删除字符，就将当前字符前移，直到找到大于或等于前一位置字符的位置，将当前字符存入即可。注意当结果字符串已经满，后序字符比结果字符串尾部的字符大时，不进行存入操作，也需要将k--，因为如果后部的更小的字符需要存入结果向量中，首先就要先将其之前的字符删除。
刷题记录：
- 思路不是很难，但是很多细节的操作容易出现漏洞，NO BUG FREE。
403. Frog Jump
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
- The number of stones is ≥ 2 and is < 1,100.
- Each stone's position will be a non-negative integer < 231.
- The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17] There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit. Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11] Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.
解题思路：
- 用一个map<int, set<int>>结构来存储在每个石头下一步能走的步数，从前往后遍历所有的石头，根据键值遍历其下一步能走的步数，如果加上下一步的值为最后一个石头的值，那么返回ture；如果下一步走到的位置的石头存在，那么在该石头代表的value值中加上当前步数step，step-1和step+1。从前遍历石头，由于每一个石头都是由前面的石头跳过来的，所以访问完前面的石头，也就确定了所有从当前石头能跳跃的步数。
- 也可以用深度优先遍历来解，如果从上一石头跳到当前石头使用的步数为step，那么如果从当前石头跳step，step-1或step+1步后得到的index石头存在，那么递归调用这一石头，将跳跃步数作为参数传入。如果当前是否为最后一个石头，那么返回true；如果递归函数返回true，当前函数也返回true。
刷题记录：
- NO BUG FREE。
404. Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
解题思路：
- 原函数中的参数根结点一定不是符合条件的左叶子，因此我们在递归调用原函数时一定要首先确认根结点不是符合条件的左叶子。所以我们首先对根结点的左子结点情况进行探讨，如果左子结点的左右子结点都为NULL，那么它是符合条件的左叶子，返回其val值+递归调用根结点的右子结点（因为右子结点显然不符合条件）。如果它不是符合条件的左叶子，那么递归调用根结点的左右子结点，返回其和。
405. Convert a Number to Hexadecimal
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
Note:
- All letters in hexadecimal (
a-f) must be in lowercase. - The hexadecimal string must not contain extra leading
0s. If the number is zero, it is represented by a single zero character'0'; otherwise, the first character in the hexadecimal string will not be the zero character. - The given number is guaranteed to fit within the range of a 32-bit signed integer.
- You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:
Input:
26 Output:
"1a"
Example 2:
Input:
-1 Output:
"ffffffff"
解题思路：
- 将一个十进制整数转化为十六进制的问题，其实就可以转换为将其二进制补码转化为十六进制，因此只需要对其二进制补码进行位操作，每次读取最低四位，转换为相应的十六进制数，直到当前数为0停止循环，当前数为0说明高位都为0，没有继续转换的必要。
406. Queue Reconstruction by Height
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and kis the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
解题思路：
- 将原向量按照高度递减，相同高度的情况下前面比他高的人数递增的顺序重排列，然后对整个向量遍历，使用直接插入排序即可。当遍历到某个元素时，由于前面所有的元素都是比他高的，即比他高的所有元素都已经在结果向量中排列完毕，因此根据pair对的第二个元素，他前面有几个比他高的人，就插入到res.begin()+人数位置即可。
407. Trapping Rain Water II
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
] Return 4.
The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
After the rain, water are trapped between the blocks. The total volume of water trapped is 4.
- 如果中间的某个block存在积水，那么它的高度一定是小于四周的最小高度的。因此这是一个从外围逐渐往里面遍历的问题，首先将最外围的方块的高度和代表其位置的整型数pair加入到优先级队列中，优先级队列按照从小到大的顺序排列，可以直接用库里的比较函数作参数，即priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>。
- 然后按顺序遍历队列，由于当前出队的是当前高度最低的block，所以如果其四周有未入队而且高度比它还低的block，那么一定能积水。维护一个二维数组来存储每个位置的block是否已经入队（即计算其积水）。
- 注意二维数组的定义和初始化都是用大括号，而且高维的大小可以不显示声明，低维的一定要声明。
刷题记录：
- 细节方面存在很多问题，NO BUG FREE。
409. Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd" Output:
7 Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
- 题意是用参数字符串中的字符去组成最长的回文字符串，而不是意味着使用某个字符的全部。因此对于出现偶数次的字符，直接加上即可；对于出现奇数次的字符，加上其减一的偶数次。最后如果返回结果与字符串长度相同，说明字符串中所有的字符都是偶数次的，返回即可，如果不同，可以在中间加一个字符，即返回结果加一。
410. Split Array Largest Sum
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note:
If n is the length of array, assume the following constraints are satisfied:
- 1 ≤ n ≤ 1000
- 1 ≤ m ≤ min(50, n)
Examples:
Input:
nums = [7,2,5,10,8]
m = 2 Output:
18 Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
解题思路：
- 根据最后返回结果的范围，用二分法来解决这个问题，将原数组划分为m个非空数组，其数组的最大值中最小显然为单个元素的最大值，而最大为整个数组的元素和，因此我们根据划分后所有数组的最大和来进行划分，看能否满足我们的要求。如果划分得到的数组个数大于m，说明当前这个mid是偏小的，如果将数组剩下元素划分到m个中去，其最大子数组的和一定是大于mid的，因此将low=mid+1;如果划分得到的数组个数是小于等于m的，那么mid可能为合适的划分，将high=mid，循环直到low=high时结束，由于最后的返回结果一定为一个确定值，所以返回此时的low或high即可。
刷题记录：
- 反向利用可能的子数组最大和来看能否合适的划分，NO BUG FREE。
412. Fizz Buzz
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15, Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
解题思路：
- 如果不用取余的方式，可以定义两个整型变量fizz和buzz随着整数的增加而变化，当fizz和buzz同时变成3和5的时候，写入“FizzBuzz”，并将其重置为0；反之当fizz为3，写入“Fizz”，重置为0；当buzz为5的时候，写入“Buzz”，重置为0。
413. Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4] return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
- 用一个int型变量diff存储之前的相邻元素差值，如果当前位置的元素与前一元素的差值与其相同，则不同的连续子数组的个数应加上i-start+1（start为等差序列开始的位置），因为由当前元素引入的等差数列一定包含当前元素；反之，将start改写为前一个元素，diff改为当前元素与前一元素的差值。
414. Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1.
Example 2:
Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
- 定义并初始化3个long long类型变量first，second，third为INT_MIN-1，目的是一定比向量里整型数的表示范围要小，否则无法直接根据third的值判断其是存在为INT_MIN，还是不存在。注意将INT_MIN直接带入运算时会自动默认变量类型为int，而不单纯表示一个数，所以需要强制转换一下数据类型。按照答案的思路，也可以用将int类型初始化为null的方式。
415. Add Strings
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
- The length of both
num1andnum2is < 5100. - Both
num1andnum2contains only digits0-9. - Both
num1andnum2does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
解题思路：
- 从两个代表数字的字符串的最高位依次遍历到最低位即可，注意循环条件是i >= 0 || j >= 0。因为字符串的最低位下标为0。
416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
解题思路：
1. 可以将该题转化为一个求数组中是否能找出部分元素之和等于其数组总和一半的问题。因此，首先使用叠加的方法求数组的元素和，取其一半为目标。
2. 因为数组中每个元素都可能取或者不取，所以理论上有2^n种组合方式，使用递归的方法会导致时间复杂度过大，出现TLE。使用动态规划的方法，dp[i][j]表示是否能用数组的0～i的元素组合成j，关系式为dp[i][j] = dp[i-1][j] || j >= nums[i] && dp[i-1][j-nums[i]，分别代表不将第i个元素和将第i个元素算入组合中的情况。由于当前循环j的状态值依赖于上一循环小于j的状态值，所以内层循环j由sum到1，从后往前，而且当j大于当前元素nums[i]时停止内层循环，因为nums[i]肯定加不进去，dp[i][j] = dp[i-1][j]。
刷题记录：
1. 思路和动态规划的构造方法很奇特，NO BUG FREE。
417. Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
- The order of returned grid coordinates does not matter.
- Both m and n are less than 150.
Example:
Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic Return: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
- 思路没有问题，就是从海岸线上的点往四周比它高的点进行循环递归，来找到所有能流到某个海洋中的点。可以定义两个2维向量来存储流向两个海洋中的情况，更好的方法是定义1个整型二维向量，用最后两个bit的情况分别表示流往两个海洋的情况，最后输出整型数为3的点，即最后两个bit为11，代表可以流往两个海洋。
419. Battleships in a Board
Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:
- You receive a valid board, made of only battleships or empty slots.
- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape
1xN(1 row, N columns) orNx1(N rows, 1 column), where N can be of any size. - At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships.
Invalid Example:
...X
XXXX
...X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
- 寻找每一个水平battleship和垂直battleship开始的点，将结果+1，怎样是一个battleship的开始呢？当前点为'X'，且其上边和左边均不为'X'。
420. Strong Password Checker
A password is considered strong if below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It must NOT contain three repeating characters in a row ("...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.
解题思路：
- 从简单的步骤到难的步骤说起，首先针对条件2，定义并初始化三个整型变量为1，分别记录是否需要补充小写、大写、数字字符。在增加、删除和替换三种处理方式中，增加和替换操作是可以同时解决条件2的问题的，删除操作不行。
- 遍历字符串的过程中，统计其不满足条件3（即单一字符重复大于等于3次的连续字符串的长度），存储的时候按照 len % 3 的值进行存储，因此定义 vector<vector<int>> repeat(3, vector<int>()) 的数据结构，下标即为对3取余的值，向量中的数值为实际长度。在处理的时候优先选择使其满足条件3时的最小操作数，即尽可能使经过增或删操作之后的重复字符串的长度对3取余为2，那么经过少量的替换操作比连续的删除更有效。而且优先对 对3取余小的重复字符串 进行删减，因为对3取余越大，进行删减的代价就越高。删减完后改写得到的重复字符串长度，再除以3为需要替换的字符串个数。
- 然后再对上述操作进行分析，如果此时需要删除的字符串个数仍大于已删除的，即还需要继续进行删除操作，就可以把之间替换的操作换成删除操作，因为删除操作是必须做的，剩下的删除次数每除以一个3，就可以减少一个替换操作。如果删除的次数超过了应该删除的次数，超出的那一次就可以换成替换操作。
- 最后 toDel + max(toAdd + rep, upper + lower + digit) ,将添加和替换的次数与需要使其满足条件2的次数对比，取其最大值。
- c++库函数包括isupper()、islower()和isdigit()用来判断一个字符是否为大写、小写和数字字符。
刷题记录：
- 很难，思路很奇妙，需要反复写几遍，NO BUG FREE。
421. Maximum XOR of Two Numbers in an Array
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.
解题思路：
1. 依次提取向量中所有数的前i位高位得到的数加入到集合中便于快速的查找异或后的数是否存在，将之前得到的 max 值与当前位的1异或得到当前位为1的可能的最大值，然后再看这个最大值与集合中的提取出的所有数的前i位异或得到的结果是否存在，如果存在，说明当前的最大值是有效的，将max改写为最大值temp，继续下一循环；如果不存在，那么保持当前的max值，继续探寻下一位是否可能为1。直到循环完所有位。
2. 这个题用字典数也可以很好的解决，用字典树的结构来存储数组中每个树从最高位bit到最低位bit的信息，在对某一元素求向量中其他元素与其最大异或时，从字典树的根结点往下遍历，优先选取使高位bit异或为1的树分支，即与当前数bit位相反的bit位，这样异或结果为1；如果不存在，只能取与其bit位相同的分支向下生长。
刷题记录：
1. NO BUG FREE。
423. Reconstruct Original Digits from English
Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.
Note:
- Input contains only lowercase English letters.
- Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
- Input length is less than 50,000.
Example 1:
Input: "owoztneoer" Output: "012"
Example 2:
Input: "fviefuro" Output: "45"
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2 Output:
4 Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1 Output:
4 Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
解题思路：
Implement a data structure supporting the following operations:
- Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
- Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
- GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string
"". - GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string
"".
Challenge: Perform all these in O(1) time complexity.
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
解题思路：
1. 可以选择按字符往后遍历，也可以定义并初始化字符串输入流istringstream in(s); 然后使用in >> word来依次读入单词，以空格或结尾为中断，当读入字符串为""时，返回结果为false。
435. Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
- You may assume the interval's end point is always bigger than its start point.
- Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ] Output: 1 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [ [1,2], [1,2], [1,2] ] Output: 2 Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
- You may assume the interval's end point is always bigger than its start point.
- You may assume none of these intervals have the same start point.
Example 1:
Input: [ [1,2] ] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: [ [3,4], [2,3], [1,2] ] Output: [-1, 0, 1] Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
Example 3:
Input: [ [1,4], [2,3], [3,4] ] Output: [-1, 2, -1] Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.
解题思路：
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
解题思路：
1. 本题要找的是从任意节点往下延伸到任意节点的路径节点和为确定目标值，借助之间求向量中任意子序列和为定值的问题思路，我们可以把之间从根节点到任意路径上的节点的和通过hash存储下来，使用map<int, int>结构，key为路径节点和，value为路径条数，可能有多条路径和相同。递归函数递归到当前节点时，求出其到根结点的和，然后在map结构中查找 cur-sum 键值是否存在，如果存在，就存在着之前的节点到当前节点的路径和为目标值。将value值加到最后的结果中。
2. 将当前路径的和加入map结构，然后对其左右子树递归，完成后，再从map结构中删除当前的和，因为之后调用右子树时与当前路径和无关。
438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc" Output:
[0, 6] Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab" Output:
[0, 1, 2] Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
解题思路：
1. 第一次做的时候使用的数据结构是两个map<char, int>，一个map存储模式字符串中的字母信息，另一个map是存储在实际搜寻过程中所遍历的子字符串的字母信息。这种方法的好处是如果遇到不属于模式字符串中的字符，可以使用map.clear()函数快速的从下一位置开始遍历。
2. 第二个方法使用的是字符数组以及count的方法，用模式字符串初始化字符数组的字符个数，使用一个宽度与模式字符串长度相同的窗口滑行进行遍历。当 letter[end] > 0时，说明这个字符是我们需要的字符，因此将count--；当 letter[start] >= 0 时，说明这个字符也是我们需要的字符，将其滑出会导致需要的有效字符数量count++。在长度为length的窗口下，如果count==0，说明所有的字符都是刚好需要的，将此时的start加入返回向量中。
440. K-th Smallest in Lexicographical Order
Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input:
n: 13 k: 2 Output:
10 Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5 The coins can form the following rows:
¤
¤ ¤
¤ ¤ Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8 The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤ Because the 4th row is incomplete, we return 3.
解题思路：
1. 使用 1+2+3+...+k <= n，用一元二次方程的公式去求即可。
442. Find All Duplicates in an Array
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1] Output:
[2,3]
解题思路：
1. 遇到这种范围在1～n之间的整数问题，一般都是借助数组的下标来进行的。第一种方法，由于所有的整数都是正数，所有遍历数组时，把nums[i]-1位置上的数转换为负数，如果在后面再次读到一个负数时，说明当前数是重复过的，加入返回向量中。
2. 第二种方法，将如果nums[i] 与nums[nums[i]-1]上的值不同，就将其交换，直到nums[i] = nums[nums[i]-1]时继续循环，此时如果i != nums[i]-1 的话说明该数为重复数。重新遍历数组将所有下标+1与数值不同的数加入返回向量中。
刷题记录：
1. NO BUG FREE。
445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
解题思路：
1. 此题需要将两个从高位到地位的链表相加，但是进位的处理是从地位往高位的，所以我们在第一次计算时先不考虑进位的问题，对应位置上的数相加是多少就保存多少。同时为了方便之后进位的处理，我们将相加得到的结果链表反向存储，由低位到高位。由于链表在增删操作上的时间复杂度为O(1)，所以将结果加到链表头部是容易做到的。注意在叠加两个不同长度的链表时，可以通过比较n1与n2来找到对应位置。
2. 第二次遍历结果链表，从低位依次往高位，考虑进进位的因素，然后把得到的结果同样反向存储，得到高位在前，地位在后的结果。
446. Arithmetic Slices II - Subsequence
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.
A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.
The function should return the number of arithmetic subsequence slices in the array A.
The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.
Example:
Input: [2, 4, 6, 8, 10] Output: 7 Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
解题思路：
1. 用一个map<int, int>的向量存储原向量中每一个元素所对应的与之前元素组成序列的差值以及序列个数，（序列个数是所有大于等于2的序列数），当循环到某一元素时，就遍历在它之前的所有元素，求其差值，然后在结果的基础上加上前面元素的map中对应差值的序列数，然后在当前元素的map对应差值key的value上加上这部分序列，再加1（这里的加一是与前一元素单独组成的长度为2的序列，后面如果遇到同样差值的元素，就可以组成一个满足条件的序列）。
447. Number of Boomerangs
Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Example:
Input:
[[0,0],[1,0],[2,0]] Output:
2 Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
解题思路：
1. 计算以每个点为中点时其他所有点与它的距离，用map<int, int>来存储距离和点的数量的关系，每个点作为中点时，满足条件的组合数量为对应的距离键值的value值size*(size-1)。也可以在存入的时候就将现有的value*2，加入即可。
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1] Output:
[5,6]
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7]
key = 3 5
/ \
3 6
/ \ \
2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5
/ \
4 6
/ \
2 7 Another valid answer is [5,2,6,null,4,null,7]. 5
/ \
2 6
\ \
4 7
解题思路：
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree" Output:
"eert" Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:
"cccaaa" Output:
"cccaaa" Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:
"Aabb" Output:
"bbAa" Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:
Input:
[[10,16], [2,8], [1,6], [7,12]] Output:
2 Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input:
[1,2,3] Output:
3 Explanation:
Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2] Output:
2 Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
解题思路：
1. 将整个问题和Sum求和划分为两部分来求解，定义一个 map<int, int> 类型，用来存储向量A与向量B中任一元素求和的结果以及对应的组合数。时间复杂度为O(n^2)，同样的方式对向量C和向量D进行二层循环遍历，求任意元素和，在前面的map中寻找对应和的负值是否存在，如果存在的话，说明这个组合与前面A[i]+B[j]对应的元素和能组合为0，在结果中加上其组合数。
455. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.
Example 1:
Input: [1,2,3], [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [1, 2, 3, 4] Output: False Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2] Output: True Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: [-1, 3, 2, 0] Output: True Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
解题思路：
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: "abab" Output: True Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba" Output: False
Example 3:
Input: "abcabcabcabc" Output: True Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache( 2 /* capacity */ ); cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4 Output: 2 Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑ The above arrows point to positions where the corresponding bits are different.
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
You may assume the array's length is at most 10,000.
Example:
Input:
[1,2,3] Output:
2 Explanation:
Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]] Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:
In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.
Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.
You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.
Example
Input:
maxChoosableInteger = 10
desiredTotal = 11 Output:
false Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".
On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.
You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.
Example:
Input:
s1="acb", n1=4
s2="ab", n2=2 Return:
2
解题思路：
Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.
Note: p consists of only lowercase English letters and the size of p might be over 10000.
Example 1:
Input: "a"
Output: 1 Explanation: Only the substring "a" of string "a" is in the string s.
Example 2:
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.
Example 3:
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.
Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.
IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;
Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.
IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).
However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.
Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.
Note: You may assume there is no extra space or special characters in the input string.
Example 1:
Input: "172.16.254.1" Output: "IPv4" Explanation: This is a valid IPv4 address, return "IPv4".
Example 2:
Input: "2001:0db8:85a3:0:0:8A2E:0370:7334" Output: "IPv6" Explanation: This is a valid IPv6 address, return "IPv6".
Example 3:
Input: "256.256.256.256" Output: "Neither" Explanation: This is neither a IPv4 address nor a IPv6 address.
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Note:
- The number of elements of the given array will not exceed
10,000 - The length sum of elements in the given array will not exceed
600,000. - All the input string will only include lower case letters.
- The returned elements order does not matter.
Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input: [1,1,2,2,2]
Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
- The length sum of the given matchsticks is in the range of
0to10^9. - The length of the given matchstick array will not exceed
15.
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Note:
- The given numbers of
0sand1swill both not exceed100 - The size of given string array won't exceed
600.
Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2:
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Note:
- Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
- Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
- As long as a house is in the heaters' warm radius range, it can be warmed.
- All the heaters follow your radius standard and the warm radius will the same.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.
解题思路：
Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Note:
- The given integer is guaranteed to fit within the range of a 32-bit signed integer.
- You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:
Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
- Elements of the given array are in the range of
0to10^9 - Length of the array will not exceed
10^4
Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.
Example:
Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
Note:
The range of n is [1,8].
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
A magical string S consists of only '1' and '2' and obeys the following rules:
The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string Sitself.
The first few elements of string S is the following: S = "1221121221221121122……"
If we group the consecutive '1's and '2's in S, it will be:
1 22 11 2 1 22 1 22 11 2 11 22 ......
and the occurrences of '1's or '2's in each group are:
1 2 2 1 1 2 1 2 2 1 2 2 ......
You can see that the occurrence sequence above is the S itself.
Given an integer N as input, return the number of '1's in the first N number in the magical string S.
Note: N will not exceed 100,000.
Example 1:
Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.
Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced.
We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case.
So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above.
Example 1:
Input: S = "2-4A0r7-4k", K = 4 Output: "24A0-R74K" Explanation: The string S has been split into two parts, each part has 4 characters.
Example 2:
Input: S = "2-4A0r7-4k", K = 3 Output: "24-A0R-74K" Explanation: The string S has been split into three parts, each part has 3 characters except the first part as it could be shorter as said above.
Note:
- The length of string S will not exceed 12,000, and K is a positive integer.
- String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
- String S is non-empty.
解题思路：
For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.
Now given a string representing n, you should return the smallest good base of n in string format.
Example 1:
Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.
Example 2:
Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.
Example 3:
Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.
Note:
- The range of n is [3, 10^18].
- The string representing n is always valid and will not have leading zeros.
Given a binary array, find the maximum number of consecutive 1s in this array.
Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
Note:
- The input array will only contain
0and1. - The length of input array is a positive integer and will not exceed 10,000
解题思路：
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
- 1 <= length of the array <= 20.
- Any scores in the given array are non-negative integers and will not exceed 10,000,000.
- If the scores of both players are equal, then player 1 is still the winner.
解题思路：
Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.
Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.
Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.
Examples:
Input: "WRRBBW", "RB"
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW
Input: "WWRRBBWW", "WRBRW"
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty
Input:"G", "GGGGG"
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty
Input: "RBYYBBRRB", "YRBGB"
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
Note:
- You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
- The number of balls on the table won't exceed 20, and the string represents these balls is called "board" in the input.
- The number of balls in your hand won't exceed 5, and the string represents these balls is called "hand" in the input.
- Both input strings will be non-empty and only contain characters 'R','Y','B','G','W'.
解题思路：
1. 此题没有太多的技巧，就是通过尝试所有可能的方法，来得到消除整个字符串所需插入球数的最小值。由于插入一个球之后可能导致字符串的连续的自我消除，因此定义一个函数来完成这个过程，每次消除一部分以后都重新遍历字符串进行消除。插入球的过程是，从前往后遍历字符串，计算出每块连续相同字符串出现的字符个数，然后用3减去这个个数为让这个字符消除所需的最少字符数。用map<char, int>结构存储我们所能插入的字符以及其个数，如果个数大于我们所需的字符数，那么尝试将该字符消除，并递归调用原函数消除剩下的字符，得到这种情况下最小所需的插入球数，与存储最小插入球数的变量取最小值。如果最后返回的最小值为INT_MAX，那么返回-1。
2. 在对字符串的处理上，存在着一个技巧，就是向原字符串尾部添加一个字符'#'，便于判断和消除处于字符串尾部的连续字符。
刷题记录：
1. 相信并勇于实践自己的思路，NO BUG FREE。
491. Increasing Subsequences
Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .
Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
- The length of the given array will not exceed 15.
- The range of integer in the given array is [-100,100].
- The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
解题思路：
For a web developer, it is very important to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
1. The area of the rectangular web page you designed must equal to the given target area.
2. The width W should not be larger than the length L, which means L >= W.
3. The difference between length L and width W should be as small as possible.
You need to output the length L and the width W of the web page you designed in sequence.
Example:
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
Note:
- The given area won't exceed 10,000,000 and is a positive integer
- The web page's width and length you designed must be positive integers.
解题思路：
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example1:
Input: [1,3,2,3,1]
Output: 2
Example2:
Input: [2,4,3,5,1]
Output: 3
Note:
- The length of the given array will not exceed
50,000. - All the numbers in the input array are in the range of 32-bit integer.
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation: -1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
解题思路：
In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo's attacking ascending time series towards Ashe and the poisoning time duration per Teemo's attacking, you need to output the total time that Ashe is in poisoned condition.
You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.
Example 1:
Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.
This poisoned status will last 2 seconds until the end of time point 2.
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.
So you finally need to output 4.
Example 2:
Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.
This poisoned status will last 2 seconds until the end of time point 2.
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.
So you finally need to output 3.
Note:
- You may assume the length of given time series array won't exceed 10000.
- You may assume the numbers in the Teemo's attacking time series and his poisoning time duration per attacking are non-negative integers, which won't exceed 10,000,000.
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
- All elements in
nums1andnums2are unique. - The length of both
nums1andnums2would not exceed 1000.
解题思路：
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:
Note:
- The total number of elements of the given matrix will not exceed 10,000.
解题思路：
Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
Example 1:
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]
Note:
- You may use one character in the keyboard more than once.
- You may assume the input string will only contain letters of alphabet.
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.
Example 1:
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1]. Output: 4 Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
- You may assume all numbers in the input are non-negative integers.
- The length of Profits array and Capital array will not exceed 50,000.
- The answer is guaranteed to fit in a 32-bit signed integer.
解题思路：
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.
Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.
Given an integer, return its base 7 string representation.
Example 1:
Input: 100
Output: "202"
Example 2:
Input: -7
Output: "-10"
Note: The input will be in range of [-1e7, 1e7].
Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".
Example 1:
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".
For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
- N is a positive integer and won't exceed 10,000.
- All the scores of athletes are guaranteed to be unique.
解题思路：
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14
Note: The input number n will not exceed 100,000,000. (1e8)
Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1
Input:
5
/ \
2 -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:
5
/ \
2 -5
return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.
In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door.
Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
- You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring's characters at the 12:00 direction, where this character must equal to the character key[i].
- If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.
Example:
Input: ring = "godding", key = "gd"
Output: 4
Explanation:
For the first key character 'g', since it is already in place, we just need 1 step to spell this character.
For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
Also, we need 1 more step for spelling.
So the final output is 4.
Note:
- Length of both ring and key will be in range 1 to 100.
- There are only lowercase letters in both strings and might be some duplcate characters in both strings.
- It's guaranteed that string key could always be spelled by rotating the string ring.
You need to find the largest value in each row of a binary tree.
Example:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: [1, 3, 9]
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".
leetcode 学习心得 (2) (301~516)的更多相关文章
-
leetcode 学习心得 (3)
源代码地址:https://github.com/hopebo/hopelee 语言:C++ 517. Super Washing Machines You have n super washing ...
-
leetcode 学习心得 (1) (24~300)
源代码地址:https://github.com/hopebo/hopelee 语言:C++ 24.Swap Nodes in Pairs Given a linked list, swap ever ...
-
leetcode 学习心得 (4)
645. Set Mismatch The set S originally contains numbers from 1 to n. But unfortunately, due to the d ...
-
我的MYSQL学习心得（一） 简单语法
我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(四) 数据类型 我的MYSQL学习心得(五) 运 ...
-
我的MYSQL学习心得（二） 数据类型宽度
我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(四) 数据类型 我的MYSQL学习心得(五) 运 ...
-
我的MYSQL学习心得（三） 查看字段长度
我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(四) 数据类型 我的MYSQL学习心得(五) 运 ...
-
我的MYSQL学习心得（四） 数据类型
我的MYSQL学习心得(四) 数据类型 我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(五) 运 ...
-
我的MYSQL学习心得（五） 运算符
我的MYSQL学习心得(五) 运算符 我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(四) 数据 ...
-
我的MYSQL学习心得（六） 函数
我的MYSQL学习心得(六) 函数 我的MYSQL学习心得(一) 简单语法 我的MYSQL学习心得(二) 数据类型宽度 我的MYSQL学习心得(三) 查看字段长度 我的MYSQL学习心得(四) 数据类 ...
随机推荐
-
neXtep 安装过程整理
1 授权root用户远程登录 2 文件下载 http://www.nextep-softwares.com/ 选择DOWNLOAD NOW 选择你需要的版本 我选择的版本是 neXtep.1.0.7 ...
-
HDU 5446 中国剩余定理+lucas
Unknown Treasure Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Other ...
-
启动tomcat时 错误: 代理抛出异常 : java.rmi.server.ExportException: Port already in use: 1099的解决办法
一.问题描述 今天一来公司,在IntelliJ IDEA 中启动Tomcat服务器时就出现了如下图所示的错误:
-
python 正则表达式 贪婪模式的简介和匹配时的几种模式
看到一篇文章,关于python正则的,http://www.cnblogs.com/huxi/archive/2010/07/04/1771073.html 贪婪模式与非贪婪模式: 正则表达式通常用于 ...
-
(5)ES6解构赋值-函数篇
函数参数的解构赋值 function sum(x, y) { return x + y; } sum(1,2); //解构赋值 function sum([x, y]) { return x + y; ...
-
2017-12-19python全栈9期第四天第二节之列表的增删查改之正向排序和倒向排序和反转
#!/user/bin/python# -*- coding:utf-8 -*-li = [3,5,6546,6,8,324,2,1,34,5,6,7]# li.sort() #正向# print(l ...
-
java之高效操作文件
代码: import java.io.IOException; import java.nio.file.FileVisitOption; import java.nio.file.FileVisit ...
-
tf.transpose函数的用法讲解
tf.transpose函数中文意思是转置,对于低维度的转置问题,很简单,不想讨论,直接转置就好(大家看下面文档,一看就懂). tf.transpose(a, perm=None, name='tra ...
-
HDU 6103 Kirinriki（尺取法）
http://acm.hdu.edu.cn/showproblem.php?pid=6103 题意: 给出一个字符串,在其中找两串互不重叠的子串,计算它们之间的dis值,要求dis值小于等于m,求能选 ...
-
我的Cocos Creator成长之路1环境搭建以及基本的文档阅读
本人原来一直是做cocos-js和cocos-lua的,应公司发展需要,现转型为creator.会在自己的博客上记录自己的成长之路. 1.文档阅读:(cocos的官方文档) http://docs.c ...