# LeetCode 1
2021.2
- 75. Sort Colors
- 148. 排序链表
- 13. Roman to Integer
- 4. Median of Two Sorted Arrays
- 1. Two Sum（两数之和）
- 11. Container With Most Water
- 15. 3Sum
- 6. ZigZag Conversion
- 16. 3Sum Closest
- 17. Letter Combinations of a Phone Number
- 19. 删除链表的倒数第 N 个结点
- 24. Swap Nodes in Pairs
- 31. Next Permutation
- 34. Find First and Last Position of Element in Sorted Array
- 48. Rotate Image（旋转图像）
- 49. Group Anagrams
- 36. 有效的数独
- 1423. Maximum Points You Can Obtain from Cards（可获得的最大点数）
- 665. Non-decreasing Array（非递减数列）
- 978. Longest Turbulent Subarray（最长湍流子数组）
- 992. Subarrays with K Different Integers（K 个不同整数的子数组）
- 567. 字符串的排列
- 448. Find All Numbers Disappeared in an Array（找到所有数组中消失的数字）
- 119. Pascal's Triangle II（杨辉三角 II）
- 703. Kth Largest Element in a Stream（数据流中的第 K 大元素）
- 485. Max Consecutive Ones（最大连续 1 的个数）
- 995. Minimum Number of K Consecutive Bit Flips（K 连续位的最小翻转次数）
- 561. Array Partition I（数组拆分 I）
- 566. Reshape the Matrix（重塑矩阵）
- 1004. Max Consecutive Ones III（最大连续1的个数 III）
- 697. 数组的度
- 765. Couples Holding Hands（情侣牵手）
- 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit （绝对差不超过限制的最长连续子数组）
- 766. Toeplitz Matrix（托普利茨矩阵）
- 1052. Grumpy Bookstore Owner（爱生气的书店老板）
- 832. Flipping an Image（翻转图像）
- 867. Transpose Matrix（转置矩阵）
- 1178. Number of Valid Words for Each Puzzle（猜字谜）
- 395. Longest Substring with At Least K Repeating Characters（至少有 K 个重复字符的最长子串）
- 896. Monotonic Array（单调数列）
- 26. Remove Duplicates from Sorted Array（删除排序数组中的重复项）
# 75. Sort Colors
// 冒泡排序
public class SortColors {
@Test
public void test() {
int[] nums = new int[]{2,0,2,1,1,0};
sortColors(nums);
System.out.println(Arrays.toString(nums));
}
public void sortColors(int[] nums) {
for (int i=0; i<nums.length-1; i++) {
for (int j=0; j<nums.length-1-i; j++) {
if (nums[j]>nums[j+1]) {
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
}
}
}
}
# 148. 排序链表
public class SortList {
@Test
public void test() {
ListNode head = new ListNode(4);
head.nextAdd(2).nextAdd(1).nextAdd(3);
ListNode result = sortList(head);
result.print();
}
@Test
public void test2() {
ListNode head = new ListNode(4);
head.nextAdd(1).nextAdd(1).nextAdd(3);
ListNode result = sortList(head);
result.print();
}
@Test
public void test3() {
ListNode head = new ListNode(4);
head.nextAdd(3).nextAdd(2).nextAdd(1);
ListNode result = sortList(head);
result.print();
}
@Test
public void test99() {
ListNode head = null;
ListNode result = sortList(head);
// result.print();
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
ListNode h = new ListNode(0);
ListNode result = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return result.next;
}
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
ListNode nextAdd(int val){
next = new ListNode(val);
return next;
}
public void print(){
System.out.print("[");
ListNode curr = this;
while (curr!=null){
System.out.print(curr.val+",");
curr = curr.next;
}
System.out.print("]");
}
}
}
分治，与上述方法一致，重刷一遍
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
private ListNode sortList(ListNode head, ListNode tail) {
if (head == null || head == tail) return head;
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
}
ListNode n1 = sortList(head, slow);
ListNode n2 = sortList(slow, tail);
return merge(n1, n2);
}
private ListNode merge(ListNode n1, ListNode n2) {
ListNode sentinel = new ListNode(0);
ListNode head = sentinel;
while (n1 != null && n2 != null) {
if (n1.val <= n2.val) {
head.next = n1;
head = head.next;
n1 = n1.next;
} else if (n2.val < n1.val) {
head.next = n2;
head = head.next;
n2 = n2.next;
}
}
if (n1 != null) {
head.next = n1;
} else {
head.next = n2;
}
return sentinel.next;
}
}
# 13. Roman to Integer
class Solution {
public int romanToInt(String s) {
s = s.replace("IV","a");
s = s.replace("IX","b");
s = s.replace("XL","c");
s = s.replace("XC","d");
s = s.replace("CD","e");
s = s.replace("CM","f");
int result = 0;
for (int i=0; i<s.length(); i++) {
result += which(s.charAt(i));
}
return result;
}
public int which(char ch) {
switch(ch) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
case 'a': return 4;
case 'b': return 9;
case 'c': return 40;
case 'd': return 90;
case 'e': return 400;
case 'f': return 900;
}
return 0;
}
}
# 4. Median of Two Sorted Arrays
@RunWith(Parameterized.class)
public class MedianOfTwoSortedArrays {
@Parameters(name = "{index}: mid({0}+{1})={2}")
public static Iterable<Object[]> data1() {
return Arrays.asList(new Object[][]{
{new int[]{1, 3}, new int[]{2}, 2d},
{new int[]{1, 3}, new int[]{2, 4}, 2.5d},
{new int[]{0, 0}, new int[]{0, 0}, 0.0d},
{new int[]{}, new int[]{1}, 1d},
{new int[]{2}, new int[]{}, 2d},
{new int[]{2,3}, new int[]{}, 2.5d},
{new int[]{2,3}, new int[]{1, 2, 3, 4, 5, 6}, 3d},
{new int[]{}, new int[]{1, 2, 3, 4, 5, 6}, 3.5d},
});
}
@Parameter
public int[] nums1;
@Parameter(1)
public int[] nums2;
@Parameter(2)
public double expected;
@Test
public void test() {
double result = findMedianSortedArrays(nums1, nums2);
Assert.assertEquals(expected, result, 0.0);
}
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int size = nums1.length + nums2.length;
int[] left = sort(nums1);
int[] right = sort(nums2);
int leftSize = left.length;
int rightSize = right.length;
int leftCount = 0;
int rightCount = 0;
int count = 0;
int[] result = new int[size];
while (leftCount < leftSize && rightCount < rightSize) {
if (left[leftCount] < right[rightCount]) {
result[count++] = left[leftCount++];
} else {
result[count++] = right[rightCount++];
}
}
while (leftCount < leftSize) {
result[count++] = left[leftCount++];
}
while (rightCount < rightSize) {
result[count++] = right[rightCount++];
}
int mid = size / 2;
if (size % 2 == 0) {
return (result[mid] + result[mid - 1]) / 2d;
} else {
return result[mid];
}
}
public int[] sort(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return nums;
}
int size = nums.length;
int mid = size / 2;
int[] left = sort(Arrays.copyOfRange(nums, 0, mid));
int[] right = sort(Arrays.copyOfRange(nums, mid, size));
int leftSize = left.length;
int rightSize = right.length;
int leftCount = 0;
int rightCount = 0;
int count = 0;
int[] result = new int[size];
while (leftCount < leftSize && rightCount < rightSize) {
if (left[leftCount] < right[rightCount]) {
result[count++] = left[leftCount++];
} else {
result[count++] = right[rightCount++];
}
}
while (leftCount < leftSize) {
result[count++] = left[leftCount++];
}
while (rightCount < rightSize) {
result[count++] = right[rightCount++];
}
return result;
}
}
# 1. Two Sum（两数之和）
public class Main {
public static void main(String[] args) {
int[] nums = new int[]{2,7,11,15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println(Arrays.toString(result));
}
/**
* 方案： 指针从第一个数开始往后移动，target减去指针数后得到result，第二个指针从第一指针开始往后移动寻找等于result的数。
* 找到相等的数，即两指针的位置为结果。
* 时间：O(n^2) 空间：
* 关注点：嵌套的第二个for循环可以修改为二分查找法，会faster。
*/
public static int[] twoSum(int[] nums, int target) {
int a = 0,b;
for (; a < nums.length; a++) {
int remain = target - nums[a];
for (b = a+1; b < nums.length; b++) {
if (remain == nums[b]) {
return new int[]{a, b};
}
}
}
return null;
}
}
# 11. Container With Most Water
@RunWith(Parameterized.class)
public class ContainerWithMostWater {
@Parameterized.Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}, 49},
{new int[]{1, 1}, 1},
{new int[]{1, 2, 1}, 2},
{new int[]{4, 3, 2, 1, 4}, 16},
{new int[]{}, 0},
{new int[]{2,3,4,5,18,17,6}, 17},
});
}
@Parameterized.Parameter
public int[] height;
@Parameterized.Parameter(1)
public int expect;
@Test
public void test() {
int result = maxArea(height);
Assert.assertEquals(expect, result);
}
public int maxArea(int[] height) {
int first = 0;
int end = height.length - 1;
if (end < 1) {
return 0;
}
int max = 0;
while (first != end) {
int min = Math.min(height[first], height[end]);
int temp = min * (end - first);
if (temp > max) {
max = temp;
}
if (height[first] >= height[end]) {
end--;
} else {
first++;
}
}
return max;
}
}
# 15. 3Sum
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
for (int first = i + 1, end = nums.length - 1; first < nums.length;first++) {
if (first - 1 > i && nums[first] == nums[first - 1]) {
continue;
}
while (first < end && nums[first] + nums[end] > target) {
end--;
}
if(first == end) {
break;
}
if (first < end && nums[i] + nums[first] + nums[end] == 0) {
result.add(Arrays.asList(nums[i], nums[first], nums[end]));
}
}
}
return result;
}
重刷：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i != 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1, t = -nums[i];
while (l < r) {
while (l < n && l != i+1 && nums[l] == nums[l-1]) {
l++;
}
while (r >= 0 && r != n-1 && nums[r] == nums[r+1]) {
r--;
}
if (l >= r) break;
int cur = nums[l] + nums[r];
if (cur > t) {
r--;
} else if (cur < t) {
l++;
} else {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
l++;
}
}
}
return res;
}
}
# 6. ZigZag Conversion
@RunWith(Parameterized.class)
public class ZigZagConversion {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{"PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"},
{"PAYPALISHIRING", 4, "PINALSIGYAHRPI"},
{"A", 1, "A"},
{"AB", 1, "AB"},
{"ABCDE", 4, "ABCED"},
{"ABCD", 5, "ABCD"},
{"ABCD", 3, "ABDC"},
{"ABC", 3, "ABC"},
});
}
@Parameter
public String s;
@Parameter(1)
public int numRows;
@Parameter(2)
public String expected;
@Test
public void test() {
Assert.assertEquals(expected, convert(s, numRows));
}
public String convert(String s, int numRows) {
char[] chars = s.toCharArray();
int len = chars.length;
if (len <= numRows || numRows == 1) {
return s;
}
int step = 2 * numRows - 2;
StringBuilder str = new StringBuilder();
for (int i = 0; i < numRows; i++) {
if (i == 0 || i == numRows - 1) {
int size = len / (2 * numRows - 2);
if ((i == 0 && len % (2 * numRows - 2) > 0)
|| ((i == numRows - 1) && len % (2 * numRows - 2) >= numRows)) {
size += 1;
}
int index = i;
str.append(chars[index]);
for (int m = 1; m < size; m++) {
index += step;
str.append(chars[index]);
}
} else {
int size = (len / (2 * numRows - 2)) * 2;
if (len % (2 * numRows - 2) > (i)) {
size += 1;
}
if (len % (2 * numRows - 2) > (2 * numRows - 2 - i)) {
size += 1;
}
int index = i;
str.append(chars[index]);
for (int m = 1; m < size; m++) {
if (m % 2 == 0) {
str.append(chars[index + step + i - i]);
index += (step + i - i);
} else {
str.append(chars[index + step - i - i]);
}
}
}
}
return str.toString();
}
}
# 16. 3Sum Closest
@RunWith(Parameterized.class)
public class The3SumClosest {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{-1, 2, 1, -4}, 1, 2},
{new int[]{-1, 2, 4}, 1, 5},
{new int[]{-1, 2, 4, 6,9,1,3,6,3,5,8,2,-5,-10}, 1, 1},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public int target;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = threeSumClosest(nums, target);
Assert.assertEquals(expect, result);
}
public int threeSumClosest(int[] nums, int target) {
int abs = 9999999;
int result = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int first = i + 1, end = nums.length - 1; first < nums.length && first < end; ) {
int sum = nums[i] + nums[first] + nums[end];
if (Math.abs(sum - target) < abs) {
abs = Math.abs(sum - target);
result = sum;
}
if (sum == target) {
return sum;
} else if (sum > target) {
end--;
} else {
first++;
}
if (first == end) {
break;
}
}
}
return result;
}
}
# 17. Letter Combinations of a Phone Number
@RunWith(Parameterized.class)
public class LetterCombinationsOfAPhoneNumber {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{"23", Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf")},
{"2", Arrays.asList("a", "b", "c")},
{"", new ArrayList<>()},
});
}
@Parameter
public String digits;
@Parameter(1)
public List<String> expected;
@Test
public void test() {
Assert.assertEquals(expected, letterCombinations(digits));
}
public List<String> letterCombinations(String digits) {
char[] arr = digits.toCharArray();
if (arr.length <= 0) {
return new ArrayList<>();
}
List<String> result = new ArrayList<>();
recursive(arr, 0, result, "");
return result;
}
public static Map<String, String[]> map = new HashMap<>();
static {
map.put("2", new String[]{"a", "b", "c"});
map.put("3", new String[]{"d", "e", "f"});
map.put("4", new String[]{"g", "h", "i"});
map.put("5", new String[]{"j", "k", "l"});
map.put("6", new String[]{"m", "n", "o"});
map.put("7", new String[]{"p", "q", "r", "s"});
map.put("8", new String[]{"t", "u", "v"});
map.put("9", new String[]{"w", "x", "y", "z"});
}
public void recursive(char[] arr, int index, List<String> result, String curr) {
if (index >= arr.length) {
result.add(curr);
return;
}
String[] strings = map.get(String.valueOf(arr[index]));
for (String str : strings) {
recursive(arr, index + 1, result, curr + str);
}
}
}
# 19. 删除链表的倒数第 N 个结点
快慢指针：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode guard = new ListNode(0, head);
ListNode slow = guard, fast = guard;
while (fast.next != null) {
fast = fast.next;
if (n <= 0) {
slow = slow.next;
} else {
n--;
}
}
delNextNode(slow);
return guard.next;
}
private void delNextNode(ListNode pre) {
if (pre == null || pre.next == null) return;
ListNode next = pre.next.next;
pre.next = next;
}
}
# 24. Swap Nodes in Pairs
@RunWith(Parameterized.class)
public class SwapNodesInPairs {
static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
static ListNode gen(int[] arr) {
if (arr.length == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode pre = head;
for (int i = 1; i < arr.length; i++) {
ListNode curr = new ListNode(arr[i]);
pre.next = curr;
pre = curr;
}
return head;
}
static boolean equals(ListNode expect, ListNode head) {
ListNode curr = new ListNode(0);
curr.next = head;
ListNode curr2 = new ListNode(0);
curr2.next = expect;
while (curr.next != null && curr2.next != null) {
curr = curr.next;
curr2 = curr2.next;
if (curr.val != curr2.val) {
return false;
}
}
return curr.next == null && curr2.next == null;
}
}
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{ListNode.gen(new int[]{1, 2, 3, 4}), ListNode.gen(new int[]{2, 1, 4, 3})},
{ListNode.gen(new int[]{1, 2, 3}), ListNode.gen(new int[]{2, 1, 3})},
{ListNode.gen(new int[]{1, 2}), ListNode.gen(new int[]{2, 1})},
{ListNode.gen(new int[]{1}), ListNode.gen(new int[]{1})},
{ListNode.gen(new int[]{}), ListNode.gen(new int[]{})},
});
}
@Parameter
public ListNode head;
@Parameter(1)
public ListNode expect;
@Test
public void test() {
ListNode result = swapPairs(head);
Assert.assertTrue(ListNode.equals(expect, result));
}
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode temp;
ListNode one = head, two = head.next;
// 交换
one.next = two.next;
two.next = one;
head = two;
// 指针归位
temp = one;
one = two;
two = temp;
// 向后+2
ListNode pre = two;
one = two.next;
if (one != null) {
two = one.next;
} else {
two = null;
}
while (one != null && two != null) {
// 两个指针交换
one.next = two.next;
two.next = one;
pre.next = two;
// 指针归位
temp = one;
one = two;
two = temp;
// 并且向后+2
pre = two;
one = two.next;
if (one != null) {
two = one.next;
} else {
two = null;
}
}
return head;
}
}
# 31. Next Permutation
public void nextPermutation(int[] nums) {
int size = nums.length;
if (size < 2) {
return;
}
int one = 0, two = 1;
int index = -1;
while (two < size) {
if (nums[one] < nums[two]) {
index = one;
}
one++;
two++;
}
if (index == -1) {
//重排序
Arrays.sort(nums);
} else {
Arrays.sort(nums, index + 1, size);
int i = index + 1;
while (i < size) {
if (nums[i] > nums[index]) {
break;
}
i++;
}
int tmp = nums[index];
nums[index] = nums[i];
nums[i] = tmp;
}
}
go解法：
import "sort"
func nextPermutation(nums []int) {
var a, b int
a = -1
pre := nums[len(nums)-1]
for i := len(nums)-2; i >= 0; i-- {
if nums[i] < pre {
a = i
break
}
pre = nums[i]
}
if a == -1 {
sort.Ints(nums)
return
}
for j := len(nums)-1; j > a; j-- {
if nums[j] > nums[a] {
b = j
break
}
}
swap(nums, a, b)
sort.Ints(nums[a+1:])
}
func swap(nums []int, a, b int) {
tmp := nums[a]
nums[a] = nums[b]
nums[b] = tmp
}
# 34. Find First and Last Position of Element in Sorted Array
@RunWith(Parameterized.class)
public class FindFirstAndLastPositionOfElementInSortedArray {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{5, 7, 7, 8, 8, 9, 9, 9, 12, 13}, 8, new int[]{3, 4}},
{new int[]{5, 7, 7, 8, 8, 10}, 8, new int[]{3, 4}},
{new int[]{5, 7, 7, 8, 8, 10}, 6, new int[]{-1, -1}},
{new int[]{}, 0, new int[]{-1, -1}},
{new int[]{1, 1}, 1, new int[]{0, 1}},
{new int[]{2, 2}, 3, new int[]{-1, -1}},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public int target;
@Parameter(2)
public int[] expect;
@Test
public void test() {
int[] result = searchRange(nums, target);
System.out.println(Arrays.toString(result));
Assert.assertEquals(Arrays.toString(expect), Arrays.toString(result));
}
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int start = 0, end = nums.length - 1;
int min = nums.length, max = nums.length;
int mid = -1;
while (start <= end) {
mid = (start + end) / 2;
if (nums[mid] >= target) {
min = mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
start = 0;
end = nums.length - 1;
while (start <= end) {
mid = (start + end) / 2;
if (nums[mid] > target) {
max = mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
max--;
if (min < nums.length && max < nums.length && nums[min] == target && nums[max] == target) {
return new int[]{min, max};
} else {
return new int[]{-1, -1};
}
}
}
# 48. Rotate Image（旋转图像）
@RunWith(Parameterized.class)
public class RotateImage {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[][]{new int[]{1, 2, 3}, new int[]{4, 5, 6}, new int[]{7, 8, 9},},
new int[][]{new int[]{7, 4, 1}, new int[]{8, 5, 2}, new int[]{9, 6, 3},}},
{ new int[][]{
new int[]{5, 1, 9, 11},
new int[]{2, 4, 8, 10},
new int[]{13, 3, 6, 7},
new int[]{15, 14, 12, 16}
},
new int[][]{
new int[]{15, 13, 2, 5},
new int[]{14, 3, 4, 1},
new int[]{12, 6, 8, 9},
new int[]{16, 7, 10, 11}
}
}
});
}
@Parameter
public int[][] matrix;
@Parameter(1)
public int[][] expected;
@Test
public void test() {
rotate(matrix);
System.out.println(Arrays.deepToString(matrix));
Assert.assertEquals(Arrays.deepToString(expected), Arrays.deepToString(matrix));
}
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int x = 0; x < n / 2; x++) {
for (int y = 0; y < (n + 1) / 2; y++) {
int temp = matrix[x][y];
matrix[x][y] = matrix[n - 1 - y][x];
matrix[n - 1 - y][x] = matrix[n - 1 - x][n - 1 - y];
matrix[n - 1 - x][n - 1 - y] = matrix[y][n - 1 - x];
matrix[y][n - 1 - x] = temp;
}
}
}
}
# 49. Group Anagrams
@RunWith(Parameterized.class)
public class GroupAnagrams {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new String[]{"eat", "tea", "tan", "ate", "nat", "bat"},
Arrays.asList(
Arrays.asList("bat"),
Arrays.asList("nat", "tan"),
Arrays.asList("ate", "eat", "tea")
)
},
});
}
@Parameter
public String[] strs;
@Parameter(1)
public List<List<String>> expect;
@Test
public void test() {
List<List<String>> result = groupAnagrams(strs);
// 判断不正确
Assert.assertEquals(expect, result);
}
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = Arrays.toString(chars);
List<String> strings = map.get(key);
if (strings == null) {
strings = new ArrayList<>();
map.put(key, strings);
}
strings.add(strs[i]);
}
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
result.add(entry.getValue());
}
return result;
}
}
# 36. 有效的数独
public boolean isValidSudoku(char[][] board) {
Map<Integer, Set<Character>> box = new HashMap<>();
for (int i = 0; i < board.length; i++) {
Set<Character> row = new HashSet<>();
Set<Character> column = new HashSet<>();
for (int num = 0; num < board.length; num++) {
// check row
char tRow = board[num][i];
if ('.' != tRow) {
if (row.contains(tRow)) {
return false;
} else {
row.add(tRow);
}
}
// check columns
char tColumn = board[i][num];
if ('.' != tColumn) {
if (column.contains(tColumn)) {
return false;
} else {
column.add(tColumn);
}
}
// check box
int r_x = num;
int r_y = i;
int key = (r_y / 3) * 10 + r_x / 3;
Set<Character> chars = box.computeIfAbsent(key, k -> new HashSet<>());
if ('.' != tRow) {
if (chars.contains(tRow)) {
return false;
} else {
chars.add(tRow);
}
}
}
}
return true;
}
优化后：
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] row = new boolean[10][10];
boolean[][] col = new boolean[10][10];
boolean[][] square = new boolean[30][10];
int n = board.length;
int m = board[0].length;
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
int cur = board[r][c] - '0';
if (cur < 0) continue;
if (row[r][cur]) {
return false;
}
if (col[c][cur]) {
return false;
}
int key = (r/3)*10 + (c/3);
if (square[key][cur]) {
return false;
}
row[r][cur] = true;
col[c][cur] = true;
square[key][cur] = true;
}
}
return true;
}
}
# 1423. Maximum Points You Can Obtain from Cards（可获得的最大点数）
@RunWith(Parameterized.class)
public class MaximumPointsYouCanObtainFromCards {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1, 2, 3, 4, 5, 6, 1}, 3, 12},
{new int[]{9, 7, 7, 9, 7, 7, 9}, 7, 55},
{new int[]{2, 2, 2}, 2, 4},
});
}
@Parameter
public int[] cardPoints;
@Parameter(1)
public int k;
@Parameter(2)
public int expect;
@Test
public void test() {
Assert.assertEquals(expect, maxScore(cardPoints, k));
}
public int maxScore(int[] cardPoints, int k) {
// 建立窗口
int size = cardPoints.length;
int winSize = size - k;
int min = 0;
if (winSize == 0) {
for (int cardPoint : cardPoints) {
min += cardPoint;
}
return min;
}
for (int i = 0; i < winSize; i++) {
min += cardPoints[i];
}
// 滑动窗口
int all = min;
int index = winSize;
int sum = min;
for (int start = 1; index < size; index++, start++) {
all += cardPoints[index];
sum = sum - cardPoints[start - 1] + cardPoints[index];
if (sum < min) {
min = sum;
}
}
return all - min;
}
}
# 665. Non-decreasing Array（非递减数列）
@RunWith(Parameterized.class)
public class NonDecreasingArray {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{4, 2, 3}, true},
{new int[]{4, 2, 1}, false},
{new int[]{1}, true},
{new int[]{0, 4, 1, 3, 4}, true},
{new int[]{3, 4, 2, 3}, false},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public boolean expect;
@Test
public void test() {
Assert.assertEquals(expect, checkPossibility(nums));
}
public boolean checkPossibility(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
int x = nums[i];
int y = nums[i + 1];
if (x > y) {
if (count > 0) {
return false;
}
if (i > 0 && y < nums[i - 1]) {
nums[i + 1] = x;
}
count++;
}
}
return true;
}
}
# 978. Longest Turbulent Subarray（最长湍流子数组）
@RunWith(Parameterized.class)
public class LongestTurbulentSubarray {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{9, 4, 2, 10, 7, 8, 8, 1, 9}, 5},
{new int[]{4, 8, 12, 16}, 2},
{new int[]{100}, 1},
});
}
@Parameter
public int[] arr;
@Parameter(1)
public int expect;
@Test
public void test() {
int result = maxTurbulenceSize(arr);
Assert.assertEquals(expect, result);
}
public int maxTurbulenceSize(int[] arr) {
int left = 0, right = 0;
int max = 1;
int size = arr.length;
while (right < size - 1) {
if (left == right) {
if (arr[right] == arr[right + 1]) {
left++;
}
right++;
} else {
if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
right++;
} else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
right++;
} else {
left = right;
}
}
if (max < right - left + 1) {
max = right - left + 1;
}
}
return max;
}
}
# 992. Subarrays with K Different Integers（K 个不同整数的子数组）
@RunWith(Parameterized.class)
public class SubarraysWithKDifferentIntegers {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1, 2, 1, 2, 3}, 2, 7},
{new int[]{1, 2, 1, 3, 4}, 3, 3},
{new int[]{3, 3, 3, 3, 2, 2, 2, 1}, 1, 17},
});
}
@Parameter
public int[] A;
@Parameter(1)
public int K;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = subarraysWithKDistinct(A, K);
Assert.assertEquals(expect, result);
}
public int subarraysWithKDistinct(int[] A, int K) {
return getMostK(A, K) - getMostK(A, K - 1);
}
public int getMostK(int[] A, int K) {
int left = 0, right = 0;
int size = A.length;
int count = 0;
int distinct = 0;
int[] set = new int[size + 1];
while (right < size) {
if (set[A[right]] == 0) {
distinct++;
}
set[A[right]] += 1;
while (distinct > K) {
set[A[left]] -= 1;
if (set[A[left]] == 0) {
distinct--;
}
left++;
}
right++;
count += right - left + 1;
}
return count;
}
/**
* 超时
*/
public int subarraysWithKDistinct2(int[] A, int K) {
int left = 0, right;
int size = A.length;
int count = 0;
int win;
Set<Integer> set = new HashSet<>();
while (left + K - 1 < size) {
right = left;
set.clear();
set.add(A[left]);
set.add(A[right]);
win = right - left + 1;
while (right < size && (win <= K || set.size() <= K)) {
if (set.size() == K) {
count++;
}
right++;
win++;
if (right < size) {
set.add(A[right]);
}
}
left++;
}
return count;
}
}
# 567. 字符串的排列
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length();
int n2 = s2.length();
if (n > n2) return false;
int[] m1 = new int[26];
int[] m2 = new int[26];
for (int i = 0; i < n; i++) {
m1[s1.charAt(i)-'a']++;
m2[s2.charAt(i)-'a']++;
}
if (Arrays.equals(m1, m2)) return true;
for (int i = n; i < n2; i++) {
m2[s2.charAt(i)-'a']++;
m2[s2.charAt(i-n)-'a']--;
if (Arrays.equals(m1, m2)) return true;
}
return false;
}
}
# 448. Find All Numbers Disappeared in an Array（找到所有数组中消失的数字）
@RunWith(Parameterized.class)
public class FindAllNumbersDisappearedInAnArray {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{4, 3, 2, 7, 8, 2, 3, 1}, Arrays.asList(5, 6)},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public List<Integer> expect;
@Test
public void test() {
List<Integer> result = findDisappearedNumbers(nums);
Assert.assertEquals(expect, result);
}
/**
* 由于数组长度n等于里面元素的范围[1,n]，从中可以想到数组下标也是[0,n-1]，能对应到数组中的元素。
* 题目要求O(n)时间复杂度，因此循环不能嵌套，但可以多次循环。
* 有两个方案：
* 1.利用下标，将元素作为下标，翻转nums[元素]值为负数，最后遍历找到不是负数的下标位置。
* 2.利用[1,n]区间条件，将nums[元素]值+n，最后遍历找到<n的下标位置。
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int num : nums) {
if (num < 0) {
num = -num;
}
if (nums[num - 1] > 0) {
nums[num - 1] = -nums[num - 1];
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
result.add(i + 1);
}
}
return result;
}
}
# 119. Pascal's Triangle II（杨辉三角 II）
@RunWith(Parameterized.class)
public class PascalsTriangleII {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{3, Arrays.asList(1,3,3,1)},
});
}
@Parameter
public int rowIndex;
@Parameter(1)
public List<Integer> expect;
@Test
public void test() {
List<Integer> result = getRow(rowIndex);
Assert.assertEquals(expect, result);
}
/**
* 获取杨辉三角的指定行
* 直接使用组合公式C(n,i) = n!/(i!*(n-i)!)
* 则第(i+1)项是第i项的倍数=(n-i)/(i+1);
*/
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<>(rowIndex + 1);
long cur = 1;
for (int i = 0; i <= rowIndex; i++) {
res.add((int) cur);
cur = cur * (rowIndex-i)/(i+1);
}
return res;
}
public List<Integer> getRow2(int rowIndex) {
Integer[] dp = new Integer[rowIndex + 1];
Arrays.fill(dp,1);
for(int i = 2;i < dp.length;i++){
for(int j = i - 1;j > 0;j--)
dp[j] = dp[j] + dp[j - 1];
}
List<Integer> res = Arrays.asList(dp);
return res;
}
}
# 703. Kth Largest Element in a Stream（数据流中的第 K 大元素）
@RunWith(Parameterized.class)
public class KthLargestElementInAStream {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{3, new int[]{4,5,8,2}, new int[]{3,5}, 5},
{3, new int[]{8,2}, new int[]{3,5}, 3},
{3, new int[]{1}, new int[]{3,5}, 1},
{1, new int[]{1}, new int[]{3,5}, 5},
{2, new int[]{0}, new int[]{3,5}, 3},
{1, new int[]{}, new int[]{-3}, -3},
{1, new int[]{}, new int[]{-3,-4}, -3},
{2, new int[]{}, new int[]{-3,-4}, -4},
});
}
@Parameter
public int k;
@Parameter(1)
public int[] nums;
@Parameter(2)
public int[] adds;
@Parameter(3)
public int expect;
@Test
public void test() {
KthLargest kthLargest = new KthLargest(k, nums);
int result = 0;
for (int add : adds) {
result = kthLargest.add(add);
}
Assert.assertEquals(expect, result);
}
class KthLargest {
int[] heap;
// array max volume
int max;
int count;
public KthLargest(int k, int[] nums) {
max = k;
int copy = max;
if (nums.length < max) {
copy = nums.length;
}
heap = new int[max + 1];
System.arraycopy(nums, 0, heap, 1, copy);
count = copy;
if (nums.length < max) {
heap[max] = Integer.MIN_VALUE;
}
buildHeap(heap, max);
// nums其余元素插入最小堆中
for (int i = k; i < nums.length; i++) {
add(nums[i]);
}
}
/**
* 如果比堆顶大，删除堆顶元素，插入，堆化。
*/
public int add(int val) {
int i = 1;
if (count < max || val > heap[i]) {
heap[i] = val;
heapify(heap, max, i);
count++;
return heap[i];
}
return heap[i];
}
private void buildHeap(int[] heap, int n) {
for (int i = n / 2; i >= 1; --i) {
heapify(heap, n, i);
}
}
private void heapify(int[] heap, int n, int i) {
while (true) {
int maxPos = i;
if (i * 2 <= n && heap[maxPos] > heap[i * 2]) {
maxPos = i * 2;
}
if (i * 2 + 1 <= n && heap[maxPos] > heap[i * 2 + 1]) {
maxPos = i * 2 + 1;
}
if (maxPos == i) {
break;
}
swap(heap, i, maxPos);
i = maxPos;
}
}
private void swap(int[] heap, int a, int b) {
int tmp = heap[a];
heap[a] = heap[b];
heap[b] = tmp;
}
}
}
# 485. Max Consecutive Ones（最大连续 1 的个数）
@RunWith(Parameterized.class)
public class MaxConsecutiveOnes {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1,0,1,1,0,1}, 2},
{new int[]{0,0,1,1,0,1}, 2},
{new int[]{}, 0},
{new int[]{0}, 0},
{new int[]{1,1,1}, 3},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public int expect;
@Test
public void test() {
int result = findMaxConsecutiveOnes(nums);
Assert.assertEquals(expect, result);
}
public int findMaxConsecutiveOnes(int[] nums) {
int left = 0, right = 0;
int max = 0;
int size = nums.length;
while (right < size) {
while (right < size && nums[right] == 0) {
right++;
left = right;
}
if(right>=size){
break;
}
if (right - left + 1 > max) {
max = right - left + 1;
}
right++;
}
return max;
}
}
# 995. Minimum Number of K Consecutive Bit Flips（K 连续位的最小翻转次数）
@RunWith(Parameterized.class)
public class MinimumNumberOfKConsecutiveBitFlips {
@Parameterized.Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{0, 1, 0}, 1, 2},
{new int[]{1, 1, 0}, 2, -1},
{new int[]{0, 0, 0, 1, 0, 1, 1, 0}, 3, 3},
});
}
@Parameter
public int[] A;
@Parameter(1)
public int K;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = minKBitFlips(A, K);
Assert.assertEquals(expect, result);
}
/**
* 此题首先要想到什么情况下翻转次数最小
* 特征：1. K位的子数组无法翻转其前面的位置 2. 重复翻转两次，其结果不变。
* 解题依赖：差分数组
*/
public int minKBitFlips(int[] A, int K) {
int res = 0;
int n = A.length;
int[] diff = new int[n + 1];
// 当前位置所需要累加翻转的次数
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += diff[i];
if ((A[i] + cnt) % 2 == 0) {
if (i + K > n) {
return -1;
}
// 总翻转计数
res++;
// 当前位置翻转计数
cnt++;
// 差分数组，用于回退cnt计数
diff[i + K]--;
}
}
return res;
}
}
# 561. Array Partition I（数组拆分 I）
@RunWith(Parameterized.class)
public class ArrayPartitionI {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1,4,3,2}, 4},
{new int[]{6,2,6,5,1,2}, 9},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public int expect;
@Test
public void test() {
int result = arrayPairSum(nums);
Assert.assertEquals(expect, result);
}
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int sum = 0;
for (int i = 0; i < n; i += 2) {
sum += nums[i];
}
return sum;
}
}
# 566. Reshape the Matrix（重塑矩阵）
@RunWith(Parameterized.class)
public class ReshapeTheMatrix {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
});
}
@Parameter
public int[][] nums;
@Parameter(1)
public int r;
@Parameter(2)
public int c;
@Parameter(3)
public int[][] expect;
@Test
public void test() {
int[][] result = matrixReshape(nums, r, c);
Assert.assertEquals(expect, result);
}
public int[][] matrixReshape(int[][] nums, int r, int c) {
int x = nums[0].length;
int y = nums.length;
if(x*y!=r*c){
return nums;
}
int[][] res = new int[r][c];
for (int i = 0; i < y * x; ++i) {
res[i / c][i % c] = nums[i / x][i % x];
}
return res;
}
}
# 1004. Max Consecutive Ones III（最大连续1的个数 III）
@RunWith(Parameterized.class)
public class MaxConsecutiveOnesIII {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2, 6},
{new int[]{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3, 10},
{new int[]{0}, 1, 1},
{new int[]{0}, 0, 0},
});
}
@Parameter
public int[] A;
@Parameter(1)
public int K;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = longestOnes(A, K);
Assert.assertEquals(expect, result);
}
/**
* 题意转换：求最长子数组，其中至多包含K个0
* 滑动窗口
*/
public int longestOnes(int[] A, int K) {
int n = A.length;
int max = 0;
int start = 0, end = 0;
int cnt = 0;
while (end < n) {
if (A[end] == 0) {
cnt++;
}
while (start < n && cnt > K) {
start++;
if (start > 0 && A[start - 1] == 0) {
cnt--;
}
}
if (end - start + 1 > max) {
max = end - start + 1;
}
end++;
}
return max;
}
}
# 697. 数组的度
public int findShortestSubArray(int[] nums) {
int n = nums.length;
// 数组0位计数，1位起始位置，2位最终位置
Map<Integer, int[]> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int[] arrays = map.get(nums[i]);
if (arrays == null) {
arrays = new int[3];
}
if (arrays[0] == 0) {
arrays[1] = i;
} else {
arrays[2] = i;
}
arrays[0]++;
map.put(nums[i], arrays);
}
int degree = 0;
int min = 99999;
Set<Map.Entry<Integer, int[]>> entries = map.entrySet();
for (Map.Entry<Integer, int[]> entry : entries) {
if (entry.getValue()[0] > degree) {
degree = entry.getValue()[0];
}
}
for (Map.Entry<Integer, int[]> entry : entries) {
if (entry.getValue()[0] == degree) {
if (degree == 1) {
min = 1;
} else if (entry.getValue()[2] - entry.getValue()[1] + 1 < min) {
min = entry.getValue()[2] - entry.getValue()[1] + 1;
}
}
}
return min;
}
时隔3个月，再做一次比以前要思路清晰，速度也快很多：
class Solution {
public int findShortestSubArray(int[] nums) {
int max = -1;
int min = 0x3f3f3f3f;
HashMap<Integer, int[]> map = new HashMap<>();
for (int i = 0 ; i < nums.length; i++) {
int[] cur = map.get(nums[i]);
if (cur == null){
cur = new int[]{1, i, i};
} else {
cur[0]++;
cur[2] = i;
}
map.put(nums[i], cur);
if ((cur[0] > max) || (cur[0] == max && (cur[2]-cur[1]) <= min)) {
max = cur[0];
min = cur[2]-cur[1]+1;
}
}
return min;
}
}
# 765. Couples Holding Hands（情侣牵手）
@RunWith(Parameterized.class)
public class CouplesHoldingHands {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{0, 2, 1, 3}, 1},
{new int[]{3, 2, 0, 1}, 0},
{new int[]{0, 2, 4, 6, 7, 1, 3, 5}, 3},
});
}
@Parameter
public int[] row;
@Parameter(1)
public int expect;
@Test
public void test() {
int result = minSwapsCouples(row);
Assert.assertEquals(expect, result);
}
public int minSwapsCouples(int[] row) {
// 构造数组映射 int[需要的值]=当前数组中所在的位置下标
int n = row.length;
int[] map = new int[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
map[row[i]] = i;
}
for (int i = 1; i < n; i += 2) {
if (row[i] % 2 == 0) {
if (row[i - 1] != row[i] + 1) {
map[row[i - 1]] = map[row[i] + 1];
swap(row, map[row[i] + 1], i - 1);
cnt++;
}
} else {
if (row[i - 1] != row[i] - 1) {
map[row[i - 1]] = map[row[i] - 1];
swap(row, map[row[i] - 1], i - 1);
cnt++;
}
}
}
return cnt;
}
// 题解
public int minSwapsCouples2(int[] row) {
int n = row.length;
// 当前值->当前所在位置
int[] mapping = new int[n];
int cnt = 0;
for (int i = 0; i < row.length; i++) {
mapping[row[i]] = i;
}
for (int i = 0; i < n; i += 2) {
int a = row[i];
int b = a ^ 1;
if (row[i + 1] != b) {
int src = i + 1;
int dest = mapping[b];
// 交换mapping中两位置的所在位置
mapping[row[src]] = dest;
mapping[row[dest]] = src;
swap(row, src, dest);
cnt++;
}
}
return cnt;
}
public void swap(int[] nums, int src, int dest) {
int tmp = nums[src];
nums[src] = nums[dest];
nums[dest] = tmp;
}
}
# 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit （绝对差不超过限制的最长连续子数组）
@RunWith(Parameterized.class)
public class LongestContinuousSubarrayWithAbsoluteDiffLessThanOrEqualToLimit {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{8, 2, 4, 7}, 4, 2},
{new int[]{10,1,2,4,7,2}, 5, 4},
});
}
@Parameter
public int[] nums;
@Parameter(1)
public int limit;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = longestSubarray(nums, limit);
Assert.assertEquals(expect, result);
}
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> max = new LinkedList<>();
Deque<Integer> min = new LinkedList<>();
int left = 0, right = 0;
int n = nums.length;
int res = 0;
while (right < n) {
while (!max.isEmpty() && nums[right] > max.peekLast()) {
max.pollLast();
}
while (!min.isEmpty() && nums[right] < min.peekLast()) {
min.pollLast();
}
max.offerLast(nums[right]);
min.offerLast(nums[right]);
while (!max.isEmpty() && !min.isEmpty() && (max.peekFirst() - min.peekFirst() > limit)) {
if (nums[left] == max.peekFirst())
max.pollFirst();
if (nums[left] == min.peekFirst())
min.pollFirst();
left++;
}
res = Math.max(res, right - left+1);
right++;
}
return res;
}
}
# 766. Toeplitz Matrix（托普利茨矩阵）
@RunWith(Parameterized.class)
public class ToeplitzMatrix {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1, 2, 2, 3, 1}, 2},
});
}
@Parameter
public int[][] matrix;
@Parameter(1)
public boolean expect;
@Test
public void test() {
boolean result = isToeplitzMatrix(matrix);
Assert.assertEquals(expect, result);
}
public boolean isToeplitzMatrix(int[][] matrix) {
int x = matrix[0].length;
int y = matrix.length;
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
if (i + 1 < y && j + 1 < x && matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}
}
# 1052. Grumpy Bookstore Owner（爱生气的书店老板）
@RunWith(Parameterized.class)
public class GrumpyBookstoreOwner {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1,0,1,2,1,1,7,5}, new int[]{0,1,0,1,0,1,0,1}, 3, 16},
{new int[]{}, new int[]{}, 1, 0},
});
}
@Parameter
public int[] customers;
@Parameter(1)
public int[] grumpy;
@Parameter(2)
public int X;
@Parameter(3)
public int expect;
@Test
public void test() {
int result = maxSatisfied(customers, grumpy, X);
Assert.assertEquals(expect, result);
}
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int left = 0, right = 0;
int n = customers.length;
int res = 0;
// 窗口中最大值grumpy=1，的数量
int max = 0;
int sum = 0;
while (right < n) {
if (grumpy[right] == 0) {
res += customers[right];
} else if (grumpy[right] == 1) {
sum += customers[right];
}
if (left > 0 && grumpy[left - 1] == 1) {
sum -= customers[left - 1];
}
while (right < n && right - left + 1 < X) {
right++;
if (grumpy[right] == 0) {
res += customers[right];
} else if (grumpy[right] == 1) {
sum += customers[right];
}
}
max = Math.max(max, sum);
left++;
right++;
}
return res + max;
}
}
# 832. Flipping an Image（翻转图像）
@RunWith(Parameterized.class)
public class FlippingAnImage {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{
new int[][]{
new int[]{1, 1, 0},
new int[]{1, 0, 1},
new int[]{0, 0, 0},
},
new int[][]{
new int[]{1, 0, 0},
new int[]{0, 1, 0},
new int[]{1, 1, 1},
}
},
{
new int[][]{
new int[]{1, 1},
new int[]{1, 0},
new int[]{0, 0},
},
new int[][]{
new int[]{0, 0},
new int[]{1, 0},
new int[]{1, 1},
}
},
{
new int[][]{
new int[]{1,1,0,0},
new int[]{1,0,0,1},
new int[]{0,1,1,1},
new int[]{1,0,1,0},
},
new int[][]{
new int[]{1,1,0,0},
new int[]{0,1,1,0},
new int[]{0,0,0,1},
new int[]{1,0,1,0},
}
},
});
}
@Parameter
public int[][] A;
@Parameter(1)
public int[][] expect;
@Test
public void test() {
int[][] result = flipAndInvertImage(A);
Assert.assertArrayEquals(expect, result);
}
public int[][] flipAndInvertImage(int[][] A) {
int n = A.length;
int m = A[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m / 2; j++) {
if (A[i][j] == A[i][m - j - 1]) {
A[i][j] ^= 1;
A[i][m - j - 1] ^= 1;
}
}
if (m % 2 == 1) {
A[i][m/2] ^= 1;
}
}
return A;
}
}
# 867. Transpose Matrix（转置矩阵）
@RunWith(Parameterized.class)
public class TransposeMatrix {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{
new int[][]{
new int[]{1, 2, 3},
new int[]{4, 5, 6},
new int[]{7, 8, 9},
},
new int[][]{
new int[]{1, 4, 7},
new int[]{2, 5, 8},
new int[]{3, 6, 9},
}
},
{
new int[][]{
new int[]{1, 2},
new int[]{4, 5},
new int[]{7, 8},
},
new int[][]{
new int[]{1,4,7},
new int[]{2,5,8},
}
},
});
}
@Parameter
public int[][] matrix;
@Parameter(1)
public int[][] expect;
@Test
public void test() {
int[][] result = transpose(matrix);
Assert.assertArrayEquals(expect, result);
}
public int[][] transpose(int[][] matrix) {
int y = matrix.length;
int x = matrix[0].length;
int[][] res = new int[x][y];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
res[j][i] = matrix[i][j];
}
}
return res;
}
}
# 1178. Number of Valid Words for Each Puzzle（猜字谜）
# 395. Longest Substring with At Least K Repeating Characters（至少有 K 个重复字符的最长子串）
@RunWith(Parameterized.class)
public class LongestSubstringWithAtLeastKRepeatingCharacters {
@Parameterized.Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{"aaabb", 3, 3},
{"ababbc", 2, 5},
{"weitong", 2, 0},
{"baaabcb", 3, 3},
});
}
@Parameter
public String s;
@Parameter(1)
public int k;
@Parameter(2)
public int expect;
@Test
public void test() {
int result = longestSubstring(s, k);
Assert.assertEquals(expect, result);
}
public int longestSubstring(String s, int k) {
// 分治；如果有小于k个的字符，记录下来，整个字符串用其分割，递归此动作即可。
return dfs(0, s.length(), s, k);
}
public int dfs(int start, int n, String s, int k) {
char[] chars = s.toCharArray();
int[] alphabet = new int[26];
for (int i = start; i < start + n; i++) {
alphabet[chars[i] - 'a']++;
}
char split = 0;
for (int i = 0; i < 26; i++) {
if (alphabet[i] > 0 && alphabet[i] < k) {
split = (char) (i + 'a');
break;
}
}
if (split == 0) {
return n;
}
int max = 0;
for (int i = start; i < start + n; i++) {
if (chars[i] == split) {
max = Math.max(dfs(start, i - start, s, k), dfs(i + 1, n - (i - start) - 1, s, k));
break;
}
}
return max;
}
}
# 896. Monotonic Array（单调数列）
@RunWith(Parameterized.class)
public class MonotonicArray {
@Parameters
public static Iterable<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{1,2,2,3}, true},
{new int[]{6,5,4,4}, true},
{new int[]{1,3,2}, false},
});
}
@Parameter
public int[] A;
@Parameter(1)
public boolean expect;
@Test
public void test() {
boolean result = isMonotonic(A);
Assert.assertEquals(expect, result);
}
public boolean isMonotonic(int[] A) {
int n = A.length;
boolean increment = true;
boolean decrement = true;
for (int i = 1; i < n; i++) {
if(A[i-1]>A[i]){
increment = false;
}
if(A[i-1]<A[i]){
decrement = false;
}
}
return increment || decrement;
}
}
# 26. Remove Duplicates from Sorted Array（删除排序数组中的重复项）
class Solution {
public int removeDuplicates(int[] nums) {
int l = 0, r = 1;
int n = nums.length;
while (r < n) {
if (nums[l] != nums[r]) {
swap(nums, ++l, r);
}
r++;
}
return l+1;
}
private void swap(int[] n, int a, int b) {
int tmp = n[a];
n[a] = n[b];
n[b] = tmp;
}
}
golang：
func removeDuplicates(nums []int) int {
l, r := 0, 1
n := len(nums)
if n == 0 {
return 0
}
for ; r < n; r++ {
if nums[l] != nums[r] {
l++
nums[l] = nums[r]
}
}
return l+1
}