当前位置：网站首页>数组解法秘籍
数组解法秘籍
2022-07-28 05:26:00 【HandsomeDog_L】
目录
双指针
删除有序数组重复元素
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}删除数组中的指定元素
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}两数之和（力扣167）
int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}反转数组
void reverseString(char[] s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length - 1;
while (left < right) {
// 交换 s[left] 和 s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}最长回文子串
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length()
&& s.charAt(l) == s.charAt(r)) {
// 双指针，向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}长度最小的子数组
class Solution {
// 滑动窗口
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
二分法
[left,right]
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}
[left,right)
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}
前缀和----多次对某个区间计算和
区域和检索（力扣303）
class NumArray {
// 前缀和数组
private int[] preSum;
/* 输入一个数组，构造前缀和 */
public NumArray(int[] nums) {
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}二维区域和检索
class NumMatrix {
// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
if (m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
}
}差分数组----多次对某个区间进行加减
// 差分数组工具类
class Difference {
// 差分数组
private int[] diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}区间加法（力扣370）
int[] getModifiedArray(int length, int[][] updates) {
// nums 初始化为全 0
int[] nums = new int[length];
// 构造差分解法
Difference df = new Difference(nums);
for (int[] update : updates) {
int i = update[0];
int j = update[1];
int val = update[2];
df.increment(i, j, val);
}
return df.result();
}航班预定统计（力扣1109）
int[] corpFlightBookings(int[][] bookings, int n) {
// nums 初始化为全 0
int[] nums = new int[n];
// 构造差分解法
Difference df = new Difference(nums);
for (int[] booking : bookings) {
// 注意转成数组索引要减一哦
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
// 对区间 nums[i..j] 增加 val
df.increment(i, j, val);
}
// 返回最终的结果数组
return df.result();
}
拼车（力扣1094）
boolean carPooling(int[][] trips, int capacity) {
// 最多有 1001 个车站
int[] nums = new int[1001];
// 构造差分解法
Difference df = new Difference(nums);
for (int[] trip : trips) {
// 乘客数量
int val = trip[0];
// 第 trip[1] 站乘客上车
int i = trip[1];
// 第 trip[2] 站乘客已经下车，
// 即乘客在车上的区间是 [trip[1], trip[2] - 1]
int j = trip[2] - 1;
// 进行区间操作
df.increment(i, j, val);
}
int[] res = df.result();
// 客车自始至终都不应该超载
for (int i = 0; i < res.length; i++) {
if (capacity < res[i]) {
return false;
}
}
return true;
}花式遍历
旋转图像（力扣48）
// 将二维矩阵原地顺时针旋转 90 度
public void rotate(int[][] matrix) {
int n = matrix.length;
// 先沿对角线镜像对称二维矩阵
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// swap(matrix[i][j], matrix[j][i]);
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
}
// 反转一维数组
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (j > i) {
// swap(arr[i], arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
螺旋矩阵（力扣54）
List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new LinkedList<>();
// res.size() == m * n 则遍历完整个数组
while (res.size() < m * n) {
if (upper_bound <= lower_bound) {
// 在顶部从左向右遍历
for (int j = left_bound; j <= right_bound; j++) {
res.add(matrix[upper_bound][j]);
}
// 上边界下移
upper_bound++;
}
if (left_bound <= right_bound) {
// 在右侧从上向下遍历
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
// 右边界左移
right_bound--;
}
if (upper_bound <= lower_bound) {
// 在底部从右向左遍历
for (int j = right_bound; j >= left_bound; j--) {
res.add(matrix[lower_bound][j]);
}
// 下边界上移
lower_bound--;
}
if (left_bound <= right_bound) {
// 在左侧从下向上遍历
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
// 左边界右移
left_bound++;
}
}
return res;
}
螺旋矩阵||（59）
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
class Solution {
public int[][] generateMatrix(int n) {
int loop = 0; // 控制循环次数
int[][] res = new int[n][n];
int start = 0; // 每次循环的开始点(start, start)
int count = 1; // 定义填充数字
int i, j;
while (loop++ < n / 2) { // 判断边界后，loop从1开始
// 模拟上侧从左到右
for (j = start; j < n - loop; j++) {
res[start][j] = count++;
}
// 模拟右侧从上到下
for (i = start; i < n - loop; i++) {
res[i][j] = count++;
}
// 模拟下侧从右到左
for (; j >= loop; j--) {
res[i][j] = count++;
}
// 模拟左侧从下到上
for (; i >= loop; i--) {
res[i][j] = count++;
}
start++;
}
if (n % 2 == 1) {
res[start][start] = count;
}
return res;
}
}
边栏推荐
猜你喜欢
JSON笔记
自定义组件--数据监听器
QT implementation outputs relevant information to log file
小程序navigator无法跳转（debug）
Cronbach’s α？ Kmo coefficient? Factor load? The most understandable course of questionnaire reliability and validity analysis in history!!! (SPSS and AMOS)
小程序创建组件
气传导蓝牙耳机什么牌子好、气传导耳机最好的品牌推荐
小程序：wsx脚本
Hugging face's problem record I
QT painting event - set background picture
随机推荐
Get the current directory in QT
VI and VIM commands
Filter
气传导蓝牙耳机怎么样、最值得入手的气传导耳机
Antenna effect solution
Combine multiple ICs calendars into a single ICs calendar
自定义组件--父子组件之间的通信
Hugging face 的入门使用
Hugging face 的问题记录 I
MFC uses the console to print program information
Vscode中，无法打开源文件 “Adafruit_GFX.h“
2022-07-19 达梦数据库 连接实例、执行脚本、系统命令
QT batch operation control and set signal slot
MySQL delete tables without deleting databases
error: redefinition of ‘xxx‘
开放式耳机推荐哪款最好、性价比最高的开放式耳机
【学习笔记】vim 编辑器
【学习笔记】驱动
2022-05-15 基于jwt令牌token
藏宝计划TPC系统开发Dapp搭建