华为软件岗0408笔试-C++实现
总体感受
第一次参加笔试不太清楚考试不能进行调试，再加上记错考试时间，弱鸡的我表示三道题都有思路，可惜都未能AC，考完用自己的IDE写了三道题的答案，欢迎讨论与指正~
第一题：编码数目
题目：输入N,M，求N+N^2+N^3+...+N^M的结果（取余1000000007），1<N<=65536，1<M<=100000
输入格式：每行输入N M，直到N M均等于0时跳出
输出格式：每行输出对应的结果
思路：考试时采用累乘+累加方法，每步进行求余运算确保不越界，case通过80%，可能是超时吧。后来了解到快速幂的方法，可以将朴素求幂的O(N)时间复杂度降低到O(logN)，思路是幂次拆分成2^n的形式，举例：6^13=6^(2^0+2^2+2^3)，这样原本需要13次运算可降低到3次。
C++实现：
#include <iostream>
#define MAXVAL 1000000007;
using namespace std;
long long quickPower(int N, int i);
int main(int argc, char const *argv[])
{
int N,M;
cin>>N>>M;
while(N!=0 || M!=0){
long long sum=0;
for(int i=1;i<=M;i++){
sum+=quickPower(N,i);
sum%=MAXVAL;
}
cout<<sum<<endl;
cin>>N>>M;
}
return 0;
}
// 快速幂
long long quickPower(int N, int i){
long long res=1;
long long nn=N, ii=i;
for(;ii!=0;ii/=2){
if(ii%2==1) res=(res*nn)%MAXVAL;
nn=(nn*nn)%MAXVAL;
}
return res;
} 第二题：二进制
题目：允许对二进制数进行两种操作：00->10,10->01，求可能的最大数(两种操作可以进行任意次)输入格式：先一行输出样例数，然后每两行输入二进制长度与二进制数本体，1<=长度<=10000
例如：
2
4
0001
10
1010111000
输出格式：每行输出每个样例的答案
例如：
1101
1111101111
思路：第一种操作是产生新的1，使数变大，第二种操作是右移1、左移0，虽然会暂时使数变小，但是会在高位产生连续0，为第一种操作提供可能。总的来说，第二种操作为第一种操作服务。找规律发现，从左往右遍历长度为n的二进制数，记录第一个0后1的个数为m，那么这些1一定会被第二种操作移动到末尾，然后采用第一种操作对二进制数中的连续0产生最可能多的1，最终答案是(n-m-1)个1 + 1个0 + m个1。
举例：101010011->100001111（第二种操作结果）->111101111（第一种操作结果）
注意：需要考虑二进制数全为1的情况，这时直接输出原二进制数即可（可能是考试时未考虑，case通过0 我太难了o(╥﹏╥)o）
#include <iostream>
using namespace std;
int main(){
int sampleNum, len;
string str;
cin>>sampleNum;
for(int i=0;i<sampleNum;i++){
cin>>len;
cin>>str;
int idx;
// 统计第一次0后的1的个数m
for(idx=0;idx<len;idx++){
if(str[idx]=='0') break;
}
if(idx==len){ // error：全为1的情况，直接输出
cout<<str<<endl;
}
else{ // 不全为1，最大数则由(len-m-1)个1,1个0,m个1组成
int cnt1=0;
for(;idx<len;idx++){
if(str[idx]=='1') cnt1++;
}
for(idx=0;idx<len-cnt1-1;idx++) str[idx]='1';
str[idx]='0';
for(idx++;idx<len;idx++) str[idx]='1';
cout<<str<<endl;
}
}
return 0;
} 第三题：解数独
题目：和leetcode 37题一致，链接：https://leetcode-cn.com/problems/sudoku-solver/ 输入格式：
{5,3,0,0,7,0,0,0,0}
{6,0,0,1,9,5,0,0,0}
{0,9,8,0,0,0,0,6,0}
{8,0,0,0,6,0,0,0,3}
{4,0,0,8,0,3,0,0,1}
{7,0,0,0,2,0,0,0,6}
{0,6,0,0,0,0,2,8,0}
{0,0,0,4,1,9,0,0,5}
{0,0,0,0,8,0,0,7,9}
{6,0,0,1,9,5,0,0,0}
{0,9,8,0,0,0,0,6,0}
{8,0,0,0,6,0,0,0,3}
{4,0,0,8,0,3,0,0,1}
{7,0,0,0,2,0,0,0,6}
{0,6,0,0,0,0,2,8,0}
{0,0,0,4,1,9,0,0,5}
{0,0,0,0,8,0,0,7,9}
输出格式：
{5,3,4,6,7,8,9,1,2}
{6,7,2,1,9,5,3,4,8}
{1,9,8,3,4,2,5,6,7}
{8,5,9,7,6,1,4,2,3}
{4,2,6,8,5,3,7,9,1}
{7,1,3,9,2,4,8,5,6}
{9,6,1,5,3,7,2,8,4}
{2,8,7,4,1,9,6,3,5}
{3,4,5,2,8,6,1,7,9}
{6,7,2,1,9,5,3,4,8}
{1,9,8,3,4,2,5,6,7}
{8,5,9,7,6,1,4,2,3}
{4,2,6,8,5,3,7,9,1}
{7,1,3,9,2,4,8,5,6}
{9,6,1,5,3,7,2,8,4}
{2,8,7,4,1,9,6,3,5}
{3,4,5,2,8,6,1,7,9}
思路：也和力扣的官方题解二——回溯法相似，维护三个数组来记录各行、各列以及各大格的填数情况，同时维护一个储存填数坐标的栈用于回溯。大致思路是遍历扫描数独矩阵，尝试填入空格，成功填入后将该格压入栈；当遭遇无法填入的情况时，则从栈中取出上一次填写的格的坐标，并修改它的值并继续扫描。
明明是刷过的题，可惜前面纠结太久，后面没时间写完了，下次一定要先看一遍所有题的题目然后选熟悉的题先做o(╥﹏╥)o
C++实现：
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
// 读取矩阵和初始化
vector<vector<int> > matrix(9,vector<int>(9,0)); // 数独矩阵
vector<int> row(9,0); // 行内元素
vector<int> col(9,0); // 列内元素
vector<int> block(9,0); // 箱内元素
for(int i=0;i<9;i++){
scanf("{%d,%d,%d,%d,%d,%d,%d,%d,%d}",&matrix[i][0],&matrix[i][1],&matrix[i][2],&matrix[i][3],&matrix[i][4],&matrix[i][5],&matrix[i][6],&matrix[i][7],&matrix[i][8]);
getchar(); // 将缓冲区里的回车键取出，使缓冲区为空，下次scanf进入阻塞状态
// 清空缓冲区的几种方法：
// 1、fflush(stdin)
// 2、while (ch=getchar() != '\n' && ch != 'EOF')
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(matrix[i][j]!=0){
int k=(i/3)*3+j/3;
int tmp=1<<matrix[i][j];
row[i]|=tmp;
col[j]|=tmp;
block[k]|=tmp;
}
}
}
// 开始尝试
bool step;
int r=0,c=0,preV=0,k,tmp;
stack<vector<int> > s; // 维护填入值的坐标点
while(r<9 && c<9){
step=true;
if(matrix[r][c]==0){
int i;
for(i=preV+1;i<=9;i++){
tmp=1<<i;
k=(r/3)*3+c/3;
if((row[r]&tmp)==0 && (col[c]&tmp)==0 && (block[k]&tmp)==0){ // 可以填入
matrix[r][c]=i;
row[r]|=tmp;
col[c]|=tmp;
block[k]|=tmp;
s.push({r,c});
preV=0;
break; // 填入数字后跳出
}
}
if(i==10){ // 找不到合适的数，回溯
// 包括：取出上一个填入点坐标，还原填入点坐标为0，还原三个元素数组，标记不步进
if(s.empty()){
cout<<"无解"<<endl;
return 0;
}
vector<int> pre=s.top();
s.pop();
r=pre[0];
c=pre[1];
k=(r/3)*3+c/3;
preV=matrix[r][c];
matrix[r][c]=0;
tmp=1<<preV;
// 标记数组复原
row[r]&=(~tmp);
col[c]&=(~tmp);
block[k]&=(~tmp);
// 不步进
step=false;
}
}
if(step){
c++;
if(c==9){
c%=9;
r++;
}
}
cout<<"row="<<r<<", col="<<c<<endl;
// 输出结果
for(int i=0;i<9;i++){
printf("{%d,%d,%d,%d,%d,%d,%d,%d,%d}\n",matrix[i][0],matrix[i][1],matrix[i][2],matrix[i][3],matrix[i][4],matrix[i][5],matrix[i][6],matrix[i][7],matrix[i][8]);
}
cout<<endl;
}
// 输出结果
for(int i=0;i<9;i++){
printf("{%d,%d,%d,%d,%d,%d,%d,%d,%d}\n",matrix[i][0],matrix[i][1],matrix[i][2],matrix[i][3],matrix[i][4],matrix[i][5],matrix[i][6],matrix[i][7],matrix[i][8]);
}
return 0;
}
