共11道数组、字符串相关题目，大多数为简单。 我分为三类，分别为翻转问题、元素重复问题和其它类，使用C++
翻转问题包括轮转数组、翻转字符串、整数翻转这3道题，元素重复题目包括删除有序数组中的重复项、存在重复元素、只出现一次的数字、字符串中的第一个唯一的字符、两个数组的交集、有效的字母异同位这6道题，还有5道其它类总结：
1.ans.size()是最常用的，几乎每题都用。其它的如reverse、erase、sort用得也很多
2.翻转问题中可以定义前后两个指针分别往中间走，用while(first<last)判断停止条件
3.元素重复题目其一要合理运用unique(+sort+erase)去重，其二可以使用set去重，其三合理使用哈希映射（关于次数的问题一般用到map）
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
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()函数
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<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;
}
};
太简单了，不放思路了
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(arr,arr+10,cmp); // 普通数组
//注意sort是左闭右开区间，就是说这里的10是数组的长度，不是想排序的尾巴数的下标，而是这段数的长度
sort(arr.begin(),arr.begin()+10,myfunction); // vector动态数组，参数必须是迭代器
bool myfunction (int i,int j) { //可以自定义排序方式
return (i<j);
}
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啊
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的映射关系
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、erase的参数同样是迭代器pop_back是尾删，erase是指定位置删除ps：网上参考价值高的C++ STL语法特性的博客真是少啊emm，比我想象得少太多了，还是买书了
leetcode，题目链接，简单
class Solution {
public:
bool isAnagram(string s, string t) {
int len1 = s.size();
int len2 = t.size();
unordered_map<char,int> hash1;
unordered_map<char,int> hash2;
if(len1 != len2) return false;
for(int i=0;i<=len1-1;i++){
hash1[s[i]]++;
hash2[t[i]]++;
}
for(char ch='a';ch<='z';ch++){
if(hash1[ch] != hash2[ch])
return false;
}
return true;
}
};
关于次数的问题map很有用哇
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() 向数组中插入元素，但是元素位置也用迭代器表示sizeof(a) / sizeof(a[0])，vector数组使用.size()vecor好像没有.length()，但是字符串好像都有，记不清的情况下还是用.size()吧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;
}
}
};
在刷一定题目后，要考虑提高代码效率，增快、减小内存开销
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;
}
};
leetcode，题目链接，简单
class Solution {
public:
bool isPalindrome(string s) {
string s1;
for(char ch:s){
if(isalnum(ch)){
s1 += tolower(ch);
}
}
int len = s1.size();
int first = 0;
int last = len-1;
while(first<last){
if(s1[first++] != s1[last--]){
return false;
}
}
return true;
}
};
leetcode，题目链接，中等
class Solution {
public:
int strToInt(string str) {
int len = str.size();
int i = 0;
int flag = 0;//0正1负
long num = 0;
//去除串首的空格，首部是数字/正负号的留下，取其连续数字；判断越界
if(len == 0){
return 0;
}
while(str[i] ==' '){
++i;
}
if(!isdigit(str[i])&&str[i]!='+'&&str[i]!='-'){
return 0;
}
if(str[i] == '-' | str[i] == '+'){
if(str[i] == '-'){
flag = 1;
}
++i;
}
while(i<len && (str[i] <= '9' && str[i] >= '0')){//可以直接用isdigit(str[i])
num = num*10 + (str[i++]-'0');
if(num > INT_MAX){
return (flag==0)?INT_MAX:INT_MIN;
}
}
if(flag == 1){
num = -num;
}
return num;
}
};
其实整体思路还是比较清晰简单的，但是在实现时候遇到一些小的出错的地方，比如字符串长度为0、字符数字转换等问题
整体还是不难的，学一下怎么表示0-9数字，如str[i] <= '9' && str[i] >= '0' 或 isdigit(str[i])，isalnum(s)是不是字母/数字，tolower转换小写等函数
hello，没想到真的有人能看到这里嘿嘿~
如果你想了解我，欢迎查看我的成长笔记，希望能与你共同学习进步~