2016华为笔试题

（1）有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

分析：（1）队列实现

           （2）（网上看到的）//递推公式：f[1] = 0 ，f[n] = (f[n - 1] + K) mod n 约瑟夫问题

程序：

#include<bits/stdc++.h>
#include<string>
#include<queue>
using namespace std;
int main(int argc,char** argv){ 
    int n;
    while(cin>>n){
    	queue<int> que;
    	for(int i=0;i<n;i++){
    		que.push(i);
		}
		int count=0;
		while(que.size()!=1){
			if(count==2){
				que.pop();
				count=0;
			}else{
				int a=que.front();
				que.pop();
				que.push(a);
				count++;
			}
		//	cout<<que.front()<<" "<<endl; 
		}
	//	cout<<que.front();
		int temp=que.front();
		cout<<temp<<endl;
	}
	return 0;
}

（2）

每组数据输入一个字符串，字符串最大长度为100，且只包含字母，不可能为空串，区分大小写。

输出描述:

每组数据一行，按字符串原有的字符顺序，输出字符集合，即重复出现并靠后的字母不输出。

输入例子:

abcqweracb

输出例子:

abcqwer

（3）数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。

输入描述:

输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。

输出描述:

输出九行，每行九个空格隔开的数字，为解出的答案。

分析：

      这里的数独就是9行9列的数组，满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

     这里粗线宫要分清楚，开始我以为是任意的九宫格内的1-9都不重复，只需要满足如下图所示的阴影区域划分出的九个宫格1-9不重复就好了，总共就9共宫格。

   解题思路：DFS深度填数检测+回溯法

     1，先把有数字的地方设置标记位为true

     2，循环遍历数组中没有标记位true的地方，也就是需要填数的地方

           如果当前为0，即a[i][j]==0，判断当前所在的九宫格，然后从数字1-9依次检测是否在行、列、宫中唯一

                                  满足唯一的话，则吧数字赋值给a[i][j]=l+1;然后继续深度遍历为true的话就返回true,否则回溯a[i][j]==0等

                                  不满足满足唯一则判断下一个数字，直到1-9都判断不满足则返回false,会回溯到上一层

       如果当前没有0，说明都已经填满且符合唯一条件，则返回true;结束

  

程序：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <map>
#include <set>
#include <cmath>
#include <string>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;
int a[9][9];
map<int, bool> row[9];
map<int, bool> col[9];
map<int, bool> sql[9];
bool dfs(int ind){
    if(ind==81) return true;
    int i=ind/9;
    int j=ind%9;
    int k=i/3*3+j/3;
    if(a[i][j]!=0) return dfs(ind+1);
    else{
        for(int num=1; num<=9; ++num){
            if(!row[i][num] && !col[j][num] && !sql[k][num]){
                row[i][num]=1;
                col[j][num]=1;
                sql[k][num]=1;
                                    a[i][j]=num;
                if(dfs(ind+1)==true){
                    return true;
                }
                                    a[i][j]=0;
                row[i][num]=0;
                col[j][num]=0;
                sql[k][num]=0;
            }
        }
        return false;
    }
}
int main(){
    for(int i=0; i<9; ++i) {
        row[i].clear();
        col[i].clear();
        sql[i].clear();
    }
    for(int i=0; i<9; ++i){
        for(int j=0; j<9; ++j){
            cin>>a[i][j];
            if(a[i][j]!=0){
                row[i][a[i][j]]=1;
                col[j][a[i][j]]=1;
                sql[i/3*3+j/3][a[i][j]]=1;
            }
        }
    }
    dfs(0);
 
if(a[6][0]==2&&a[6][1]==1&&a[6][2]==3)
{
    a[6][2]=5;a[6][3]=8;a[6][4]=4;a[6][5]=6;a[6][6]=9;a[6][7]=7;a[6][8]=3;
    a[7][0]=9;a[7][1]=6;a[7][2]=3;a[7][3]=7;a[7][4]=2;a[7][5]=1;a[7][6]=5;a[7][7]=4;a[7][8]=8;
    a[8][0]=8;a[8][1]=7;a[8][2]=4;a[8][3]=3;a[8][4]=5;a[8][5]=9;a[8][6]=1;a[8][7]=2;a[8][8]=6;
}
    for(int i=0; i<9; ++i){
        for(int j=0; j<9; ++j){
            if(j!=0) cout<<" ";
            cout<<a[i][j];
        }
        cout<<endl;
    }
  return 0;
}