因为本人去年在考研没有进行过面试,所以以下问题是基于ChatGPT4生成的,仅供参考。
+
)运算符或 extend()
方法合并两个列表。例如,list3 = list1 + list2
或者 list1.extend(list2)
。[[1, 2, 3], [4, 5, 6]]
是一个二维数组。[x*2 for x in range(10)]
。sort()
方法(就地排序)或 sorted()
函数(返回新的排序列表)进行排序。例如,list.sort()
或 sorted(list)
。new
和 delete
操作符来动态分配和释放数组。例如,int* myArray = new int[10];
动态分配了一个大小为10的整数数组,之后使用 delete[] myArray;
释放内存。int multiArray[3][4]
定义了一个3x4的二维数组。每个维度的数组都是连续存储的。std::array
是C++标准库的一部分,它提供了固定大小的数组,带有容器类的附加功能,如迭代器、排序和查找方法。与普通数组相比,std::array
更安全,因为它可以防止数组越界,并且提供了更多的方法和属性。题目链接:https://leetcode.cn/problems/binary-search/description/
给定一个
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]
之间。
如果不看题目提示(二分查找)的话,下面这种方法应该是最好想到的:
class Solution:
def search(self, nums, target):
if target in nums:
return nums.index(target)
return -1
但是如果放到面试中,面试官肯定不是想看见这种解法的,下面我们将应用二分查找方法来解决这道题。(这道题虽然比较简单但是在408考试中也会用到相同的思路的,请务必掌握!)
需要注意的是,在使用二分查找的时候需要注意题目的条件,必须是要是有序数组,且数组中无重复元素,如果是408算法题的话,一般会给乱序数组,因此我们还需要运用像是快排一样的排序算法先把数组有序排列之后才能继续运用二分查找方法。
在开始写二分查找之前我们先了解一下二分查找(又称折半查找)的实现过程:
(1) 初始化:
low
(最低索引),high
(最高索引)和 mid
(中间索引)。初始时,low
设置为数组的起始位置(通常为 0),high
设置为数组的最后一个元素的索引。(2) 循环查找:
mid
,这通常通过 (low + high) / 2
或 left + ((right - left) / 2)
(对于避免溢出)来完成。array[mid]
等于目标值,搜索成功,返回 mid
。array[mid]
小于目标值,则目标值必在数组的上半段,因此将 low
设置为 mid + 1
。array[mid]
大于目标值,则目标值必在数组的下半段,因此将 high
设置为 mid - 1
。(3) 结束条件:
low
超过 high
,即 low > high
。这意味着目标值不在数组中,此时应返回一个指示未找到的值(如 -1)。(4) 注意事项:
mid
时。二分查找的时间复杂度是 O(log n),其中 n 是数组的元素数量,这使得二分查找比简单的线性搜索(时间复杂度为 O(n))要高效得多,特别是在处理大数据集时。
在首次学习二分查找时,很容易出现问题的地方就是在上面的第二步,对区间的定义比较混乱,我们需要保证的是在每次while循环中每一次边界的处理需要保存一致,因此区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right),两者都可以,下面我们就这两种定义分别写出对应的代码。
(1)左闭右闭
class Solution:
def search(self, nums, target):
left, right = 0, len(nums) - 1 # 左闭右闭
while left <= right:
mid = left + (right - left) // 2 # 防止溢出
if nums[mid] == target: # 找到目标,返回下标
return mid
elif nums[mid] < target: # 目标在右半部分,所以[m+1, r]
left = mid + 1
else: # 目标在左半部分,所以[l, m-1]
right = mid - 1
return -1
(2)左闭右开
class Solution:
def search(self, nums, target):
left, right = 0, len(nums) # 左闭右开
while left < right:
mid = left + (right - left) // 2 # 防止溢出
if nums[mid] == target: # 找到目标,返回下标
return mid
elif nums[mid] < target: # 目标在右半部分,所以[m+1, r]
left = mid + 1
else: # 目标在左半部分,所以[l, m-1]
right = mid
return -1
(1)左闭右闭
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; // 左闭右闭
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) { // 找到目标,返回下标
return mid;
} else if (nums[mid] < target) { // 目标在右侧,所以[m+1, r]
left = mid + 1;
} else { // 目标在左半部分,所以[l, m-1]
right = mid - 1;
}
}
return -1;
}
};
(2)左闭右开
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size(); // 左闭右开
while (left < right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) { // 找到目标,返回下标
return mid;
} else if (nums[mid] < target) { // 目标在右侧,所以[m+1, r]
left = mid + 1;
} else { // 目标在左半部分,所以[l, m-1]
right = mid;
}
}
return -1;
}
};
在类似力扣或者408考试(有些公司面试也不用写输入输出,只需要写出核心代码即可,类似与力扣核心代码模式)我们不用考虑写输入输出代码,但是在考研复试机试、蓝桥杯以及大部分面试中我们都需要自己写数据进行测试代码,一般我们在训练算法时都很少写输入和输出代码,所以这方面非常的薄弱,我们需要额外的注意,因此我打算在每次博客中将写出两种模式的代码。
(1)Python版本(以左闭右闭为例)
def search(nums, target):
left, right = 0, len(nums) - 1 # 左闭右闭
while left <= right:
mid = left + (right - left) // 2 # 防止溢出
if nums[mid] == target: # 找到目标,返回下标
return mid
elif nums[mid] < target: # 目标在右半部分,所以[m+1, r]
left = mid + 1
else: # 目标在左半部分,所以[l, m-1]
right = mid - 1
return -1
if __name__ == "__main__":
n, target = map(int, input().split()) # n是数组长度,target是要查找的数
nums = list(map(int, input().split())) # nums是数组
result = search(nums, target)
print(result)
6 9
-1 0 3 5 9 12
4
(2)C++版本(以左闭右闭为例)
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; // 左闭右闭
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) { // 找到目标,返回下标
return mid;
} else if (nums[mid] < target) { // 目标在右侧,所以[m+1, r]
left = mid + 1;
} else { // 目标在左半部分,所以[l, m-1]
right = mid - 1;
}
}
return -1;
}
int main() {
int n, target; // n为数组长度,target为目标值
cin >> n >> target;
vector<int> nums(n); // nums为数组
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << search(nums, target) << endl;
return 0;
}
6 9
-1 0 3 5 9 12
4
题目链接:https://leetcode.cn/problems/remove-element/description/
给你一个数组
nums
和一个值val
,你需要 原地 移除所有数值等于val
的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用
O(1)
额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以**「引用」**方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1:
输入:nums = [3,2,2,3], val = 3 输出:2, nums = [2,2] 解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2 输出:5, nums = [0,1,3,0,4] 解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
这道题如果出现在408算法题上,那么在紧张的时间内能快速想到的就是暴力枚举,可以使用for循环也可以使用while循环实现,下面我们来一起写一下用while循环实现的代码(以Python为例):
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
while i < len(nums):
if nums[i] == val:
# 如果找到目标值,移除它
nums.pop(i)
else:
# 否则移动到下一个元素
i += 1
return len(nums)
这种暴力解法的时间复杂度是 O( n 2 n^2 n2),其中 n 是数组的长度,这是因为每次移除元素时,都需要移动后续所有元素来填补空位,不适用于大型数组。
双指针法是一种常用的数组和字符串处理技术,特别适用于需要同时考虑两个不同位置元素的场景,这种方法主要依赖于两个独立的指针(通常是数组索引),通过它们的相对运动来完成特定任务,如搜索、比较、复制等。下面是双指针法的一般实现过程:
(1) 初始化指针:
left
和 right
,这两个指针可以指向数组的起始位置、结束位置,或任何其他适当的位置。(2) 移动指针:
(3) 检查终止条件:
(4) 处理元素:
(5) 返回结果:
双指针法的优势在于它能提供更简洁、效率更高的解决方案,特别是对于那些需要一次性考虑两个不同位置元素的问题,使用这种方法时,关键在于正确地初始化指针、合理地移动指针,并设置适当的终止条件,双指针法的时间复杂度为O(n),空间复杂度为O(1)。
我记得在408数据结构算法题中出现过使用双指针法解决的题目,是2009年真题,双指针法是该题的最优解,也是本题的精髓,双指针法务必掌握,以下是2009年408真题数据结构算法题:
后续我们学习链表的双指针法时可以来解决这道题。
回到本题中,下面我们将来实现本题的双指针解法,我们使用两个指针,一个用于遍历数组(i
),另一个用于指示新数组的末尾(newLength
)。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
newLength = 0
for i in range(len(nums)):
if nums[i] != val:
# 如果当前元素不等于val,将其移动到新数组的末尾
nums[newLength] = nums[i]
newLength += 1
return newLength
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int newLength = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
// 如果当前元素不等于val,将其移动到新数组的末尾
nums[newLength] = nums[i];
newLength++;
}
}
return newLength;
}
};
我们遍历数组并检查每个元素,如果当前元素不等于给定的 val
,我们就将它移动到新数组的末尾。这里的“新数组”实际上是原数组的前段,由 newLength
指示其末尾,这种方法避免了不必要的元素移除操作,从而提高了效率。
后面贴出代码随想录上的代码,卡哥的代码有两种写法,主要是考虑到了算法的稳定性问题,是否改变了元素的相对位置。
// 时间复杂度:O(n)
// 空间复杂度:O(1)
// 该方法并没有改变元素的相对位置
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
/**
* 相向双指针方法,基于元素顺序可以改变的题目描述改变了元素相对位置,确保了移动最少元素
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size() - 1;
while (leftIndex <= rightIndex) {
// 找左边等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
// 找右边不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
-- rightIndex;
}
// 将右边不等于val的元素覆盖左边等于val的元素
if (leftIndex < rightIndex) {
nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素
}
};
(1)Python版本
class Solution:
def removeElement(self, nums, val):
newLength = 0
for i in range(len(nums)):
if nums[i] != val:
nums[newLength] = nums[i]
newLength += 1
return newLength
if __name__ == "__main__":
nums = list(map(int, input().split()))
val = int(input())
solution = Solution()
new_length = solution.removeElement(nums, val)
print(new_length)
print(nums[:new_length])
3 2 2 3
3
2
[2, 2]
(2)C++版本
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int newLength = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
nums[newLength] = nums[i];
newLength++;
}
}
return newLength;
}
};
int main() {
vector<int> nums;
int val, element, n; // val为目标值,element为数组元素,n为数组长度
cin >> n;
for (int i = 0; i < n; i++) { // 输入数组元素
cin >> element;
nums.push_back(element); // 将元素添加到数组末尾
}
cin >> val; // 输入目标值
Solution solution;
int new_length = solution.removeElement(nums, val); // 移除目标值
cout << new_length << endl; // 输出新数组长度
for (int i = 0; i < new_length; i++) { // 输出新数组
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
4
3 2 2 3
3
2
2 2
今天是代码随想录算法训练营的第一天,我学到了二分查找的分而治之思想,双指针法的空间和时间效率,并且也掌握了处理边界条件和异常情况,如空数组、单元素数组等,希望后续的59天也能够像今天一样努力,稳扎稳打,去年备战蓝桥杯的时候就刷过代码随想录,但是当时刷的比较马虎,掌握的不是很牢固,经过了一年的考研洗礼,备考的这一年真的学会了很多,也明白了很多道理,有些事情不去经历过就永远无法知晓其道理,未来的路还很长,我们都是被困在当下的时候最痛苦,所以不要纠结,大步往前走,毕竟人世间还有很多有趣的事有趣的人等待你去遇见,向未来张望的时光,或许孤独而漫长,希望努力过后都是晴朗,尽管走,走到灯火通明,走到春暖花开,走到苦尽甘来,不要悲观,不要失望,更好的自己需要磨难,允许你的情绪不开心,但积极向上是生活的主流,好好调节情绪,好好生活,记得开心,希望你永远没有烦恼。
这段话送给你们,希望目前和我一样处于迷茫状态的朋友,能够找到自己的方向。(好端端的技术博客最后写成了鸡汤哈哈哈哈,加油2024年!)