🚀个人主页：奋斗的小羊

🚀所属专栏：C++

很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

目录

💥1、string💥1.1 字符串相加💥1.2 验证回文字符串💥1.3 反转字符串💥1.4 字符串最后一个单词的长度💥1.5 字符串中的第一个唯一字符💥1.6 反转字符串中的单词

💥2、vector💥2.1 杨辉三角💥2.2 只出现一次的数字 II💥2.3 只出现一次的数字 III

总结

---

💥1、string

💥1.1 字符串相加

Leetcode——字符串相加

有时候我们需要非常大的数据相加时，整型的范围不够，就可以将数据转换为字符串的形式运算，再将结果转回为整型。

整型相加时是从后往前加的，这里的字符串相加我们也从后往前加。不断取出两个字符串的末尾字符，转换为整形后相加，再用<code>+=追加到字符串末尾，其中还要考虑进位的情况。

因为string类支持operator[]，所以我们可以通过下标的方式遍历字符串。

其中两个字符串的第一位相加也可能有进位，所以循环结束后还需要判断进位是否为1。

因为我们是从后往前加的，所以最后还需要用reverse将字符串翻转过来。

class Solution { -- -->

public:

string addStrings(string num1, string num2) {

string s;

int n = 0;

int end1 = num1.size() - 1;

int end2 = num2.size() - 1;

while (end1>=0 || end2>=0)

{

int n1 = end1>=0 ? num1[end1--] - '0' : 0;

int n2 = end2>=0 ? num2[end2--] - '0' : 0;

int ret = n1 + n2 + n;

n = ret / 10;

ret %= 10;

s += ret + '0';

}

if (n == 1)

{

s += '1';

}

reverse(s.begin(), s.end());

return s;

}

};

用下标的方式从后往前遍历字符串，相加得到的值追加到字符串，最后再反转字符串。

---

💥1.2 验证回文字符串

Leetcode——验证回文串

将字符串存到一个<code>stack和一个queue中，循环比较top()，当栈和队列为空时则字符串回文，当某次top()不相等时则不回文。

用范围for遍历字符串，如果是符合我们要求的字符就插入栈和队列中。

class Solution { -- -->

public:

bool isPalindrome(string s) {

for (auto e : s)

{

if (e >= 'a' && e <= 'z')

{

_st.push(e);

_qu.push(e);

}

if (e >= 'A' && e <= 'Z')

{

e += 32;

_st.push(e);

_qu.push(e);

}

if (e >= '0' && e <= '9')

{

_st.push(e);

_qu.push(e);

}

}

while (!_st.empty())

{

if (_st.top() != _qu.front())

{

return false;

}

_st.pop();

_qu.pop();

}

return true;

}

private:

stack<int> _st;

queue<int> _qu;

};

---

💥1.3 反转字符串

Leetcode——反转字符串

只需要反转对应的区间就行，注意不能越界。

<code>class Solution { -- -->

public:

string reverseStr(string s, int k) {

for (size_t i = 0; i < s.size(); i += 2*k)

{

size_t n = i + k > s.size() ? s.size() : i + k;

reverse(s.begin() + i, s.begin() + n);

}

return s;

}

};

---

💥1.4 字符串最后一个单词的长度

牛客——最后一个单词的长度

<code>#include <iostream>

using namespace std;

int main() { -- -->

string s;

getline(cin, s);

size_t pos = s.rfind(" ");

size_t length = s.size() - pos - 1;

cout << length << endl;

}

---

💥1.5 字符串中的第一个唯一字符

Leetcode——字符串中的第一个唯一字符

这种类似计数的题可以用哈希映射的方法，首先定义一个用于计数的数组，然后将字符串映射到数组中，再通过遍历字符串得到下标间接遍历数组来找出为1的元素，返回下标。

定义数组时需要初始化为全0。

<code>class Solution { -- -->

public:

int firstUniqChar(string s) {

int arr[26] = { 0};

for (auto e : s)

{

arr[e - 'a']++;

}

for (size_t i = 0; i < s.size(); i++)

{

if (1 == arr[s[i] - 'a'])

{

return i;

}

}

return -1;

}

};

---

💥1.6 反转字符串中的单词

Leetcode——反转字符串中的单词

<code>reverse(s.begin(), s.end());

参数：双向迭代器，指向要反转的序列的初始和最终位置。使用的范围是[ )左闭右开。

从前往后遍历字符串，找" "空格的位置，用reverse反转单词。需要注意的是reverse的参数是左闭右开的。

class Solution { -- -->

public:

string reverseWords(string s) {

int pos1 = 0;

int pos2 = s.find(" ", pos1);

while (pos2 < s.size())

{

reverse(s.begin() + pos1, s.begin() + pos2);

pos1 = pos2 + 1;

pos2 = s.find(" ", pos1);

}

reverse(s.begin() + pos1, s.end());

return s;

}

};

---

💥2、vector

💥2.1 杨辉三角

Leetcode——杨辉三角

类似一个二维数组，用<code>vector<vector<int>>会很方便。

class Solution { -- -->

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> vv(numRows);

for (int i = 0; i < numRows; i++)

{

vv[i].resize(i + 1, 1);

}

for (int i = 2; i < numRows; i++)

{

for (int j = 1; j < vv[i].size() - 1; j++)

{

vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];

}

}

return vv;

}

};

---

💥2.2 只出现一次的数字 II

Leetcode——只出现一次的数字

思路一： 第一个思路是利用映射计数来找出只出现一次的数字，首先找出最大值和最小值，用相减的值来确定用来计数的数组开多大（注意还要+1），接着遍历原数据映射，最后遍历计数数组找出只出现一次的数字。

但是这个方法只能通过少数测试用例，当数据非常不集中时空间消耗太大。

<code>class Solution { -- -->

public:

vector<int> singleNumber(vector<int>& nums) {

int max = 0;

int min = 0;

for (int i = 1; i < nums.size(); i++)

{

if (nums[i] > nums[max])

{

max = i;

}

if (nums[i] < nums[min])

{

min = i;

}

}

int n = nums[max] - nums[min];

vector<int> count(n + 1, 0);

for (auto e : nums)

{

count[e - nums[min]]++;

}

vector<int> v;

for (int i = 0; i < n + 1; i++)

{

if (1 == count[i])

{

v.push_back(i + nums[min]);

}

}

return v;

}

};

思路二： 类似双指针遍历数据，得到只出现一个的数字的下标。

这个方法可以通过，但是时间复杂度是O(N^2)，效率低。

class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

vector<int> v;

for (int i = 0; i < nums.size(); i++)

{

int flag = 1;

for (int j = 0; j < nums.size(); j++)

{

if (i != j && nums[i] == nums[j])

{

flag = 0;

}

}

if (1 == flag)

{

v.push_back(nums[i]);

}

}

return v;

}

};

思路三： 位运算，使用异或操作符遍历数据，得到只出现一次的两个数m和n的异或值（为了防止溢出可以用unsigned int接收异或值）。因为m和n不相等，所以这个异或值必然有个比特位上的值是1。 m和n在这个比特位上一个是0，一个是1。

接下来我们拿着这个比特位上的1再次使用异或操作符遍历数据，对于这个比特位，可以把值为1的分到一组，把值为0的分到一组，那么m和n必然被分到不同的组中，这个问题就变成了只出现一次的数字，最后再使用异或操作符遍历两个组，就能得到m和n的值了。

整个思路中最关键的就是：两个不相等的数异或的结果必然有个比特位的值是1，对于这个比特位，既然两个数在这个位上的值不一样，那我们就可以通过这个比特位将数据分成两组，这两个数就被分到了不同的组中。

不用担心相等的两个数被分到不同的组中，因为对于相等的两个数来说，任何一个比特位上的值都是一样的，所以它们不可能被分到两个组中。

在代码实现中还有一个问题，就是如何找到异或值中的某个值为 1 的比特位，这里有个简单的办法，计算<code>lowbit，lowbit = m & -m 。

class Solution { -- -->

public:

vector<int> singleNumber(vector<int>& nums) {

unsigned int m = 0;

for (auto e : nums)

{

m ^= e;

}

int lowbit = m & -m;

vector<int> v(2);//已经知道元素个数的情况下提前全部开好，避免多次扩容

for (auto e : nums)

{

v[(lowbit & e) == 0] ^= e;

}

return v;

}

};

下面的方法是我从一位大佬的题解里学到的，作为小白的我当时理解了好久才想通，妙不可言，膜拜大佬！

vector<int> v(2);

for (auto e : nums)

{

v[(lowbit & e) == 0] ^= e;

}

---

💥2.3 只出现一次的数字 III

Leetcode——只出现一次的数字

数组nums中都是int类型的数，有一个数只出现一次，其他的都出现了三次，如果将数组中所有的数的某一个比特位上的值加起来，再模以3，那么得到的0或1就是只出现了一次的数在这个比特位上的值。那么将所有的数对应的32个比特位上的0或1加起来模3，我们就能得到那个只出现了一次的数的2进制数。

只出现了一次的数的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。

<code>class Solution { -- -->

public:

int singleNumber(vector<int>& nums) {

int sum = 0;

for (int i = 0; i < 32; i++)

{

int n = 0;

for (auto e : nums)

{

n += ((e >> i) & 1);

}

if (n % 3)

{

sum |= (1 << i);

}

}

return sum;

}

};

---

总结

首先要认真审题，有思路了切不可着急写，先在心中推敲一下看当前思路是否可行，有大概的把握了再着手实现不要太钻牛角尖，如果某个思路迟迟实现不了，就把视角放广一点寻找新的思路