算法入门打卡Day1
今日收获
- 了解了时间复杂度的意义和简单计算方式
- 二分查找
- 双指针法、快慢指针法
- 右移运算符在除法的应用
学习时长：2h
正文
时间复杂度的计算
我参考的学习视频如下：
【数据结构——时间复杂度计算】
总体思想为，找出循环次数i与执行次数t的关系，再与含n的临界条件联立解出
或者在双层循环中，列出外层循环的变量i值与对应的内层循环执行次数，在外层执行到与n相关的临界条件时对内层执行次数进行求和，通常是等差或者等比数列
二分查找
LeetCode704
给定一个升序的不重复数组查找target的位置。
以下定义的区间为左闭右开[left, right)
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};
快慢指针
LeetCode27
给你一个数组 nums 和一个值 val，你需要移除所有数值等于 val 的元素。然后返回 nums 中与 val 不同的元素的数量。
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;}
快指针负责查找前方的元素，慢指针在后方停留出足够的空间存放从快指针转移来的元素。
若慢指针开始连续停留，则快慢指针间（左闭右开）一定全是特殊元素，后面快指针找到有效元素一个个填充即可。
任何时候快慢指针之间的元素都可以被替换，因为都是特殊元素和已经被转移到慢指针前的有效元素。
双指针
LeetCode977
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int> arr(k + 1);int rightIndex = k;int leftIndex = 0;while (leftIndex <= rightIndex) {if (nums[leftIndex] * nums[leftIndex] < nums[rightIndex] * nums[rightIndex]) {arr[k--] = nums[rightIndex] * nums[rightIndex];rightIndex--;}else {arr[k--] = nums[leftIndex] * nums[leftIndex];leftIndex++;}}return arr;}
由于平方最大的只会出现在两个端点，于是新建一个数组和双指针，从两头往中间将最大的一个个填入新数组末尾即可。
这里我出现过一个语法错误，即误将vector<int> arr(k + 1)写作vector<int> arr[k + 1]，要注意后者中括号中的不是给整型数组初始化的长度，而是一个元素为整型数组的数组的长度，正确的写法是前者。
右移运算符在除法的应用
核心原理是二进制数的右移，在左边空白部分正补0负补1，最右边一位舍弃。
在整型为正时：
n >> 1; 等价于：n / 2;
而且前者的运行速度更快！
在整型为负时：
-7 / 2 = -3; //向0取整
-7 >> 1 = -4; //向下取整