【LeetCode】算法与数据结构笔记(一) 数组和字符串

  本文主要为LeetCode刷题学习笔记。

核心要点

集合

  集合里的元素类型不一定相同。

  集合里的元素没有顺序。

列表

  是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。

  列表最常见的表现形式有数组和链表，而栈和队列则是两种特殊类型的列表。

数组

  数组与列表的区别在于索引。索引是数组中的一个重要概念，列表中没有索引这个概念。在大多数编程语言中，索引是从0算起的。

  数组中元素在内存中也是连续存储的。

  数组中有基本的四种操作：

1. 读取元素

nums[i] // 读取第数组中的第i个元素。

2. 查找元素

s1.find(s2,position) //在S1中查找子串S2, position示从从这个位置开始的字符串中找指定元素，默认为0。
//返回值为目标字符的位置，当没有找到目标字符时返回npos。

3. 插入元素

s1.insert(2,"123") // 下标为2处插入“123”。

4. 删除元素

s1.erase(1,3) // 删除从1开始，长度为3的子串

  除此之外还有：

s1.append(s2,1,3) // 添加s2下标从1开始，长度为3的字符串到s1。
s1.swap(s2) // 交换s1，s2.
s1.assign(4,"K") // s1赋值为“KKKK"

编程实例

一维数组

合并区间

  给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

• 实现思想

  思想也就很简单，首先按照二维数组里面的一维数组的第一个元素排序，这个时候比较上一个一维数组的末尾元素(比如[1,3]中的3)与下一个一维数组的第一个元素(比如[2,6]中的2)大小，然后判断是否要合并。

• C++实现

class Solution {
public:
    static bool cmp(vector<int> num1, vector<int> num2){
            return num1[0]<num2[0];
        }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<2) return intervals;
        
        sort(intervals.begin(), intervals.end(),cmp);
        int n = intervals.size();
        vector<vector<int>> ans;
        ans.push_back(intervals[0]);
        for(int i=1; i<n; ++i){
            if(ans.back()[1] >= intervals[i][0]){
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            } else {
                ans.push_back(intervals[i]);
            }
        }
        return ans;
    }
};

  这里要注意：

    static bool cmp(vector<int> num1, vector<int> num2){
            return num1[0]<num2[0];

  之所以要加static的原因是：使用了函数指针，而函数指针所指函数须得是静态才行。如果不加的话，报错如下：

fatal error: reference to non-static member function must be called

二维数组

旋转图像

  给定一个 n × n 的二维矩阵表示一个图像。

  将图像顺时针旋转 90 度。

  说明：

  你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

  示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

• 思路

  我们首先需要对其最外层循环，将每个数字旋转90度，然后进入内层循环，所以我们要循环的外层数就是N/2(for(int r=0; r<n/2;++r))；当确定了循环的层数之后，我们需要进入内层循环，内层循环的起始位置s=r，内层循环的终止位置从右边往左边看就是N-1-r。

  接下来就是需要确定各个元素的位置了，刚开始起始位置的元素坐标是(r,i)。因为是按照顺时针旋转90度，所以逆时针旋转的坐标为(end-(i-s), r)，(end, end-(i-s)), (i, end)。

• C++实现

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int r=0; r<n/2;++r){
            int s = r;
            int end = n-1-r;
            for(int i=s; i<end; i++){
                int temp = matrix[r][i];
                matrix[r][i] = matrix[end-(i-s)][r];
                matrix[end-(i-s)][r] = matrix[end][end-(i-s)];
                matrix[end][end-(i-s)] = matrix[i][end];
                matrix[i][end] = temp;

            }
        }
    }
};

对角线遍历

  给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

  示例:

输入:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]

  解释：

  说明:

  给定矩阵中的元素总数不会超过 100000 。

• 思路解析

  我们可以知道每一条斜线上的坐标之和为一个固定的值，从0到m+n。如果我们以这个和作为大循环遍历的话(for(int s=0; s<=m+n;s++))，我们只需要去确定行或者列中的一个，我们就可以通过总和s减去行或者列得到另一个。以行为例，如果我们知道行坐标r的范围，那么s-r就是纵坐标的值。

  那现在的问题就是如何确定行坐标的值。

  当s小于行坐标的总数时，行坐标的最大值为s，否者为m = matrix.size()-1。程序里面表示为int max_r = min(s, m);，(对应第0列边界)。

  当s很大时，大到被最后一列限制的时候，此时行坐标的最小值为s-n，否者为0。程序里面表示为int min_r = max(0, s-n)，(对应第最后一列边界)。

• C++实现

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if (matrix.empty()) return ans;
        
        int m = matrix.size()-1;
        int n = matrix[0].size()-1;

        for(int s=0; s<=m+n;s++){
            int min_r = max(0, s-n);
            int max_r = min(s, m);
            if(s%2==1){
                for(int r=min_r; r<=max_r; ++r){
                    ans.push_back(matrix[r][s-r]);
                }
            } else {
                for(int r=max_r; r>=min_r; --r){
                    ans.push_back(matrix[r][s-r]);
                }
            }
        }
        return ans;
    }
};

字符串简介

最长公共前缀

  编写一个函数来查找字符串数组中的最长公共前缀。

  如果不存在公共前缀，返回空字符串 “”。

  示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

  示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

  说明:

  所有输入只包含小写字母 a-z 。

• 解题思路

  先从字符串数组中取出第一个字符strs[0]，之后从前往后取出子字符，for(int i=0;i<=strs[0].length();++i)，sub_tem = strs[0].substr(0, i);，拿到的子字符与剩余字符一一对比，如果能找到且返回的坐标是0，也就是从头开始就匹配到了，那就说明这个字符满足要求，否者循环就没必要进行下去，已经不满足要求了。

  如果到最后一个都能找到的话，就说明当前这个子字串是最长公共前缀。

• C++实现

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
        int n = strs.size();
        string ans = "";
        if(n==0) return ans;
        if(n==1) return strs[0];
        string sub_tem;
        
        for(int i=0;i<=strs[0].length();++i){
            sub_tem = strs[0].substr(0, i);
            for(int j=1;j< strs.size();++j){
                if(strs[j].find(sub_tem)!=0) break;
                if(j==strs.size()-1) ans.swap(sub_tem);
            }
            
        }
        return ans;
    }
};

翻转字符串里的单词

  给定一个字符串，逐个翻转字符串中的每个单词。

  示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

  示例 2：

输入: "  hello world!  "
输出: "world! hello"

  解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

  示例 3：

输入: "a good   example"
输出: "example good a"

  解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

  说明：

  无空格字符构成一个单词。

  输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

  如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

  进阶：

  请选用$C$C 语言的用户尝试使用 $O(1)$O(1) 额外空间复杂度的原地解法。

双指针

移除元素

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

  不要使用额外的数组空间，你必须仅使用 $O(1)$O(1) 额外空间并 原地 修改输入数组。

  元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

  示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

  示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

• 解题思路

  设定两个快慢指针slow和fast，slow指针从0开始，fast指针随着循环从0到n(数组长度)。当遇到非val值时，fast元素赋值到slow，并且++slow，为下一个赋值做准备。当循环结束，slow的值就是非val值的个数。

• C++实现

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int slow=0;
        for(int fast=0;fast<n;++fast){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                ++slow;
            }
        }
        return slow;
    }
};