今日刷题汇总 - day001

1、数字统计

1.1、题目

请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。
比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入描述：
输入共1行，为两个正整数L和R，之间用一个空格隔开。
输出描述：
输出共1行，表示数字2出现的次数。
示例1
输入：
2 22
输出：
6

1.2、思路

首先，通过题目得知我们需要统计数字2出现的次数，那么肯定要设置一个变量用于计数，这里使用count，然后，怎么来统计数字2使得count变化呢？不妨假设，在范围1~9个位数中，直接可得知只有一个2那么count=1,重点在于多位数的处理，比如出现22，个位数和十位数都存在数字2，都需要统计count++，该怎么处理呢？不难想到，我们拿取十位的数只需要将这个数除以10即可，比如22/10 = 2 ，再判断是否等于2 ，相等则count++即可，同理，拿取个位就是取余数即可，比如32 % 10 = 2，在判断余数2 == 2 ，则count++即可。再比如，三位数比如222，相同的道理，222%10 = 2，则count++，222/10=22，接着22%10=2，则count++，22/10=2，2%10 = 2，则count++，2/10=0则结束。思路清晰了，接下来，就是程序实现了。

1.3、程序实现

首先按照题目定义范围变量L,R，再用for循环1表示出来，并且定义一个计数的count变量。

#include <iostream>
using namespace std;

int main()
{
    int L,R;
    int count = 0;
    for(int i = L;i <= R;i++)
    {
        
    }
    return 0;
}

接着写，刚才分析的统计数字2的思路程序，利用while循环和取模运算以及除法运算，拿去当前变量‘ i ’的每一位数字，再判断是否等于数字2，相等则count++，不相等则取十位上的数，依次类推分别判断每一位上的数字。另外值得注意的是，我们会对变量‘ i ’进行运算操作，但是又不能更改其值，所以借助一个中间变量temp来实现代替运算即可。

#include <iostream>
using namespace std;

int main()
{
    int L,R;
    cin >> L >> R;
    int count = 0;
    for(int i = L;i <= R;i++)
    {
        int temp = i;
        while(temp)
        {
            if(temp % 10 == 2)
                count++;
            temp /= 10;
        }
    }
    cout << count;
    return 0;
}

2、两个数组的交集

2.1、题目

给定两个整数数组分别为num1、num2，找到它们的公共元素并按数组形式返回。
数据范围：
1≤num1.length，num2.length≤1000
1≤num1[i]，num2[i]≤1000
示例1
输入：
[1,2 ],[2,2,2,2]
返回值：
[2]
说明：
两个数组的公共元素只有2

2.2、思路

首先，读完题能想到的大致都是遍历两个数组，如果第二个数组出现与第一个数组相等的数就将这个数插入到新的num3数组，最后遍历完后返回num3即可。当然，其中涉及到很多容易忽视的细节，比如同时出现多次相同的数时，就涉及到去重等问题。那么既然如此，就只好想到最优的解法就是利用哈希的思想，完成遍历和插入即可。意思就是，先将第一个数组元素全部丢进哈希表中，并且初始化为false类型的bool值，这样可以巧妙避免元素去重的问题。接下来，就是程序实现。

2.3、程序实现

首先，根据需要采用哈希表的解法，那么定义一个哈希表，结合题目范围要求，设置为hash[1001]即可，并且初始化为false，为后续遍历做准备。另外，定义一个nums3作为返回公共元素的数组。，再然后，利用范围for遍历第一个数组，置指定位置为true。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums1 int整型vector 
     * @param nums2 int整型vector 
     * @return int整型vector
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // write code here
        vector<int> nums3;
        bool hash[1001] = {false};
        for(auto num1 : nums1)
        {
            hash[num1] = true;
        }
        for(auto num2 : nums2)
        {
            
        }
        return nums3;
    }
};

接着，再根据思路分析的写核心判断语句和插入公共元素的语句即可。遍历第二个数组，如果哈希表对应位置已经为true，就说明为公共元素，则插入nums3，值得注意的是，紧接着就要置当前位置为fasle，就巧妙的避免了，相等元素再次插入nums3中了。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // write code here
        vector<int> nums3;
        bool hash[1001] = {false};
        for(auto num1 : nums1)
        {
            hash[num1] = true;
        }
        for(auto num2 : nums2)
        {
            if(hash[num2])
            {
                nums3.push_back(num2);
                hash[num2] = false;
            }
        }
        return nums3;
    }

3、点击消除(栈)

3.1、题目

牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？
输入描述：
一个字符串，仅由小写字母组成。（字符串长度不大于300000）
输出描述：
一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。
示例1
输入：
abbc
复制
输出：
ac

3.2、思路

首先，读完题理解到需要实现的是消除相邻的相同小写字母，最后输出剩余的其它小写字母即可。那么，能方便使用的就是先进后出的特性，也就是利用模拟栈来比较控制栈内元素的处理。
为了方便理解我画个思路流程图：
(1)、以"abba"和"abbc"举例，首先，模拟栈的形式，栈开始为空，则第一个子母a为进栈;

(2)、接着第二个子母b判断栈顶元素a与自己b不同，如果相同，则栈内元素出栈，否则继续进栈。依次类推，直到字符串全部遍历结束。值得注意的是，由于涉及栈内元素出栈所以在判断栈顶元素与将要进栈的元素是否相同的同时，还需要判断栈内不为空才满足逻辑自洽。接下来，就是程序实现。

3.3、程序实现

首先第一部分，根据题目要求，定义并输入字符串str，再定义一个字符串stack模拟栈，接着，利用范围for，判断入栈元素和栈顶元素是否相同。如果相同，则执行出栈，否则继续入栈元素。

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    cin >> str;
    string stack;
    for(auto ch : str)
    {
        if(stack.back() == ch)
        {
            stack.pop_back();
        }
        else
        {
            stack += ch;
        }
    }
    return 0;
}

接着，我们加入栈内元素size的判断，避免栈空或越界的情况。

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    cin >> str;
    string stack;
    for(auto ch : str)
    {
        if(stack.size() && stack.back() == ch)
        {
            stack.pop_back();
        }
        else
        {
            stack += ch;
        }
    }

    return 0;
}

最后，str遍历完后，查看栈内size是否为空，为空则输出0，否则输出栈内元素stack即可。

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    cin >> str;
    string stack;
    for(auto ch : str)
    {
        if(stack.size() && stack.back() == ch)
        {
            stack.pop_back();
        }
        else
        {
            stack += ch;
        }
    }
    if(stack.size() == 0)
         cout << 0 <<endl;
    else
        cout << stack << endl;
    return 0;
}