556. Next Greater Element III
这个题还蛮有意思的，最开始我以为还是单调栈的问题，后来看应该是数组题。
首先brute force肯定是不行的，阶乘的复杂度。
排列原数字的digits，怎么才能排列出刚好比原数字大的下一个数？
首先，如果一个数的digits是递减的排列，比如95321，那么它不可能有比它还大的排列了。大的数字放在尽可能靠前的位置，这样是一个最大的排列，反过来，一个递增的排列，如12359就应该是最小的排列。
所以在一个递减的区间里，我们是没有办法替换digit使数字变大的，也就是说，我们要找一个递增区间来把数字变大。
但想要把一个数变大，又尽可能小的变大，就要找一个最靠右的递增区间，因为越靠右，增加的值越小。
我们考虑一个数，比如158476531。
从末尾开始，向左遍历，直到不再增加，76531，这是我们找到的原排列的右侧递减区间，4-7是最靠右的递增区间。7后面的数字没有比7更大的了。我们要找一个digit来替换4，我们既要让替换后的数字变大又要尽可能小的变大，所以这时替换的digit应该是右侧比4大的数中最小的那个，就是5。然后swap 4 5。
当然如果7后面的数都比4小，就把4和7对调就行了。
最后一步，把76431这个区间变成递增区间，13467，这样得到的才是最小的比原数字大的数。158513467
Time complexity : O(n). In worst case, only two scans of the whole array are needed. Here, n refers to the number of digits in the given number.
Space complexity : O(n). An array a of size n is used, where n is the number of digits in the given number.
public class Solution {
public int nextGreaterElement(int n) {
char[] number = (n + "").toCharArray();
int i, j;
for (i = number.length - 1; i > 0; --i) {
if (number[i - 1] < number[i]) break;
}
if (i == 0) return -1;
int smallest = i;
for (j = i + 1; j < number.length; j++) {
if (number[j] <= number[i - 1]) break;
}
char tmp = number[i - 1];
number[i - 1] = number[j - 1];
number[j - 1] = tmp;
Arrays.sort(number, i, number.length);
long val = Long.parseLong(new String(number));
return (val <= Integer.MAX_VALUE) ? (int) val : -1;
}
}
566. Reshape the Matrix
LC第30周的weekly contest第一题，三分。
Time complexity : O(mn). We traverse the entire matrix of size mn once only. Here, m and n refers to the number of rows and columns in the given matrix
public class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int row = nums.length;
int column = nums[0].length;
if (row * column != r * c) return nums;
int[][] result = new int[r][c];
int newRow = 0;
int newColumn = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < column; ++j) {
result[newRow][newColumn] = nums[i][j];
newColumn++;
if (newColumn == c) {
newColumn = 0;
newRow++;
}
}
}
return result;
}
}
更机智的写法，利用一个count计数，用除法和取余计算行数列数。
public class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
res[count / c][count % c] = nums[i][j];
count++;
}
}
return res;
}
}
560. Subarray Sum Equals K
LC第30周的weekly contest第二题，5分。
O(n^2)/O(1)的做法。把每一个subarray都试一遍。
public class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
int count = 0;
for (int i = 0; i < nums.length; ++i) {
int sum = 0;
for (int j = i; j < nums.length; ++j) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}
}
非常巧妙的HashMap的做法，O(n)/O(n)复杂度，这个涉及到前缀和的理解运用，后面细讲。
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap<Integer, Integer> map = new HashMap <> ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
if (map.containsKey(sum))
map.put(sum, map.get(sum) + 1);
else
map.put(sum, 1);
}
return count;
}
}
581. Shortest Unsorted Continuous Subarray
虽然是easy题，但是觉得并不是很好想。
思路是用一个排序好的和没排序的比较，找出不同的区段。
注意clone(), deep copy 还有start用length的值，保证一个元素的时候end - start小于零。
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int start = nums.length;
int end = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != sorted[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return end - start >= 0 ? end - start + 1 : 0;
}
}
128. Longest Consecutive Sequence
特别强调了Your algorithm should run in O(n) complexity.
不然你直接排序一下就行了，这题就没意义了。做法是用set记录出现了哪些数，然后对于每一个数左右扫，找出最长的，同时remove set里面用过的数，降低时间，每一个数都只访问了一遍所以是线性的时间。
这题我见过用union-find做的，还有hashmap的，反正都看起来就巨麻烦，union-find的时候我再写一遍，但是完全没必要，杀鸡用牛刀。
public class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
int max = 0;
for (int i = 0; i < nums.length; ++i) {
int down = nums[i] - 1;
while (set.contains(down)) {
set.remove(down);
down--;
}
int up = nums[i] + 1;
while (set.contains(up)) {
set.remove(up);
up++;
}
max = Math.max(max, up - down - 1);
}
return max;
}
}
349. Intersection of Two Arrays
没见过这么傻逼的题。
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return new int[0];
for (int i = 0; i < nums1.length; ++i) {
set.add(nums1[i]);
}
Set<Integer> set2 = new HashSet<>();
for (int i = 0; i < nums2.length; ++i) {
if (set.contains(nums2[i])) {
set2.add(nums2[i]);
}
}
int[] res = new int[set2.size()];
int index = 0;
for (int k : set2) {
res[index++] = k;
}
return res;
}
}
350. Intersection of Two Arrays II
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return new int[0];
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums1.length; ++i) {
if (map.containsKey(nums1[i])) {
map.put(nums1[i], map.get(nums1[i]) + 1);
} else {
map.put(nums1[i], 1);
}
}
for (int i = 0; i < nums2.length; ++i) {
if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
list.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
360. Sort Transformed Array
public class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int[] result = new int[nums.length];
if (nums == null || nums.length == 0) return new int[0];
for (int i = 0; i < nums.length; ++i) {
result[i] = convert(nums[i], a, b, c);
}
Arrays.sort(result);
return result;
}
private int convert(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
}
O(n)解法
public class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int[] sorted = new int[n];
int i = 0, j = n - 1;
int index = a >= 0 ? n - 1 : 0;
while (i <= j) {
if (a >= 0) {
sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c);
} else {
sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c);
}
}
return sorted;
}
private int quad(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
}