414. Third Maximum Number
给一个非空的整数数组，找到这个数组中第三大的值，如果不存在，那么返回最大的值。要求时间复杂度为o（n）
例如：
Example 1:
Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1.
Example 2:
Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum.
思路：设定三个值，max，second，third，先找到最大值，然后第二次遍历排除最大值的情况下找第二大的值，然后找第三大的值。容易出错的地方在于没有第三大的值，比如［2，2，1］这种，所以在遍历第三大值的时候要加一个标记，判断到底第三大的值有没有更改过，如果更改过，那么flag为true，否则为false，全部返回max。 还有个出错点，一定要判断是>=当前值，因为third有可能为负的最小值。
public class ThirdMaximum { public int thirdMax(int[] nums) { int max = Integer.MIN_VALUE; int second = Integer.MIN_VALUE; int third = Integer.MIN_VALUE; boolean flag = false; if (nums.length < 3) { if (nums.length == 1) { return nums[0]; } else { return nums[0] > nums[1] ? nums[0] : nums[1]; } } for (int i = 0; i < nums.length; i++) { if (nums[i] > max) { max = nums[i]; } } for (int i = 0; i < nums.length; i++) { if (nums[i] > second && nums[i] != max) { second = nums[i]; } } for (int i = 0; i < nums.length; i++) { if (nums[i] >= third && (nums[i] != max) && (nums[i] != second)) { third = nums[i]; flag = true; } } return flag == true ? third : max; } }
1. Two Sum
给一个整形数组，和一个目标值，找到该数组中等于该目标值的两个索引，可以认为每一个目标值只有对应的一个解。
例如：
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
思路：其实开始想到的是先排序，再用双指针法去查找，但这样的复杂度为o（nlogn），所以想到了利用hashmap，每访问一个元素，就把需要的另一个元素的值存到map里，这样遍历下一个元素的时候就会对比map中是否该元素是需要的。下标也可以对应的存储到了map里。
public class TwoSum { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); int[] index = new int[2]; for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { index[0] = map.get(nums[i]); index[1] = i; return index; } map.put(target - nums[i], i); } return index; } }
167. Two Sum II - Input array is sorted
相比上题，多的条件是给定的数组是已经按升序排好，另外就是返回的下标不是基于0的了，而是从1开始。另外就是第一个下标一定要小于第二个下标.
思路：类似上题，因为排过序了，直接双指针法去解决就好，另外有个小问题就是数组之中两个数的和相加可能超过int，所以用long去处理下更好。不过代码没写，可以注意下。
public class TwoSumII { public int[] twoSum(int[] numbers, int target) { int[] nums = new int[2]; if (numbers == null || numbers.length < 2) { return nums; } int left = 0; int right = numbers.length - 1; while (left < right) { long sum = numbers[left] + numbers[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { nums[0] = ++left; nums[1] = ++right; break; } } return nums; } }
118. Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
思路：利用定义：每一层的第i个位置，等于上一层第i-1与第i个位置之和。第一行直接添加进去，后面的判断即可，这里我用的是先把首位和末尾都置1，然后再处理中间的方法。需要注意的是，list为空没有赋值的时候是不能用set方法去替换的。所以要先将list内部的值处理一下。这里我写两个方法，第二种是改进的做法。
public class PascalTriangle { public List<List<Integer>> generate(int numRows) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); if (numRows == 0) { return list; } innerlist.add(1); list.add(innerlist); for (int i = 1; i < numRows; i++) { innerlist = new ArrayList<>(i + 1); for (int j = 0; j < i + 1; j++) { innerlist.add(-1); } innerlist.set(0, 1); innerlist.set(i, 1); for (int j = 1; j < i; j++) { innerlist.set(j, list.get(i - 1).get(j - 1) + list.get(i - 1).get(j)); } list.add(innerlist); } return list; } }
第二种(更为简洁）推荐：
public class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> list=new ArrayList<>(); if(numRows==0) { return list; } for(int i=0;i<numRows;i++) { List<Integer> innerlist=new ArrayList<>(); for(int j=0;j<=i;j++) { if(j==0||j==i) { innerlist.add(1); }else { innerlist.add(list.get(i-1).get(j-1)+list.get(i-1).get(j)); } } list.add(innerlist); } return list; } }
119. Pascal's Triangle II
与上题不同的地方在于，这次会给一个索引k，要返回第k行。For example, given k = 3,
Return [1,3,3,1].要求空间复杂度为o(k).
思路：类似上题，因为只要返回当前行，所以一个list处理，唯一需要注意的地方在于，为了让每一行中的中间数值不被set的时候覆盖掉，应该用add（0，1）也就是在每行的最前面加1；
public class PascalTriangleII { public List<Integer> getRow(int rowIndex) { List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < rowIndex + 1; i++) { list.add(0, 1);// 用于在列表的指定位置插入指定元素，并将当前处于该位置的元素及其后续元素的索引加1 for (int j = 1; j < list.size() - 1; j++) { list.set(j, list.get(j) + list.get(j + 1)); /* 注意这个元素一定是j+1.因为list.add(0，1)是在0位置加1，所以原来对应的中间那个值向后移动了。 */ } } return list; }
217. Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
思路：很简单该题，利用一个hashmap去存储。
public class Solution { public boolean containsDuplicate(int[] nums) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++) { if(map.containsKey(nums[i])) { return true; } map.put(nums[i],i); } return false; } }
219. Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the difference between i and j is at most k.
思路：相比上题多了个两个相同值的下标之差不能超过k的条件。思路类似上题，在发现重复元素的同时，同时判断index的差是否满足条件即可。
public class ContainsDuplicateII { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k)) { return true; } map.put(nums[i], i); } return false; } }
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0.
思路：此题就是选择买入卖出股票的最大收益，对于第i天卖出的最大收益即为第i天的股市价格减去[0,i-1]天内的最小股市价格，当第i天的股市价格比漆面最低股市价格还低，则更新最低股市价格。然后取最大的股市收益，为DP问题。用profit[i]表示第i天的收益，则minBuyPrice = min(minBuyPrice, prices[i]),并且profit[i] = prices[i]-minBuyPrice. 然后取profit中的最大值。
public class Solution { public int maxProfit(int[] prices) { if(prices.length==0) { return 0; } int max=0; int min=prices[0]; for(int i=1;i<prices.length;i++) { min=Math.min(prices[i],min); if(prices[i]>prices[i-1]) { max=Math.max(prices[i]-min,max); } } return max; } }
122. Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
思路：与i不同的地方在于可以进行多次交易，但同一天要先卖才能再买。核心思想是贪心算法核心思想：每一段单调递增区间的收益累加。
public class Solution { public int maxProfit(int[] prices) { int profit=0; int diff=0; for(int i=1;i<prices.length;i++) { if(prices[i]>prices[i-1]) { diff=prices[i]-prices[i-1]; profit+=diff; } } return profit; } }
123. Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
思路：两种方法。第一种：动态规划。对于每个i，第一个数组pre[i]用来表示在[0,i]内进行买入卖出的最大收益，post[i]表示在[i,n-1]内进行买入卖出的最大收益。然后最大收益即为max(pre[i]+post[i]);时间复杂度o（n），空间复杂度o(n);
第二种很难想到：
核心是假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，手上的钱需要加上这个price。
它定义了4个状态：
Buy1[i]表示前i天做第一笔交易买入股票后剩下的最多的钱；
Sell1[i]表示前i天做第一笔交易卖出股票后剩下的最多的钱；
Buy2[i]表示前i天做第二笔交易买入股票后剩下的最多的钱；
Sell2[i]表示前i天做第二笔交易卖出股票后剩下的最多的钱；
那么Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[i]}
Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[i]}
Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[i]}
Buy1[i]=max{Buy[i-1],-prices[i]}
可以发现上面四个状态都是只与前一个状态有关，所以可以不使用数组而是使用变量来存储即可。空间复杂度为o（1）。
第一种：
public class Solution { public int maxProfit(int[] prices) { if(prices.length<2) { return 0; } int profit=0; int min=prices[0]; int [] pre=new int[prices.length]; int [] pro=new int[prices.length]; for(int i=1;i<prices.length;i++) { min=Math.min(min,prices[i]); pre[i]=Math.max(pre[i-1],prices[i]-min); } int max=prices[prices.length-1]; for(int i=prices.length-2;i>=0;i--) { max=Math.max(max,prices[i]); pro[i]=Math.max(pro[i+1],max-prices[i]); } for(int i=1;i<prices.length;i++) { profit=Math.max(pre[i]+pro[i],profit); } return profit; } }
第二种：
public class Solution { public int maxProfit(int[] prices) { int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE; int release1 = 0, release2 = 0; for(int i:prices){ // Assume we only have 0 money at first release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far. hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far. release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far. hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far. } return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1. } }
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
思路：两种解法，第一种：正负号标记法，把原数组中出现的数其应该所在的位置上置为负值，然后重新遍历如果大于0，则表示从未出现过。
第二种解法：交换法，利用两个条件，if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1]。每次交换都会至少保证一个值正确，所以也是o（n）
第一种：
public class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> list=new ArrayList<>(); for(int i=0;i<nums.length;i++) { int index=Math.abs(nums[i])-1; if(nums[index]>0) { nums[index]=-nums[index]; } } for(int i=0;i<nums.length;i++) { if(nums[i]>0) { list.add(i+1); } } return list; } }
第二种：
public class FindNumbersDisappeared { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> list=new ArrayList<>(); if(nums==null||nums.length==0){ return list; } for(int i=0;i<nums.length;i++) { while(nums[i]!=i+1&&nums[i]!=nums[nums[i]-1]){ int swap=nums[i]; nums[i]=nums[swap-1]; nums[swap-1]=swap; } } for(int i=0;i<nums.length;i++) { if(nums[i]!=i+1){ list.add(i+1); } } return list; }
442. Find All Duplicates in an Array
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input: [4,3,2,7,8,2,3,1] Output: [2,3]
思路：类似上一题，同样用正负号标记法，当查找到负值时，添加当前值进去，continue即可。
public class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> list =new ArrayList<>(); for(int i=0;i<nums.length;i++) { int index=Math.abs(nums[i])-1; if(nums[index]<0) { list.add(Math.abs(nums[i])); continue; } nums[index]=-nums[index]; } return list; } }
26. Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
思路：双指针法，双指针前进即可。
public class Solution { public int removeDuplicates(int[] nums) { if(nums.length==0) { return 0; } int k=1; for(int i=1;i<nums.length;i++) { if(nums[i]!=nums[i-1]) { nums[k++]=nums[i]; } } return k; } }
80. Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
思路：其实跟上题一样，我们从第三个数值开始判断即可。k也从2开始赋值。
public class Solution { public int removeDuplicates(int[] nums) { if(nums.length<3){ return nums.length; } int k=2; for(int i=2;i<nums.length;i++) { if(nums[i] != nums[k - 2]) { nums[k++]=nums[i]; } } return k; } }
27. Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
思路：类似之前的双指针题目。只不过这次是只要发现不同就赋值给对应的k
public class Solution { public int removeElement(int[] nums, int val) { int k=0; for(int i=0;i<nums.length;i++) { if(nums[i]!=val) { nums[k++]=nums[i]; } } return k; } }
283. Move Zeroes
给定任意一个数组，把其中的0都移到该数组的末尾，其他的数字相对顺序要保持不变。例如：nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
思路：不是0的往前赋值，同时用一个下标纪录当前赋值的数量，最后从这个下标开始赋值0即可。
public class MoveZeroes {
public void moveZeroes(int[] nums) {
if (nums.length == 0) {
return;
}
int start = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[start++] = nums[i];
}
}
for (int i = start; i < nums.length; i++) {
nums[i] = 0;
}
}
}
189. Rotate Array
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
思路：首先要处理k，k先％nums.length。再把数组反转，再将(0，k-1)反转，最后将（k－1，nums.length）反转
public class RotateArray { public void rotate(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--; } } }
169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路：题目要求我们找到这个数组中的主要元素，也就是出现的次数超过了数组的一半。三种思路，着重介绍第三种
第一种：因为majority element超过了数组的一半 ，所以可以先排序，然后截取数组的前一半。最后的值一定是majority element
public class MajorityElement { public int majorityElementI(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }
第二种：利用hashmap，将不同的元素作为key，出现的次数作为value，存储到map中，一旦value超过二分之一，那么返回当前对应的key，但用了额外的空间O(n).
public class MajorityElement { public int majorityElement(int[] nums) { int value=0; Map<Integer,Integer> map = new HashMap<>(); for(int i=0; i<nums.length; i++) { if(map.containsKey(nums[i])) { map.put(nums[i],map.get(nums[i])+1); }else { map.put(nums[i],1); } if(map.get(nums[i])>nums.length/2) { value=nums[i]; } } return value; } }
第三种，也是要重点介绍的一种，利用了Moore voting alogrithm。该算法的思路是对于大小为n的数组，且已知其中必然有某个元素出现的次数占据一半以上（不妨记这个元素为elem）。如果我们从数组中取出一对不相同的元素，如果这两个元素都不是elem，那么取出它们两个之后，elem仍然会占据多一半。如果这两个元素中有一个是elem，那么取出它们两个之后，elem还是会占据多一半。因此，从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。 删除操作可以在常数时间内完成，但是查找不同的元素无法在常数时间内完成，这里有一个技巧，使用常量空间来记录一个候选元素c以及它的出现次数f(c)。
public class MajorityElement {public int majorityElement(int[] nums) { int count=0; int result=nums[0]; for(int i=0;i<nums.length;i++) { if (count==0||nums[i]==result) { count++; result=nums[i]; } else { count--; } } return result; } }
229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
思路：注意与1的区别，首先满足的条件是超过数组长度／3，其次，该题并没有说主值到底存不存在，所以主值有可能不存在，所以在遍历完所有的元素后，要判断出现的数量是否超过了n/3.另外相对于n/2，另一个区别就是主值最多变成了2个。同时时间复杂度变成了线性，空间复杂度为o(1)所以我们这题必须要用moore alogrithm。只不过用两个变量去存储即可。
public class MajorityElement { public List<Integer> majorityElement(int[] nums) { List<Integer> list=new ArrayList<>(); if(nums.length==0||nums==null) { return list; } int number1=nums[0]; int number2=nums[0]; int count1=0; int count2=0; for(int i=0;i<nums.length;i++) { if(nums[i]==number1) { count1++; }else if(nums[i]==number2) { count2++; }else if(count1==0) { number1=nums[i]; count1=1; }else if(count2==0) { number2=nums[i]; count2=1; }else { count1--; count2--; } } count1=0; count2=0; for(int i=0;i<nums.length;i++) { if(nums[i]==number1) { count1++; }else if(nums[i]==number2){ count2++; } } if(count1>nums.length/3) { list.add(number1); } if(count2>nums.length/3) { list.add(number2); } return list; } }
88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
思路：其实就是归并排序，只不过可以在原数组进行，因为nums1的长度可以认为是大于或者等于m＋n的。所以利用原数组，但又不会覆盖前面值的情况下，我们从后往前归并。
public class MergeSortedArray { public void merge(int[] nums1, int m, int[] nums2, int n) { int k=m+n-1; int i=m-1; int j=n-1; while(i>=0&&j>=0) { if(nums1[i]>nums2[j]) { nums1[k--]=nums1[i--]; }else { nums1[k--]=nums2[j--]; } } while(j>=0) { nums1[k--]=nums2[j--]; } } }
66. Plus One
给定一个数组，这个数组的所有数字代表一个非负的整数，最高位在最前面。代表的这个整数加1，求返回的新数组。
思路：其实这个题从最右边开始判断即可，用％去表示当前的值，用／表示进位。但其实有个更好更简单的思路，如果最高位小于9，那么直接加1返回数组即可。如果最高位＝9，那么直接设0，下次遍历的时候接着判断是否<9,里面再加1即可。只要没有返回，说明每位都加了1.最后给新数组开头添加一个1即可。
public class PlusOne { public int[] plusOne(int[] digits) { for (int i = digits.length - 1; i >= 0; --i) { if (digits[i] < 9) { digits[i]++; return digits; } digits[i] = 0; } int[] newdigit = new int[digits.length + 1]; newdigit[0] = 1; return newdigit; } }
243: Shortest Word Distance
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
思路：利用两个下标去存储当前值即可，比较的时候记得要用equals不要用＝＝，另外就是找到一个值后，一定要当下就与之前的另外一个下标做比较，同时保存更新最小值。
public class ShortestWordDistance { public int shortestDistance(String[] words, String word1, String word2) { int min=Integer.MAX_VALUE; int index1=-1; int index2=-1; for(int i=0;i<words.length;i++) { if(words[i].equals(word1)){ index1=i; if(index2!=-1) { min=Math.min(min,index1-index2 ); } } if(words[i].equals(word2)) { index2=i; if(index1!=-1) { min=Math.min(min, index2-index1); } } } return min; } }
244. Shortest Word Distance II
This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
思路：与上题不同的地方在于我们会一直调用这个函数，传入的word1和word2会有不同的很多组，因此一遍一遍的查询对应的index会很麻烦，因此我们用一个hashmap去存储这个words数组。若出现重复单词，则在value里增加相应的索引。然后将要查找的单词的两个索引拿出来，找到最小值.
public class ShortestWordDistanceII { HashMap<String,List<Integer>> map=new HashMap<>(); int min=Integer.MAX_VALUE; int post1=0; int post2=0; List<Integer> index1=new ArrayList<>(); List<Integer> index2 = new ArrayList<> (); public ShortestWordDistanceII(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); } } } public int ShortestDistance(String word1, String word2) { index1=map.get(word1); index2=map.get(word2); int i = 0; int j = 0; while(i < index1.size() && j < index2.size()) { post1=index1.get(i); post2 = index2.get(j); if(post1 > post2) { min=Math.min(min, post1-post2); j++; } else { min=Math.min(min, post2-post1); i++; } } return min; } }
245.Shortest Word Distance III
This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.
Note:You may assume word1 and word2 are both in the list.
思路：与前两题不同之处在于word1和word2可能相同。因此不妨设置一个turn来区别第一次访问和第二次访问这个值。代码类似第一种
public class ShortestWordDistanceIII { public int shortestWordDistance(String[] words, String word1, String word2) { int index1 = -1; int index2 = -1; int times = word1.equals(word2) ? 1 : 0; int turn = 0; int min = Integer.MAX_VALUE; for (int i = 0; i < words.length; i++) { if (words[i].equals(word1) && (turn % 2 == 0)) { index1 = i; if (index2 != -1) { min = Math.min(min, index1 - index2); } turn += times; } else if (words[i].equals(word2)) { index2 = i; if (index1 != -1) { min = Math.min(min, index2 - index1); } turn += times; } } return min; } }
64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
思路：很简单的动态规划，后一步取决于前一步的情况，我们找出最小值即可。
public class MinimumPathSum { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { grid[i][j] = grid[i][j]; } else if (i == 0 && j != 0) { grid[i][j] = grid[i][j] + grid[i][j - 1]; } else if (i != 0 && j == 0) { grid[i][j] = grid[i][j] + grid[i - 1][j]; } else { grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; } } } return grid[m - 1][n - 1]; } }
162. Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
思路：这道题可以用当前值去比较左右的值，但这样如果情况不好复杂度会为o(n)，因此这道题我们用二分查找来做，复杂度为O(logn).
public class Solution { public int findPeakElement(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[mid + 1]) { left = mid + 1; } else { right = mid; } } return left; } }
209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
思路：两种解法，第一种双指针法由两个指针组成的滑动窗口。 使用两个指针来标记滑动窗口的左右界限。 当总和大于等于目标值时，移动左指针；当总和小于目标值时，滑动右指针。
第二种解法，二分法，因为给定的数组是无序的，但都是非负的，所以他们递增的和是有序的。所以可以利用二分也可以做这个题，但复杂度就是o(nlogn).
public class MinimumSizeSubarraySum { public int minSubArrayLen(int s, int[] nums) { int first = 0; int last = 0; int sum = 0; int min = Integer.MAX_VALUE; while (last < nums.length) { sum += nums[last++]; while (sum >= s) { min = Math.min(min, last - first); sum -= nums[first++]; } } return min == Integer.MAX_VALUE ? 0 : min; } }
第二种：
public class Solution { public int minSubArrayLen(int s, int[] nums) { int[] sums = new int[nums.length + 1]; for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1]; int minLen = Integer.MAX_VALUE; for (int i = 0; i < sums.length; i++) { int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums); if (end == sums.length) break; if (end - i < minLen) minLen = end - i; } return minLen == Integer.MAX_VALUE ? 0 : minLen; } private int binarySearch(int lo, int hi, int key, int[] sums) { while (lo <= hi) { int mid = (lo + hi) / 2; if (sums[mid] >= key){ hi = mid - 1; } else { lo = mid + 1; } } return lo; } }
153. Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
思路：没用重复元素，而且是排过序，不论怎么旋转总有一半是排序好的。我们就找排序好的那一半，二分解决。
public class MinimuminRotatedSortedArray { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; } }
154. Find Minimum in Rotated Sorted Array II
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
思路：与上题不同的地方在于这题包含了重复元素。
假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，
这样的我们判断左边缘和中心的时候都是3，我们并不知道应该截掉哪一半。
解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。
所以最坏情况就会出现每次移动一步，总共移动n此，算法的时间复杂度变成O(n)。
public class Solution { public int findMin(int[] nums) { int left=0; int right=nums.length-1; while(left<right) { int mid=left+(right-left)/2; if(nums[mid]>nums[right]) { left=mid+1; }else if(nums[mid]<nums[left]) { right=mid; }else { right--; } } return nums[right]; } }
152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
思路：
思路：一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优，这是由于乘法的性质不像加法那样，累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。我们只需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积
public class MaximumProductSubarray { public int maxProduct(int[] nums) { if(nums ==null || nums.length == 0) return 0; if(nums.length == 1) return nums[0]; int max_local = nums[0]; int min_local = nums[0]; int global = nums[0]; for(int i=1;i<nums.length;i++) { int max_copy = max_local; max_local = Math.max(Math.max(nums[i]*max_local, nums[i]), nums[i]*min_local); min_local = Math.min(Math.min(nums[i]*max_copy, nums[i]), nums[i]*min_local); global = Math.max(global, max_local); } return global; } }
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
思路：动态规划，找到当前局部最大值，然后再得出全局最大值。
public class MaximumSubarray { public int maxSubArray(int[] nums) { int local=nums[0]; int global=nums[0]; for(int i=1;i<nums.length;i++) { local=Math.max(local+nums[i],nums[i]); global=Math.max(global,local); } return global; } }
228. Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
思路：该题要找到数组中的连续的范围，可以利用两个游标来判断nums[i+1]==nums[i]+1，但该解法巧妙的利用了i作为游标
如果长度不超过，且满足条件，i就自动＋＋，如果不满足条件了 跳出内层while，同时判断当前的nums［i］是否是进入for循环时候
的的num，如果不是，打印对应的区间，如果还是当前进入循环的num值，打印当前的num的。最后利用for语句中带的i++自动向下判断下一位
public class SummaryRanges { public List<String> summaryRanges(int[] nums) { List<String> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; while (i + 1 < nums.length && nums[i + 1] == nums[i] + 1) { i++; } if (num != nums[i]) { list.add("" + num + "->" + nums[i]); } else { list.add("" + num); } } return list; } }
39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[ [7], [2, 2, 3] ]
思路：采用深度优先搜索的思想。
public class CombinationSum { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); // 全局变量，静态局部变量，静态全局变量都在静态存储区分配空间，而局部变量在栈里分配空间。尽量声明成局部，这样用完后会立即释放空间。 Arrays.sort(candidates); help(candidates, 0, target, 0, list, innerlist); return list; } public void help(int[] candidates, int sum, int target, int level, List<List<Integer>> list, List<Integer> innerlist) { if (sum > target) { return; } if (sum == target) { List<Integer> temp = new ArrayList<>(); temp.addAll(innerlist);// 可以用list.add(new // ArrayList<>(innerlist));来替代 list.add(temp); return; } for (int i = level; i < candidates.length; i++) { innerlist.add(candidates[i]); help(candidates, sum + candidates[i], target, i, list, innerlist); innerlist.remove(innerlist.size() - 1); } } }
40. Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
思路：与i不同的地方在于，同一个元素不能在一个集合中出现多次。需要注意的是会排序后会出现重复的元素，
1、在同一层递归树中，如果某元素已经处理并进入下一层递归，那么与该元素相同的值就应该跳过。否则将出现重复。
例如：1,1,2,3 如果第一个1已经处理并进入下一层递归1,2,3 那么第二个1就应该跳过，因为后续所有情况都已经被覆盖掉。
2、相同元素第一个进入下一层递归，而不是任意一个
例如：1,1,2,3 如果第一个1已经处理并进入下一层递归1,2,3，那么两个1是可以同时成为可行解的 .而如果选择的是第二个1并进入下一层递归2,3，那么不会出现两个1的解了。需要避开
public class CombinationSumII { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); Arrays.sort(candidates); help(candidates, target, 0, 0, list, innerlist); return list; } public void help(int[] candidates, int target, int sum, int index, List<List<Integer>> list, List<Integer> innerlist) { if (sum > target) { return; } if (sum == target) { list.add(new ArrayList<>(innerlist)); return; } for (int i = index; i < candidates.length; i++) { if (i > index && candidates[i] == candidates[i - 1]) continue; innerlist.add(candidates[i]); help(candidates, target, sum + candidates[i], i + 1, list, innerlist); innerlist.remove(innerlist.size() - 1); } } }
216. Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
思路：多一个判断list中数的多少的条件，另外1-9每个值只能用一次，所以在递归下一个值的时候，index应该＝i+1
public class CombinationSumIII { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); if (n == 0) { return list; } help(k, n, 0, 1, list, innerlist); return list; } public void help(int k, int n, int sum, int index, List<List<Integer>> list, List<Integer> innerlist) { if (sum > n || innerlist.size() > k) { return; } if (innerlist.size() == k && sum == n) { list.add(new ArrayList<>(innerlist)); return; } for (int i = index; i <= 9; i++) { innerlist.add(i); help(k, n, sum + i, i + 1, list, innerlist); innerlist.remove(innerlist.size() - 1); } } }
120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
思路：此题明显是一个求取约束条件下最小路径的题，用动态规划（Dynamic Programming）解再合适不过，既然是DP问题，那么我们需要抽象出状态转移方程：把三角形数阵可以抽象成一个二维矩阵，那么：
设：从位置（i,j）达到底部的最小路径和为MP(i,j)；根据约束条件，从位置（i,j）只能达到下一行的（i+1,j）和（i+1,j+1）两个位置；如果，根据题意我们知道，位置（i,j）处的权值为输入三角形数阵对应的数据：triangle[i][j];So,状态转移方程为：MP(i,j)=min{MP(i+1,j),MP(i+1,j+1)}+triangle[i][j];
三角形顶部到底部最小路径和：MP(0,0)=min{MP(1,0),MP(1,1)}+triangle[0][0];
而：MP(1,0)=min{MP(2,0),MP(2,1)}+triangle[1][0];
MP(1,1)=min{MP(2,1),MP(2,2)}+triangle[1][1]....
很明显，这种自顶向下的求解方式会形成一个“树形结构”，并且自顶向下的求解过程，计算式中一直存在未知式，这显然不是一种好的方式，因此，我们采用自底向上的求解思路：以题目中给出的例子为例：
MP(3,0)=triangle[3][0]=4;
MP(3,1)=triangle[3][1]=1;
MP(3,2)=triangle[3][1]=8;
MP(3,3)=triangle[3][1]=3;
MP(2,0)=min{MP(3,0),MP(3,1)}+triangle[2][0]=1+6=7;
MP(2,1)=min{MP(3,1),MP(3,2)}+triangle[2][1]=1+5=6;
MP(2,2)=min{MP(3,2),MP(3,3)}+triangle[2][2]=3+7=10;
MP(1,0)=min{MP(2,0),MP(2,1)}+triangle[1][0]=6+3=9;
MP(1,1)=min{MP(2,1),MP(2,2)}+triangle[1][1]=6+6=12;
MP(0,0)=min{MP(1,0),MP(1,1)}+triangle[0][0]=9+2=11;
很明显，自底向上计算，最后MP(0,0)就是我们要的结果，采用两重循环即可完成求解：
关于空间复杂度的问题：可以用一个一维数组来存储自底向上的路径向量，路径向量初始化为三角形数阵底部向量，
此后每计算一次，更新一次，空间复杂度为O(n),且不影响输入三角形数阵的原始数据，程序如下：
public class Triangle { public int minimumTotal(List<List<Integer>> triangle) { int length = triangle.size() - 1; if (triangle.size() == 0) { return 0; } if (triangle.size() == 1) { return triangle.get(0).get(0); } List<Integer> sum = triangle.get(length); for (int i = length - 1; i >= 0; i--) { for (int j = 0; j < triangle.get(i).size(); j++) { int sum1 = triangle.get(i).get(j) + sum.get(j); int sum2 = triangle.get(i).get(j) + sum.get(j + 1); sum.set(j, Math.min(sum1, sum2)); } } return sum.get(0); } }
78. Subsets
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路：还是回溯发，类似combination sum。
public class Subsets { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); if (nums.length == 0 || nums == null) { return list; } help(nums, 0, list, innerlist); return list; } public void help(int[] nums, int index, List<List<Integer>> list, List<Integer> innerlist) { list.add(new ArrayList<>(innerlist)); for (int i = index; i < nums.length; i++) { innerlist.add(nums[i]); help(nums, i + 1, list, innerlist); innerlist.remove(innerlist.size() - 1); } } }
90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路：与上题不同的地方在于多了重复的元素，因此我们要先排序，遇到重复的直接跳过。
public class SubsetsII { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> list = new ArrayList<>(); List<Integer> innerlist = new ArrayList<>(); Arrays.sort(nums); if (nums.length == 0 || nums == null) { return list; } help(nums, 0, list, innerlist); return list; } public void help(int[] nums, int index, List<List<Integer>> list, List<Integer> innerlist) { list.add(new ArrayList<>(innerlist)); for (int i = index; i < nums.length; i++) { if (i > index && nums[i] == nums[i - 1]) continue; innerlist.add(nums[i]); help(nums, i + 1, list, innerlist); innerlist.remove(innerlist.size() - 1); } } }
238. Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
思路：
1）分别计算两个数组，left、right，left[i]为nums[i]的左边元素的成绩，right[i]为nums[i]右边元素的乘积。
2）result[i] = left[i] * right[i]
这样算法的时间复杂度为O（n），但算法空间复杂度也为O（n），不满足空间O（1）的需求.
题目中提到 返回的结果不计空间，所以直接在result中保存right值。左边的值用变量left代替
public class ProductArrayExceptSelf { public int[] productExceptSelf(int[] nums) { int[] result = new int[nums.length]; int left = 1; result[nums.length - 1] = 1; for (int i = nums.length - 2; i >= 0; i--) { result[i] = result[i + 1] * nums[i + 1]; } for (int i = 0; i < nums.length; i++) { result[i] = result[i] * left; left = left * nums[i]; } return result; } }
33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
思路：二分法，类似之前的minimum in Rotated Sorted Array ,不管怎么旋转，总有一半是排序好的，另一半是没有旋转过的。利用这一点。然后再将target值判断是在哪个区间，在用二分寻找。要注意取等号的情况。
public int search(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right) { int mid=left+(right-left)/2; if(nums[mid]==target) { return mid; }else if(nums[mid]>=nums[left]) { if(target>=nums[left]&&target<nums[mid]) { right=mid-1; }else { left=mid+1; } }else { if(target>nums[mid]&&target<=nums[right]) { left=mid+1; }else { right=mid-1; } } } return -1; }
81. Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
思路：相比上题多了个重复。类似之前的minimum in RotatedSortedArray。发现不符合有重复 就缩小范围。
public boolean search(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right) { int mid=left+(right-left)/2; if(target==nums[mid]) { return true; }else if(nums[mid]>nums[left]){ if(target<nums[mid]&&target>=nums[left]) { right=mid-1; }else { left=mid+1; } }else if(nums[mid]<nums[left]) { if(target>nums[mid]&&target<=nums[right]) { left=mid+1; }else { right=mid-1; } }else { left++; } } return false; }
79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
思路：还是回溯法。要注意同一个字母只能用一次，因此要用个visited数组来存当前元素是否访问过。
public class Solution { boolean visited[][]; public boolean exist(char[][] board, String word) { visited=new boolean[board.length][board[0].length]; for(int i=0;i<board.length;i++) { for(int j=0;j<board[0].length;j++) { if(word.charAt(0)==board[i][j]&&search(board,word,i,j,0)) { return true; } } } return false; } private boolean search(char[][]board, String word, int i, int j, int index){ if(index==word.length()) { return true; } if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(index)||visited[i][j]) { return false; } visited[i][j]=true; if(search(board,word,i+1,j,index+1)|| search(board,word,i-1,j,index+1)|| search(board,word,i,j+1,index+1)|| search(board,word,i,j-1,index+1)) { return true; } visited[i][j]=false; return false; } }
75. Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.Note:
You are not suppose to use the library's sort function for this problem.
思路：把0放到最前面，把2放到最后面，中间剩下的自然是1了。但需要注意的是有可能替换后，后面的2又跑到了前面，所以要用循环去一直做位移
public class SortColors { public void sortColors(int[] nums) { int start = 0; int end = nums.length - 1; for (int i = 0; i < nums.length; i++) { while (nums[i] == 2 && i < end) { int temp = nums[i]; nums[i] = nums[end]; nums[end] = temp; end--; } while (nums[i] == 0 && i > start) { int temp = nums[i]; nums[i] = nums[start]; nums[start] = temp; start++; } } } }
74. Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
思路：该题很简单，把该二维数组想象成排序好的一维数组，然后二分法解决，唯一需要考虑的是找到当前的索引。
public class Search2DMatrix { public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix == null) { return false; } int start = 0; int end = matrix.length * matrix[0].length - 1; int col = matrix[0].length; while (start <= end) { int mid = start + (end - start) / 2; if (matrix[mid / col][mid % col] == target) { return true; } else if (matrix[mid / col][mid % col] < target) { start = mid + 1; } else { end = mid - 1; } } return false; } }
73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
思路：常数空间的话，第一可以考虑是不是固定数量的几个变量能搞定；否则可以考虑是不是问题本身已经提供了足够的空间。
这道题属于后者，就是利用矩阵的第一行和第一列来作为辅助空间使用。不用开辟新的存储空间。方法就是：
1.先确定第一行和第一列是否需要清零
即，看看第一行中是否有0，记下来。也同时记下来第一列中有没有0。
2.扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0
这里不用担心会将本来第一行或第一列的1改成了0，因为这些值最后注定要成为0的，比如matrix[i][j]==0，那么matrix[i][0]处在第i行，matrix[0][j]处于第j列，最后都要设置为0的。
3.根据第一行和第一列的信息，已经可以将剩下的矩阵元素赋值为结果所需的值了即，拿第一行为例，如果扫描到一个0，就将这一列都清0.
4.根据1中确定的状态，处理第一行和第一列。
如果最开始得到的第一行中有0的话，就整行清零。同理对列进行处理。
＊＊＊易错的地方：错误的地方在于假设第一行和第一列都没有0.那么在遍历的过程中，假设第一次遇到了0，那么会把该0所在行的第一个值和所在列的第一个值置为0，当访问下个值的时候，前面两个if就会发现第一行和第一列的0，从而将第一行和第一列置为true；导致了第一行和第一列原本就有0的错误情况。解决的方法就是在遍历的过程中，一定要发现遍历的当前值为0时，才进行判断当前所在行和列分别是不是第一行和第一列。
public class Solution { public void setZeroes(int[][] matrix) { boolean firstrowzero=false; boolean firstcolzero=false; for(int i=0;i<matrix.length;i++) { for(int j=0;j<matrix[0].length;j++) { if(matrix[i][j]==0) { if(i==0) { firstrowzero=true; } if(j==0) { firstcolzero=true; } matrix[0][j]=0; matrix[i][0]=0; } } } for(int i=1;i<matrix.length;i++) { for(int j=1;j<matrix[0].length;j++) { if(matrix[0][j]==0) { matrix[i][j]=0; } if(matrix[i][0]==0) { matrix[i][j]=0; } } } if(firstrowzero) { for(int i=0;i<matrix[0].length;i++) { matrix[0][i]=0; } } if(firstcolzero) { for(int i=0;i<matrix.length;i++) { matrix[i][0]=0; } } } }
163: Missing Ranges
Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
思路：从头遍历，不断更新最小值。
public class MissingRanges { public List<String> findMissingRanges(int[] A, int lower, int upper) { if (A == null) return null; List<String> res = new ArrayList<String>(); for (int i = 0; i < A.length; i++) { while (i < A.length && A[i] == lower) { lower++; i++; } if (i >= A.length) break; if (A[i] == lower + 1) { res.add(String.valueOf(lower)); } else { res.add("" + lower + "->" + (A[i] - 1)); } lower = A[i] + 1; } if (lower == upper) { res.add(String.valueOf(lower)); } else if (lower < upper) { res.add("" + lower + "->" + upper); } return res; } }
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
思路：此题并没有说是排序好的，而且要用线性的时间复杂度，所以不能先排序，因为sort排序是归并排序，时间复杂度是nlogn
这是一个典型的位运算的题，要用到异或。异或的特性：a^b^b =a,因为nums［i］＝i；所以结合下标与数组的值我们可以利用异或去解决。
public class MissingNumber { public int missingNumber(int[] nums) { int xor = 0, i = 0; for (i = 0; i < nums.length; i++) { xor = xor ^ i ^ nums[i];//最终结果应该为一个(下标^与最后的num值） } return xor ^ i;//最后的num值再与数组的长度也就是i异或就会得出对应的那个下标，也就是少的那个值。 } }
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
思路：到达每一个网格的路径数等于它上面和左面网格的路径数之和。
据此，我们可以建立一个数组来保存一行网格所拥有的路径数。
这个数组的个数是网格的列数，遍历网格的方式是一行一行的遍历。这样，每计算完一个网格的路径数，就自动取代了上一行当前列的网格的路径数。
注：递归的思路在本题中会超时
public class UniquePaths { public int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) return 0; int[] res = new int[n]; res[0] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { res[j] = res[j] + res[j - 1]; } } return res[n - 1]; } }
63. Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
思路：与上题不同的地方增加了一个障碍物，用直观的思路去解决。
public class UniquePathsII { public int uniquePathsWithObstacles(int[][] obstacleGrid) { //Empty case if(obstacleGrid.length == 0) return 0; int rows = obstacleGrid.length; int cols = obstacleGrid[0].length; for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0; else if(i == 0 && j == 0) obstacleGrid[i][j] = 1; else if(i == 0) obstacleGrid[i][j] = obstacleGrid[i][j - 1];// For row 0, if there are no paths to left cell, then its 0,else 1 else if(j == 0) obstacleGrid[i][j] = obstacleGrid[i - 1][j];// For col 0, if there are no paths to upper cell, then its 0,else 1 else obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } } return obstacleGrid[rows - 1][cols - 1]; } }
54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
思路：四个方向不断添加值，但要注意每遍历完一行或者一列，要缩小范围，缩小行值或者列值。直到起始等于结尾退出循环。
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<>(); if (matrix.length == 0) { return list; } int rowstart = 0; int rowend = matrix.length - 1; int colstart = 0; int colend = matrix[0].length - 1; while (rowstart <= rowend && colstart <= colend) { for (int i = colstart; i <= colend; i++) { list.add(matrix[rowstart][i]); } rowstart++; for (int i = rowstart; i <= rowend; i++) { list.add(matrix[i][colend]); } colend--; if (rowstart <= rowend) { for (int i = colend; i >= colstart; --i) { list.add(matrix[rowend][i]); } } rowend--; if (colstart <= colend) { for (int i = rowend; i >= rowstart; i--) { list.add(matrix[i][colstart]); } } colstart++; } return list; }
59. Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路：类似1，反过来而已。
public class SpiralMatrixII { public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int rowstart = 0; int rowend = n - 1; int colstart = 0; int colend = n - 1; if (n == 0) { return matrix; } int num = 1; while (rowstart <= rowend && colstart <= colend) { for (int i = colstart; i <= colend; i++) { matrix[rowstart][i] = num; num++; } rowstart++; for (int i = rowstart; i <= rowend; i++) { matrix[i][colend] = num; num++; } colend--; if (rowstart <= rowend) { for (int i = colend; i >= colstart; i--) { matrix[rowend][i] = num; num++; } } rowend--; if (colstart <= colend) { for (int i = rowend; i >= rowstart; i--) { matrix[i][colstart] = num; num++; } } colstart++; } return matrix; } }
15. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：从数组第一个值开始取，设置两个下标，当第一个值确定后，两个下标分别从第一个值＋1和最后一个值取。等于的时候添加进去
大于的话后面的游标就减1，小于前面的游标就加1，但要注意排除重复的情况。
public class ThreeSum { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list =new ArrayList<>(); Arrays.sort(nums); if(nums.length==0) { return list; } for(int i=0;i<nums.length;i++) { if(i==0||i>0&&nums[i]!=nums[i-1]) { int lo=i+1; int hi=nums.length-1; int sum=0-nums[i]; while(lo<hi) { if(nums[lo]+nums[hi]==sum) { list.add(Arrays.asList(nums[lo],nums[hi],nums[i])); while(lo<hi&&nums[lo]==nums[lo+1]) { lo++; } while(lo<hi&&nums[hi]==nums[hi-1]) { hi--; } lo++; hi--; }else if(nums[lo]+nums[hi]>sum) { hi--; }else { while(lo<hi&&nums[lo]==nums[lo+1]) { lo++; } lo++; } } } } return list; } }
259.3Sum Smaller
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up: Could you solve it in O(n2) runtime?
思路：解题思路和3SUM一样，也是先对整个数组排序，然后一个外层循环确定第一个数，然后里面使用头尾指针left和right进行夹逼，
得到三个数的和。如果这个和大于或者等于目标数，就把right向前一位。如果这个和小于目标数，
那就有right - left个有效的结果。因为假设我们此时固定好外层的那个数，还有头指针left指向的数不变，
那把尾指针向左移0位一直到左移到left之前一位，这些组合都是小于目标数的。另外就是这个题可以包含重复，所以不用判断重复元素
public class ThreeSumSmaller { public int threeSumSmaller(int[]nums, int target) { Arrays.sort(nums); int count=0; for(int i=0;i<nums.length-2;i++) { int start=i+1; int end=nums.length-1; while(start<end) { if(nums[i]+nums[start]+nums[end]>=target) { end--; }else { count+=end-start; start++; } } } return count; } }
16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
思路类似之前的3个数的题
public class ThreeSumClosest { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int result=nums[0]+nums[1]+nums[nums.length-1]; for(int i=0;i<nums.length-2;i++) { int start=i+1; int end=nums.length-1; while(start<end) { int sum=nums[i]+nums[start]+nums[end]; if(Math.abs(sum-target)<Math.abs(result-target)) { result=sum; } if(sum>target) { end--; } if(sum<target) { start++; } if(sum==target) { return target; } } } return result; } }
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路：类似3sum，找到第一个值后，找第二个值，然后剩下的2个值2分查找。
public class FourSum { public List<List<Integer>> fourSum(int[] num, int target) { ArrayList<List<Integer>> ans = new ArrayList<>(); if (num.length < 4) return ans; Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { if (i > 0 && num[i] == num[i - 1]) continue; for (int j = i + 1; j < num.length - 2; j++) { if (j > i + 1 && num[j] == num[j - 1]) continue; int low = j + 1, high = num.length - 1; while (low < high) { int sum = num[i] + num[j] + num[low] + num[high]; if (sum == target) { ans.add(Arrays.asList(num[i], num[j], num[low], num[high])); while (low < high && num[low] == num[low + 1]) low++; while (low < high && num[high] == num[high - 1]) high--; low++; high--; } else if (sum < target) low++; else high--; } } } return ans; } }
55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
思路：此题典型的贪心算法。如下思考，从i＝0开始，nums[i]+i代表每个数组中的值能到的最远距离，那么把该值记录下来，
数组中的下一个值的下标代表距离起点的距离，如果当前的最大距离到不了下一个值的下标，那么说明到不了，如果能到，那么
接着记录能到的最大距离，直到发现当前下标对应的值超过了最大距离，说明到不了。否则能到。
public class JumpGame { public boolean canJump(int[] nums) { int reachable = 0; for (int i = 0; i < nums.length; i++) { if (i > reachable) { return false; } reachable = Math.max(reachable, nums[i] + i); } return true; } }
45. Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.
思路：The main idea is based on greedy.
Let's say the range of the current jump is [curBegin, curEnd],
curFarthest is the farthest point that all points in [curBegin, curEnd] can reach.
Once the current point reaches curEnd, then trigger another jump,
and set the new curEnd with curFarthest, then keep the above steps,要注意范围应该是i<length-1;因为到最后一个值就算到达了。
public class JumpGameII { 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; } } return jumps; } }
48. Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
思路：the idea was firstly transpose the matrix and then flip it symmetrically. For instance,
1 2 3
4 5 6
7 8 9
after transpose, it will be swap(matrix[i][j], matrix[j][i])
1 4 7
2 5 8
3 6 9
Then flip the matrix horizontally. (swap(matrix[i][j], matrix[i][matrix.length-1-j])
7 4 1
8 5 2
9 6 3
public class RotateImage { public void rotate(int[][] matrix) { for(int i = 0; i<matrix.length; i++){ for(int j = i; j<matrix[0].length; j++){ int temp = 0; temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } for(int i =0 ; i<matrix.length; i++){ for(int j = 0; j<matrix.length/2; j++){ int temp = 0; temp = matrix[i][j]; matrix[i][j] = matrix[i][matrix.length-1-j]; matrix[i][matrix.length-1-j] = temp; } } } }
277.Find the Celebrity
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.
思路：如果a认识b，则a不会是名人；如果a不认识b，则b不会是名人。
因此每询问一次a是否认识b，都可以排除掉一个人，所以在O(n)时间内就可以排除掉n-1个人。
最后还要检查确认，是否其他人都认识这个人，以及这个人都不认识其他人。
/* The knows API is defined in the parent class Relation. boolean knows(int a, int b); */ public class FindCelebrity { public int findCelebrity(int n) { int celebrity=0; for(int i=1;i<n;i++) { if(knows(celebrity,i)) { celebrity=i; } } for(int i=0;i<n;i++) { if(celebrity != i&&knows(celebrity,i)) { return -1; } if(celebrity != i&&!knows(i,celebrity)) { return -1; } } return celebrity; } }
280.Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
思路：两种解法，第一种比较容易想到，o（nlogn）先排序，然后交换第第二个和第三个，第四个和第五个。以此类推。就能满足题目要求。
第二种解法o（n）：仔细观察会发现，奇数下标一定是nums[i]>=nums[i-1],偶数下标一定是nums［i］<=nums[i-1];利用该性质。
如果对应的下标不满足，那么交换她们即可。
public class WIggleSort { public void wiggleSort(int[] nums) { Arrays.sort(nums); for(int i=2;i<nums.length;i+=2) { int temp=nums[i-1]; nums[i-1]=nums[i]; nums[i]=temp; } } }
public class WIggleSort { 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-1]; nums[i-1]=nums[i]; nums[i]=temp; } } } }
289. Game of Life
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules
Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up: Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
思路：DEAD->LIVE, DEAD->DEAD, LIVE->LIVE, LIVE->DEAD 即可.int 完全可以找4个数来表示这4种状态.
这里我用了 0,1, 10, 11 表示.
public class GameOfLife { public void gameOfLife(int[][] board) { //check input if(board==null || board.length==0 || board[0]==null || board[0].length==0) return; int m = board.length; int n = board[0].length; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { int x = getLiveNum(board, i, j); if(board[i][j] == 0) { if(x==3) board[i][j]+=10; } else { if(x==2 || x==3) board[i][j]+=10; } } } for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { board[i][j] /= 10; } } } private int getLiveNum(int[][] board, int x, int y) { int c=0; for(int i=x-1; i<=x+1; i++) { for(int j=y-1; j<=y+1; j++) { if(i<0 || j<0 || i>board.length-1 || j>board[0].length-1 || (i==x && j==y)) continue; if(board[i][j]%10==1) c++; } } return c; } }
35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
思路：典型的二分。以上实现方式有一个好处，就是当循环结束时，如果没有找到目标元素，
那么l一定停在恰好比目标大的index上，r一定停在恰好比目标小的index上，所以个人比较推荐这种实现方式。
public class SearchInsertPosition { public int searchInsert(int[] nums, int target) { int start = 0; int end = nums.length - 1; while (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] < target) { start = mid + 1; } if (nums[mid] == target) { return mid; } if (nums[mid] > target) { end = mid - 1; } } return start; } }
370. Range Addition
Assume you have an array of length n initialized with all 0's and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.
Example:
Given:
length = 5,
updates = [
[1, 3, 2],
[2, 4, 3],
[0, 2, -2]
]
Output:
[-2, 0, 3, 5, 3]
Explanation:
Initial state:
[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]
思路：achieve the final result array in two passes:
Iterate through the k update operations and "somehow" mark them in the [0, 0, 0, 0, 0] array (using length 5 for example), for each operation, only update startIndex and endIndex + 1. this is O(k) in total.
iterate through the marked array and "somehow" transforms it to the final result array. this is O(n) in total (n = length).
All in all it is O(n + k).
Now think in a simpler way first, if you have only one update operation, suppose input is (n = 5, updates = { {1, 3, 2} }), what does the O(n + k) solution do?
Initialize the result array as length of n + 1, because we will operate on endIndex + 1:
result = [0, 0, 0, 0, 0, 0]
Then marks index 1 as 2 and marks index 3+1 as -2:
result = [0, 2, 0, 0, -2, 0]
Next, iterate through result, and accumulates previous sum to current position, just like 303. Range Sum Query - Immutable:
result = [0, 0 + 2, 0 + 2, 0 + 2, 2 + (-2), 0] = [0, 2, 2, 2, 0, 0]
Finally, trivial work to discard the last element because we don't need it:
result = [0, 2, 2, 2, 0], which is the final result.
Now you might see why we do "puts inc at startIndex and -inc at endIndex + 1":
Put inc at startIndex allows the inc to be carried to the next index starting from startIndex when we do the sum accumulation.
Put -inc at endIndex + 1 simply means cancel out the previous carry from the next index of the endIndex, because the previous carry should not be counted beyond endIndex.
And finally, because each of the update operation is independent and the list operation is just an accumulation of the "marks" we do, so it can be "makred" all at once first and do the range sum at one time at last step.
public class RangeAddition { public int[] getModifiedArray(int length, int[][] updates) { int[] result = new int[length]; for (int i = 0; i < updates.length; i++) { int start = updates[i][0], end = updates[i][1]; int inc = updates[i][2]; result[start] += inc; if (end < length - 1) { result[end + 1] -= inc; } } int sum = 0; for (int i = 0; i < length; i++) { sum += result[i]; result[i] = sum; } return result; } }
11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
思路：双标记从头和从末尾向里收缩，哪边的值相对另一边较小就收缩哪边
public class MostWater { public int maxArea(int[] height) { int max = Integer.MIN_VALUE; int left = 0; int right = height.length - 1; while (left < right) { max = Math.max(max, (right - left) * Math.min(height[left], height[right])); if (height[left] < height[right]) { left++; } else { right--; } } return max; } }