美文网首页
数组和字符串

数组和字符串

作者: 小小何先生 | 来源:发表于2021-02-03 10:46 被阅读0次

    @[toc]
      本文主要为LeetCode刷题学习笔记。

    核心要点

    集合

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

      集合里的元素没有顺序

    列表

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

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

    数组

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

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

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

    1. 读取元素
    nums[i] // 读取第数组中的第i个元素。
    
    1. 查找元素
    s1.find(s2,position) //在S1中查找子串S2, position示从从这个位置开始的字符串中找指定元素,默认为0。
    //返回值为目标字符的位置,当没有找到目标字符时返回npos。
    
    1. 插入元素
    s1.insert(2,"123") // 下标为2处插入“123”。
    
    1. 删除元素
    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]
    
    

      解释

    image

      说明:

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

    • 思路解析

      我们可以知道每一条斜线上的坐标之和为一个固定的值,从0m+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 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

    双指针

    移除元素

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

      不要使用额外的数组空间,你必须仅使用 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。
    注意这五个元素可为任意顺序。
    你不需要考虑数组中超出新长度后面的元素。
    
    • 解题思路

      设定两个快慢指针slowfastslow指针从0开始,fast指针随着循环从0n(数组长度)。当遇到非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;
        }
    };
    

    相关文章

      网友评论

          本文标题:数组和字符串

          本文链接:https://www.haomeiwen.com/subject/yoyptltx.html