『LeetCode』#3刷题日记
前言 📢
本日记为个人的刷题学习日记，内容非原创，仅为自己复习知识时，能够看得懂自己写的CV的代码，快速理解题意。另外，👍力扣官方的题解很好用，三叶姐🍭nb！！！！！
1990. 寻找数组中心索引 ✅
题意
- 给你一个数组
nums，请计算数组的中心下标； - 相当于一个天平，寻找数组中的一个元素为天平轴(不计算)，使得天平左右两端数字和相等
思路
// 计算数组的总和，把中心点当做滑动块，左右两边重量为left、right
// 每次滑动一格， left加上新增的元素， right等于sum - left - 减少的元素
class Solution {
public int pivotIndex(int[] nums) {
int sum = 0;
int len = nums.length;
for(int i=0; i<nums.length; i++) {
sum += nums[i];
}
int left = 0;
int right;
for(int i=0; i<len; i++) {
right = sum - left - nums[i];
if(left == right){
return i;
} else {
left = left + nums[i];
}
}
return -1;
}
}35. 搜索插入位置 ✅
题意
- 给定一个严格递增数组和一个目标值，返回该数组中目标值的下标，如果不含该值，返回顺序插入的位置
思路
// 二分法
// 最后跳出循环的模拟 假设 此时在下标为3 4 的区间 数值分别是9和12 target为10 数值应当插入下标4的位置
// mid = 3; nums[mid] < target (9<10); left = mid + 1; 此时left==right==4
// 再一次循环 nums[mid] > target (12>10) right = mid - 1; 此时right为3 left为4 返回left
class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(target == nums[mid]) {
return mid;
} else if(target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}面试题01.07 旋转矩阵 ✅
题意
- 给你一个N*N大小的矩阵，将其顺时针旋转90°，得到旋转后的数组
思路
- 在使用额外空间的情况下，可以考虑观察旋转后的规律：
- 新矩阵的行 对应原矩阵的列
- 举例说明：新矩阵从左到右的一行为
7,4,1，原矩阵从下往上数第一列为7,4,1 - 按照对应的顺序，给新矩阵赋值即可
class Solution {
public void rotate(int[][] matrix) {
int len = matrix.length;
int[][] matrix_new = new int[n][n];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
matrix_new[j][len - i - 1] = matrix[i][j];
}
}
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
matrix[i][j] = matrix_new[i][j];
}
}
}
}- 在不使用额外空间的情况下，将数组上下翻转，再沿对角线交换对称元素即可
class Solution {
public void rotate(int[][] matrix) {
int len = matrix[0].length;
int temp;
// 先上下翻转
for(int i =0; i<len/2; i++) {
for(int j=0; j<len; j++) {
temp = matrix[i][j];
matrix[i][j] = matrix[len-1-i][j];
matrix[len-1-i][j] = temp;
}
}
// 再沿对角线翻转
for(int i=0; i<len; i++) {
for(int j=0; j<i; j++) {
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
