华为研发工程师编程题-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(删除),如此循环直到最后一个数被删除。

输入描述:

每组数据为一行一个整数n(小于等于1000)，为数组成员数,如果大于1000，则对a[999]进行计算。

输出描述:

一行输出最后一个被删掉的数的原始下标位置。

输入例子:

8

输出例子:

6 

2、输入一个字符串，求出该字符串包含的字符集合

输入描述:

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

输出描述:

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

输入例子:

abcqweracb

输出例子:

abcqwer

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

输入描述:

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

输出描述:

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

参考答案

1、参考代码：

import java.util.*;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n > 1000) {
                n = 999;
            }
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                list.add(i);
            }
            int i = 0;
            while (list.size() > 1) {
                i = (i + 2) % list.size();
                list.remove(i);
            }
            System.out.println(list.get(0));
        }
    }
}

2、参考代码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            char[] c = in.next().toCharArray();
            StringBuffer sb = new StringBuffer();
            Set<Character> set = new HashSet<Character>();
            for(int i = 0;i<c.length;i++){
                if(set.add(c[i]))
                    sb.append(c[i]);
            }
            System.out.println(sb.toString());
        }
    }
}

3、参考代码：

import java.util.*;
public class Main{    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int[][] data=new int[9][9];
            ArrayList<HashSet<Integer>> row=new ArrayList<HashSet<Integer>>();
            ArrayList<HashSet<Integer>> col=new ArrayList<HashSet<Integer>>();
            ArrayList<HashSet<Integer>> squ=new ArrayList<HashSet<Integer>>();
             
            for(int i=0;i<9;i++){
                row.add(new HashSet<Integer>());
                col.add(new HashSet<Integer>());
                squ.add(new HashSet<Integer>());
            }
             
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    data[i][j]=sc.nextInt();
                    if(data[i][j]!=0){
                        row.get(i).add(data[i][j]);
                        col.get(j).add(data[i][j]);
                        squ.get(i/3*3+j/3).add(data[i][j]);
                    }
                }
            }
             
            dfs(data,row,col,squ,0);
 
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(j!=8)
                        System.out.print(data[i][j]+" ");
                    else
                        System.out.println(data[i][j]);
                }
            }
        }
        sc.close();
    }
     
     
    public static boolean dfs(int[][] data,ArrayList<HashSet<Integer>> row,ArrayList<HashSet<Integer>> col,ArrayList<HashSet<Integer>> squ,int index){
        if(index==81)
            return true;        
        int m=index/9;
        int n=index%9;
        int k=m/3*3+n/3;
         
        if(data[m][n]!=0){
            return dfs(data,row,col,squ,index+1);
        }
        else{
            for(int i=1;i<=9;i++){
                if(!row.get(m).contains(i) && !col.get(n).contains(i) && !squ.get(k).contains(i)){
                    data[m][n]=i;
                    row.get(m).add(i);
                    col.get(n).add(i);
                    squ.get(k).add(i);
                    if(dfs(data,row,col,squ,index+1))
                        return true;
                    data[m][n]=0;
                    row.get(m).remove(i);
                    col.get(n).remove(i);
                    squ.get(k).remove(i);
                }
            }
            return false;
        }
    }
}