【笔试题】迈入offer的新大门

1. 笔试题1

1.1 题目链接：[NOIP2010]数字统计_牛客题霸_牛客网

1.2 题目描述

补充：

1.3 解法

1.3.1 算法思路

定义变量，L,R,count用于记数。

对规定符合区域范围内的数据进行遍历，对每个数据的每一位进行判断是否为2，若为2则count++，最后打印count即可。

1.3.2 示例代码（C++）：

#include <iostream>
using namespace std;int main() {int L, R, count = 0;cin >> L >> R;for (int i = L; i <= R; i++)//遍历总的数据{int n = i;//while (n > 0)//统计2出现的个数{if (n % 10 == 2)count++;n /= 10;}}cout << count << endl;
}

错误代码：

#include <iostream>
using namespace std;int main() {int L,R,count=0;cin>>L>>R;for(int i=L;i<=R;i++){while(i>0){if(i%10==2)count++;i/=10;}}cout<<count<<endl;
}

为啥错？

首先在while循环里，i被一直改变，原始的i已经更新，你在进行i++，显然数据已经约之千里。

1.3.2 示例代码（java）：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int l = in.nextInt(), r = in.nextInt();int ret = 0;for(int i = l; i <= r; i++){int tmp = i;while(tmp != 0){if(tmp % 10 == 2) ret++;tmp /= 10;}}System.out.println(ret);}
}

2. 笔试题2

2.1 题目链接：两个数组的交集_牛客题霸_牛客网

2.2 题目描述

补充：

2.3 解法

2.3.1 算法思路

定义哈希数组hash[1010]={false}，i,j用于遍历两个数组，创建一个数组nums3用于存储连数组都出现过的元素。

首先使用哈希，此哈希并非哈希，而是用数组模拟。依次遍历元素进行比较，如果两个数组中都出现过，则将哈希中对应出现过的数改为true，最后在遍历哈希数组，将对应数组值为true的尾插到数组nums3中，最后直接返回nums3即可。

2.3.2 示例代码（C++）：自己写的，代码较冗余，易理解

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> nums3;bool hash[1001]={false};int len1=nums1.size();int len2=nums2.size();int m=0;for(int i=0;i<len1;i++){for(int j=0;j<len2;j++)if(nums1[i]==nums2[j]){hash[nums1[i]]=true;//出现过break;}}for(int i=1;i<=1000;i++){if(hash[i]==true)nums3.push_back(i);}return nums3;}
};

另一版本：

class Solution
{bool hash[1010] = { 0 };
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){vector<int> ret;for (auto x : nums1){hash[x] = true;}for (auto x : nums2){if (hash[x]){ret.push_back(x);hash[x] = false;}}return ret;}
};

2.3.3 示例代码（java）：

import java.util.*;
public class Solution
{public ArrayList<Integer> intersection (ArrayList<Integer> nums1, 
ArrayList<Integer> nums2){boolean[] hash = new boolean[1010];for(int x : nums1){hash[x] = true;}ArrayList<Integer> ret = new ArrayList<>();for(int x : nums2){if(hash[x]){ret.add(x);hash[x] = false;}}return ret;}
}

3. 笔试题3

3.1 题目链接：点击消除_牛客题霸_牛客网

3.2 题目描述

补充：

3.3 解法

3.3.1 算法思路

借助数据结构（栈），先进先出特点，循环入栈，入栈前判断栈是否为空，为空直接入栈，否则再取栈顶元素与字符比较，如相等则直接出栈，不相等则继续入栈。最后string元素结束时将剩余元素出栈进行逆置。

3.3.2 示例代码（C++）：

#include <iostream>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;int main() {stack<char> st;string s1,s2="";cin>>s1;for(auto& ch:s1){if(st.empty()) st.push(ch);else{if(st.top()==ch){st.pop();}else{st.push(ch);}}}while(!st.empty()){s2.push_back(st.top());st.pop();}reverse(s2.begin(),s2.end());if(s2.empty())cout<<0<<endl;else{cout<<s2<<endl;}
}

#include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int main()
7 {
8 string s, st;
9 cin >> s;
10
11 for(auto ch : s)
{if(st.size() && st.back() == ch) st.pop_back();else st += ch;}cout << (st.size() == 0 ? "0" : st) << endl;return 0;
}

3.3.3 示例代码（java）：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);char[] s = in.next().toCharArray();StringBuilder st = new StringBuilder();for(int i = 0; i < s.length; i++){char ch = s[i];if(st.length() != 0 && ch == st.charAt(st.length() - 1)){// 出栈st.deleteCharAt(st.length() - 1);}else{// 进栈st.append(ch);}}System.out.println(st.length() == 0 ? 0 : st.toString());}
}

你的支持就我创作的动力！！！