[数据结构与算法]【数据结构】数组和字符串

本文是对leetbook《数组和字符串》学习完成后的总结。

数组简介

寻找数组的中心索引

搜索插入位置

合并区间

二维数组简介

旋转矩阵

零矩阵

对角线遍历

字符串简介

最长公共前缀

最长回文子串

翻转字符串里的单词

字符串匹配算法：KMP

实现 strStr()

双指针技巧

双指针情形一:
指针向中间或两端移动，移动方向始终相对

反转字符串

数组拆分 I

两数之和 II - 输入有序数组

双指针情形二：
指针向同侧移动，形成前后指针或快慢指针

移除元素

最大连续1的个数

长度最小的子数组

小结

杨辉三角

杨辉三角是以图的形式展示了二项式的性质
按照性质往下打印即可
一个注意点是先打印两边(第0列和第i列），再打印中间（j<i）

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例
1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2:
输入: numRows = 1 输出: [[1]] 提示: 1 <= numRows <= 30

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);//一共numRows行
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);//第i行有i+1列
            ret[i][0] = ret[i][i] = 1;//每一行的首尾都是1
            for (int j = 1; j < i; ++j) {//除首尾以外的，每个数等于上面两个数之和
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

杨辉三角Ⅱ

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:0 <= rowIndex <= 33
进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);//要遍历到rowIndex行所以设置成rowIndex+1的大小
        row[0] = 1;//每行第一个数是1
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;//防止数据溢出，要用long long型的
        }
        return row;
    }
};

时间复杂度：O(rowIndex)。
空间复杂度：O(1)。不考虑返回值的空间占用。

反转字符串中的单词Ⅲ

可以再开辟一个数组的空间，也可以原地操作（Java,javascript不适用其string为不可变类型）。
原地操作，向后扫描，遇到空格，调换一个单词的顺序

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1：
输入：s = “Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”
示例 2:
输入： s = “God Ding” 输出：“doG gniD”
提示：
1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少有一个词。 s 中的所有单词都用一个空格隔开。

class Solution {
public:
    string reverseWords(string s) {
        int length = s.length();
        int i=0;
        while(i<length){//向后遍历
            int start = i;//记录单词初始位置
            while(i<length&&s[i]!=' '){//遍历到单词结尾
                i++;
            }
            int left = start,right = i-1;//交换一个单词的首尾
            while(left<right){
                swap(s[left],s[right]);
                left++;
                right--;
            }
            while(i<length && s[i]==' '){//遍历下一个单词，空格位置不动
                i++;
            }
        }
        return s;
    }
};

寻找旋转排序数组中的最小值

二分法
对于数组中最后一个数x，在最小值右侧的元素都小于x,在最小值左侧的值都大于x（旋转到前面的一段比后面的一段大），通过这条性质来收缩查找区间。所以只用比较mid和right的大小

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums =
[0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到
[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n)的算法解决此问题。
示例 1： 输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3次得到输入数组。
示例 2： 输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。
示例 3： 输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示： n == nums.length 1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同 nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        while(left<right){
                int mid = left+(right-left)/2;
                if(nums[mid]>nums[right]){//找最小值
                    left = mid+1;
                }
                else right = mid;
        }
        return nums[left];
    }
};

删除排序数组中的重复项

双指针。快指针表示遍历数组达到的下标位置，慢指针表示下一个不同的元素要填入的位置。将快指针与其前一个位置所指值比较

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104 nums 已按 升序 排列

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int fast=1,slow=1;
        if(!nums.size()||nums.size()==1)
        return nums.size();

        for(int i=1;i<nums.size();i++){
            if(nums[fast-1]!=nums[fast]){
                nums[slow++]=nums[fast];
            }
            fast++;
        }
        return slow;
    }
};

移动零

双指针，快指针遍历到达的下标的位置，慢指针指向需要交换的0的位置，快指针碰到非零数就与慢指针的值进行交换

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int left = 0,right= 0;
        while(right<n){//right向前找非零值
            if(nums[right]){//找到就将其交换，慢指针向后移动一步
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};