[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。
老规矩，跳过需要付费的题目。题目是越来越不好做，我尽量把自己的思路写下来。
| 371 | 51.9% | Easy | |
| 368 | 31.9% | Medium | |
| 367 | 36.9% | Medium | |
| 365 | 24.7% | Medium | |
| 363 | 30.6% | Hard | |
| 357 | 44.2% | Medium | |
| 355 | 23.5% | Medium | |
| 354 | 30.6% | Hard | |
| 352 | 38.2% | Hard | |
| 350 | 42.6% | Easy | |
| 349 | 44.5% | Easy | |
| 347 | 44.4% | Medium | |
| 345 | 36.6% | Easy | |
| 344 | 58.1% | Easy | |
| 343 | 43.8% | Medium | |
| 342 | 36.6% | Easy | |
| 341 | 35.3% | Medium | |
| 338 | 58.6% | Medium | |
| 337 | 40.2% | Medium | |
| 336 | 22.7% | Hard | |
| 335 | 22.8% | Hard | |
| 334 | 36.7% | Medium | |
| 332 | 26.8% | Medium | |
| 331 | 33.9% | Medium | |
| 330 | 30.8% | Hard | |
| 329 | 34.0% | Hard | |
| 328 | 40.7% | Medium | |
| 327 | 27.7% | Hard | |
| 326 | 38.6% | Easy | |
| 324 | 24.3% | Medium | |
| 322 | 25.8% | Medium | |
| 321 | 22.9% | Hard | |
| 319 | 41.5% | Medium | |
| 318 | 41.3% | Medium | |
| 316 | 27.5% | Hard | |
| 315 | 32.5% | Hard | |
| 313 | 36.5% | Medium | |
| 312 | 40.4% | Hard |
【题目】
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 异或一下得到 x，因为每一位上相加，如果两个都是 0，结果就是 0，如果两个都是 1，结果还是 0，只有一个 1 一个 0，结果才是 1。
- 但是单单异或是不够的，因为这样做完全没有考虑进位的问题。于是 a 和 b 与一下，因为每一位上相加，如果都是 0，不需要进位，如果一个 1 一个 0，也不需要进位，只有两个都是 1 才需要进位。相与之后还需要左移一位，因为进位的关系，进位的”1″ 必须要作用在更高一位才有用。
- 上面这两个结果，作为新的参数继续去调用 getSum 计算，反复进行，直到没有进位为止。
public class Solution {
public int getSum(int a, int b) {
if (a==0)
return b;
int x = a ^ b;
int c = (a & b) << 1;
return getSum(c, x);
}
}
【题目】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]
【解答】要找这样的一个子集合，使得所有元素都可以互为整除或者被整除的关系。
在一切开始前，大脑里面大致有这样一个方向：我需要把 nums 排序，然后从较小的一端开始逐个审查归类，因为每查看一个新数的时候，我应该在手边有一个不断构建着的集合，这个集合根据整除关系包含了若干个分类，而且里面的数都比当前审查的数小，所以我会挨个从集合里拿出数来去尝试整除这个被审查数，根据结果去更新这个集合。
于是我建立这样一个数据结构：一个 list，其中第 i 个元素表示以 nums[i] 作为最大值且必须包含它的最大分类；而每个分类又是由一串数组成，它们互为整除或被整除关系，并且升序排列。为什么要升序排列？因为排列以后，每个分类最大的那个数，可以作为分类的代表，如果有新数要比较，和它比就可以，如果它和新数存在前面提到的整除关系，那么这个分类中任何一个数都会和新数存在整除关系。这一点是解题的关键。
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length==0)
return new ArrayList<>();
// lens[i] means the largest divisible subset which is in asc sort and ended with nums[i]
List<List<Integer>> lens = new ArrayList<>();
Arrays.sort(nums);
List<Integer> first = new ArrayList<>(1);
first.add(nums[0]);
lens.add(first);
for (int i=1; i<nums.length; i++) {
Integer maxIndex = null;
for (int j=0; j<i; j++) {
List<Integer> list = lens.get(j);
if (maxIndex!=null && list.size() <= lens.get(maxIndex).size())
continue;
int prevMax = list.get(list.size()-1);
if (nums[i] % prevMax == 0) {
maxIndex = j;
}
}
List<Integer> newList;
if (maxIndex==null)
newList = new ArrayList<>();
else
newList = new ArrayList<>(lens.get(maxIndex));
newList.add(nums[i]);
lens.add(newList);
}
List<Integer> result = null;
for (List<Integer> list : lens) {
if (result==null || result.size()<list.size())
result = list;
}
return result;
}
}
【题目】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 的数 x 是不是完全平方数，可以从 x/2 开始试起，慢慢减小。这个可以减小计算量。结论应该是对的，但是需要证明一下以严谨一点：
x^2 – 2*x = x^2 – 2*x + 1 – 1 = (x-1)^2 -1 >= -1, when x>=2 it’s >= 0
so x^2 >= 2*x when x>=2
好了，这就可以写代码了。使用 long 型，防止平方的时候溢出：
public class Solution {
public boolean isPerfectSquare(int num) {
if (num==0 || num==1)
return true;
int half = num/2;
for (long i=half; i>0; i--) { // long
if (i*i>num)
continue;
else if (i*i==num)
return true;
else
return false;
}
return false;
}
}
【题目】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 升水来。
题目描述那么简单，通用性那么强，很容易给人一个 “数学定理” 的感觉。事实上，还真有一个数学定理来帮助解决这个问题，如果不知道那个定理，这个题目做起来就会非常痛苦，如果知道，那就非常简单。这个定理，就叫做裴蜀定理（维基百科上有证明）：
对任何整数 a、b 和它们的最大公约数 d，关于未知数 x 和 y 的裴蜀等式：
ax + by = m
有整数解时当且仅当 m 是 d 的倍数。
裴蜀等式有解时必然有无穷多个整数解。
而这个问题，就可以映射到上面这个式子中去。于是我们可以求这两个壶容量的最大公约数，看看要弄出的水升数 z 是不是这个最大公约数的倍数。这种题居然不是 hard 真是天理难容……
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
//limit brought by the statement that water is finallly in one or both buckets
if(x + y < z) return false;
//case x or y is zero
if( x == z || y == z || x + y == z ) return true;
//get GCD, then we can use the property of Bézout's identity
return z%GCD(x, y) == 0;
}
public int GCD(int a, int b){
while(b != 0 ){
int temp = b;
b = a%b;
a = temp;
}
return a;
}
}
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?
【解答】要找一个矩形，让矩形框起来的范围内，所有数的和能够不超过 k，但是又要尽量大。这道题我折腾了挺长时间也没有做对，我觉得还是比较难的。下面这个解法来自讨论区的这个帖子，我认为是我看到的几个解法里面比较好的。就着代码做一个说明。为了简化理解的复杂度，不妨假设列数> 行数。
通过 i 从 0 到 m 的循环，和 j 从 i 到 0 的循环，形成 [j, i] 这样一个区间，在这样的循环内部我们会看到二维问题被转化为一维问题来求解。
- 数组 array 用来记录这样一种累加值：array[k] 表示在 i 已经锁定的情况下，随着 j 不断变小，行区间 [i, j] 跨度不断变大，又有从第 0 列到第 k 列 [0, k] 形成了列区间，对于仅仅第 k 列这单列，在不同行跨度下的累加值。
- val 则是在 i、j 都锁定的情况下，即行区间完全确定的情况下，对不同 k 的时候，array[k] 的累加。也就是说，即随着 k 从 0 变化到 n，val 表示从第 0 列到第 k 列，以及从第 j 行到 i 行，所形成的的这样一个矩形包含所有数的累加值。这个 val 是要被不断放入一个 TreeSet 的。
- val-target 就是这个矩形值和目标值的差距，使用这个 TreeSet 的 ceiling 方法（这也是使用 TreeSet 的原因，查找的复杂度是 log n），去找一个必须大于等于这个差距的最小值 subres。这里减去 target 再去 TreeSet 里面找就是为了保证在计算差距的时候始终预留好目标值的空间。
- 用 val 这个矩形值减去 subres，就是小于目标值，但是又尽量大的结果了。
分析一下复杂度：min(m,n)^2 * max(m,n) * log(max(m,n))，还是假设列数> 行数以简化描述。
- i 和 j 的不断变化，形成 [j, i] 这样的行区间，这里有 i 和 j 的循环嵌套，因此这一步复杂度是 m 的平方；
- k 从 0 变化到 n，因此这一步复杂度是 n；
- 对于 TreeSet 的使用，时间复杂度是 log n。
因此，三者相乘，就形成了这样的复杂度。
/* first consider the situation matrix is 1D
we can save every sum of 0~i(0<=i<len) and binary search previous sum to find
possible result for every index, time complexity is O(NlogN).
so in 2D matrix, we can sum up all values from row i to row j and create a 1D array
to use 1D array solution.
If col number is less than row number, we can sum up all values from col i to col j
then use 1D array solution.
*/
public int maxSumSubmatrix(int[][] matrix, int target) {
int row = matrix.length;
if(row==0)return 0;
int col = matrix[0].length;
int m = Math.min(row,col);
int n = Math.max(row,col);
//indicating sum up in every row or every column
boolean colIsBig = col>row;
int res = Integer.MIN_VALUE;
for(int i = 0;i<m;i++){
int[] array = new int[n];
// sum from row j to row i
for(int j = i;j>=0;j--){
int val = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(0);
//traverse every column/row and sum up
for(int k = 0;k<n;k++){
array[k]=array[k]+(colIsBig?matrix[j][k]:matrix[k][j]);
val = val + array[k];
//use TreeMap to binary search previous sum to get possible result
Integer subres = set.ceiling(val-target);
if(null!=subres){
res=Math.max(res,val-subres);
}
set.add(val);
}
}
}
return res;
}
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])
【解答】要找不包含重复数字的数。主要思路还是分类讨论。
这里有一个比较容易想到的递归关系，比如 n=3 的时候，如果我能够拿到 n=2 的结果，即 0≤x<100，再加上 101≤x<1000 之间的部分，就可以得到结果。也就是说，是对于所有一位数和两位数的解，再加上新增加的三位数的部分。
但是怎么得到这个三位数部分的解，有两种方向可以考虑（起码我是这样想的）：（1）已知的所有两位数，或者是十位为 0 并拼接一位数的所有可能，合并起来再在百位上放一个非 0 的数，这样形成的三位数里面，去掉重复数字的部分；（2）单独考虑满足条件的三位数形成的所有组合，不和两位数的关联关系挂钩。如果按照思路（1）走，也许也能得出结果，但是逻辑会非常复杂；下面是按照（2）的思路来进行的步骤：
- 先递归拿到 n 如果是 n-1 的时候的解。
- 然后考虑 n 位数部分，最高位只有从 1 到 9 这 9 种可能，因为 0 不能选；次高位有 0 到 9，但是去除最高位已经用过的数，因此也是 9 种可能；再往下，则是 8 种可能；再往下是 7 种……把这些可能累加起来即可。
- 注意的是，由于数字只有从 0 到 9 这 10 个，因此如果 n>10 了，随着 n 的增加，结果无法再增加了。
public class Solution {
public int countNumbersWithUniqueDigits(int n) {
int total = 0;
if (n>0)
total += countNumbersWithUniqueDigits(n-1);
else
return 1;
if (n>10)
return total;
int product = 1;
int numberToSelect = 10;
for (int i=n; i>=1 ; i--) {
// the highest digit, 0 is disallowed
if (i==n) {
product *= 9;
} else {
product *= numberToSelect;
}
numberToSelect--;
}
return total + product;
}
}
【题目】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);
【解答】这一类问题还是比较有趣的，因为和实际问题（需求）更接近。仔细斟酌题目中的四个 case，其中 3 和 4 看起来似乎单纯和简单一些：用 map 就可以解决，一个用户 id 映射到一串用户 id，以表示 follow 的关系。和 tweet 相关的 1 和 2 中，1 似乎也比较容易处理，也是一个 map 的映射关系。麻烦的是 2，一个用户可以 follow 若干个不同的其它用户，要返回这堆用户中最近的 10 条 tweet，看起来似乎没有特别好的办法。因为这 10 条可能集中在某一个人身上，也可能分散在不同的人当中。
不过，一点是肯定的，无论是集中还是分散，任何一个人所发的 tweet 中，不可能取回超过 10 条。因此可以从该用户关注的所有人中，每个人都取得最多 10 条最近的 tweet，然后把结果汇总起来按时间排序，返回最近的 10 条即可。这个思路看起来很像 MapReduce 那个经典的取 top xx 的问题。
最后，既然要涉及单个人的 “最近”10 条 tweet，那就需要在存储这些 tweet 的时候：（1）按照不同的用户来归类；（2）按照时间顺序来存放。
有了这些思路，整理一下，这道题还是比较容易解出来的。这样的问题，把具体问题抽象成可以解决的数学问题，特别是找到合适的数据结构来表示这些物件之间的关系，是解决问题的关键。同为算法问题，有些问题 “算” 本身的逻辑比较复杂，有些问题则是把复杂性放在模型的建立上。
class TweetItem implements Comparable<TweetItem> {
int time;
int tweetId;
public TweetItem (int time, int tweetId) {
this.time = time;
this.tweetId = tweetId;
}
@Override
public int compareTo(TweetItem that) {
if (this.time < that.time)
return 1;
else if (this.time == that.time)
return 0;
else
return -1;
}
}
public class Twitter {
private Map<Integer, List<TweetItem>> tweets = new HashMap<>();
private Map<Integer, Set<Integer>> follows = new HashMap<>();
private int time = 0;
private static int RECENT_TWEET_COUNT = 10;
/** Initialize your data structure here. */
public Twitter() {
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (!tweets.containsKey(userId))
tweets.put(userId, new ArrayList<>());
tweets.get(userId).add(new TweetItem(time++, tweetId));
}
/** 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. */
public List<Integer> getNewsFeed(int userId) {
Set<Integer> set;
if (!follows.containsKey(userId))
set = new HashSet<>();
else
set = follows.get(userId);
// himself/herself
set.add(userId);
List<TweetItem> newTweets = new ArrayList<>();
for (int fId : set) {
if (!tweets.containsKey(fId))
continue;
List<TweetItem> subList;
if (tweets.get(fId).size() > RECENT_TWEET_COUNT){
// latest 10 records
subList = tweets.get(fId).subList(tweets.get(fId).size()-RECENT_TWEET_COUNT, tweets.get(fId).size());
} else {
subList = tweets.get(fId).subList(0, tweets.get(fId).size());
}
newTweets.addAll(subList);
}
Collections.sort(newTweets);
List<TweetItem> subTweets;
if (newTweets.size() > RECENT_TWEET_COUNT) {
subTweets = newTweets.subList(0, RECENT_TWEET_COUNT);
} else {
subTweets = newTweets;
}
List<Integer> retList = new ArrayList<>();
for (TweetItem item : subTweets) {
retList.add(item.tweetId);
}
return retList;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (!follows.containsKey(followerId))
follows.put(followerId, new HashSet<>());
follows.get(followerId).add(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if (!follows.containsKey(followerId))
return;
follows.get(followerId).remove(followeeId);
}
}
【题目】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]).
【解答】像俄罗斯套娃一样的套信封问题，怎样套到最多的信封。如果是一维的问题，这道题是非常简单的，从最小的信封开始，每次都尽可能去挑最小的信封套。但是现在是二维的问题（宽和高），也是题目相对来说难度增加的地方。如果把单独一维抽出来讨论，是肯定无法做到最优解的。下面是我的思路，相对简单，但是可以优化。
- 首先排序，优先考虑宽，宽一样的时候考虑高。
- 然后两重循环，第一层从序列的头到末尾，也就是说宽度是递增的；第二层从 i-1 到 0，也就是说宽度是递减的（因为 ≥i 的部分宽度更大，显然无法放到当前的信封内）。使用 numberArray 存储排序完之后，第 i 个信封为最外层时，最多可以套到多少个信封。
- 在循环内判断宽和高，要求外层的宽大于内层的宽，外层的高大于内层的高。
也就是说，整个过程里面，宽这一维做到了减少暴力解法带来的过多计算问题，因为第二层比较时只需要从 i-1 遍历到 0；但是高这一维度却没有。
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null)
throw new IllegalArgumentException();
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] left, int[] right) {
if (left[0] != right[0]) {
return left[0] - right[0];
} else {
return left[1] - right[1];
}
}
});
int max = 0;
int[] numberArray = new int[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
numberArray[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
numberArray[i] = Math.max(numberArray[i], numberArray[j] + 1);
}
}
max = Math.max(max, numberArray[i]);
}
return max;
}
}
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?
【解答】首先要理解题意，随着数据流不断地流入，要把不断添加进来的数据进行分段，凡是连着的整数就算一段，每次调用 getIntervals 要打印出现在所有的数据段。
下面的方法是我开始思考的方法，使用 TreeMap，也就是红黑树，使用它有一个好处，在于 key 是排序了的，这样可以用 log n 的复杂度找到邻近的数据段。这个 map 的 key 是数值，value 是这个点的类型，分为三种：数据段开头、数据段结尾，以及数据点（即即为开头又为结尾）。然后分类讨论，用这种方法大致的方向是对的，但是下面分类讨论的 case 非常多，导致代码非常复杂。最后有一个巨长的测试 case 过不去，也不是很好调试了。为了记录思路，我把这个不好的代码例子先放在下面。
public class SummaryRanges {
private static final Integer RANGE_START = 0;
private static final Integer RANGE_END = 1;
private static final Integer RANGE_START_AND_END = 2;
private TreeMap<Integer, Integer> tm = new TreeMap<>();
/** Initialize your data structure here. */
public SummaryRanges() {
}
public void addNum(int val) {
Map.Entry<Integer, Integer> ceiling = tm.ceilingEntry(val);
Map.Entry<Integer, Integer> floor = tm.floorEntry(val);
if (ceiling == null && floor == null) { // case 1: the tree map is empty
tm.put(val, RANGE_START_AND_END);
} else if (ceiling == null) { // case 2: put the value at the end of the ranges
if (floor.getKey() == val) {
;
} else if (floor.getKey() == val-1) {
tm.put(val, RANGE_END);
if (floor.getValue() == RANGE_END)
tm.remove(floor.getKey());
else // floor.getValue() == RANGE_START_AND_END
tm.put(floor.getKey(), RANGE_START);
} else {
tm.put(val, RANGE_START_AND_END);
}
} else if (floor == null) { // case 3: put the value at the beginning of the ranges
if (ceiling.getKey() == val) {
;
} else if (ceiling.getKey() == val+1) {
tm.put(val, RANGE_START);
if (ceiling.getValue() == RANGE_START)
tm.remove(ceiling.getKey());
else // ceiling.getValue() == RANGE_START_AND_END
tm.put(ceiling.getKey(), RANGE_END);
} else {
tm.put(val, RANGE_START_AND_END);
}
} else if (floor.getKey() == val || ceiling.getKey() == val) { // case 4: the value is already existed as the boundary of a range
;
} else if (floor.getKey() == val-1) { // case 5: the value extends a lower range
if (floor.getValue() == RANGE_START){
;
} else {
if (floor.getValue() == RANGE_END) {
tm.remove(floor.getKey());
} else { // floor.getValue() == RANGE_START_AND_END
tm.put(val-1, RANGE_START);
}
if (ceiling.getKey() == val+1) {
if (ceiling.getValue() == RANGE_START) {
tm.remove(ceiling.getKey());
} else { // ceiling.getValue() == RANGE_START_AND_END
tm.put(val+1, RANGE_END);
}
} else {
tm.put(val, RANGE_END);
}
}
} else if (ceiling.getKey() == val+1) { // case 6: the value extends a higher range
if (ceiling.getValue() == RANGE_END) {
;
} else {
if (ceiling.getValue() == RANGE_START) {
tm.remove(ceiling.getKey());
} else { // ceiling.getValue == RANGE_START_AND_END
tm.put(val+1, RANGE_END);
}
if (floor.getKey() == val-1) {
if (floor.getValue() == RANGE_END) {
tm.remove(floor.getKey());
} else { // floor.getValue == RANGE_START_AND_END
tm.put(val-1, RANGE_START);
}
} else {
tm.put(val, RANGE_START);
}
}
} else { // case 7: single point
tm.put(val, RANGE_START_AND_END);
}
}
public List<Interval> getIntervals() {
List<Interval> list = new ArrayList<>();
Interval inter = null;
for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
if (entry.getValue() == RANGE_START_AND_END) {
list.add(new Interval(entry.getKey(), entry.getKey()));
} else if (entry.getValue() == RANGE_START) {
inter = new Interval();
inter.start = entry.getKey();
} else {
inter.end = entry.getKey();
list.add(inter);
}
}
return list;
}
}
上面啰嗦的方法没再研究下去，而下面则祭出 “Top Solutions” 的第一个，思路就明显简洁清晰很多。也是用 TreeMap，key 是数值，表示的是这个数据段的开头，但是 value 直接放 Interval 对象了，这样在 TreeMap 中一下就可以少最多一半的数据量，因为 key 只需要存放开头数，不需要存放结尾数。同时，更重要的是，case 也简洁很多，只需要讨论这样四种 case：
- 左段和右段当前是分开的，但是加上这个新数以后，就接上了；
- 右段无影响，但是左段的结尾可能会被新数延长；
- 左段无影响，但是右段的开头可能会被新数延长；
- 左右都挨不着，新数成为孤岛数段。
public class SummaryRanges {
TreeMap<Integer, Interval> tree;
public SummaryRanges() {
tree = new TreeMap<>();
}
public void addNum(int val) {
if(tree.containsKey(val)) return;
Integer l = tree.lowerKey(val);
Integer h = tree.higherKey(val);
if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
tree.get(l).end = tree.get(h).end;
tree.remove(h);
} else if(l != null && tree.get(l).end + 1 >= val) {
tree.get(l).end = Math.max(tree.get(l).end, val);
} else if(h != null && h == val + 1) {
tree.put(val, new Interval(val, tree.get(h).end));
tree.remove(h);
} else {
tree.put(val, new Interval(val, val));
}
}
public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}
【题目】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?
【解答】和 Intersection of Two Arrays 就一点区别，就是不需要去重。那就用 HashMap 来替代 HashSet 就好了，key 是数字，value 是该数字出现的次数。
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums1) {
if (!map.containsKey(num))
map.put(num, 0);
map.put(num, map.get(num)+1);
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
Integer val = map.get(num);
if (val!=null && val!=0) {
list.add(num);
map.put(num, val-1);
}
}
int[] ret = new int[list.size()];
for (int i=0; i<list.size(); i++) {
ret[i] = list.get(i);
}
return ret;
}
}
【题目】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.
【解答】求交集。用 HashSet 就好了，既可以找交集，又可以去重。
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1==null || nums2==null)
throw new IllegalArgumentException();
Set<Integer> set2 = new HashSet<>();
for (int n : nums2) {
set2.add(n);
}
Set<Integer> set3 = new HashSet<>();
for (int n : nums1) {
if (set2.contains(n))
set3.add(n);
}
int[] intersection = new int[set3.size()];
int i=0;
for (int n : set3) {
intersection[i] = n;
i++;
}
return intersection;
}
}
【题目】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.
【解答】从一堆数中寻找 k 个出现次数最多的，首先出现在大脑里的思路是，先用一个 map 记录下每个元素的出现次数，然后再排序一下，这样复杂度就是 n*logn。下面我用的是 TreeMap（红黑树）的做法，TreeMap 本身提供的是具有排序 key 的 map 这样的功能，它的 put/get 的时间复杂度都是 log n，因而对于 n 个元素这样的情况来看，理论上的时间复杂度量级依然是 n*logn。因此兴许它的时间开销会比 map 记录下所有元素出现次数以后，再排序一下这种方法好一些，也通过了所有的测试用例，但依然是同一级别的。也就是说，并不能算是满足题目 note 里面的要求使用比 O(n log n) 更好的复杂度，欢迎提供更佳的解法。
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
if (nums==null || nums.length==0 || k<=0)
return new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.get(num) == null)
map.put(num, 0);
map.put(num, map.get(num)+1);
}
TreeMap<Integer, Set<Integer>> reverseMap = new TreeMap<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (reverseMap.get(entry.getValue()) == null)
reverseMap.put(entry.getValue(), new HashSet<>());
Set<Integer> set = reverseMap.get(entry.getValue());
set.add(entry.getKey());
reverseMap.put(entry.getValue(), set);
}
List<Integer> ret = new ArrayList<>(k);
while(k>0) {
Integer key = reverseMap.lastKey();
if (key==null)
break;
Set<Integer> set = reverseMap.get(key);
reverseMap.remove(key);
if (set.size()<=k) {
ret.addAll(set);
k -= set.size();
}
else {
for (int s : set) {
ret.add(s);
k--;
if (k==0)
break;
}
}
}
return ret;
}
}
【题目】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”.
【解答】要把元音反转。思路就是准备两个指针，一个从前往后，一个从后往前，找到元音就互换位置。
public class Solution {
public String reverseVowels(String s) {
if (null==s)
return s;
int i=0, j=s.length()-1;
char[] arr = s.toCharArray();
while (i<j) {
if (!isVowel(arr[i])) {
i++;
continue;
}
if (!isVowel(arr[j])) {
j--;
continue;
}
swap(arr, i, j);
i++;
j--;
}
return new String(arr);
}
private boolean isVowel(char c) {
return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' || c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
}
private void swap(char[] arr, int i, int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
【题目】Write a function that takes a string as input and returns the string reversed.
Example:
Given s = “hello”, return “olleh”.
【解答】这个题没有太多可说的。
public class Solution {
public String reverseString(String s) {
if (null==s)
return null;
int len = s.length();
char[] arr = new char[len];
for (int i=len-1; i>=0; i--) {
arr[len-i-1] = s.charAt(i);
}
return new String(arr);
}
}
【题目】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.
【解答】把一个数拆分成若干个数的和，最后要求使得这几个数的乘积最大。
现在假设这个数 n，需要拆成 k 个数，那么一点是肯定的，一旦 k 被确定下来，这几个数越平均越好。因为拆出来的这几个数，越是接近，乘积就越大。
因此考虑所有 k 的可能，拆数的时候，n/k 未必能够整除，但是能够得到一个 “基数”，即这种最平均的拆分法，拆出来的数要么是 n/k 向下取整，要么是 n/k 向下取整+1，也就是说任意两个数之间的差别不会超过 1。
public class Solution {
public int integerBreak(int n) {
int max = -1;
for (int k=2; k<=n; k++) {
int res = cal(n, k);
if (res>max)
max = res;
else
return max;
}
return max;
}
private int cal(int n, int k) {
int c = n/k;
int adding = (n - c*k);
int result = 1;
if (c==0)
return -1;
for (int i=1; i<=k; i++) {
if (adding>0) {
adding--;
result *= c+1;
}
else {
result *= c;
}
}
return result;
}
}
【题目】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?
【解答】要看一个数是不是 4 的幂。做法有很多，利用一些数的性质可以简化计算：
（1）如果一个数 num 是 2 的幂，那它应该是这样的数：
1 -> 1
2 -> 10
4 -> 100
8 -> 1000
……
因此 num & (num-1) 应该得到 0。
（2）考虑这样的因数分解：
4^n – 1 = (4-1) (4^(n-1) + 4^(n-2) + 4^(n-3) + … + 4 + 1)
因此取 3 的模应该为 0。
我觉得这二个条件的必要性应该是正确的，但是惭愧的是充分性我并没有证明出来。即，上面的（1）和（2）可以说是 “一个数是 4 的幂” 的必要条件，但是如何证明它们也是充分条件呢？
其实，通过（1）的筛选可以找到符合 “2 的幂” 这个条件，而想想 2 的幂如果它同时也是 4 的幂，那肯定能被 3 整除，这一点已经被（2）说明，现在问题转化为，如何说明 2 的幂但不为 4 的幂的时候，是无法被 3 整除的呢？
如果你知道怎样证明，或者有别的思路，我们可以讨论。
public class Solution {
public boolean isPowerOfFour(int num) {
if(num<=0)
return false;
// powers of 2
// 10000000...
if ((num & (num-1)) != 0)
return false;
// 4^n - 1 = (4-1) (4^(n-1) + 4^(n-2) + 4^(n-3) + ... + 4 + 1)
if ((num-1) % 3 != 0)
return false;
return true;
}
}
【题目】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].
【解答】使用一个栈 stack 来存放外层的链表节点。每次调用 next 的时候，都从 stack 里面 pop 一个元素出来，然后让它的 index 往后走。不过如果走不了了，即已经全部遍历过了，那就只能出栈了。
有一个注意的地方是对于 hasNext 方法的设计。我的做法是在 hasNext 方法的时候把下一个元素应该返回什么的工作做好，并且使用一个标识量 checked 表示是否已经通过 hasNext 检查过了，这样在调用 next 方法的时候就不用做
class Item {
List<NestedInteger> list;
int index;
}
public class NestedIterator implements Iterator<Integer> {
private boolean checked;
private Integer nextVal;
private Stack<Item> stack = new Stack<>();
public NestedIterator(List<NestedInteger> nestedList) {
checked = false;
nextVal = null;
Item item = new Item();
item.list = nestedList;
item.index = 0;
stack.push(item);
}
private void check() {
if (stack.isEmpty()) {
checked = true;
nextVal = null;
return;
}
Item item = stack.peek();
if (item.list.size()<=item.index) {
stack.pop();
this.check();
} else {
NestedInteger nestedInteger = item.list.get(item.index);
item.index++;
if (nestedInteger.isInteger()) {
nextVal = nestedInteger.getInteger();
checked = true;
} else {
Item subItem = new Item();
subItem.list = nestedInteger.getList();
subItem.index = 0;
stack.push(subItem);
this.check();
}
}
}
@Override
public Integer next() {
if (!checked)
this.check();
return nextVal;
}
@Override
public boolean hasNext() {
this.check();
return nextVal != null;
}
}
【题目】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
【解答】要数 1 的个数，再看题目里对复杂度的要求，对 1 到 n 的每一个数拿出来，必须要在常数时间复杂度内就得出结果。因此考虑 1 到 n 中每一个数和它之前的数之间的关系，利用之前的数已经算得的结果（存在数组 array 中），再加上变化的增量，以减少计算量。
array[0] = 0，1 的数量：0
array[1] = 1 -> 2^0 -> 1，1 的数量：1
array[2] = 2 -> 2^1 -> 10，1 的数量：array[0] + 1
array[3] = 3 -> 2^1 + 1 -> 11，1 的数量：array[1] + 1
array[4] = 4 -> 2^2 -> 100，1 的数量：array[0] + 1
array[5] = 5 -> 2^2 + 1 -> 101，1 的数量：array[1] + 1
array[6] = 6 -> 2^2 + 2 -> 110，1 的数量：array[2] + 1
array[7] = 7 -> 2^2 + 3 -> 111，1 的数量：array[3] + 1
array[8] = 8 -> 2^3 -> 1000，1 的数量：array[0] + 1
在纸上写出如上，寻找思路：
- 任意一个数出现的时候，比如 1101010101，只有最高位的 1 是个新东西，去掉最高位之后，101010101 在之前已经出现过了，因此使用一个数组 array 来存储已经计算过的结果；
- 使用 pos 下标来表示当前这个数去掉最高位以后，剩下的数在 array 出现的位置，那么加上 1 就可以得到当前这个数的 1 的数量；
- 用 cycleLength 来记录一个表示 2 的 cycleCount 次方的结果，在 cycleCount 没有变化的时候，1 的数量是去掉最高位以后的值+1，但是如果 cycleCount 变化（即 cycleLength≤pos），需要把 pos 清零，把 cycleCount 自增 1，并更新 cycleLength。
public class Solution {
public int[] countBits(int num) {
if (num==0)
return new int[]{0};
else if (num==1)
return new int[]{0, 1};
int cycleCount = 1;
int pos = 0;
int[] array = new int[num+1];
array[0] = 0;
array[1] = 1;
int cycleLength = (int)Math.pow(2, cycleCount);
for (int i=2; i<array.length; i++) {
array[i] = array[pos] + 1;
pos++;
if (pos>=cycleLength) {
pos = 0;
cycleCount++;
cycleLength = (int)Math.pow(2, cycleCount);
}
}
return array;
}
}
【题目】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 / \ 45 / \ \ 1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
【解答】这道题思路相对还是比较简单的。建立两个 map，一个用来存放指定节点被抢劫的最优解，一个用来存放指定节点不被抢劫的最优解。
然后就可以从 root 开始递归遍历，注意递归方法需要传入一个 boolean 变量表示在某种情况下，这次的递归调用所对应的节点是否可以被抢劫：
- 如果可以被抢劫就需要在两个 map 中分别存放被抢劫和不被抢劫的最优解；
- 如果不可以被抢劫，就只需要在后一个 map 中存放不被抢劫的最优解。
public class Solution {
public int rob(TreeNode root) {
return rob(root, true, new HashMap<>(), new HashMap<>());
}
private int rob(TreeNode root, boolean robbable, Map<TreeNode, Integer> robbedCache, Map<TreeNode, Integer> unrobbedCache) {
if (root==null)
return 0;
int robbed = 0;
if (robbable) {
if (robbedCache.get(root) != null) {
robbed = robbedCache.get(root);
} else {
robbed += root.val;
robbed += rob(root.left, false, robbedCache, unrobbedCache);
robbed += rob(root.right, false, robbedCache, unrobbedCache);
robbedCache.put(root, robbed);
}
}
int unrobbed = 0;
if (unrobbedCache.get(root) != null) {
unrobbed = unrobbedCache.get(root);
} else {
unrobbed += rob(root.left, true, robbedCache, unrobbedCache);
unrobbed += rob(root.right, true, robbedCache, unrobbedCache);
unrobbedCache.put(root, unrobbed);
}
return Math.max(robbed, unrobbed);
}
}
【题目】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"]
【解答】从一堆单词里面找出两个，连接在一起组成回文，要列出所有这样的可能性。
最暴力的解法就是两两组合，考虑所有的可能性，但是复杂度在 n 平方。
因此思考改进的方式。两个单词连接，如果较短的那一个已经确定，再去取较长的那一个的时候，满足如下条件：
- 较短字符串必须以逆序出现在较长串的一端；
- 同时，长串减去短串后剩下的部分，必须自成回文。
对于长串和短串的关系，具体说，有两种情况：
- 短串出现在长串的左端，比如 “abc” 和 “ba”，ba 的逆序就出现在 abc 的左端，而长串减去短串为 c，自成回文串，这种情况下可行的连接是把较短串放到右边，组成 abcba；
- 短串出现在长串的右端，比如 “cdcab” 和 “ba”，ba 的逆序就出现在 cdcab 的右端，而长串减去短串为 cbc，自成回文串，这种情况下可行的连接是把较短串放到左边，组成 bacdcab。
明确这个关系以后，改进的方式就在心中浮现了：如果拿到任意一个串，视之为短串，能够不需要遍历剩余所有的串，而比较快速地得到以他的反串为前缀或者后缀的对应长串，再来判断长串减去短串后余下部分是否是回文即可。
对下面的代码做一个简要说明，首先构造如下的数据结构：
- 根据字符串中字符的前后关系，分别建立两棵树，一棵是正序遍历，一棵是逆序遍历，而下面的 Node 即为树的节点。
- stringToIndex 这个 map 是从字符串到位置下标的映射，toReversed 是字符串正序向逆序的映射，toOriginal 则反之，这两个是用空间换时间，用来减少反复操作逆序的运算量的。
- stringToNodeForward 和 stringToNodeBackward 分别是字符串像正序遍历树和逆序遍历树中终点节点映射的 map。
构造以上结构完成之后，以这样的输入来举例：[ae, ab, bac, ca]。
- 左图是顺序树，右图是逆序树。
- 如果要找短串出现在长串右端的情况，需要把源串逆序，然后到顺序树中去找，比如 ab，逆序为 ba，到左图去找，找到中间的 ba，继续往下还有 c，而 c 自成回文，因此 bac+ab 满足题意；
- 如果要找短串出现在长串左端的情况，需要保持源串顺序，但是去逆序树中找，比如 ca，到右图去找，第三列找到 ca，继续往下还有 b，而 b 自成回文，因此 ca+bac 满足题意。
class Node {
Character ch;
Map<Character, Node> nextMap = new HashMap<>();
String word;
public Node(Character ch) {
this.ch = ch;
}
@Override
public String toString() {
return "\"" + word + "\"-" + nextMap;
}
}
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> stringToIndex = new HashMap<>();
Map<String, String> toReversed = new HashMap<>();
Map<String, String> toOriginal = new HashMap<>();
// key: reversed word, value: end node in the word letters iteration tree
Map<String, Node> stringToNodeForward = new HashMap<>();
// key: word, value: end node in the word letters backward iteration tree
Map<String, Node> stringToNodeBackward = new HashMap<>();
Node forwardRoot = new Node(null);
Node backwardRoot = new Node(null);
for (int i=0; i<words.length; i++) {
String word = words[i];
stringToIndex.put(word, i);
// forward
Node cursor = forwardRoot;
for (int j=0; j<word.length(); j++) {
Character ch = word.charAt(j);
if (!cursor.nextMap.containsKey(ch))
cursor.nextMap.put(ch, new Node(ch));
cursor = cursor.nextMap.get(ch);
}
String reverse = new StringBuilder(word).reverse().toString();
toReversed.put(word, reverse);
toOriginal.put(reverse, word);
cursor.word = word;
stringToNodeForward.put(reverse, cursor);
// backward
cursor = backwardRoot;
for (int j=word.length()-1; j>=0; j--) {
Character ch = word.charAt(j);
if (!cursor.nextMap.containsKey(ch))
cursor.nextMap.put(ch, new Node(ch));
cursor = cursor.nextMap.get(ch);
}
cursor.word = word;
stringToNodeBackward.put(word, cursor);
}
List<List<Integer>> list = new ArrayList<>();
for (String word : words) {
// case 1
String reverse = toReversed.get(word);
Node node = getNode(reverse, forwardRoot);
if (node != null) {
Set<String> set = new HashSet<>();
recursiveSearch(node, set, word.length(), true);
for (String p : set) {
List<Integer> item = new ArrayList<>(2);
item.add(stringToIndex.get(p));
item.add(stringToIndex.get(word));
if (item.get(0) != item.get(1)) // filter out the map to itself
list.add(item);
}
}
// case 2
node = getNode(word, backwardRoot);
if (node != null) {
Set<String> set = new HashSet<>();
recursiveSearch(node, set, word.length(), false);
for (String p : set) {
List<Integer> item = new ArrayList<>(2);
item.add(stringToIndex.get(word));
item.add(stringToIndex.get(p));
if (item.get(0) != item.get(1)) // filter out the map to itself
list.add(item);
}
}
}
return list;
}
private Node getNode(String s, Node root) {
Node n = root;
for (int i=0; i<s.length(); i++) {
Character ch = s.charAt(i);
Node next = n.nextMap.get(ch);
if (next != null)
n = next;
else
return null;
}
return n;
}
private void recursiveSearch(Node node, Set<String> set, int baseLength, boolean forward) {
if (node == null)
return;
if (node.word != null) {
String rest = null;
if (forward)
rest = node.word.substring(baseLength);
else if (node.word.length() != baseLength) // dedup
rest = node.word.substring(0, node.word.length() - baseLength);
// if the rest is palindrome
if (rest != null && new StringBuilder(rest).reverse().toString().equals(rest))
set.add(node.word);
}
for (Node next : node.nextMap.values())
recursiveSearch(next, set, baseLength, forward);
}
}
【题目】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)
【解答】题目本身很清晰，这道题 hard 难度，我确实折腾了好一会儿。我发现 LeetCode 的题目是越来越难做了，是我思维退步了还是出题人心理越来越阴暗了？……
用的还是分类 case 来归纳讨论的思路。虽然结果通过了，但是我并非很有信心，因为这里的 case 实在是折腾得我有点思路混乱。无论如何，我把我的解法放在了下面。
首先，大类上可以归纳为这样三种，我觉得这点是不会有错的：
- 膨胀型
- 收缩型
- 先膨胀再收缩型
一旦收缩以后就无法再膨胀了，因此没有 “先收缩再膨胀” 这种类型。下面代码的 shrink 变量表示是收缩还是膨胀，而 inflateToShrink 变量用来表示从膨胀到收缩那个临界变化的位置，在那个位置有很多特殊的 case。
public class Solution {
public boolean isSelfCrossing(int[] x) {
if (x==null || x.length<4)
return false;
boolean shrink;
if (x[2] <x[0])
shrink = true;
else if (x[2] > x[0])
shrink = false;
else if (x[3] < x[1])
shrink = true;
else if (x[3] > x[1])
shrink = false;
else
return true; // rectangle
boolean inflateToShrink = false;
for (int i=3; i<x.length; i++) {
if (shrink) {
if (x[i] > x[i-2]) // 1
return true;
else if (x[i] == x[i-2] && x[i-1] == x[i-3]) // 2
return true;
else // 3
;
} else {
if (x[i] == x[i-2] && x[i-1] == x[i-3]) { // 4
return true;
} else if (i == 3) {
if (x[i] == x[i-2]) // 5
inflateToShrink = true;
else if (x[i] < x[i-2]) // 6
shrink = true;
else // 7
;
} else if (x[i] < x[i-2]) {
if (x[i] + x[i-4] < x[i-2]) { // 8
shrink = true;
} else {
if (inflateToShrink) // 9
return true;
else // 10
inflateToShrink = true;
}
} else { // 11
;
}
}
}
return false;
}
}
在讨论区有非常清晰简洁的解法，我就不贴在这里了，也是分类讨论的办法，但是清晰很多，而且不需要状态变量。兴许这一类题目有某种思路简单的套路可以采用呢？
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.
【解答】要找出三个数，随着下标增加，数的大小也是递增的。这个问题其实通过仔细的分类讨论就可以解决。
参见下面的代码，核心逻辑是：
- 如果发现连续两个数递增的情况，就看第三个数，是不是继续递增，如果是，那就返回了；如果不是，更新第二个数为它。
- 如果是递减的，那就和第一个数比较，如果比第一个数大，就把它列为未来可能替换掉第一个数的备选；如果比第一个数小，就无视之。
public class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums==null || nums.length<3)
return false;
int first = 0, second = -1, third = -1;
// if there is already first and second number found (nums[first]<nums[second]),
// and if another number x occurs and x < nums[first],
// then we don't know if x should be put in the triplet if there is, so we put its index in a "firstBackup" variable temporarily
int firstBackup = -1;
for (int i=1; i<nums.length; i++) {
// increasing
if (nums[i]>nums[i-1]) {
if (second==-1) {
second = i;
} else {
if (nums[i]>nums[second])
return true;
else
second = i;
}
}
// decreasing
else {
if (second==-1) {
if (nums[i]<=nums[first])
first = i;
else
second = i;
} else {
if (nums[i]>nums[second]) {
return true; // unreachable, impossible case
} else {
if (nums[i]>nums[first]) {
if (firstBackup != -1) {
first = firstBackup;
firstBackup = -1;
}
second = i;
} else {
if (firstBackup==-1 || nums[i]<firstBackup)
firstBackup = i;
else
; // ignore
}
}
}
}
}
return false;
}
}
【题目】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.
【解答】寻找一个以 JFK 为首的连续路径，要求把机票都用完，每张机票只用一次。
一开始思路是，使用一个名为 visited 的 map 来存储机票是不是用过了，然后使用一个 value 为 list 的 map 来存储出发点和终点之间的对应关系。接着从 JFK 出发，遍历所有可能性。写代码的时候就觉得有些忐忑，因为看起来整个方法平平淡淡，并不优雅，结果不出意外地超时了。
public class Solution {
public List<String> findItinerary(String[][] tickets) {
List<String> result = new ArrayList<>();
if (null==tickets)
return null;
else if(tickets.length==0)
return result;
Map<String, Boolean> visited = new HashMap<>();
Map<String, List<String>> paths = new HashMap<>();
for (String[] pair : tickets) {
if (!paths.containsKey(pair[0]))
paths.put(pair[0], new ArrayList<String>());
paths.get(pair[0]).add(pair[1]);
visited.put(pair[0]+pair[1], false);
}
for (List<String> list : paths.values()) {
Collections.sort(list);
}
String key = "JFK";
result.add(key);
if (traverse(paths, visited, key, result))
return result;
else
return null;
}
private boolean traverse(Map<String, List<String>> paths, Map<String, Boolean> visited, String key, List<String> result) {
if (result.size()-1 == visited.size())
return true;
List<String> list = paths.get(key);
if (list==null)
return false;
for (String val : list) {
String visitedKey = key+val;
if (!visited.get(visitedKey)) {
visited.put(visitedKey, true);
result.add(val);
if (traverse(paths, visited, val, result)) {
return true;
} else {
result.remove(result.size()-1);
visited.put(visitedKey, false);
continue;
}
}
}
return false;
}
}
如何简化？其实和下面的那道二叉树先序遍历的题类似，图和路径的问题与树一样，也可以考虑使用入度和出度之间的关系来简化。
下面的简明无比的思路来自这里，核心是根据入度和出度的关系，入口的入度-1=出度，而出口的入度+1=出度。
还是使用 map 来存储出发点和终点的对应关系，但是使用优先级队列来存储终点列表，以免去手动 sort 之苦。
在下面的递归调用 visit 的方法中，传入当前所在的地点，只要 map 中还包含，就从它对应的终点中 poll 一个出来继续 visit，以此 while 不断进行，直到无法进行下去为止。为什么有了递归还需要这个 while？因为一个地点有可能遍历到好几次，即有多张机票的起点相同。
但是形成最终路径的时候，要在 while 循环之后，在已有路径的头部插入当前地点，因为当前地点是已生成路径的出发点。
// All nodes except entrance and exit should have the same indegree and outdegree,
// if a node indegree-1 == outdegree, it's the exit, and it's also the exit of "while" and the recursion
//
// use PriorityQueue so there's no need to sort the list explicitly
public class Solution {
private Map<String, PriorityQueue<String>> targets = new HashMap<>();
private List<String> route = new LinkedList<String>();
public List<String> findItinerary(String[][] tickets) {
for (String[] pair : tickets) {
if (targets.get(pair[0]) == null)
targets.put(pair[0], new PriorityQueue<String>());
targets.get(pair[0]).add(pair[1]);
}
this.visit("JFK");
return route;
}
private void visit(String airport) {
while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
this.visit(targets.get(airport).poll());
route.add(0, airport);
}
}
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
【解答】开始的思路是，既然是先序遍历，那给定串的第一个数肯定是 root，剩下的部分拆分成左子树和右子树，考虑所有拆分可能，并且用一个布尔型二维数组来表示一段区间是否是合法的二叉树以避免重复计算：
class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder==null)
return false;
String[] arr = preorder.split(",");
// (from, to]
return verify(arr, 0, arr.length, new Boolean[arr.length][arr.length]);
}
private boolean verify(String[] arr, int from, int to, Boolean[][] cache) {
if (from==to) {
return true;
} else if (from+2==to) {
return false;
}
else if (from+1==to) {
if ("#".equals(arr[from]))
return true;
else
return false;
}
if (cache[from][to-1] != null)
return cache[from][to-1];
String root = arr[from];
if ("#".equals(root)) {
cache[from][to-1] = false;
return false;
}
for (int i=from+2; i<to; i++) {
// a tree must be ended with "#"
if (!"#".equals(arr[i-1]))
continue;
boolean left = verify(arr, from+1, i, cache);
if (!left)
continue;
boolean right = verify(arr, i, to, cache);
if (right) {
cache[from][to-1] = true;
return true;
}
}
cache[from][to-1] = false;
return false;
}
}
这个思路确实容易想到，可是很快超时了。在讨论区我看到了一种巧妙的办法，而且具有一定的典型性，对于树的问题可以通过利用入度和出度之间的关系来简化计算：
对于每一个节点，我们认定从父节点来的路径为入，通往子节点的路径为出，
- 那么显而易见 root 的入度为 0，而出度为 2；
- 其它非叶子节点的入度为 1，出度为 2；
- 叶子节点的入度为 1，出度为 0。
有了这样的关系，我们就可以沿着先序遍历的顺序从 root 开始挨个遍历，使用 diff 来跟踪当前 (入度-出度) 的值，并且给定一个初始补偿值 1，这就意味着，如果这个先序遍历是合法的，那么整个便利过程中，应该不会出现 diff 小于 0 的情况，并且，在遍历完成后，diff 应该等于 0。
这个解法的复杂度只有 O(n)，而且不用考虑使用额外占用空间复杂度的布尔数组来存储中间值。
class Solution {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1;
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
}
【题目】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.
【解答】要给一个升序正整数数组打补丁，即添加上若干个数以后，使得使用这些数能够相加组合出从 1 到 n 所有的值来。
如果按照正向的思路去想，当前这个正整数组能够产生在 1 到 n 之间的哪些数，还差哪些数，添加怎样的数去覆盖这些差的数，就会走入死路，非常难解。但是如果从另外一个角度去看这个问题，问题就好办很多。把 1 到 n 这些数从小到大挨个拿出来看，第一个数能不能生成，第二个数能不能生成……一直到第 n 个：
- x 表示当前需要被生成的数；
- max 表示现在这些数里面能够连续覆盖到的最大的数，即覆盖 1 到 max；
- index 表示现有升序正整数数组的下标。
好，考虑这样的递推关系：当前 [1, max] 是可以被覆盖的，那么下面我要从 nums 中去取下一个数，
- 如果这个数取出来和 max+1 一样大，那就说明这个能覆盖数的范围正好接上了，即从原来的 [1,max] 变成了 [1,max+1]；
- 但是如果这个数大于 max+1，说明接不上了，即 max+1 没有办法生成，这就需要打 patch，而这个 patch 就是 max+1。
上面这一步的思考非常重要，想到的话基本上解题就顺理成章了。
那么如果打了 max+1 这个 patch，新的覆盖范围会变成多少呢？原来的范围是 [1,max]，现在有了 max+1，这就意味着原来的范围中的每一个数都加上 max+1 也可以生成了，即可以覆盖 [1+(max+1), max+(max+1)]，再加上原来就已经覆盖的 [1,max]，于是最新的覆盖范围是 [1, max+(max+1)]。
public class Solution {
public int minPatches(int[] nums, int n) {
// the index indicates [1, x] needs to be covered; use long to avoid overflow
long x = 1;
// the index in nums
int index = 0;
// for now [1, max] can be covered
long max = 0;
int patch = 0;
while (x<=n) {
// a new number is needed to cover x
if (max<x) {
// no more existing number, or the next number can't cover max+1
if (index>=nums.length || nums[index]>max+1) {
// patch needed, and the patch number is max+1
max = max + (max+1);
patch++;
} else {
// the new range from max to (max+nums[index]) can be covered because
// before now from 1 to max can be covered, and now there's a new number nums[index]
// so adding nums[index] to previous range [1, max] we'll get a new covered range [nums[index]+1, nums[index]+max],
// union both above to get the range [1, max+nums[index]]
max = max + nums[index];
index++;
}
} else {
// no new number needed
x = max+1;
}
}
return patch;
}
}
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.
【解答】这道题比较简单。要找出最长的递增路径。基本思路是尝试以每一个点为起点去遍历寻找，但是如果已经找过的部分，就不要重复找了。因此用一个 map 来存储这个已经找过的结果，lenMap[i][j] 表示以 matrix[i][j] 为起点的最长路径的长度。
public class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix==null)
return 0;
int h = matrix.length;
if (h==0)
return 0;
int w = matrix[0].length;
if (w==0)
return 0;
int[][] lenMap = new int[h][w];
int max = 0;
for (int i=0; i<h; i++) {
for (int j=0; j<w; j++) {
max = Math.max(max, getLen(matrix, i, j, lenMap));
}
}
return max;
}
private int getLen(int[][] matrix, int i, int j, int[][] lenMap) {
int h = matrix.length;
int w = matrix[0].length;
if (i<0 || i>=h || j<0 || j>=w)
return 0;
if (lenMap[i][j]>0)
return lenMap[i][j];
int len = 1;
if (i+1<h && matrix[i][j]<matrix[i+1][j]) {
int down = getLen(matrix, i+1, j, lenMap);
len = Math.max(len, down+1);
}
if (j+1<w && matrix[i][j]<matrix[i][j+1]) {
int right = getLen(matrix, i, j+1, lenMap);
len = Math.max(len, right+1);
}
if (i-1>=0 && matrix[i][j]<matrix[i-1][j]) {
int up = getLen(matrix, i-1, j, lenMap);
len = Math.max(len, up+1);
}
if (j-1>=0 && matrix[i][j]<matrix[i][j-1]) {
int left = getLen(matrix, i, j-1, lenMap);
len = Math.max(len, left+1);
}
lenMap[i][j] = len;
return lenMap[i][j];
}
}
【题目】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 …
【解答】题目本身没有什么特别的，只不过要求 O(1) 的空间复杂度，这就意味着基本上只能用简单的指针来解决，不能用辅助栈或者辅助数组。题目比较简单，注意对奇数链表和偶数链表头和尾的把握。
public class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode odd = new ListNode(0);
ListNode tailOdd = odd;
ListNode even = new ListNode(0);
ListNode tailEven = even;
boolean isOdd = true;
ListNode cur = head;
while (cur != null) {
if (isOdd) {
tailOdd.next = cur;
tailOdd = cur;
} else {
tailEven.next = cur;
tailEven = cur;
}
cur = cur.next;
isOdd = !isOdd;
}
tailOdd.next = even.next;
tailEven.next = null;
return odd.next;
}
}
【题目】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.
【解答】要找数组满足条件的区间数，要求区间内数之和在 i 和 j 之间。确实很容易想到 n 平方的解法，很清晰也很简单，但是如果要进一步优化时间复杂度，数组并非有序，就不是那么好办了。于是思路开始自然地往动态规划上面靠，可是怎样减少计算量呢？任意一个区间的和，可以由它邻近区间的一个已知结果加减差异元素来得出，可是这样的算法依然要求遍历每一个区间的可能，并未减小复杂度的量级。
这个问题的常规解法有两种，第一种是树状数组（Fenwick tree，或者 Binary Indexed Tree – BIT），对于它这个问题是很有代表性的。它用来解决的问题是数组元素更新和连续的 N 个数求和之间性能开销的平衡问题，换言之，如果我总是需要对某个数组的元素进行更新，而更新以后我有需要得到它任意区间和的最新值，那么用树状数组往往可以获得比较好的性能。定义上不是那么直观，如果原数组是 array，树状数组 BIT 元素的通式为：BIT[i] = array[i–2^k+ 1] + … + array[i]，其中 2^k=i&(i^(i-1))，即 i&(-i)。但是转换成图示可能会容易理解一点，下面这张图来自维基百科，非常形象地说明了树状数组的构件过程：有这样一个数组 [1,2,3,4,5]，从左往右每次取一个元素，每一个 BIT 的元素都代表了其中一段的和。这样在扫描数组的时候，可以一段一段扫描，而不是像普通数组那样一个一个数地扫描；在更新的时候，也只需要遍历从 BIT 树的叶子节点一路往上走，直到根为止，没有遍历到的节点不需要更新。这个复杂度就可以降到 nlogn。
下面这张图（来自这里）更容易看出每一个 BIT 元素所代表的哪一段的区间和：
遗憾的是，BIT 树在 JDK 里面没有实现，因此即便好不容易想到了用它来解，还需要自己去实现（参考实现）BIT，这就让这道题变成 hard 难度。
另一种解法来自这个讨论中的高票回答，不需要 BIT 的知识，却巧妙借用归并排序的思想，二分归并这个行为本身的复杂度 log n，乘以每一个子数组遍历的复杂度 n，因此复杂度就是 nlogn。如果我们能对原数组进行排序，这样就可以利用二分查找的方法把复杂度降下来，但是因为我们需要找的是区间的和，区间意味着连续的数串，因此对原数组排序是不可行的。但是，如果我们定义一个和数组 sums，sums[i] 表示的是原数组签名 i 个元素的和，那么我们就可以对 sums[i] 来进行归并排序，这一思路是解题的关键：
- 取中点，然后对中点之前的前半段进行归并排序，并返回符合要求的元素个数，再对后半段做同样的事；
- 对于每个给定的 i，对数组中区间和小于下限的个数记为 k，小于上限的个数记为 j，那么符合要求的元素个数就是所有 (j-k) 的累加。
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}
private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
if (end - start <= 1) return 0;
int mid = (start + end) / 2;
int count = countWhileMergeSort(sums, start, mid, lower, upper)
+ countWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (k < end && sums[k] - sums[i] < lower) k++;
while (j < end && sums[j] - sums[i] <= upper) j++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
count += j - k;
}
System.arraycopy(cache, 0, sums, start, t - start);
return count;
}
}
【题目】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 的乘方数来。当心溢出就好。
public class Solution {
private Set<Integer> all = new HashSet<>();
public Solution() {
int upperLimit = Integer.MAX_VALUE/3;
int n=1;
while(true) {
all.add(n);
if (n<upperLimit)
n = n*3;
else
break;
}
}
public boolean isPowerOfThree(int n) {
return all.contains(n);
}
}
【题目】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?
【解答】要最终排成一大一小依次排列的结果。我的做法是：
- 先排序；
- 然后把大的一半先拿出来，放到最终结果的奇数位置上去；
- 再把剩下小的一半拿出来，放到最终结果的偶数位置上去。
要着重说明的一点就是，上面这个过程，遍历都是逆序的。也就是说，排好序之后从左到右是从小到大，但是取数的时候是从右到左，即从大到小来取的。
为什么要这样做？
因为排序以后的数组是从小到大的，因此第一遍拿大的一半，那么最大的数会在结果数组靠左的位置，而原数组中居中的数会在结果数组靠右的位置；第二遍拿小的一半，于是原数组中居中的数会在结果数组靠左的位置，而最小的数会在结果数组中靠右的位置——于是居中的数被拆开了，分别在结果数组的最左边和最右边。这样就避免了重复的数落在了结果数组中相邻的位置。
比如说 4，5，5，6：如果按照上面的方法逆序遍历会得到 5，6，4，5，但是如果顺序遍历，会得到 4，5，5，6，于是问题就出在相邻的两个 5 上。
// time: O(nlogn), space: O(n)
public class Solution {
public void wiggleSort(int[] nums) {
// clone and sort
int[] copy = nums.clone();
Arrays.sort(copy);
int index = copy.length-1;
// fill in nums with odd index, going backward in array copy:
// they're all large numbers
for (int i=1; i<nums.length; i+=2) {
nums[i] = copy[index];
index--;
}
// fill in nums with even index, going backward in array copy:
// they're all small numbers
for (int i=0; i<nums.length; i+=2) {
nums[i] = copy[index];
index--;
}
}
}
【题目】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.
【解答】要求最少钱币的数目。
如果有 1、2、5 三枚面值不同的硬币，那么对于任意目标值 x，我如果能知道 (x-1)、(x-2) 和 (x-5) 这三个值所用到的最少钱币数目就好了。
想到这里，就可以用动态规划来解答了。
public class Solution {
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
return coin(coins, coins.length-1, amount, new int[coins.length][amount+1]);
}
private int coin(int[] coins, int pos, int amount, int[][] cache) {
if (amount==0)
return 0;
if (cache[pos][amount]!=0)
return cache[pos][amount];
int min = -1;
for (int i=pos; i>=0; i--) {
if (coins[i]>amount)
continue;
int count = coin(coins, i, amount-coins[i], cache);
if (count!=-1 && (count<min || min==-1))
min = count;
}
if (min!=-1)
min++;
cache[pos][amount] = min;
return min;
}
}
【题目】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]
【解答】给两串数 m 和 n，分别取几个，加起来的个数不超过 k，并且从 m 和 n 中取的子串保持在原串中顺序相对位置，然后任意位置 merge 起来。要求最后得到的那一串数所代表的那个数尽可能大。
看起来，这道题给人的第一印象是，从 m 中选一串数，从 n 中也选一串数，这两个是变化点。但是如果这两串数定下来，那么下面的行为类似于归并排序，每一个子串都有一个指针记录当前位置，从这两个子串中取数每次都取尽量大的数。
顺着这样的思路，我一开始建立了一个比较复杂的模型，一个三维的动态规划。但是我们一般只会接触到最多二维的动态规划，所以当时的感觉就觉得可能走到歪路上去了。果然，还是过于复杂，执行超时了。简单介绍当时的思路。
建立 dp[x][y][k] 表示第一个子串从 m 的 [x, m.length) 中取，第二个子串从 n 的 [y, n.length) 中取，那么分析如下四种 case：
- case 1，m[x] 是结果中的一部分，因此当我拿掉 m[x] 的时候，两个子串和 k 分别变成了 m[x+1, m.length)，n[y, n.length)，k-1
- case 2，n[y] 是结果中的一部分，因此当我拿掉 n[y] 的时候，两个子串和 k 分别变成了 m[x, m.length)，n[y+1, n.length)，k-1
- case 3，m[x] 不是结果中的一部分，因此当我拿掉 m[x]，对结果没有影响，两个子串和 k 分别为 m[x+1, m.length)，n[y, n.length)，k
- case 4，n[y] 不是结果中的一部分，因此当我拿掉 n[y]，对结果没有影响，两个子串和 k 分别为 m[x, m.length)，n[y+1, n.length)，k
也就是说，当前的子串状态，可能源于上面四个 case，发生变化得到，具体哪一个呢，需要再去比较以上这 4 个 case 情况下的大小，取最大的结果……很多数组拷贝，看着就很冗长。
class Item {
int[] data;
}
public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
Item[][][] dp = new Item[nums1.length+1][nums2.length+1][k+1];
Item result = maxNumber(nums1, nums2, 0, 0, k, dp);
return result.data;
}
private Item maxNumber(int[] nums1, int[] nums2, int x, int y, int k, Item[][][] dp) {
if (dp[x][y][k]!=null)
return dp[x][y][k];
Item item = new Item();
if (k==0) {
item.data = new int[]{};
dp[x][y][k] = item;
return item;
}
if (nums1.length-x + nums2.length-y < k)
return null;
// case 1: pick from nums1
Item pickNums1 = null;
if (x<nums1.length)
pickNums1 = buildItem(nums1[x], maxNumber(nums1, nums2, x+1, y, k-1, dp));
// case 2: pick from nums2
Item pickNums2 = null;
if (y<nums2.length)
pickNums2 = buildItem(nums2[y], maxNumber(nums1, nums2, x, y+1, k-1, dp));
// case 3: pass in nums1
Item passNums1 = null;
if (x<nums1.length)
passNums1 = maxNumber(nums1, nums2, x+1, y, k, dp);
// case 4: pass in nums2
Item passNums2 = null;
if (y<nums2.length)
passNums2 = maxNumber(nums1, nums2, x, y+1, k, dp);
// choose the largest one
Item result = max(pickNums1, pickNums2, passNums1, passNums2);
dp[x][y][k] = result;
return result;
}
private Item buildItem(int num, Item item) {
if (item==null)
return null;
Item newItem = new Item();
newItem.data = new int[item.data.length+1];
System.arraycopy(item.data, 0, newItem.data, 1, item.data.length);
newItem.data[0] = num;
return newItem;
}
private Item max(Item... items) {
Item max = null;
for (Item item : items) {
boolean result = compare(max, item);
if (!result)
max = item;
}
return max;
}
private boolean compare(Item a, Item b) {
if (b==null) return true;
if (a==null) return false;
if (a.data.length > b.data.length) return true;
if (a.data.length < b.data.length) return false;
for (int i=0; i<a.data.length; i++) {
if (a.data[i] > b.data[i])
return true;
if (a.data[i] < b.data[i])
return false;
}
return true;
}
}
在这个网站上有一个好的解法，我拿过来了。基本思路是：
- 不管怎么取，要从 nums1 中取 i 个数组成的子数组 A，要从 nums2 中取 k-i 个数组成的子数组 B；
- 那么当给定某一个 i 的时候，A 要尽量大，而这个尽量大和 B 无关；同样，B 要尽量大，也和 A 无关，因此，在给定某一个 i 的时候，可以得到唯一的最佳解 A 和最佳解 B——这个强化条件然后分治的思路是简化这个问题的核心；
- 接着计算 A 和 B，即要从一个给定数组中，挑出给定数目的数所组成的子数组，使之所表示的数最大，就比较简单了；
- 最后再遍历所有 i 的取值，得出最终结果。
public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); i++) {
int[] res1 = get_max_sub_array(nums1, i);
int[] res2 = get_max_sub_array(nums2, k - i);
int[] res = new int[k];
int pos1 = 0, pos2 = 0, tpos = 0;
while (pos1 < res1.length || pos2 < res2.length) {
res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
}
if (!greater(ans, 0, res, 0))
ans = res;
}
return ans;
}
public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
if (nums1[start1] > nums2[start2]) return true;
if (nums1[start1] < nums2[start2]) return false;
}
return start1 != nums1.length;
}
public int[] get_max_sub_array(int[] nums, int k) {
int[] res = new int[k];
int len = 0;
for (int i = 0; i < nums.length; i++) {
while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
len--;
}
if (len < k)
res[len++] = nums[i];
}
return res;
}
}
【题目】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.
【解答】如果你和我开始一样，尝试用循环去模拟所有的灯泡开关行为，能得到答案，但是大的 case 肯定会超时。
在讨论区找打了一个精妙的解答。任意一个数，如果可以分解成两个数 a 和 b 的乘积，那么当 a 和 b 不等的时候，就意味着成对出现了灯状态改变的行为。例如 36=4×9，36=9×4，即偶数次的改变相当于不变。但是，如果 a=b，在这种唯一的情况下，这种状态改变是成单的，并最终导致了灯泡状态的改变。也就是说，这种情况一定意味着该数可以被开平方。
public class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
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.
【解答】要找出互无重复字母的两个单词长度之积的最大值，很容易想到的是，不存在大小和递推关系，只有等和不等，因此如果没有特殊的方法，要两两比较，O(n²) 这样的复杂度是少不了的。
那如果是这样的话，下面要解决的问题就是：从中给出两个单词，要比较这两个单词之间是否有字母重复，怎样让时间和空间复杂度尽量小。
开始尝试用 HashSet 来解决，即把一个单词中出现的字母全部找出来放到 HashSet 里面，如果另一个单词中的字母能从这个 HashSet 中找到，就说明有重复，反之则没有。我照着思路做了以后，超时了。
于是使用 BitMap 来改进：一个整数有 32 位，因此有 32 个位置可以表示 0 或者 1，但是字母只有 26 个，因此如果某字母出现过，那么在相应位上面就为 1 而不为 0，这样一个整数就可以表示任意一个单词中出现的字母种类。把单词转换成整数的方法可以作为 “预处理” 的步骤之一，而实际在实际的比较中，只需要先看两个单词所代表的整数相 “与”，如果全 0 则表示无重复字母。用这种方法可比比较整个 HashSet 效率高多了。
public class Solution {
public int maxProduct(String[] words) {
// bit map
List<Integer> list = new ArrayList<>();
for (String w : words) {
int num = 0;
for (int i=0; i<w.length(); i++) {
num = num | getMask(w.charAt(i));
}
list.add(num);
}
int max = 0;
for (int i=0; i<list.size(); i++) {
for (int j=i+1; j<list.size(); j++) {
if ( ( list.get(i).intValue() & list.get(j).intValue() ) != 0 )
continue;
max = Math.max(words[i].length() * words[j].length(), max);
}
}
return max;
}
private int getMask(char c) {
return 1 << (c - 'a');
}
}
【题目】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 来存放字母出现的位置：key 为字母，value 为出现位置下标的数组（因为可能出现多次，所以用数组）。
- 这个 map 构造完成之后，从 a 开始遍历检查到 z，期间用 lastPos 保存上一个字母选取的位置：如果当前字母的位置都在 lastPos 的左边，那就选一个最小的；如果有存在在 lastPos 右边的，就二分查找取一个最接近且大于 lastPos 的。
举例来说：对于字符串 “acbab”，构造这样的 map：
- a -> [0, 3]
- b -> [2, 4]
- c -> [1]
然后开始从 a-z 遍历：
- 对 a，有两个，但是 lastPos 为初始值-1，因此直接取最小的，就是下标为 0 的 a，赋值 lastPos=0；
- 对 b，出现位置有 lastPos 右边的，二分查找取最接近且比 0 大的，于是取了下标 2 的 b，赋值 lastPos=2；
- 对 c，发现全都在 lastPos 左边的，取最小的（也只有一个），于是去了下标为 1 的，赋值 lastPos=1。
于是结果为 “acb”，看起来逻辑是对的。
但是写完代码跑用例的时候傻眼了，有一个 case 用这个方法是过不去的，比如 “cbacdcbc”，用上面的办法得到的是 “adbc”，但实际应该是 “acdb”。
原因在于，选 a 的时候没问题，选 b 的时候也没问题，但是选 c 的时候，上面的方法本质上是一种贪心的策略，因此挑了一个出现在 b 右侧的 c，而在这里用贪心是行不通的，因为 d 的关系。
public class Solution {
public String removeDuplicateLetters(String s) {
Map<Character, List<Integer>> map = new HashMap<>();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (!map.containsKey(ch))
map.put(ch, new ArrayList<>());
map.get(ch).add(i);
}
int lastPos = -1;
Map<Character, Integer> posMap = new HashMap<>();
for (int i=0; i<26; i++) {
char ch = (char)('a' + i);
if (!map.containsKey(ch))
continue;
if (lastPos==-1) {
lastPos = map.get(ch).get(0);
} else {
List<Integer> list = map.get(ch);
if (list.get(list.size()-1) > lastPos) {
lastPos = binarySearch(map.get(ch), lastPos);
} else {
lastPos = map.get(ch).get(0);
}
}
posMap.put(ch, lastPos);
}
List<Character> resultList = new LinkedList<>();
for (Map.Entry<Character, Integer> entry : posMap.entrySet()) {
char ch = entry.getKey();
int pos = entry.getValue();
int insertPos = 0;
while(insertPos<resultList.size() && pos>posMap.get(resultList.get(insertPos)))
insertPos++;
resultList.add(insertPos, ch);
}
String result = "";
for (char ch : resultList) {
result += ch;
}
return result;
}
private int binarySearch(List<Integer> list, int pivot) {
int left = 0;
int right = list.size()-1;
while (left<=right) {
int mid = (left+right)/2;
if (list.get(mid)>pivot)
right = mid - 1;
else
left = mid + 1;
}
return list.get(left);
}
}
在题目的讨论中有一种正确而且简洁的解法。思路是：
- 用一个数组 cnt 记录每个字母出现的次数；
- 用 pos 表示是当前 s 中最小字母出现的位置，遍历 s 中的每一个字母，如果当前位置 i 的字母的字典序比 pos 所代表的字母更小，就更新 pos；
- cnt 中表示该位置 i 的字母的次数减一，如果为 0 了就跳出遍历；
- 以 pos 上所指的字母为本次方法调用所选择的字母，余下字母继续递归调用执行以上逻辑。
- 第一次遍历完 a 以后跳出，选出 a 来，然后把 a 左边的子串 “cd” 删掉，余下子串 “cdcbc”；
- 第二次便利完 d 以后跳出，选出 c 中的第一个来，这个 c 左边没有子串，右边子串中的 c 删掉，因此余下子串 “db”；
- 第三次便利完 d 以后跳出，选出 d 来，余下子串 “d”；
- 第四次选出 c 来，于是结果就是 “acdb”。
public class Solution {
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
int pos = 0;
for (int i = 0; i < s.length(); i++)
cnt[s.charAt(i) - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos))
pos = i;
if (--cnt[s.charAt(i) - 'a'] == 0)
break;
}
return s.length() == 0 ? "" : s.charAt(pos)
+ removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
}
}
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].
【解答】每次取 nums 数组的最右边的 x 个数，形成数列 arr，把其中比 arr[0] 小的数的个数统计出来为 y，随着 x 从 n 变到 1，得出这个统计值 y 变化的结果并形成数组返回。
这个 x 如果是从 1 变到 n，可能会更好计算。因为我每时每刻只要维护一个有序数组用来表示当前 arr 中所有的数们，只不过他们是被排序了的，x 每次递增则意味着要从 nums 里面取一个新数放到这个有序数组里面去。根据放进去的位置，就能够知道当时有多少个数比它小。
public class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> sorted = new ArrayList<>(nums.length);
List<Integer> result = new ArrayList<>(nums.length);
for (int i=nums.length-1; i>=0; i--) {
int index = insert(nums[i], sorted);
result.add(0, index);
}
return result;
}
private int insert(int num, List<Integer> sorted) {
if (sorted.isEmpty()) {
sorted.add(num);
return 0;
}
int left = 0;
int right = sorted.size() - 1;
while(left<=right) {
int mid = (left+right)/2;
if (sorted.get(mid)>=num) {
right = mid-1;
} else {
left = mid+1;
}
}
sorted.add(left, num);
return left;
}
}
【题目】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.
【解答】首先读懂题意。Super Ugly 数是指一串正数，他们的质因数由给定的 prime list 组成，现在给定一个 prime list，要求第 k 个 Super Ugly 数。
建立这个 Super Ugly 数序列的数组 arr，并且首元素置为 1。
再创建一个 indexArr 数组，其中的下标 i 表示在 primes 中的第 i 个质数，而存放的值表示 arr 中的下标。为什么要建立它，主要是因为对于任何一个在 primes 中的质数，如果要乘以 arr 中的某一个数的时候，需要用一个数记录当前在哪个数上面，而它前面的已经乘过了，因此现在要乘以 primes[x] 的话，需要从 arr[indexArr[x]] 开始。也就是说，这是一个存放的是下标的数组。这个思路其实有点绕，也是这个题目的关键，如果这一步想出来了这个题就没有难度了。
最后，注意去重的处理。
总的来说，我觉得这道题要做对挺难的啊，不止 Medium 难度。
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n<=0 || primes==null || primes.length==0)
throw new IllegalArgumentException();
int[] arr = new int[n];
arr[0] = 1;
// each prime owns its dedicated index on arr
int[] indexArr = new int[primes.length];
for (int i=1; i<n; i++) {
int min = Integer.MAX_VALUE;
int posToIncrease = -1;
for (int j=0; j<primes.length; j++) {
int index = indexArr[j];
int prime = primes[j];
if (prime*arr[index] < min) {
min = prime * arr[index];
posToIncrease = j;
}
}
indexArr[posToIncrease] += 1;
// dedup
if(arr[i-1] == min)
i--;
else
arr[i] = min;
}
return arr[arr.length-1];
}
}
【题目】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
【解答】这道题其实难度我觉得 Medium 比较合适。
直观上，要使结果尽可能大，那么大的数要晚些引爆，这样不断参与乘法运算，就能使结果尽可能大。
对于首尾气球的处理，题目已经给了提示，nums[-1] = nums[n] = 1，因此创建一个长度为 nums.length+2 的数组。动态规划的记忆数组 cache[from][to] 表示从 from 个气球到 to 个气球，全部爆炸以后得到的值是多少。
接着，每次爆炸的时候，考虑根据切分点 i 把当前气球序列分成 leftPart 和 rightPart 两部分，其中 leftPart 为 [from, i)，rightPart 为 (i, to]，因此递归求出 leftPart 和 rightPart 的值，并和 nums[i] 相乘，取不同 i 取值下的最大值。
public class Solution {
public int maxCoins(int[] nums) {
int[] clone = new int[nums.length + 2];
clone[0] = 1;
clone[nums.length + 1] = 1;
for (int i = 0; i < nums.length; i++)
clone[i + 1] = nums[i];
int[][] cache = new int[nums.length + 2][nums.length + 2];
return maxCoins(clone, 1, nums.length, cache);
}
public int maxCoins(int[] nums, int from, int to, int[][] cache) {
if (cache[from][to] > 0)
return cache[from][to];
int max = 0;
for (int i = from; i <= to; i++) {
int leftPart = maxCoins(nums, from, i - 1, cache);
int rightPart = maxCoins(nums, i + 1, to, cache);
max = Math.max(max, leftPart + nums[from - 1] * nums[i] * nums[to + 1] + rightPart);
}
cache[from][to] = max;
return max;
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
能讲解下做 LeetCode 的好处么？
算法练习而已。
有很多途径可以选，也可以选别的方式。