开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

[数据结构与算法]leecode刷算法C++ | 字符串数组12道题最全总结easy题型 | 删除有序数组中的重复项 | 轮转数组 | 两个数组的交集 | 只出现一次的数字

共11道数组、字符串相关题目，大多数为简单。我分为三类，分别为翻转问题、元素重复问题和其它类，使用C++
翻转问题包括轮转数组、翻转字符串、整数翻转这3道题，元素重复题目包括删除有序数组中的重复项、存在重复元素、只出现一次的数字、字符串中的第一个唯一的字符、两个数组的交集这5道题，还有3道其它类

总结：
1.ans.size()是最常用的，几乎每题都用。其它的如reverse、erase、sort用得也很多
2.翻转问题中可以定义前后两个指针分别往中间走，用while(first<last)判断停止条件
3.元素重复题目其一要合理运用unique(+sort+erase)去重，其二可以使用set去重，其三合理使用哈希映射（关于次数的问题一般用到map）

在这里插入图片描述

翻转问题

189.轮转数组

题目

leetcode，题目链接，中等

代码

class Solution {
public:

    void reverse1(vector<int>& nums,int first,int last){//下标
        int j = last;
        int last1 = (first + last) / 2;

        for(int i = first;i <= last1;i++){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j--] = tmp;
        }
    }


    void rotate(vector<int>& nums, int k) {
        int len1 = nums.size();
        k = k % len1;
        
        if(len1 > 1 & k > 0){
            reverse(nums.begin(),nums.end());
            reverse1(nums,0,k - 1);
            reverse1(nums,k,len1 - 1);
        }
    }
};

分析

这道题有点意思，其实前后两段是有顺序的，所以将数组全体翻转一次，前后两部分各翻转一次就OK了

细节

像翻转的代码就可以封装起来成函数

知识

直接用reverse是不行的，好像这类函数包括sort等的参数都是迭代器，用数组下标不大行
所以写了个reverse1

344.反转字符串

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len1 = s.size();
        int first = 0,last = len1 - 1;

        while(first < last){
            swap(s[first],s[last]);
            ++ first;
            -- last;
        }
    }
};

思路

像这种翻转题目，一般定义头尾两个指针同时往中间互换就行了，用while(first<last)比较好，用if的话之前记得好像要考虑偶数个数还是奇数个数的问题，有点麻烦

知识点

交换两个数，除了使用第三个中间变量tmp辅助交换，还可以直接调用swap()函数

7.整数翻转

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    int reverse(int x) {

        int ans = 0;

        while(x != 0){
            if (ans < INT_MIN / 10 || ans > INT_MAX / 10) {
                return 0;
            }
            int num = x % 10;
            x = x / 10;       
            ans = ans * 10 + num;
        }
        
        return ans;
    }
};

思路

这个题也蛮有意思的，我刚开始想着定义数组先把每一位分出来，但是发现直接对它本身取余及除10操作就可以了
还有设置取值范围，并且禁止用long的问题，题解中给了数学推导

元素重复

26. 删除有序数组中的重复项

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j = 1;
        int len1 = nums.size();

        if(len1 < 2) return len1;

        for(i = 1;i <= len1 - 1;i++){
            if(nums[j-1] != nums[i]){
                 nums[j] = nums[i];
                 j++;
            }
        }
        return j;
    }
};

太简单了，不放思路了

217.存在重复元素

题目

在这里插入图片描述
leetcode，题目链接，简单

代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int len2 = nums.size();
        bool flag = false;

        sort(nums.begin(),nums.begin() + len2);

        for(int i = 0;i < len2 - 1;i++){
            if(nums[i] == nums[i + 1]){
                flag = true;
                return flag;
            }
        }

        return flag;
    }
};

知识

begin()和end()返回的是一个迭代器，迭代器类似一个指向vector中元素的指针
sort()排序
定义：

sort(arr,arr+10,cmp);  // 普通数组 
//注意sort是左闭右开区间，就是说这里的10是数组的长度，不是想排序的尾巴数的下标，而是这段数的长度

sort(arr.begin(),arr.begin()+10,myfunction);   // vector动态数组，参数必须是迭代器
bool myfunction (int i,int j) { //可以自定义排序方式
	return (i<j); 
}

136.只出现一次的数字

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int len1 = nums.size(); // 没有length属性
        sort(nums.begin(),nums.begin() + len1);

        for(int i = 0;i < len1 - 1;i += 2){
            if(nums[i] != nums[i + 1]){
                return nums[i];
            }

        }
        return nums[len1 - 1];
    }
};

必然sort啊

387.字符串中的第一个唯一的字符

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    int firstUniqChar(string s) {

        unordered_map<int,int> hash;
        // key为值，value为出现次数 因为key是唯一的
        // value = hash[key] 

        for(char ch:s){ //这种循环方式，直接取数
            ++ hash[ch];
        }
        
        for(int i = 0;i <= s.size();i++){
            if(hash[s[i]] == 1)
                return i;
        }
        return -1;
    }
};

思路

关于次数的问题，都可以用哈希表数据结构
map是有序的，unordere_map是无序的，它的查询更快，但是构建占用内存更多，二者都是key-value的映射关系

349.两个数组的交集

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       vector<int> ans;

        int len1 = nums1.size();
        int len2 = nums2.size();

        sort(nums1.begin(),nums1.begin() + len1);
        sort(nums2.begin(),nums2.begin() + len2);

        nums1.erase(unique(nums1.begin(),nums1.end()),nums1.end());
        nums2.erase(unique(nums2.begin(),nums2.end()),nums2.end());

        len1 = nums1.size();
        len2 = nums2.size();

        for(int i = 0;i <= len1 -1 ;i++){
            for(int j = ans.size();j <= len2 - 1;j++){
                if(nums1[i] == nums2[j]){
                    ans.push_back(nums1[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

知识点

去重：
unique结合sort去重，注意unique前必须排序，而且unique不是删除了重复元素，而是排到后面了，所以需要erase擦除后面的元素
unique、erase的参数同样是迭代器
string中erase使用
pop_back是尾删，erase是指定位置删除

ps：网上参考价值高的C++ STL语法特性的博客真是少啊emm，比我想象得少太多了，还是买书了

其它

66.加一

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int len1 = digits.size();

        for(int i = len1 - 1;i >= 0;i--){
            if(digits[i] != 9){
                digits[i] += 1;
                break;
            }
            digits[i] = 0; 
        }

        if(digits[0] == 0){
            digits.insert(digits.begin(),1);
        }
        
        return digits;
    }
};

知识点

.insert() 向数组中插入元素，但是元素位置也用迭代器表示
数组变量大小：普通的int数组变量 sizeof(a) / sizeof(a[0])，vector数组使用.size()
ps：vecor好像没有.length()，但是字符串好像都有，记不清的情况下还是用.size()吧

283.移动零

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len1 = nums.size();

        int j=0;

        for(int num:nums){
            if(num !=0){
                nums[j++]=num;
            }
            
        }

        for(int i=j;i<=len1-1;i++){
            nums[i]=0;
        }

    }
};

在刷一定题目后，要考虑提高代码效率，增快、减小内存开销

1.两数之和

题目

leetcode，题目链接，简单
在这里插入图片描述

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len1 = nums.size();
        vector<int> ans;

        for(int i=0;i<=len1-1;i++){
            for(int j=i+1;j<=len1-1;j++){
                if(nums[j]+nums[i] == target){
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }
        return ans;
    }
};