目录
题目
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3: 输入: nums = [1,3,5,6], target = 7 输出: 4
思路
首先, 此题为有序数组,无重复,容易想到用二分查找来实现,但是与普通的二分查找所不同的是,此题可能存在不存在的情况,要我们返回它将会被按顺序插入的位置。但是本质上还是二分查找,稍加改变,即可得到相应的解法。 首先明确可能遇到的几种情况:
之后再对这些情况一一分析即可
python 代码
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1 # 确定区间为闭区间
while left <= right: # 之所以是小于等于,是因为我们选择的区间是闭区间,如果是开区间,则不需要等号
middle = (right + left) >> 1
# 将中间值设置好,这个地方选择用位运算,不过对于python来说速度提升不大,还有一点,就是要防止溢出所以会选择 middle = left + ((right - left) >> 1)这种写法
if nums[middle] < target: # target 在右区间,所以在[middle + 1, right]这个区间
left = middle + 1
elif nums[middle] > target: # target 在左区间,所以在[left, middle - 1]这个区间
right = middle - 1
else:
return middle
return right + 1 # 经过模拟计算,发现需要返回right + 1
c代码
int searchInsert(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right + 1;
}
不得不说,C语言是真的快
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2: 输入:target = 4, nums = [1,4,4] 输出:1 示例 3: 输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0
思路 1
一开始比较容易想到用暴力破解,用两个循环,一遍一遍去寻找,但时间复杂度为n^2,耗时较长。
C代码
int minSubArrayLen(int s, int* nums, int numsSize) {
if (numsSize == 0) {
return 0; // 判断数组是否存在
}
int ans = numsSize+1; // 将ans设置成numsSize+1就足够了,有些人设置为无穷大,也可以
for (int i = 0; i < numsSize; i++) { // 第一层循环
int sum = 0;
for (int j = i; j < numsSize; j++) { // 第二层循环
sum += nums[j];
if (sum >= s) {
ans = fmin(ans, j - i + 1); // 判断新的子列是否短于之前的子列
break;
}
}
}
return ans == numsSize+1 ? 0 : ans; // 最终输出判断
}
Python代码,与c语言思路相同,不再描述。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1
for i in range(n):
total = 0
for j in range(i, n):
total += nums[j]
if total >= target:
ans = min(ans, j - i + 1)
break
return 0 if ans == n + 1 else ans
思路2
在看了其他人的题解的之后,看到了一种新的解题思路——滑动窗口,不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
C代码
int minSubArrayLen(int s, int* nums, int numsSize) {
int result = numsSize + 1;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < numsSize; j++) {
sum += nums[j];
// 这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
}
}
// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
return result == numsSize + 1 ? 0 : result;
}
Python代码,与c语言思路相同,不再描述。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
res = len(nums) + 1
Sum = 0
index = 0
for i in range(len(nums)):
Sum += nums[i]
while Sum >= target:
res = min(res, i-index+1)
Sum -= nums[index]
index += 1
return 0 if res==len(nums) + 1 else res
窗口滑动,与双指针有类似的地方,可以结合双指针一起学习
题目
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路1
一开始的思路还是暴力破解,找到目标元素后,就用后面的元素去覆盖掉这个数,两层循环,时间复杂度较高,但是运行速度好像还可以。
C代码
int removeElement(int* nums, int numsSize, int val){
for (int i = 0; i < numsSize; i++) {
if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
for (int j = i + 1; j < numsSize; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下表i以后的数值都向前移动了一位,所以i也向前移动一位
numsSize--; // 此时数组的大小-1
}
}
return numsSize;
}
思路2
还有一个想法,就是遍历一下数组,如果不相同,就放入原来数组,如果相同,就不放入,再接着判断。后来发现,这就是双指针解法,大概就是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
C代码
int removeElement(int* nums, int numsSize, int val){
int i,j=0;
for(i=0;i<numsSize;i++)
{
if(nums[i]!=val) nums[j++]=nums[i];
}
return j;
}
思路3
后来了解了双指针的方法之后,还知道双指针还可以再优化一下,防止最坏情况出现,大概就是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
C代码
int removeElement(int* nums, int numsSize, int val){
int left = 0, right = numsSize;
while (left < right) { // 循环判断条件,左闭右开
if (nums[left] == val) { // 如果左指针等于目标值
nums[left] = nums[right - 1]; // 把左指针和右指针的值调换
right--; // 右指针左移
} else {
left++; // 否则左指针右移
}
}
return left; // 返回左指针的值
}
Python代码
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
right = len(nums)
while right > left:
if (nums[left] == val):
nums[left] = nums[right-1]
right -= 1
else:
left += 1
return left
思路4
这个不能叫思路,就是Python自带删除元素的方法,直接删就完了
Python代码
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
while True:
try:
nums.remove(val) # 直接删,最暴力的解法
except:
break
return len(nums)
题目
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1:
输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]] 示例 2: 输入:n = 1 输出:[[1]]
思路1
一开始想的就是模拟旋转的过程,但是对于边界的判断不清楚导致没有注意到细节,以及对于C语言的指针掌握程度不够深,导致代码整体的效果不是很好,在看了其他人的题解之后,也算是写完了。
C代码
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
// 初始化返回数组大小
*returnSize = n;
*returnColumnSizes =(int*)malloc(sizeof(int) * n); // 动态内存分配
// 初始化返回数组(二维数组)
int** ans = (int**)malloc(sizeof(int*) * n);
int i;
for(i = 0; i < n; i++){
ans[i] = (int*)malloc(sizeof(int ) * n);
(*returnColumnSizes)[i] = n;
}
// 设置起始位置
int startX = 0;
int startY = 0;
// 设置中间值
int mid = n / 2;
// 设置圈数
int loop = n / 2;
// 每一次添加与 n 相差的数,比如3的时候,就是差1,每次加一,下一个圈,自然要加2
int offset = 1;
// 数值
int count = 1;
while(loop){
int i = startX;
int j = startY;
// 上侧从左到右添加
for (; j < startY + n - offset; j++){
ans[startX][j] = count++;
}
// 右侧从上到下添加
for (; i < startX + n - offset; i++){
ans[i][j] = count++;
}
// 下侧从右到左添加
for (; j > startY; j--){
ans[i][j] = count++;
}
// 左侧从下到上添加
for (; i > startX; i--){
ans[i][j] = count++;
}
// 差值加2
offset += 2;
// 重新设定起始位置
startX++;
startY++;
// 圈数减一
loop--;
}
// 如果是奇数,单独添加中心值
if(n % 2){
ans[mid][mid] = count;
}
return ans;
思路2
在看题解的时候,还发现了一种思路,感觉也是特别清晰,就是不断缩小边界,减小了判断边界的困难度,在此给出Python的代码,思路和前面有相似之处。
Python代码
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
l, r, t, b = 0, n - 1, 0, n - 1 # 设置边界
mat = [[0 for _ in range(n)] for _ in range(n)] # 设置返回数组
num, tar = 1, n * n # 初始化
while num <= tar: # 判断条件
for i in range(l, r + 1): # 上面从左往右添加元素
mat[t][i] = num
num += 1
t += 1 # 上边界下移
for i in range(t, b + 1): # 右边从上往下添加
mat[i][r] = num
num += 1
r -= 1 # 右边界左移
for i in range(r, l - 1, -1): # 下边从右往左
mat[b][i] = num
num += 1
b -= 1 # 下边界上移
for i in range(b, t - 1, -1): # 左边从下往上
mat[i][l] = num
num += 1
l += 1 # 左边界右移
return mat