双指针: 一个指针是for循环，第二个指针是for循环之外的一个指针(通常是int)。
Leetcode 27. Remove Element
public int removeElement(int[] nums, int val) {
int res = 0;
for(int i = 0; i< nums.length;i++){
if(nums[i] != val){
nums[res++] = nums[i];
}
}
return res;
}
Leetcode 26. Remove Duplicates from Sorted Array.
注意 res-1.
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int res = 1;
for(int i = 1; i< nums.length; i++){
if(nums[res-1] != nums[i]){
nums[res++] = nums[i];
}
}
return res;
}
Leetcode 80. Remove Duplicates from Sorted Array II.
注意 res-2。
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0){ return 0;}
int res = 2;
for(int i = 1;i < nums.length; i++){
if(nums[res -2] != nums[i] ){
nums[res++] = nums[i];
}
}
return res;
}
Leetcode 277. Find the Celebrity.
public int findCelebrity(int n) {
if(n<2) return -1;
int possible = 0;
for(int i = 1; i< n;i++){
if(knows(possible,i)){
possible = i;
}
}
for(int i = 0; i< n; i++){
if(possible != i && (knows(possible,i)||!knows(i,possible)) ){
return -1;
}
}
return possible;
}
Leetcode 189. Rotate Array.
方法1. 用int[] temp来记录整个新int[]。
Time: O(n). Space: O(n).
public void rotate1(int[] nums, int k ){
int[] temp = new int[nums.length];
for(int i = 0; i< nums.length; i++){
temp[(i + k)% nums.length] = nums[i];
}
for(int i = 0; i< nums.length; i++){
nums[i] = temp[i];
}
}
方法2. reverse.
Time: O(n). Space: O(1).
[0 1 2 3 4 5 6]
reverse 变为 [6 5 4 3 2 1 0]
然后 [4 5 6 3 2 1 0]
[4 5 6 0 1 2 3]
public void rotate2(int[] nums, int k ){
k %= nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
}
public void reverse(int[] nums, int start, int end){
while(start < end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
方法3. 用temp仅记录最后k位。
Time: O(n). Space: O(1).
public void rotate2(int[] nums, int k ){
k %= nums.length;
int[] temp = new int[k];
for(int i = 0; i< k;i++){
temp[i] = nums[nums.length-k+i];
}
for(int i= nums.length-1;i>=k;i--){
nums[i] = nums[i-k];
}
for(int i = 0; i<k;i++){
nums[i] = temp[i];
}
}
Leetcode 41. First Missing Positive
桶排序的思想。关键：while 和 xxx != xx 条件。
Time: O(n), Space: O(1).
class Solution {
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0) return 1;
for(int i =0; i< nums.length; i++){
while(nums[i]>0 && nums[i]<= nums.length && nums[nums[i]-1]!= nums[i]){
int temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
}
}
for(int i =0; i< nums.length; i++){
if(nums[i] != i+1){
return i+1;
}
}
return nums.length + 1;
}
}
Leetcode 299. Bulls and Cows.
Time: O(n), Space: O(1).
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;
int[] count = new int[10]; // 每个位置分别记录 0 - 9 数字的情况
for(int i = 0; i< secret.length();i++){
if(secret.charAt(i) == guess.charAt(i)){
bulls++;
} else {
if(count[secret.charAt(i) - '0'] < 0) cows++; // <0 说明guess 中有xx数量的(secret.charAt(i) - '0')值被计入count中对应位置
count[secret.charAt(i) - '0']++; //把 第i位的secret 记入count
if(count[guess.charAt(i) - '0'] >0) cows++; // >0 说明secret 中有xx数量的(guess.charAt(i) - '0')值被计入count中对应位置
count[guess.charAt(i)-'0']--; //把 第i位的guess 记入count
/**
* 这四行代码相当于
* if(count[secret.charAt(i) - '0']++ < 0) cows++;
* if(count[guess.charAt(i) - '0']-- >0) cows++;
**/
}
}
return bulls + "A" + cows + "B";
}
}
Leetcode 134. Gas Station
Time: O(n), Space: O(1).
两个想法：
1）If car starts at A and can not reach B. Any station between A and B
can not reach B.(B is the first station that A can not reach.)
2）If the total number of gas is bigger than the total number of cost. There must be a solution.
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas.length == 0 || cost.length ==0 || gas.length != cost.length ) return -1;
int total = 0, start = 0, startAddingUp = 0;
for(int i = 0; i< gas.length;i++){
total += gas[i] - cost[i];
if(startAddingUp < 0){
startAddingUp = gas[i] - cost[i];
start = i;
} else {
startAddingUp += gas[i] - cost[i];
}
}
return total < 0 ? -1 : start;
}
}
Leetcode 118. Pascal's Triangle
在原list首部增加int 1，然后从第二个开始两者相加；把新list加到List<List<Integer>>中
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for(int i = 0; i< numRows; i++){
list.add(0,1);
for(int j = 1; j < list.size() -1 ; j++){
list.set(j,list.get(j)+list.get(j+1));
}
res.add(new ArrayList<>(list) ); // 重点: 创建new list
}
return res;
}
Leetcode 119. Pascal's Triangle II
public List<Integer> getRow(int rowIndex) {
//List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < rowIndex +1; i++){
list.add(0,1);
for(int j = 1; j< list.size()-1;j++){
list.set(j,list.get(j)+list.get(j+1));
}
}
return list;
}
Leetcode 169. Majority Element
Moore Voting Algorithms算法介绍：Time: O(n), Space: O(1)
摩尔投票算法：每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。
//法1. 排序，取中间位置的值
Time: O(nlogn), Space: O(1).
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[ nums.length / 2 ];
}
//法2. 用HashMap 记录
Time: O(n), Space: O(n).
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int num: nums){
if(!map.containsKey(num)){
map.put(num,1);
} else {
map.put(num,map.get(num)+1);
}
if(map.get(num) > nums.length/2 ){
res = num;
break;
}
}
return res;
}
// 法3. Moore Voting Algorithm.
Time: O(n), Space: O(1).
public int majorityElement(int[] nums) {
int res = 0, count = 0;
for(int num : nums){
if(count ==0) res = num;
if(res == num ){
count++;
} else {
count--;
}
}
return res;
}
Leetcode 229. Majority Element II : 要求Time O(n) 和 Space O(1).
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<>();
int num1 = 0, num2 = 0;
int count1 = 0, count2 = 0;
for(int num: nums){
if(num == num1){
count1++;
} else if (num == num2){
count2++;
} else if (count1 == 0){
count1 ++;
num1 = num;
} else if (count2 == 0){
count2++;
num2 = num;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for(int num: nums){ //需要重新过一遍，验证
if(num == num1) {count1++;}
else if(num == num2) {count2++;} // 注意这里else if. 不然的话可能num1= num2，就麻烦
}
if(count1 > nums.length/3){res.add(num1);}
if(count2 > nums.length/3){res.add(num2);}
return res;
}
Leetcode 274. H-Index
//法1. 排序后，从尾部开始遍历。
Time: O(nlogn), Space: O(1).
public int hIndex(int[] citations) {
Arrays.sort(citations);
int res = 0;
while(res < citations.length && citations[citations.length -1 -res] > res ){
res++;
}
return res;
}
//法2. 用新的int[] 记录>=每一位的数量。
比如说，array X: [x1,x2,x3,x4] 对应的helper [h0,h1,h2,h3] 含义是：
h4表示 X 中值>=3+1的数量；同理，h1表示>=0+1的数量。
我们不用记录>=0的数量, 因为在0的情况下返回值为0.
Time: O(n), Space: O(n).
public int hIndex(int[] citations) {
int[] helper = new int[citations.length];
for(int i = 0; i< citations.length; i++){
if( citations[i]>=citations.length ){
helper[citations.length-1]++;
} else if(citations[i] >= 1){
helper[citations[i]-1]++;
}
}
//System.out.println(Arrays.toString(helper)+"--helper");
int sum = 0;
int res = 0;
for(int j = citations.length-1; j>=0; j--){
sum += helper[j];
if(sum>=j+1){
res = j+1;
return res;
}
}
return 0;
}
Leetcode 275. H-Index II
Could you solve it in logarithmic time complexity? 就是能不能在时间复杂度为O(logn)内解决问题。
因为这题已经排好序，所以用二分法解决问题即可。
public int hIndex(int[] citations) {
int len = citations.length;
int left = 0, right = len -1;
while(left<=right){
int mid = (right-left)/2 + left;
if(citations[mid] == len-mid){
return len-mid;
} else if (citations[mid] > len - mid){
right = mid -1;
} else {
left = mid +1;
}
}
return len - left ;
}
Leetcode 243. Shortest Word Distance
//法1. Time: O(n).
public int shortestDistance(String[] words, String word1, String word2) {
int res = words.length;
int a = -1, b = -1;
for(int i = 0; i< words.length;i++){
if(words[i].equals(word1)){
a = i;
} else if (words[i].equals(word2)){
b = i;
}
if( a!= -1 && b != -1 ) {
res = Math.min(res, Math.abs(a-b));
}
}
return res;
}
//法2. Time: O(n2).
public int shortestDistance(String[] words, String word1, String word2) {
int res = words.length;
for(int i=0; i< words.length;i++){
if(words[i].equals(word1) ){
for(int j = 0; j < words.length;j++){
if(words[j].equals(word2)){
res = Math.min(res,Math.abs(i-j));
}
}
}
}
return res;
}
Leetcode 244. Shortest Word Distance II 重复调用。
用HashMap。
class WordDistance {
//设置参数和构造方法constructor
HashMap<String, List<Integer>> map = new HashMap<>();
public WordDistance(String[] words) {
for(int i = 0; i< words.length;i++){
if(map.containsKey(words[i])){
map.get(words[i]).add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(words[i],list);
}
}
}
//法1，O(n*m)
public int shortest1(String word1, String word2) {
int res = Integer.MAX_VALUE;
List<Integer> list1 = map.get(word1);
List<Integer> list2 = map.get(word2);
for(int num1: list1){
for(int num2: list2){
res = Math.min(res, Math.abs(num1-num2));
}
}
return res;
}
//法2，O(n+m).
public int shortest2(String word1, String word2) {
List<int> list1 = map.get(word1);
List<int> list2 = map.get(word2);
int i = 0, j = 0, res = Integer.MAX_VALUE;
while (i < list1.size() && j < list2.size() ) {
res = Math.min(res, Math.abs(list1.get(i) - list2.get(j)));
if(list1.get(i) < list2.get(j)){
i++;
} else {
j++;
}
}
return res;
}
}
Leetcode 245. Shortest Word Distance III
//Time: O(n), Space: O(1).
class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
int res = words.length;
int a = -1, b = -1;
for(int i = 0; i< words.length;i++){
if(words[i].equals(word1)){
a = i;
}
if (words[i].equals(word2)){
if(word1.equals(word2)){
a = b;
}
b = i;
}
if( a != -1 && b != -1){
res = Math.min(res, Math.abs(a - b));
}
}
return res;
}
}
Leetcode 217. Contains Duplicate
class Solution {
// 用HashSet，Time: O(n). Space: O(n).
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i =0; i< nums.length;i++){
if(!set.add(nums[i])) return true;
}
return false;
}
//或者先排序再遍历, 用Arrays.sort(). Time: O(nlogn), Space: O(1).
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i = 1; i < nums.length; i++ ) {
if(nums[i] == nums[i-1]) return true;
}
return false;
}
}
Leetcode 219. Contains Duplicate II
//用HashMap，Time: O(n), Space: O(n).
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++ ){
if(map.containsKey(nums[i])){
if(i - map.get(nums[i]) <= k)return true;
}
map.put(nums[i],i);
}
return false;
}
}
Leetcode 220. Contains Duplicate III
用TreeSet 或 Bucket桶排序。
TreeSet.ceiling() 返回最小的更大值(>=此数)。
TreeSet.floor() 返回最大的更小值(<=此数)。
TreeSet: 先验证，然后才加入TreeSet中。这样才能使用ceiling().
// Time: O(nlogk), Space: O(k).
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums.length == 0){
return false;
}
TreeSet<Long> treeSet = new TreeSet<>();
for(int i = 0;i < nums.length;i++){
Long ceil = treeSet.ceiling((long)nums[i] - t ); //nums[i]还没加入TreeSet; 这里就是验证TreeSet中有无与nums[i]匹配的数
if (ceil != null && ceil <= (long)nums[i] + t){
return true;
}
treeSet.add((long)nums[i]);
if (treeSet.size() > k){ //这里是对的。这个判断是下个i才能发挥作用的。
treeSet.remove((long)nums[i - k]);
}
}
return false;
}
// bucket。
Time complexity : O(n). For each of the nn elements, we do at most three searches,
one insert, and one delete on the HashMap, which costs constant time on average.
Thus, the entire algorithm costs O(n) time.
Space complexity : O(min(n,k)). Space is dominated by the HashMap, which is linear to
the size of its elements. The size of the HashMap is upper bounded by both n and k.
Thus the space complexity is O(\min(n, k))O(min(n,k)).
public class Solution {
// Get the ID of the bucket from element value x and bucket width w
// In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.//所以要-1
private long getID(long x, long w) {
return x < 0 ? (x+1) / w - 1 : x / w; // (x+1)是针对 -5, -10等情况。其实删掉+1,程序也是会通过的。
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> map = new HashMap<>();
long w = (long)t + 1; //这里是因为 "at most t". 所以要t+1分隔.
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
// check if bucket m is empty, each bucket may contain at most one element
if (map.containsKey(m))
return true;
// check the neighbor buckets for almost duplicate
if (map.containsKey(m - 1) && Math.abs(nums[i] - map.get(m - 1)) < w)
return true;
if (map.containsKey(m + 1) && Math.abs(nums[i] - map.get(m + 1)) < w)
return true;
// now bucket m is empty and no almost duplicate in neighbor buckets
map.put(m, (long)nums[i]);
if (i >= k) map.remove(getID(nums[i - k], w));
}
return false;
}
}
Leetcode 55. Jump Game.
注意到 nums[i]+i 表示能跳的最远距离即可。
Greedy Time: O(n), Space: O(1).
// Greedy. 顺序：
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for(int i = 0; i< nums.length; i++){
if(i>max) return false;
max = Math.max(max,nums[i]+i);
}
return true;
}
}
//Greedy. 逆序(更容易理解)：
public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}
Leetcode 45. Jump Game II.
// Greedy. Time: O(n), Space: O(1).
class Solution {
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
curFarthest = Math.max(curFarthest, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = curFarthest;
//if(curFarthest >= nums.length -1 ) break; 这句可写可不写
}
}
return jumps;
}
}
// DFS，BFS等其他解法，目前没看。
Leetcode 53. Maximum Subarray.
// 动态规划，DP。Time: O(n), Space: O(n).
class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0 ) return 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i< nums.length;i++){
dp[i] = nums[i] + (dp[i-1] < 0? 0: dp[i-1]);
max = Math.max(max, dp[i]);
}
return max;
}
}
// Kadane算法，Time: O(n), Space: O(1).
class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int sum = 0; // sum = nums[0];
int max = nums[0];
for(int number: nums){
sum = Math.max(number, sum + number);
max = Math.max(max,sum);
}
/**for(int i = 1; i < nums.length; i++){
sum = Math.max(nums[i], sum + nums[i]);
max = Math.max(max,sum);
}
**/
}
return max;
}
}
Leetcode 121.
// Kadane算法(最大子数组问题)，Time: O(n), Space: O(1).
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
int maxProfit = 0; // 不能用 maxProfit = prices[0]
int min = prices[0];
for(int price: prices){
min = Math.min(min,price);
maxProfit = Math.max(maxProfit, price - min);
}
return maxProfit;
}
}
// 和上面只是表达不同。
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0) return 0;
int buy = prices[0];
int hypoTheticalProfit = 0;
for(int i = 0; i < prices.length; i++){
if(prices[i] < buy){
buy = prices[i];
}
if(prices[i] - buy > hypoTheticalProfit){
hypoTheticalProfit = prices[i] - buy;
}
}
return hypoTheticalProfit;
}
}
Leetcode 122. Best Time to Buy and Sell Stock II
//贪婪算法。Time: O(n), Space: O(1).
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length <= 1) return 0;
int maxProfit = 0;
int buy = prices[0], sell = 0;
for(int i = 1; i<prices.length ; i++){
if(prices[i] > prices[i-1]){
maxProfit += prices[i] - prices[i-1];
}
}
return maxProfit;
}
}
//法2: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/discuss/208241/Explanation-for-the-dummy-like-me
// Time: O(n), Space: O(1).
// sub-profit = prices[j] - prices[i], We should choose j that prices[j] is as big as
// possible, and choose i that prices[i] is as small as possible.
class Solution {
public int maxProfit(int[] prices) {
int i = 0, buy, sell, profit = 0, N = prices.length -1; // 因为用了i++
while (i < N) {
while (i < N && prices[i] >= prices[i+1]) i++;
buy = prices[i];
while (i < N && prices[i] < prices[i + 1] ) i++;
sell = prices[i];
profit += sell - buy;
}
return profit;
}
}
Leetcode 123. Best Time to Buy and Sell Stock III.
用DP来解。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/39615/my-explanation-for-on-solution
public int maxProfit(int[] prices) {
int sell1 = 0, buy1 = Integer.MIN_VALUE;
int sell2 = 0, buy2 = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
/**
When you update sell2, it is based on the dp result of buy2 from last iteration,
which means the max value you can possibly get if you finished the
2nd buy transaction by yesterday.
For the same reason, buy2 relies on sell1 of yesterday.
So the sequence must be sell2, buy2, sell1, buy1.
为了便于理解，顺序应该是sell2, buy2, sell1, buy1.
但其实，buy1 sell1 buy2 sell2 也是可以通过的。因为：
order shouldn't matter. On a given iteration, only one of the 4 is being updated.
Try shuffling and it should still work.
**/
另外，若
拓展至 k transactions：
Leetcode 188. Best Time to Buy and Sell Stock IV.
//https://www.youtube.com/watch?v=oDhu5uGq_ic
//
dp[i, j] 表示 最大交换i次，前j天，得到的max profit.
第一步分析：
dp[i,j] = Math.max(dp[i,j-1], prices[j] -prices[m] + dp[i-1,m]); m = 0...j-1
第二步分析：
dp[i,j] = Math.max(dp[i,j-1], prices[j] + MaxDiff );
每次j结束后计算 MaxDiff, = dp[i-1,j] - prices[j].
公式1：dp[i, j] = Math.max(dp[i, j-1], price[j] + maxDifference);
2: maxDifference = Math.max(maxDifference, price[j] )
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (prices == null || n <= 1) return 0;
//if k >= n/2, then you can make maximum number of transactions.
if (k >= n/2) {
int maxPro = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
maxPro += prices[i] - prices[i-1];
}
return maxPro;
}
//if (k >= n/2) k = n/2; 亦可，但这使得 k >= n/2 的时间复杂度由O(n)变为O(k*n).
//dp[i, j] represents the max profit up until prices[j] using at most i transactions.
int[][] dp = new int[k+1][n];
for (int i = 1; i <= k; i++) {
int maxDifference = dp[i-1][0] - prices[0]; // dp[i-1][0] = 0.
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxDifference);
maxDifference = Math.max(maxDifference, dp[i-1][j] - prices[j]);
}
}
return dp[k][n-1];
}
Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
DP题。关键是找到 递推关系：
1， buy[i] = max(sell[i-2]-price, buy[i-1])
2， sell[i] = max(buy[i-1]+price, sell[i-1])
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75931/Easiest-JAVA-solution-with-explanations
Let bi2, bi1, bi represent buy[i - 2], buy[i - 1], buy[i]
Let selli2, selli1, selli represent sell[i - 2], sell[i - 1], sell[i]
注意初始化。bi1=bi = - prices[0], selli2,selli1,selli = 0.
class Solution {
public int maxProfit(int[] prices) {
//buy[i] = Math.max(buy[i-1], sell[i-2]-prices[i]);
//sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i]);
if(prices == null || prices.length <=1) return 0;
int bi = -prices[0], bi1 = bi;
int selli = 0, selli1 = 0, selli2 = 0;
for(int i = 1;i < prices.length;i++){
bi = Math.max(bi1,selli2-prices[i]);
selli = Math.max(selli1,bi1+prices[i]);
bi1 = bi; selli2 = selli1; selli1 = selli;
}
return selli;
}
}
Leetcode 11. Container With Most Water.
两个for循环，可以得到 O(n2)的解答。
这里是首尾的两个指针，向中间靠拢。
class Solution {
public int maxArea(int[] height) {
if(height ==null || height.length == 0) return 0;
int res = 0;
int left = 0, right = height.length -1;
while( left < right){
res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
if(height[left] <= height[right]){
left++;
} else {
right--;
}
}
return res;
}
}
Leetcode 42. Trapping Rain Water.
双指针，最好，Time: O(n), Space: O(1).
可以用stack，可以用DP，都是 Time: O(n), Space: O(n).
class Solution {
public int trap(int[] height) {
if(height == null || height.length <=1) return 0;
int left = 0, right = height.length-1;
int leftMax = 0, rightMax = 0;
int res = 0;
while(left < right){
if(height[left] < height[right]){
if( height[left] < leftMax){
res += leftMax - height[left];
} else {
leftMax = height[left];
}
left++;
} else { // if判断 简化版
rightMax = Math.max(rightMax,height[right]);
res += rightMax - height[right];
// if( height[right] < rightMax){
// res += rightMax - height[right];
// } else {
// rightMax = height[right];
// }
right--;
}
}
return res;
}
}
Leetcode 334. Increasing Triplet Subsequence
class Solution {
public boolean increasingTriplet(int[] nums) {
int FirstNum = Integer.MAX_VALUE,SecondNum = Integer.MAX_VALUE;
for(int num: nums){
if(num <= FirstNum) FirstNum = num; //这里的等号不能去掉。否则有了 [1,1,6] 通过的情况。
else if(num <= SecondNum) SecondNum = num;
else return true;
}
return false;
}
}
Leetcode 128. Longest Consecutive Sequence
题目要求 Time O(n).
class Solution {
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int res = 0;
HashSet<Integer> set = new HashSet<>();
for(int num: nums){
set.add(num);
}
for(int num: nums){
int less = num -1;
while(set.contains(less)){
set.remove(less);
less--;
} // 或者：while(set.remove(less)) less--;
int more = num + 1;
while(set.contains(more)){
set.remove(more);
more++;
} // while(set.remove(more)) more++;
res = Math.max(res, more - less - 1 );
}
return res;
}
}
Leetcode 164. Maximum Gap.
题目要求：solve it in linear time/space. 用基数排序。这题桶排序太麻烦。
基数排序：
class Solution {
public int maximumGap(int[] nums) {
if(nums == null || nums.length < 2) return 0;
int max = Integer.MIN_VALUE;
for(int num: nums){
max = Math.max(max,num);
}
int[] temp = new int[nums.length];
int exp = 1;
while( max >= exp ){
int[] count = new int[10]; //10 digits. Integer最大值是2^31=2147483647,十位数
for (int i = 0; i < nums.length; i++) {
count[(nums[i] / exp) % 10]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
//这个倒序遍历for很关键。
for (int i = nums.length-1; i >= 0; i--) {
// int a = count[(nums[i]/exp)%10]-1;
// temp[a] = nums[i];
// count[(nums[i]/exp)%10]--;
temp[--count[(nums[i]/exp)%10]] = nums[i];
}
/** 正序遍历
for (int i = 0; i < nums.length; i++){
temp[--count[(nums[i]/exp)%10]] = nums[i];
}
错误。按照这种做法，对于同一位相同的数字会混乱。
比如 [90,45,75,70]
从nums.length-1到0的基数排序应该得到：第一次[90,70,45,75],第二次[45,70,75,90]
用这个for从0到nums.length-1，得到：第一次[70,90,75,45],第二次[45,75,70,90]
Notice that the first time 90 goes behind 70.
In the first while We meet 90 first, and assign it to aux[1] instead of aux[0], and it leads to the wrong sort.
**/
for (int i = 0; i < nums.length; i++) {
nums[i] = temp[i];
}
exp *= 10;
}
int maxGap = 0;
for(int i = 1; i < nums.length; i++) {
maxGap = Math.max(maxGap,nums[i]-nums[i-1]);
}
return maxGap;
}
}
桶排序：
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) return 0;
// get the max and min value of the array
int min = nums[0];
int max = nums[0];
for (int i:nums) {
min = Math.min(min, i);
max = Math.max(max, i);
}
// the minimum possible gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(nums.length - 1));
int[] bucketsMIN = new int[nums.length - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[nums.length - 1]; // store the max value in that bucket
Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
// put numbers into buckets
for (int num:nums) {
if (num == min || num == max) continue;
int idx = (num - min) / gap; // index of the right position in the buckets
bucketsMIN[idx] = Math.min(num, bucketsMIN[idx]);
//确保了bucketMIN和bucketMAX要么同时为最值，要么是同一个常数(只存在一个数)/不同常数(有两个数以上)
bucketsMAX[idx] = Math.max(num, bucketsMAX[idx]);
}
// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previousMAX = min;
for(int i =0;i < nums.length-1;i++){
if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE) continue;
maxGap = Math.max(maxGap,bucketMIN[i]-previous);
previous = bucketMAX[i];
}
maxGap = Math.max(maxGap, max - previous);
//不用比较min处的bucket，是因为maxGap必不出现在同一个bucket。而比较max处bucket，是因为previous代表的可能不是最后的bucket，就是说可能max前好几个bucket都是空。
}
}
Leetcode 287. Find the Duplicate Number.
解法1，二分法。
Time: O(nlogn), Space: O(1).
class Solution {
public int findDuplicate(int[] nums) {
int low = 0, high = nums.length -1;
while(low<high){
int mid = (high - low) /2 + low;
int count = 0;
for(int num: nums){
if(num <= mid) count++;
} // 这里的比较是稍微修改了，改为遍历并记录count
if( count > mid ){
high = mid;
} else {
low = mid + 1;
}
}
return low; // high 也行。结果是 low = high。
}
}
解法2，参考Leetcode 142 Linked List Cycle II 的解法。
Time: O(n), Space: O(1).
比如说(1,3,4,2,2) 形成：0-1-3-2-4-2-4-2 , 2与4形成环。
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0],fast = nums[nums[0]]; // fast = nums[0] 错误，会导致没进入第一个while循环
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int slow2 = 0;
while(slow != slow2){
slow = nums[slow];
slow2 = nums[slow2];
}
return slow;
}
}
Leetcode 142 Linked List Cycle II
一个slow每跑一步，一个fast跑两步。
一个slow每跑一步，一个fast跑两步
龟兔相遇点
另一个龟从起点出发
两龟相遇，就是Loop的起始点
Z点相遇; Y为所求(环的起点)
a + b = 1/2 * (a + b + n(b+c)) ==> a = (n-1)(b+c) + c , where n>=1
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode slow2 = head;
while(slow != slow2){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
Leetcode 135. Candy
主要是理解题意。
(5,6,7)得到的糖果是(1,2,3).
(5,6,7,6,4,4,2)得到的糖果是(1,2,3,2,1,2,1)
class Solution {
public int candy(int[] ratings) {
int[] res = new int[ratings.length];
Arrays.fill(res,1);
for(int i = 1; i< ratings.length;i++){
if(ratings[i]>ratings[i-1]){
res[i] = res[i-1] + 1;
}
}
for(int i = ratings.length -2; i>=0;i--){
if(ratings[i]>ratings[i+1]){
res[i] = Math.max(res[i], res[i+1] + 1);
}
}
int result = 0;
for(int candy: res){
result += candy;
}
return result;
}
}
Leetcode 330. Patching Array
最佳答案的解析：https://leetcode.com/problems/patching-array/discuss/78488/Solution-%2B-explanation
Explanation：Let miss be the smallest sum in [0,n] that we might be missing. Meaning we already know we can build all sums in [0,miss). Then if we have a number num <= miss in the given array, we can add it to those smaller sums to build all sums in [0,miss+num). If we don't, then we must add such a number to the array, and it's best to add miss itself, to maximize the reach.
Example: Let's say the input is nums = [1, 2, 4, 13, 43] and n = 100. We need to ensure that all sums in the range [1,100] are possible.
Using the given numbers 1, 2 and 4, we can already build all sums from 0 to 7, i.e., the range [0,8). But we can't build the sum 8, and the next given number (13) is too large. So we insert 8 into the array. Then we can build all sums in [0,16).
Do we need to insert 16 into the array? No! We can already build the sum 3, and adding the given 13 gives us sum 16. We can also add the 13 to the other sums, extending our range to [0,29).
And so on. The given 43 is too large to help with sum 29, so we must insert 29 into our array. This extends our range to [0,58). But then the 43 becomes useful and expands our range to [0,101). At which point we're done.
// Time: O(n), Space: O(1).
class Solution {
public int minPatches(int[] nums, int n) {
long missLine = 1; // missLine 要设为long,不然miss *=2会导致超过Integer.MAX_VALUE
int res = 0;
int i = 0;
while(missLine <= n) {
if(i < nums.length && nums[i]<=missLine){
missLine += nums[i];
i++;
} else {
missLine += missLine;
res++;
}
}
return res;
}
}
Leetcode 4. Median of Two Sorted Arrays
很重要，常考。要求：Time: O(log(m+n)), 但也会follow up到 O( log(min(m,n)) ).
思路：https://blog.csdn.net/chen_xinjia/article/details/69258706
cut1: nums1数组的断点左边有几个元素
cut2: nums2数组的断点左边有几个元素. cut2 依赖于cut1，因为 2*(cut1+cut2) = nums1.length + nums2.length.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length > nums2.length){
return findMedianSortedArrays(nums2,nums1);
}
int totalLength = nums1.length + nums2.length;
int cut1 = 0,cut2 = 0;
//nums1的切点左右数字分别为L1，R1；nums2的切点左右数字分别为L2，R2；假设两数组排序后得到nums3.
//找到最终切点的表面条件：两个切点左边的两个子数组，组成nums3的左边的半个数组。然后取L1和L2的最大值为L，取R1和R2的最小值为R，求L和R平均值，即为nums3是偶数数组情况下的解。奇数情况下稍作改变即可。
//找到最终切点的条件，代码表示为：L1<=R2,且L2<=R1.
//若L1>R2,则cut1左移(同时cut2随着cut1变化而右移)；(cut1左移范围是(cutL,cut1-1))
//若L2>R1,则cut1右移(同时cut2随着cut1变化而左移)。(cut1右移范围是(cut1+1,cutR))
int cutL = 0, cutR = nums1.length; // cutL,cutR是nums1中cut1的范围(范围逐渐缩小)
while(cut1<=nums1.length){
cut1 = (cutR - cutL)/2 + cutL;
cut2 = totalLength/2 - cut1;
double L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1-1];
double L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2-1];
double R1 = (cut1 == nums1.length) ? Integer.MAX_VALUE : nums1[cut1];
double R2 = (cut2 == nums2.length) ? Integer.MAX_VALUE : nums2[cut2];
if(L1>R2){
cutR = cut1 - 1;
} else if (L2>R1){
cutL = cut1 + 1;
} else { // else 说明 L1<=R2,L2<=R1 条件都满足；两个切点是正确切点。
if(totalLength %2 == 0){ //nums3数组个数为偶数
L1 = Math.max(L1,L2); // nums3左半数组的最大值
R1 = Math.min(R1,R2); //nums3右半数组的最小值
return (L1+R1)/2;
} else { //nums3数组个数为奇数，取R1和R2中最小的，就是解
R1 = Math.min(R1,R2);
return R1;
}
}
}
return -1;
}
}
Leetcode 252. Meeting Rooms. 【Easy】
用Arrays.sort() Comparator 的compare方法排序。
Time: O(nlogn), Space: O(1).
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if(intervals.length < 2) return true;
Arrays.sort(intervals,new Comparator<int[]>() {
@Override
public int compare(int[] a,int[] b){
return a[0] - b[0];
}
});
for(int i = 1; i<intervals.length;i++){
if(intervals[i][0]<intervals[i-1][1]){
return false;
}
}
return true;
}
}
Leetcode 253. Meeting Rooms II 【Medium】
class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for(int i = 0; i < intervals.length; i++){
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int endInt = 0;
int rooms = 0;
for(int i = 0; i< intervals.length; i++){
if(starts[i]<ends[endInt]){
rooms++;
} else {
endInt++;
}
}
return rooms;
}
}
第二种写法，PriorityQueue, 在这题不推荐。
class Solution {
public int minMeetingRooms(int[][] intervals) {
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> a[0]==b[0]? a[1]-b[1]:a[0]-b[0]);
for(int[] meeting: intervals){
queue.offer(new int[]{meeting[0],1});
queue.offer(new int[]{meeting[1],-1});
}
int rooms = 0;
int current = 0;
while(!queue.isEmpty()){
rooms = Math.max(rooms,current+=queue.poll()[1]);
}
return rooms;
Leetcode 56. Merge Intervals
扫描线算法。
Sorting takes O(n log(n)) and merging the intervals takes O(n). Space O(n).
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals == null || intervals.length <2) return intervals;
Arrays.sort(intervals,(a,b) -> a[0]-b[0]); // Takes O(nlogn).
int start = intervals[0][0], end = intervals[0][1];
//List<int[]> result = new int[intervals.length][2];
int resultLength = 0;
for(int[] meeting: intervals){
if(meeting[0]<= end){
end = Math.max(end, meeting[1]);
} else {
intervals[resultLength++] = (new int[]{start,end});
start = meeting[0];
end = meeting[1];
}
}
intervals[resultLength++] = (new int[]{start,end});
return Arrays.copyOfRange(intervals, 0, resultLength);
}
}
Leetcode 57. Insert Interval. 【Hard】
关键在于 两个while条件。
用start和end确定合并开始和结束的index。用startBoundary和endBoundary确定合并的区间起点和终点。然后建立int[][] res, 重新遍历并赋值。
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
if(intervals == null) return intervals;
int start = 0;
while(start<intervals.length && intervals[start][1]<newInterval[0]){
start++;
}
int end = start;
int startBoundary = 0, endBoundary = 0;
while(end<intervals.length && intervals[end][0]<=newInterval[1]){
newInterval[0] = Math.min(newInterval[0],intervals[end][0]);
newInterval[1] = Math.max(newInterval[1],intervals[end][1]);
end++;
}
int[][] res = new int[intervals.length-end+start+1][2];
for(int i = 0;i<start;i++){
res[i] = intervals[i];
}
res[start] = newInterval;
for(int i= end;i<intervals.length;i++){
res[++start] = intervals[i];
}
return res;
}
}
Leetcode 352. Data Stream as Disjoint Intervals 【Hard】
Time: O(logn), 因为：
1）For operations like add, remove, containsKey, time complexity is O(log n where n is number of elements present in TreeMap.
2）TreeMap always keeps the elements in a sorted(increasing) order, while the elements in a HashMap have no order.
class SummaryRanges {
TreeMap<Integer,int[]> map; // 在这里加上attribute：TreeMap
/** Initialize your data structure here. */
public SummaryRanges() {
map = new TreeMap<>();
}
public void addNum(int val) {
if(map.containsKey(val)) return; // 排除了输入lowerKey值的情况 (special1)
Integer lowerKey = map.lowerKey(val);
Integer higherKey = map.higherKey(val);
if(lowerKey != null && higherKey !=null && val == map.get(lowerKey)[1]+1
&& val == map.get(higherKey)[0] -1 ){
map.get(lowerKey)[1] = map.get(higherKey)[1];
map.remove(higherKey);
} else if (lowerKey != null && val <= map.get(lowerKey)[1] +1 ){
// 这里 val<= ， 和下面的 val== 不同，根本原因是，TreeMap中存储的方式是以某区间的最小值(lower key)作为key进行存储。该区间的最大值存储在value中
map.get(lowerKey)[1] = Math.max(val,map.get(lowerKey)[1]);
} else if (higherKey != null && val == map.get(higherKey)[0] -1 ){
map.put(val,new int[]{val,map.get(higherKey)[1]});
map.remove(higherKey);
} else {
map.put(val,new int[]{val,val});
}
}
public int[][] getIntervals() {
int[][] res = new int[map.size()][2];
int i = 0;
for(int[] a:map.values()){
res[i++] = a;
}
return res;
}
}
Leetcode 239. Sliding Window Maximum 【Hard】
Deque：double ended queue双端队列, 同时拥有栈Stack和队列Queue的优点。
Deque基础知识：https://blog.csdn.net/top_code/article/details/8650729
用Deque 来记录窗口的值所在的数组下标。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length == 0) return nums;
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length+1-k];
for(int i=0; i<nums.length;i++){
if( !deque.isEmpty() && deque.peekFirst() == i-k ){ //如果队列头部记录的index位于当前sliding window外，就删掉头部
deque.pollFirst(); // = removeFirst()
}
while( !deque.isEmpty() && nums[deque.peekLast()]<nums[i]){ // while循环，把比当前i index的数组值小的deque末端全都删掉
deque.removeLast(); =pollLast()
}
deque.offerLast(i); // 把当前i index的数组值放入deque末端
if( i+1 >= k ){
res[i+1-k] = nums[deque.peekFirst()]; //如果已经形成了完整的window，就要把deque头部记入res结果中
}
}
return res;
}
}
Leetcode 295. Find Median from Data Stream. 【Hard】
用两个PriorityQueue, 记录small的一半和large的一半。
PriorityQueue内部是默认按照从小到大排列的，每次add新数据，要重新二分法加入，所以 Time: O(logn). Space: O(n).
class MedianFinder {
private PriorityQueue<Long> small;
private PriorityQueue<Long> large;
/** initialize your data structure here. */
public MedianFinder() {
small = new PriorityQueue<>();
large = new PriorityQueue<>();
}
public void addNum(int num) {
large.add((long)num);
small.add(-large.poll());
if(large.size() < small.size()){
large.add(-small.poll());
}
System.out.print(small.peek()+"//");
}
public double findMedian() {
return large.size() > small.size() ? large.peek() : (large.peek() - small.peek()+0.0)/2.0; //这里注意，+0.0和/2.0 二选一，使得结果不是int整除
}
}
Leetcode 325. Maximum Size Subarray Sum Equals k 【Medium】
- 遍历第一遍，nums[i]改为前i项之和
- 遍历第二遍，用HashMap记录(nums[i],i)，然后计算Max的Res
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
int res = 0;
for(int i=1; i < nums.length;i++){
nums[i]+=nums[i-1];
}
map.put(0,-1);
for(int i=0; i < nums.length;i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],i);
}
if(map.containsKey(nums[i]-k)){
res= Math.max(res,i-map.get(nums[i]-k));
} //若是求最短的subarray，应该是：res初始化为MaxValue, res = min(xxxx); 无论是否contain(nums[i])都更新map.put(nums[i],i). )
}
return res;
}
}
Leetcode 209. Minimum Size Subarray Sum. 【Medium】
有FollowUp，要求掌握O(n) 和O(nlogn) 的解法。
O(n)解法：
- O(n)解法, 一次遍历即可。
- 题目求的是最短长度, 在for循环中, 用left记录左端位置，用while循环使得left++直到sum<s, 才结束本次i循环
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int res = Integer.MAX_VALUE;
int left = 0, sum = 0;
for(int i =0;i < nums.length;i++){ //O(n)解法, 一次遍历即可
sum += nums[i];
while(left<=i && sum>=s){ // 在for循环中，
res = Math.min(res,i-left+1);
sum -= nums[left++];
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
O(nlogn) 解法:
先考虑n^2 的解法，(1)遍历从0到nums.length的子数组长度，(2)遍历从0到n-1的数组，得到O(n^2)的解法。要想达到nlogn的时间，要么对(1)使用二分法，要么对(2)使用二分法。
(推荐：) 第一种，由于题目求的是最短足数组长度，我们可以对从0到nums.length的子数组长度进行二分。取mid=(0+nums.length)/2，遍历整个数组，然后根据情况改变mid，再遍历整个数组。由此可见，二分法在外侧得到O(nlogn)，遍历数组在二分法代码里面得到O(n)。
整个解法，不受数组是否是正数的影响。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0, right = nums.length;
int res = Integer.MAX_VALUE;
for(int i=1;i<nums.length;i++) nums[i] += nums[i-1];
while(left<=right){
int mid = (right-left)/2 + left;
for(int i=0;i<nums.length;i++){
int test = (i>=mid) ? nums[i]-nums[i-mid]:nums[i];
if(test>=s){
res = Math.min(res,mid);
right = mid-1;
break;
}
}
if(right != mid-1) left = mid+1;
}
return res == Integer.MAX_VALUE ? 0 : res;
}
// private int binarySearch(){ 可以把for循环单独抽出来
// }
}
第二种：遍历整个数组，在第 i 位计算以这个数为起始的点的最小长度(由于整个数组都是正数，所以可以二分法来断定end是在哪。)
由此可见，整个方法在外层是for循环得到O(n), 在for循环内部用二分法断定以第i个数为start的最小数组长度，得到O(logn).
class Solution {
public int minSubArrayLen(int s, int[] nums) {
for(int i=1; i<nums.length;i++) nums[i] += nums[i-1];
int res = Integer.MAX_VALUE;
for(int i=0; i<nums.length;i++){ // includes original nums[i]
int left = 1, right = nums.length - i;
while(left<=right){
int mid = (right + left)/2;
int before = (i == 0)? 0 : nums[i-1]; //注意 i-1可能越界
if(nums[i+mid-1]-before>=s){ //从第i位开始，长度为mid的子数组
res = Math.min(res,mid);
right = mid-1;
} else {
left = mid+1;
}
}
System.out.print(left+"/"+right+"//");
}
return res == Integer.MAX_VALUE ? 0 : res;
}
// private int binarySearch(){
// }
}
Leetcode 238. Product of Array Except Self 【Medium】
这题就一个解法，先顺序遍历得到初步的res[] 数组(前i-1项的积)，然后设一个int: right, 逆序遍历可得到正确结果。
class Solution {
public int[] productExceptSelf(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int[] res = new int[nums.length];
res[0] = 1;
for(int i=1; i<nums.length; i++){
res[i] = res[i-1] * nums[i-1];
}
int right = 1;
for(int i=nums.length-1; i>=0;i--){
res[i] *= right;
right *= nums[i];
}
return res;
}
}
Leetcode 152. Maximum Product Subarray 【Medium】
这题的关键是正负数。用min和max分别记录最大值和最小值，遍历一次即可。
这题的遍历的for循环内部有两个写法，一个是遇到负数就swap最大值和最小值；一个是max(maxnum[i], minnum[i],num[i]), min同理，目的都是保证max和min中含有num[i]。
Time: O(n), Space: O(1).
class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
for(int i=1,max=res,min=res;i<nums.length;i++){
if(nums[i]<0){
int temp = max;
max = min;min = temp;
}
max = Math.max(nums[i],max*nums[i]);
min = Math.min(nums[i],min*nums[i]);
res = Math.max(res,max);
}
// for(int i=1; i<nums.length;i++){
// int oldMax = max;
// max = Math.max(Math.max(max*nums[i],min*nums[i]),nums[i]);
// min = Math.min(Math.min(min*nums[i],oldMax*nums[i]),nums[i]);
// res = Math.max(res,max);
// }
return res;
}
}
Leetcode 228. Summary Ranges
很简单，一次遍历。
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<>();
for(int i=0;i<nums.length;i++){
int start = nums[i];
while(i < nums.length-1 &&nums[i] +1 == nums[i+1]){
i++;
}
if(start != nums[i]){
res.add(start+"->"+nums[i]);
} else {
res.add(nums[i]+"");
}
}
return res;
}
}
Leetcode 163. Missing Ranges. 【Medium】
题目要求很奇怪。暴力解法，遍历一遍。关键在于for循环内部的两层if条件判断，以及for循环之后的一个对upper的if条件判断。
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> list = new ArrayList<>();
long longLower = (long)lower, longUpper = (long)upper;
for(int num: nums){
if(num>longUpper) break;
if(longLower == num){
longLower++;
} else if(longLower < num){
if(longLower + 1== num){
list.add(longLower+"");
} else {
list.add(longLower+"->"+(num-1));
}
longLower=(long)num+1;
}
}
if(longLower==longUpper) list.add(longLower+"");
if(longLower<longUpper) list.add(longLower+"->"+longUpper);
return list;
}
}
Leetcode 289. Game of Life. 【Medium】
位运算，&运算符。
本题Leetcode答案：https://leetcode.com/problems/game-of-life/discuss/73223/Easiest-JAVA-solution-with-explanation
To solve it in place, we use 2 bits to store 2 states:
[2nd bit, 1st bit] = [next state, current state]
- 00 dead (next) <- dead (current)
- 01 dead (next) <- live (current)
- 10 live (next) <- dead (current)
- 11 live (next) <- live (current)
To get the current state, simply do: board[i][j] & 1 (判断: board[i][j]最末位&1)
To get the next state, simply do: board[i][j] >> 1 (左移一位，使得第二位记录next的值推到第一位current)
【Time: O(mn), Space: O(1). 】*
class Solution {
public void gameOfLife(int[][] board) {
if(board == null || board.length == 0) return;
for(int i=0;i<board.length;i++){
for(int j=0; j<board[0].length;j++){
int count = countNeighbor(board,i,j);
//只需要对下一轮能存活的家庭 +=2，即可
if(count==2 && board[i][j]==1){
board[i][j] += 2;
}
if(count==3){
board[i][j] += 2;
}
}
}
//再一次遍历，集体右移，从而得到下一轮的生存情况
for(int i=0;i<board.length;i++){
for(int j=0; j<board[0].length;j++){
board[i][j] >>= 1; //移位操作，>>是右移符号，相当于末位取0再除以2
}
}
}
//countNeighbor函数，计算board[i][j]的邻居数量。
private int countNeighbor(int[][] board, int i, int j){
int neighbor = 0;
for(int row = Math.max(0,i-1);row<=Math.min(board.length-1,i+1);row++){
for(int col = Math.max(0,j-1);col<=Math.min(board[0].length-1,j+1);col++){
if(row == i && col == j) continue;
if((board[row][col] & 1)==1 ) neighbor++;
}
}
return neighbor;
}
}
Leetcode 327. Count of Range Sum.
题目要求：A naive algorithm of O(n2) is trivial. You MUST do better than that.
【推荐：】最简单的暴力解法，Time: O(n2), Space: O(1)或O(n).
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] sums = new long[ nums.length+1 ]; //必须设long数组，因为sum可能越界
for(int i=1;i<nums.length+1;i++){
sums[i] = sums[i-1] + nums[i-1];
}
int res = 0;
for(int i=0; i<nums.length;i++){
for(int j=i+1;j<nums.length+1;j++){
if(sums[j]-sums[i] >=lower && sums[j]-sums[i] <= upper) res++;
}
}
return res;
}
}
【不推荐：】考虑用TreeMap来做。Time: O(n2), Space: O(n).
面试问题：为什么用treeMap做？
treemap用来记录(sum，个数)
如果不存在负数，那么nums会递增，就可以不用treemap。
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
if(nums == null || nums.length == 0) return 0;
TreeMap<Long,Long> map = new TreeMap<>();
map.put((long)0,(long)1); //核心，有了这一句，才能保证：
//可以不截取任何前几项而是全部的前i项。如果没加，那么sum就必须截取一个以num[0]为首的subarray
long count = 0;
long sum = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
long low = sum - (long)upper;
long up = sum - (long)lower;
Map<Long,Long> sub = map.subMap(low,true,up,true); //time是O(1).
for(Long value: sub.values()) {count += value;} //这一句的time是O(n),因为返回的是collection，对于collection的遍历，用时O(n).
if(map.containsKey(sum)){
map.put(sum,map.get(sum)+1);
} else {
map.put(sum,(long)1);
}
System.out.print(up+"/");
}
return (int)count;
}
}
法2，分治法MergeSort。
MergeSort 经典代码：https://www.geeksforgeeks.org/merge-sort/
【推荐：】正常的分治法, 要构建两个method：sort()和 merge()。
- sort(), 就三行核心代码：
sort(前半段)，sort(后半段)，合并 merge()。 - merge(), 三个while循环，对于已经各自排好序的两段进行merge，形成有序的一段 (到了最底层只有两个数字。所以sort()已经在merge代码中实现了) 。
优点：用分治算法主定理可得时间复杂度为O(nlogn)，相同元素的顺序不会颠倒，是稳定排序。
缺点：需要辅助数组，所需空间复杂度为O(n)。
为什么i的范围是[start,mid].jpg
class Solution {
int count = 0;
int lower;
int upper;
public int countRangeSum(int[] nums, int lower, int upper) {
long[] sum = new long[nums.length + 1];
long[] temp = new long[nums.length + 1];
this.lower = lower;
this.upper = upper;
for (int i = 1; i <= nums.length; i++) {
sum[i] = sum[i - 1] + (long) nums[i - 1];
}
mergesort(sum, 0, nums.length, temp); //传了sum, sum的start index和end index
return count;
}
private void mergeSort(long[] sum, int start, int end, long[] temp) {
if (start >= end) return;
int mid = start + (end - start) / 2;
mergeSort(sum, start, mid, temp);
mergeSort(sum, mid + 1, end, temp);
merge(sum, start, mid, end, temp);
}
private void merge(long[] sum, int start, int mid, int end, long[] temp) {
//为什么i的范围是[start,mid],而不是[start,end]?因为[start,mid]内部和[mid,end]内部已经做了一遍。如果再做，就会重复。看下面的图示。
int startIndex = mid + 1, endIndex = mid + 1; // represents the index of sum that falls between lower and upper
for (int i = start; i <= mid; i++) {
while (startIndex <= end && sum[startIndex] - sum[i] < lower) {
startIndex++;
}
while (endIndex <= end && sum[endIndex] - sum[i] <= upper) {
endIndex++;
} //[start,end]的sum数组在上一轮已经排序，所以可以while循环
count += endIndex - startIndex;
}
//先计算count，然后才能sort。可以从最底层的角度去理解。比如sum[8]=20,sum[9]=25,两者相减得到num[9]的值并与lower和upper对比。若是先排序，得到的-5没有意义，不能拿去与lower,upper对比。或者从图示的两个区间来看，后半区的数减前半区的数，得到的是一个subarray的和，这才有意义；若先排序，就没意义了。
//下面三个while，是典型的mergesort的sort步骤。
//从start到end, 把sum的数字排序，并记录在temp中
int index = start;
int tLeft = start, tRight = mid+1;
while( tLeft<=mid && tRight<=end ){ // temp记录
if(sum[tLeft]>sum[tRight]){
temp[index++] = sum[tRight++];
} else {
temp[index++] = sum[tLeft++];
}
}
while(tLeft<=mid){
temp[index++] = sum[tLeft++];
}
while(tRight<=end){
temp[index++] = sum[tRight++];
}
//排序后，把temp的(start,end)的顺序赋给sum(start,end)
for (int i = start; i <= end; i++) {
sum[i] = temp[i];
}
}
}
Leetcode 88. Merge Sorted Array. 【Easy】
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m-1;
int j = n-1;
int k = m+n-1;
while(i>=0 && j>=0){
nums1[k--] = nums1[i] >= nums2[j]? nums1[i--]:nums2[j--];
}
while(j>=0){
nums1[k--] = nums2[j--];
}
// 不用while(i>=0) 是因为 直接记录在 nums1中。如果用新数组来记录，就需要while(i>=0)
}
}
Leetcode 75. Sort Colors. 【Medium】
题目FollowUp要求：用两次遍历 two-pass 当然容易，请用一次遍历 one-pass 解决。
in-space: 在原来的space操作，不是copy等需要更多空间的方式。
class Solution {
public void sortColors(int[] nums) {
if(nums == null || nums.length == 0) return;
int left = 0, right = nums.length-1;
int index = 0;
//方法1
while(index<=right){
if(nums[index]==0) swap(nums,index++,left++);
else if(nums[index]==2) swap(nums,index,right--);
else index++;
}
//方法2
for(int i=0;i<=right;i++){
while(nums[i]==2 && i<right) swap(nums,i,right--);
while(nums[i]==0 && i>left) swap(nums,i,left++);
}
//方法3
for(int i=0;i<=right;i++){
if(nums[i]==0) swap(nums,i,left++);
else if (nums[i]==2) swap(nums,i--,right--); //重点在于i--
}
//方法4,计算0，1，2各自的数量
int num0 = 0, num1 = 0, num2 = 0;
for(int i = 0; i < nums.length; i++) {
if (nums[i] == 0) num0++;
else if (nums[i] == 1) num1++;
else num2++;
}
System.out.print(num0+"/"+num1+num2);
for(int i=0;i<nums.length;i++){
if(num0>0) {num0--;nums[i]=0;}
else if (num1>0) {num1--; nums[i]=1;}
else {nums[i]=2;}
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Leetcode 283. Move Zeroes. 【Easy】
题目要求：1) in-place ， 2) Minimize the total number of operations.
//方法1, Time: O(n), Space: O(1). Number of Operatioins: nums.length.
class Solution {
public void moveZeroes(int[] nums) {
int start = 0;
for(int i=0; i<nums.length;i++){
if(nums[i] != 0){
nums[start++] = nums[i];
}
}
while(start<nums.length) {
nums[start++] = 0;
}
}
}
//方法2, Time: O(n), Space: O(1). Number of Operatioins: 2 * number of non-Zero.
给temp赋值，没改变原来数组，不算operation。
class Solution {
public void moveZeroes(int[] nums) {
int notZero = 0;
for(int i=0; i<nums.length;i++){
if(nums[i] != 0){
int temp = nums[i];
nums[i] = nums[notZero];
nums[notZero++] = temp;
//小于notZero的index都是非零数(notZero本身不确定)
}
}
}
}
Leetcode 376. Wiggle Subsequence. 【Medium】
Greedy 或 DP 解法，用 两个int：up和down 来记录长度。
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums==null || nums.length == 0 ) return 0;
int up = 1, down = 1;
for(int i=1;i<nums.length;i++){
if(nums[i]>nums[i-1]){
up = down + 1;
} else if (nums[i] < nums[i-1]){
down = up + 1;
}
}
return Math.max(up,down);
}
}
Leetcode 280. Wiggle Sort. 【Medium】
就是 nums[i]和nums[i-1]对比，看看是否swap
Time: O(n), Space: O(1).
class Solution {
public void wiggleSort(int[] nums) {
for(int i=1;i<nums.length;i++){
if((i%2 ==1 && nums[i]<nums[i-1])||(i%2==0 && nums[i]>nums[i-1])){
int temp = nums[i];
nums[i] = nums[i-1];
nums[i-1] = temp;
}
}
}
}
Leetcode 215. Kth Largest Element in an Array. 【Medium】经典题型
参考quickSort 快速排序：https://www.geeksforgeeks.org/quick-sort/
方法1，iterative。
class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k; // convert to index of k largest
int left = 0, right = nums.length -1;
while(left<=right){
int i = left;
for(int j=left+1;j<=right;j++){
if(nums[j]<nums[left]){
swap(nums,j,++i);
}
}
swap(nums,i,left);
if(k<i){
right = i-1;
} else if (k>i){
left = i+1;
} else {
return nums[i];
}
}
return -1; // invalid k.
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
方法2，recursive。建立quickSelect函数，返回 k th smallest，并用 recursive 写。
class Solution {
public int findKthLargest(int[] nums, int k) {
// Kth largest, equals (nums.length-k)th smallest
return quickSelect(nums, 0, nums.length-1, nums.length-k);
}
// return kth smallest.
private int quickSelect(int[] nums, int low, int high, int k /* index we're looking for */) {
//partition numbers into either side of pivot.
// 保证了j和j之后都是大于pivot的，而i最后=j，i之前都是小于pivot的
int i=low, j = high, pivot = nums[high];
// while(i < j) {
// if (nums[i++] > pivot) swap(nums, --i, --j);
// }
//相当于：
while(i < j){
if(nums[i]>pivot){
swap(nums,i,--j);
} else {
i++;
}
}
swap(nums, j, high);
// nums[i] is the i th smallest.
if(i == k)
return nums[i];
else if(i > k)
return quickSelect(nums, low, i-1, k);
else
return quickSelect(nums, i+1, high, k);
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Leetcode 324. Wiggle Sort II. 【Medium】
怎么达到题目要求？
应该先排序(比如排序后的[1,2,3,4,5,6])，
然后偶数index倒序，奇数index也倒序.
得到：[3,6,2,5,1,4]，大于median的6,5,4倒序排列在奇数index：1,3,5位置上，而小于median的3,2,1倒序排列在偶数index：0,2,4位置上.
最终的目的，是为了将排序后相等的几项 不相邻not-adjacent。
排序后的数组，相等而且相邻的情况会被奇数index 偶数index的记录隔开。最大需要排除的情况就是median（有可能存在一串相等的median数的情况）。所以我们应该将排序后数组的median前的数和median后的数分别记录在temp最前端和最后端。
考虑[4,5,5,6] 的情况，median分隔得到4,5和5,6. 倒序后得到的是 [5,6,4,5], 才能符合要求。
所以，奇数项，记录median后的倒序数组；偶数项，记录median前的倒序数组。
方法1，用 Arrays.sort(nums) 排序。然后 倒序记录在temp数组中，最后 copy到原来数组
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int[] temp = new int[nums.length];
// 奇数index，从nums最大值开始倒序记录
int bigger = nums.length-1;
for(int i=1;i<nums.length;i+=2){
temp[i] = nums[bigger--];
}
// 偶数index，从nums中位数之前的最大值开始倒序记录
int smaller = (nums.length-1)/2;
for(int j=0;j<nums.length;j+=2){
temp[j] = nums[smaller--];
}
System.arraycopy(temp,0,nums,0,nums.length);
}
}
方法2，
https://leetcode.com/problems/wiggle-sort-ii/discuss/77682/Step-by-step-explanation-of-index-mapping-in-Java
正文的答案没研究，Time:O(n), Space: O(1).
正文下的最高赞答案，Time: O(n), Space: O(n)，如下：
class Solution {
public void wiggleSort(int[] nums) {
int median = findKthLargest(nums,(nums.length+1)/2);
int big = 1, small = nums.length%2 == 0? nums.length-2:nums.length-1;
int[] temp = new int[nums.length];
for(int i=0;i<nums.length;i++){
if(nums[i]>median){
temp[big] = nums[i];
big += 2;
} else if (nums[i]<median){
temp[small] = nums[i];
small -= 2;
}
}
while(big<nums.length){
temp[big] = median;
big += 2;
}
while(small>=0){
temp[small] = median;
small -= 2;
}
System.arraycopy(temp,0,nums,0,nums.length);
}
public int findKthLargest(int[] nums, int k) {
k = nums.length - k; // convert to index of k largest
int left = 0, right = nums.length -1;
while(left<=right){
int i = left;
for(int j=left+1;j<=right;j++){
if(nums[j]<nums[left]){
swap(nums,j,++i);
}
}
swap(nums,i,left);
if(k<i){
right = i-1;
} else if (k>i){
left = i+1;
} else {
return nums[i];
}
}
return -1;
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
