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

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

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

• 翻转问题
• • 189.轮转数组
  • • 题目
    • 代码
    • 分析
    • 细节
    • 知识
  • 344.反转字符串
  • • 题目
    • 代码
    • 思路
    • 知识点
  • 7.整数翻转
  • • 题目
    • 代码
    • 思路
• 元素重复
• • 26. 删除有序数组中的重复项
  • • 题目
    • 代码
  • 217.存在重复元素
  • • 题目
    • 代码
    • 知识
  • 136.只出现一次的数字
  • • 题目
    • 代码
  • 387.字符串中的第一个唯一的字符
  • • 题目
    • 代码
    • 思路
  • 349.两个数组的交集
  • • 题目
  • 代码
  • • 知识点
• 其它
• • 66.加一
  • • 题目
    • 代码
    • 知识点
  • 283.移动零
  • • 题目
    • 代码
  • 1.两数之和
  • • 题目
    • 代码

leetcode，题目链接，中等

class Solution {
public:

    void reverse1(vector& 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& 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

leetcode，题目链接，简单

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

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

像这种翻转题目，一般定义头尾两个指针同时往中间互换就行了，用while(first 知识点

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

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的问题，题解中给了数学推导

leetcode，题目链接，简单

class Solution {
public:
    int removeDuplicates(vector& 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;
    }
};

太简单了，不放思路了

leetcode，题目链接，简单

class Solution {
public:
    bool containsDuplicate(vector& 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 
136.只出现一次的数字 
题目 
leetcode，题目链接，简单
 
 
代码 
class Solution {
public:
    int singleNumber(vector& 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 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 intersection(vector& nums1, vector& nums2) {
       vector 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 plusOne(vector& 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& 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 twoSum(vector& nums, int target) {
        int len1 = nums.size();
        vector 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;
    }
};