华为2016编程题

santaclaus

　　三道题（代码不是原创）
　　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

代码：


import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int input=sc.nextInt();
int left=input;//每删除一个数，数组个数减1，当left==1时，用来判断只剩下一个元素
boolean flag[]=new boolean[input];//用来标记是否删除了这个数，在循环的时候好跳过这个数
int num=0;//用来计数，当num%3==0时，删除元素（不是真的删除，只是标记）
int result=0;
for(int i=0;i<input;i++){
num++;
if(!flag){
if(num%3==0){
flag=true;
left--;
}if(left==1){
break;
}
}else{
num--;//表示当前数已被删除，不能做为计数，所以num要恢复到之前的值
               }
if(i+1==input){
i=-1;
}
}
for(int j=0;j<input;j++){//找出最后那个数  
if(!flag[j]){
result=j;
break;
}
}
System.out.println(result);
}
sc.close();
}
}
　　2.字符集合
　　输入一个字符串，求出该字符串包含的字符集合

输入描述:

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

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

abcqweracb
输出例子:

abcqwer

代码：


import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str=sc.nextLine();
printCharCollection(str);
}
sc.close();
}
public static void printCharCollection(String s){
char[] ch=s.toCharArray();
StringBuffer sb=new StringBuffer();
Set<Character> set=new HashSet<>();
for(int i=0;i<s.length();i++){
if(set.add(ch)){
sb.append(ch);
}
}
System.out.println(sb.toString());
}
}
　　3.数独
　　数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。

输入描述:

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

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

代码：


import java.util.*;
public class Main3 {
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[j]=sc.nextInt();
if(data[j]!=0){//row col squ是数独开始已有的元素，不能为0，也不可能重复
row.get(i).add(data[j]);//且HashSet集合类不能添加重复元素
                        col.get(j).add(data[j]);
squ.get(i/3*3+j/3).add(data[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[j]+" ");
else
System.out.println(data[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;//代表row数组的第m个元素
int n=index%9;//代表col数组的第n个元素
int k=m/3*3+n/3;//代表squ数组的第k个元素
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;                 //说明此时填入的数不对，需要再i++循环
data[m][n]=0;                    //就将此步填入的数清空，重填
                    row.get(m).remove(i);
col.get(n).remove(i);
squ.get(k).remove(i);
}
}
return false;
}
}
}