- 剑指 Offer 05. 替换空格
- 189. 旋转数组
- 剑指 Offer 61. 扑克牌中的顺子
- 剑指 Offer 03. 数组中重复的数字
- 剑指 Offer 39. 数组中出现次数超过一半的数字
- 剑指 Offer 53 - I. 在排序数组中查找数字 I
- 4. 寻找两个正序数组的中位数
- 剑指 Offer 53 - II. 0～n-1中缺失的数字
- 41. 缺失的第一个正数
- 448. 找到所有数组中消失的数字
- 移动零
- 剑指 Offer 42. 连续子数组的最大和
- 最大连续1的个数
- 剑指 Offer 04. 二维数组中的查找
- 378. 有序矩阵中第K小的元素
- 剑指 Offer 29. 顺时针打印矩阵
- 48. 旋转图像
- 重塑矩阵
- 56. 合并区间
- 919. 会议室 II
- 错误的集合
- 寻找重复数
- 优美的排列 II
- 621. 任务调度器
- 数组的度
- 托普利茨矩阵
- 数组嵌套
- 最多能完成排序的块
- 31. 下一个排列
- 剑指 Offer 05. 替换空格
- 189. 旋转数组
- 剑指 Offer 61. 扑克牌中的顺子
- 剑指 Offer 03. 数组中重复的数字
- 剑指 Offer 39. 数组中出现次数超过一半的数字
- 剑指 Offer 53 - I. 在排序数组中查找数字 I
- 4. 寻找两个正序数组的中位数
- 剑指 Offer 53 - II. 0～n-1中缺失的数字
- 41. 缺失的第一个正数
- 448. 找到所有数组中消失的数字
- 移动零
- 剑指 Offer 42. 连续子数组的最大和
- 最大连续1的个数
- 剑指 Offer 04. 二维数组中的查找
- 378. 有序矩阵中第K小的元素
- 剑指 Offer 29. 顺时针打印矩阵
- 48. 旋转图像
- 重塑矩阵
- 56. 合并区间
- 919. 会议室 II
- 错误的集合
- 寻找重复数
- 优美的排列 II
- 621. 任务调度器
- 数组的度
- 托普利茨矩阵
- 数组嵌套
- 最多能完成排序的块
- 31. 下一个排列
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：输入：s = "We are happy."输出："We%20are%20happy."限制：0 <= s 的长度 <= 10000
解法
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String res = new String(array, 0, size);
return res;
}
}
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
解法
class Solution {
public void rotate(int[] nums, int k) {
// write code here
int n = nums.length;
k = k % n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
public void reverse(int[] a, int start, int end) {
while (start < end) {
int temp = a[start];
a[start] = a[end];
a[end] = temp;
start++;
end--;
}
}
}
剑指 Offer 61. 扑克牌中的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制：
数组长度为 5
数组的数取值为 [0, 13] .
set集合
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for (int num : nums) {
// 跳过大小王
if (num == 0) {
continue;
}
max = Math.max(max, num);
min = Math.min(min, num);
// 若有重复，提前返回 false
if (repeat.contains(num)) {
return false;
}
repeat.add(num);
}
// 最大牌 - 最小牌 < 5 则可构成顺子
return max - min < 5;
}
}
排序+遍历
class Solution {
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums);
for (int i = 0; i < 4; i++) {
if (nums[i] == 0) {
joker++;
} else if (nums[i] == nums[i + 1]){
return false;
}
}
return nums[4] - nums[joker] < 5;
}
}
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
解法
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int repeat = -1;
for (int num : nums) {
if (!set.add(num)) {
repeat = num;
break;
}
}
return repeat;
}
}
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
投票法
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for (int num : nums) {
if (votes == 0) {
x = num;
}
votes += num == x ? 1 : -1;
}
return x;
}
}
剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制：
0 <= 数组长度 <= 50000
解法
用二分法找到第一次出现target的位置，然后遍历即可。
class Solution {
public int search(int[] nums, int target) {
int firstIndex = -1;
if (nums.length == 0 || nums[0] > target) {
return 0;
}
int low = 0, high = nums.length - 1;
// 用二分查找，找到第一次出现target的位置
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] >= target) {
if (mid == 0 || (nums[mid] == target && nums[mid - 1] < target)) {
firstIndex = mid;
break;
}
else {
high = mid - 1;
}
}
else {
low = mid + 1;
}
}
if (firstIndex != -1 && nums[firstIndex] == target) {
if (firstIndex == nums.length - 1) {
return 1;
}
else {
// 往下遍历找到第二次出现target 的位置
for (int i = firstIndex + 1; i < nums.length; ++i) {
if (nums[i] != target) {
return i - firstIndex; // i - 1 - firstIndex + 1
}
if (i == nums.length - 1 && nums[i] == target) {
return i - firstIndex + 1;
}
}
}
}
return 0;
}
}
二分查找另一种写法
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target){
right = mid;
} else {
right = mid - 1;
}
}
int count = 0;
while (left < nums.length && nums[left] == target) {
left++;
count++;
}
return count;
}
}
4. 寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解法
直接遍历找到中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
right = nums1[aStart++];
} else {
right = nums2[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
解法
1 = 1 ^ 2 ^ 2;三个数做异或运算会除去相同的数。
class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; ++i) {
result = result ^ i ^ nums[i];
}
return result ^ nums.length;
}
}
等差数列
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int sum = (n + 1) * n / 2;
for (int num : nums) {
sum -= num;
}
return sum;
}
}
二分法
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int mid = i + ((j - i) >> 1);
if (nums[mid] == mid) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return i;
}
}
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
提示：
0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1
解法
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] < n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
448. 找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
解法
- 先遍历一遍数组，标记哪些出现过，如果nums[Math.abs(nums[i]) - 1] > 0，就表示i + 1出现过
- 再遍历一遍，把nums[i - 1] > 0 的加大结果数组里。nums[i - 1] < 0说明i没出现过
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int newIndex = Math.abs(nums[i]) - 1;
if (nums[newIndex] > 0) {
nums[newIndex] *= -1;
}
}
List<Integer> result = new LinkedList<>();
for (int i = 1; i <= nums.length; i++) {
if (nums[i - 1] > 0) {
result.add(i);
}
}
return result;
}
}
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解法1
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
while (index < nums.length) {
nums[index++] = 0;
}
}
}
解法2
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
if (i != index - 1) {
nums[i] = 0;
}
}
}
}
}
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
解法
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int ans = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0) { // sum + num > num
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
}
最大连续1的个数
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。
解法
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, cur = 0;
for (int x : nums) {
cur = x == 0 ? 0 : cur + 1;
max = Math.max(max, cur);
}
return max;
}
}
剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
解法
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
int tmp = matrix[i][j];
if (tmp > target) {
j--;
} else if (tmp < target) {
i++;
} else {
return true;
}
}
return false;
}
}
378. 有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
二分查找法
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int left = matrix[0][0], right = matrix[m - 1][n - 1];
while (left <= right) {
int mid = left + (right - left) / 2;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
count++;
}
}
if (count < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
堆排序
维持一个小顶堆
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
for (int j = 0; j < n; ++j) {
pq.offer(new Tuple(0, j, matrix[0][j]));
}
for (int i = 0; i < k - 1; ++i) {
Tuple t = pq.poll();
if (t.x == m - 1) {
continue;
}
pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
}
return pq.poll().val;
}
class Tuple implements Comparable<Tuple> {
int x, y, val;
public Tuple(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo(Tuple tuple) {
return this.val - tuple.val;
}
}
}
剑指 Offer 29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
解法
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int row = 0, col = 0, m = matrix.length - 1, n = matrix[0].length - 1;
int[] res = new int[(m+1) * (n+1)];
int index = 0;
while (true) {
for (int i = col; i <= n; ++i) {
res[index++] = matrix[row][i];
}
if (++row > m) {
break;
}
for (int i = row; i <= m; ++i) {
res[index++] = matrix[i][n];
}
if (--n < col) {
break;
}
for (int i = n; i >= col; --i) {
res[index++] = matrix[m][i];
}
if (--m < row) {
break;
}
for (int i = m; i >= row; --i) {
res[index++] = matrix[i][col];
}
if (++col > n) {
break;
}
}
return res;
}
}
48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
解法
先转置矩阵，再翻转每一行
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 转置矩阵
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// 翻转每一行
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}
}
重塑矩阵
在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例 1:
输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:
输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：
给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
解法
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int row = nums.length, col = nums[0].length;
if (row * col != r * c) {
return nums;
}
int[][] res = new int[r][c];
int index = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
res[i][j] = nums[index / col][index % col];
index++;
}
}
return res;
}
}
56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
提示：
intervals[i][0] <= intervals[i]
排序
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
if (intervals.length == 0 || intervals == null) {
return res.toArray(new int[0][]);
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int i = 0;
int len = intervals.length;
while (i < len) {
int left = intervals[i][0];
int right = intervals[i][1];
// 找出重复的
while (i < len - 1 && intervals[i + 1][0] <= right) {
i++;
right = Math.max(right, intervals[i][1]);
}
res.add(new int[]{left, right});
i++;
}
return res.toArray(new int[0][]);
}
}
919. 会议室 II
给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。
样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
样例2
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了
排序
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: the minimum number of conference rooms required
*/
public int minMeetingRooms(List<Interval> intervals) {
// 对intervals，按start升序排列
Collections.sort(intervals, (x, y) -> x.start - y.start);
List<Integer> rooms = new ArrayList<Integer>();
boolean flag = false;
for (Interval x : intervals) {
for (int i = 0; i < rooms.size(); i++) {
// 满足这个条件，说明可以共用一个room
if (x.start > rooms.get(i)) {
rooms.set(i, x.end);
flag = true;
break;
}
}
// flag = false,说明只能新开一个room
if (!flag) {
rooms.add(x.end);
}
flag = false;
}
// 最后rooms的大小，即结果
return rooms.size();
}
}
错误的集合
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
给定的数组是无序的。
解法
第一个for循环将nums数组排好序，第二个for循环返回结果。
class Solution {
public int[] findErrorNums(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return new int[]{nums[i], i + 1};
}
}
return null;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
双指针
把数组当成有环链表，此题变成寻找环入口。
详细题解https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
将这个题目给的特殊的数组当作一个链表来看，数组的下标就是指向元素的指针，把数组的元素也看作指针。如 0 是指针，指向 nums[0]，而 nums[0] 也是指针，指向 nums[nums[0]].
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
优美的排列 II
给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
② 如果存在多种答案，你只需实现并返回其中任意一种.
示例 1:
输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
示例 2:
输入: n = 3, k = 2
输出: [1, 3, 2]
解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2
提示:
n 和 k 满足条件 1 <= k < n <= 104.
解法
让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 … k/2 k/2+1.
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
res[0] = 1;
for (int i = 1, interval = k; i <= k; i++, interval--) {
res[i] = i % 2 == 1 ? res[i - 1] + interval : res[i - 1] - interval;
}
for (int i = k + 1; i < n; i++) {
res[i] = i + 1;
}
return res;
}
}
621. 任务调度器
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
提示：
任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。
排序
详解见leetcode
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] map = new int[26];
for (char c : tasks) {
map[c - 'A']++;
}
Arrays.sort(map);
int maxVal = map[25] - 1, slots = maxVal * n;
for (int i = 24; i >= 0 && map[i] > 0; i--) {
slots -= Math.min(map[i], maxVal);
}
return slots > 0 ? slots + tasks.length : tasks.length;
}
}
数组的度
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
注意:
nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。
解法
class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> numsCount = new HashMap<>();
Map<Integer, Integer> numsLastIndex = new HashMap<>();
Map<Integer, Integer> numsFirstIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
numsCount.put(num, numsCount.getOrDefault(num, 0) + 1);
numsLastIndex.put(num, i);
if (!numsFirstIndex.containsKey(num)) {
numsFirstIndex.put(num, i);
}
}
int maxCount = 0;
for (int num : nums) {
maxCount = Math.max(maxCount, numsCount.get(num));
}
int result = nums.length;
for (int num : nums) {
int count = numsCount.get(num);
if (count != maxCount) {
continue;
}
result = Math.min(result, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
}
return result;
}
}
托普利茨矩阵
如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。
给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
示例 1:
输入:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是True。
示例 2:
输入:
matrix = [
[1,2],
[2,2]
]
输出: False
解释:
对角线"[1, 2]"上的元素不同。
说明:
matrix 是一个包含整数的二维数组。
matrix 的行数和列数均在 [1, 20]范围内。
matrix[i][j] 包含的整数在 [0, 99]范围内。
进阶:
如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？
解法
先检查上三角矩阵，然后检查下三角矩阵
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix[0].length; i++) {
if (!check(matrix, matrix[0][i], 0, i)) {
return false;
}
}
for (int i = 1; i < matrix.length; i++) {
if (!check(matrix, matrix[i][0], i, 0)) {
return false;
}
}
return true;
}
private boolean check(int[][] matrix, int expectValue, int row, int col) {
if (row >= matrix.length || col >= matrix[0].length) {
return true;
}
if (matrix[row][col] != expectValue) {
return false;
}
return check(matrix, expectValue, row + 1, col + 1);
}
}
数组嵌套
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示：
N是[1, 20,000]之间的整数。
A中不含有重复的元素。
A中的元素大小在[0, N-1]之间。
解法
class Solution {
public int arrayNesting(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = i; nums[j] != -1; ) {
count++;
int t = nums[j];
nums[j] = -1;
j = t;
}
max = Math.max(count, max);
}
return max;
}
}
最多能完成排序的块
数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:
输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:
输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
注意:
arr 的长度在 [1, 10] 之间。
arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。
解法
class Solution {
public int maxChunksToSorted(int[] arr) {
if (arr == null) {
return 0;
}
int result = 0;
int right = arr[0];
for (int i = 0; i < arr.length; i++) {
right = Math.max(right, arr[i]);
if (right == i) {
result++;
}
}
return result;
}
}
31. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
解法
- 从后往前遍历，找到第一个降序的nums[i]
- 从后往前遍历，找到第一个比nums[i]大的数nums[j]，交换nums[i]和nums[j]
- 最后将，[i + 1, nums.length - 1]中的数交换位置
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int end = nums.length - 1;
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}
欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。
若有收获，就点个赞吧
0 人点赞
