2022-01-04

字数统计: 3.1k字 | 阅读时长: 14分

数组

需要两点注意的是:

数组下标都是从0开始的。
数组内存空间的地址是连续的。
数组的元素是不能删的，只能覆盖。

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

严格来讲vector是容器，不是数组。

二分查找

二分查找的关键在于边界的控制,数组的开闭区间等

704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right)
    {
        int middle = (left + right)/2;
        if (nums[middle] > target)
        {
            right = middle - 1;
        }
        else if (nums[middle] < target)
        {
            left = middle + 1;
        }
        else
        return middle;
    }
    return -1;
    }
};

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return left;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

69. x 的平方根 - 力扣（LeetCode） (leetcode-cn.com)

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

class Solution {
public:
    int mySqrt(int x) {
        int i = 1;
        while(i <= x/i)
        {
            i = i + 1;
        }
    return i - 1;
    }
};

注意:i 要从1开始，为了防止溢出用while(i <= x/i)

367. 有效的完全平方数 - 力扣（LeetCode） (leetcode-cn.com)

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要使用任何内置的库函数，如 sqrt 。

class Solution {
public:
    bool isPerfectSquare(int num) {
        int i = 1;
        while(i < num/i)
        {
            i = i + 1;
        }
        if (i == num/i && num % i == 0)
            return true;
        else
            return false;
    }
};

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 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;
    }
};

26. 删除有序数组中的重复项 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
    int size = nums.size();
	if (nums.size() < 2) return nums.size();
	int j = 0;
	for (int i = 1; i < nums.size(); i++)
		if (nums[j] != nums[i])
        {
        nums[++j] = nums[i];
        }
        else
        size--;
    return size;
    }
};

283. 移动零 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        int j = 0;
        int pos = nums.size() - 1;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] != 0)
            {
                nums[j++] = nums[i];
            }
        }
        for(int i = j; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }
};

844. 比较含退格的字符串 - 力扣（LeetCode） (leetcode-cn.com)

自己的版本有点bug

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();
        for (int i = 0; i < len1; i++)
        {
            if(s[i] == '#')
            {
                for(int j = i; j < len1; j++)
                {
                    if(i >= 1)
                    {
                    s[j - 1] = s[j + 1];
                    len1 = len1 - 2;
                    }
                    else
                    {
                    s[j] = s[j + 1];
                    len1 = len1 - 1;
                    }
                }
            
            }
        }
        for (int i = 0; i < len2; i++)
        {
            if(t[i] == '#')
            {
                for(int j = i; j < len2; j++)
                {
                    if(i >= 1)
                    {
                    t[j - 1] = t[j + 1];
                    len2 = len2 - 2;
                    }
                    else
                    {
                    t[j] = t[j + 1];
                    len2 = len2 - 1;
                    }
                }
            }
        }
        if (len1 != len2)
        return false;
        else 
        {
            for(int i = 0; i < len1; i++)
            {
                if(s[i]!=t[i])
                return false;
            }
        return true;
        }
    }
};

题解版本

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S[i] == '#') {
                    skipS++, i--;
                } else if (skipS > 0) {
                    skipS--, i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T[j] == '#') {
                    skipT++, j--;
                } else if (skipT > 0) {
                    skipT--, j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S[i] != T[j]) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};

另一种解法:双指针法，看起来更简便

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        changestring(s);
        changestring(t);
        return s==t;
    }
    void changestring(string &s)
    {
        int slow=0;
        for(int fast=0;fast<s.size();fast++)
        {
            if(s[fast]!='#')
            s[slow++]=s[fast];
            else if(slow!=0)
                slow--;
        }
        s.resize(slow);
    }
};

string(s)表示字符串
s.length 表示字符串的长度
resize()，设置大小（size）;
reserve()，设置容量（capacity）;
size()是分配容器的内存大小，而capacity()只是设置容器容量大小，但并没有真正分配内存。
打个比方：正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说明这部车内部空间大小可以放得下40张座椅而已。而车里面安装了40个座椅(resize(40);)，这个时候车里面才真正有了40个座椅，这些座椅就可以使用了

977. 有序数组的平方 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int k = nums.size() - 1;
        vector<int> result(nums.size(), 0); //初始化一个全0的vector
        for(int i = 0,j = nums.size() - 1; i <= j;)
        {
            if(nums[i] * nums[i]<=nums[j] * nums[j])
            {
                result[k--] = nums[j] * nums[j];
                j--;
            }
            else
            {
                result[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return result;
    }
};

双指针的方法。

209. 长度最小的子数组 - 力扣（LeetCode） (leetcode-cn.com)

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

//滑动窗口
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int i = 0; //开始的位置
        int sum = 0;
        int sublength = 0;
        for(int j = 0; j < nums.size(); j++)
        {
            sum += nums[j];
            while(sum >= target)
            {
                sublength = (j - i + 1);
                result = result < sublength ?  result : sublength;
                sum -= nums[i++];
            }
            
        }
        return result == INT32_MAX ? 0 : result;
    }
};

滑动窗口的思想

时间复杂度O(n)，空间复杂度O(1)

904.水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int temp, sub1=0, sub2=0, j=0, result=INT_MIN;
        //temp临时储存的可行解值
        //两个sub是两种水果
        //result 最后的结果
        for ( int i=0; i<fruits.size(); i++ ) //左滑窗 找到可行解
        {
            sub1 = fruits[i]; //记录第一种水果
            for ( int k=i; k<fruits.size(); k++ ) //寻找可以采摘的第二种水果
            {
                if ( fruits[k]!=fruits[i] )//找到
                {
                    sub2 = fruits[k];
                    break;
                }
            }
            while ( fruits[j]==sub1 || fruits[j]==sub2 )//满足采摘的两种水果
            { //在满足可行解前提下扩大又窗口寻找最大的（最优解）
                temp = j - i + 1;//记录当前的长度
                result = temp > result ? temp : result;//寻找最大的解
                j ++; //右边界扩展
                if ( j==fruits.size() ) //右边界到达临界值
                {
                    return result == INT_MIN ? 0 : result;
                    //没有给result赋值就是没有可行解
                }
            } 
        }
        return result; //无关 不会执行到
    }
};

也是滑动窗口的思想。

vector生成二维数组:

1	vector<vector<int> > Matrix(N, vector<int>(M)); //生成N*M维的数组

59.螺旋矩阵Ⅱ

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

注意:边界一定要明确，统一，一圈一圈的循环，中间的值分奇偶特别处理以下。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n,vector<int>(n,0)); //定义一个二维数组
        int startx = 0, starty = 0;
        int loop = n / 2;
        int mid = n / 2;
        int offset = 1;
        int num = 1;
        while(loop--)
        {
            int i = startx;
            int j = starty;
            for(j = starty; j < starty + n - offset; j++)
            {
                matrix[startx][j] = num++;
            }
            for(i = startx; i < startx + n - offset; i++)
            {
                matrix[i][j] = num++;
            }
            for(; j > starty; j--)
            {
                matrix[i][j] = num++;
            }
            for(; i > startx; i--)
            {
                matrix[i][j] = num++;
            }
            startx++;
            starty++;
            offset += 2;
        }
        if(n % 2 != 0)
        matrix[mid][mid] = n * n;
        return matrix;
    }
    
};

54.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector <int> ans;
        if(matrix.empty()) return ans; //若数组为空，直接返回答案
        int u = 0; //赋值上下左右边界
        int d = matrix.size() - 1;
        int l = 0;
        int r = matrix[0].size() - 1;
        while(true)
        {
            for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
            if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
            for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
            if(-- r < l) break; //重新设定有边界
            for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
            if(-- d < u) break; //重新设定下边界
            for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
            if(++ l > r) break; //重新设定左边界
        }
        return ans;
    }
};

注意matrix.size()代表行数，matrix[0].size()代表列数。