文章目录
前言
在学习数据结构的过程中，我通过力扣整理了一些常见的数据结构数组题。这些题目帮助我回顾了学习过程中的关键知识点。
二分查找
力扣题目 704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例1：
输入:
nums = [-1,0,3,5,9,12], target = 9
输出:4
解释:9 出现在 nums 中并且下标为 4
示例2：
输入:
nums = [-1,0,3,5,9,12], target = 2
输出:-1
解释:2 不存在 nums 中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
思路
题目前提是数组为有序数组，题目还强调数组中无重复元素。因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。
二分法第一种写法
target 是在左闭右闭的区间里查找，即[left,right]。
- 循环条件：
- 使用
while (left <= right)。这是因为当left和right相等时，它们指向的数组元素可能是要查找的目标元素。
- 使用
- 中间索引计算：
- 使用
left + ((right - left) / 2)来计算middle，这样可以避免整数溢出。
- 使用
- 元素比较与指针更新：
- 如果
nums[middle] == target，则找到目标元素，直接返回middle。 - 如果
nums[middle] < target，则更新left = middle + 1，继续在右侧搜索。 - 如果
nums[middle] > target，则更新right = middle - 1，继续在左侧搜索。
- 如果
- 返回结果：
- 如果循环结束后仍未找到目标元素，返回 -1 。
- 特殊情况处理：
- 如果数组为空，可以在开始时检查，并直接返回-1。
代码如下：
- 如果数组为空，可以在开始时检查，并直接返回-1。
class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0){
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] > target){
right = mid - 1;
}else if (nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
二分法第二种写法
target 是在左闭右开的区间里查找，即[left,right)。
- 循环条件:
- 使用
while (left < right)。因为区间是左闭右开的，所以当 left 等于 right 时，实际上已经没有元素可以查找了，循环应该终止。
- 使用
- 中间索引计算:
- 中间索引的计算方式与左闭右闭区间相同，使用
left + (right - left) / 2;来防止整数溢出。
- 中间索引的计算方式与左闭右闭区间相同，使用
- 元素比较与指针更新:
- 如果
nums[middle] == target，则找到目标元素，直接返回middle。 - 如果
nums[middle] < target，则更新left = middle + 1，继续在右侧搜索。 - 如果
nums[middle] > target，则更新right = middle。 - 注意：这里是
right = middle而不是right = middle - 1，因为区间是左闭右开的。
- 如果
- 返回结果:
- 如果循环结束后仍未找到目标元素，则返回 -1。
- 特殊情况处理:
- 与左闭右闭区间一样，开始处检查数组是否为空，并直接返回 -1。
代码如下：
- 与左闭右闭区间一样，开始处检查数组是否为空，并直接返回 -1。
class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0){
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if (nums[mid] > target){
right = mid;
}else if (nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例1：
输入：
n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例2：
输入：
n = 1
输出：[[1]]
提示 ：1 <= n <= 20
思路
这一题很考验做题者对代码的掌控能力。我们使用左闭右开原则进行绘图。
如图所示，我们每次遍历一条边，都是以左闭右开来遍历，这样就不容易出错。
如果是奇数圈的话，我们就对其进行判断，手动将其填充即可。
代码如下：
class Solution {
public int[][] generateMatrix(int n) {
// 初始化一个要填充的目标矩阵
int[][] matrix = new int[n][n];
// 定义螺旋开始的行和列,标识我们在哪里开始填充矩阵
int rowStart = 0;
int columnStart = 0;
// 定义螺旋的层级,标识我们正在填充的螺旋层级
int level = 1;
// 定义边界的偏移量,计算在每一层螺旋中，需要填充的行或列的范围
int offset = 1;
// 定义要填充的数字
int number = 1;
// 定义行和列的索引
int row, column;
// 当螺旋层级小于等于 n / 2 时，进行螺旋填充
while(level <= n / 2){
// 从左到右填充上方的行
for(column = columnStart; column < n - offset; column++){
matrix[rowStart][column] = number++;
}
// 从上到下填充右方的列
for(row = rowStart; row < n - offset; row++){
matrix[row][column] = number++;
}
// 从右到左填充下方的行
for(; column > columnStart; column--){
matrix[row][column] = number++;
}
// 从下到上填充左方的列
for(; row > rowStart; row--){
matrix[row][column] = number++;
}
// 更新螺旋开始的行和列，螺旋层级和边界偏移量
rowStart++;
columnStart++;
level++;
offset++;
}
// 如果 n 是奇数，填充中心的元素
if(n % 2 != 0){
matrix[rowStart][columnStart] = number;
}
return matrix;
}
}
为什么循环是 n/2 次：
主要是理解螺旋填充的过程。在一个n x n的矩阵中，螺旋填充的过程可以看作是一层一层向内进行的。每一层都是一个环形，从外层开始，逐渐向内层进行。
因为对于一个n x n的矩阵，最多有n / 2层环形（如果n是奇数，中心的单个元素也被视为一层）。
例如，当n = 3时，矩阵如下：
1 2 3
8 9 4
7 6 5
这个矩阵有两层环形，外层环形包含元素1, 2, 3, 4, 5, 6, 7, 8，内层环形（一个点）包含元素9。
所以，当螺旋层级小于等于n / 2时，我们就继续进行螺旋填充，直到所有的环形层级都被填充完毕。
结尾
如果您觉得今天的文章对您有帮助，我相信您一定会喜欢我的博客。
哈利の小屋
在那里，我会定期更新关于计算机类的文章，并与您分享更多实用的经验和知识。欢迎您来访问和留言交流。