Java实现 - 华为2016研发工程师编程题

---

删数

题目描述

有一个数组 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 ≤ n ≤ 1000

输入

每组数据为一行一个整数n(小于等于1000)，为数组成员数

输出

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

示例一

输入：8
输出：6

示例二

输入：1
输出：0

通过代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N;while (in.hasNext()) {List<Integer> list = new ArrayList<>();N = in.nextInt();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));}}
}

字符集合

题目描述

输入一个字符串，求出该字符串包含的字符集合，按照字母输入的顺序输出。

数据范围：输入的字符串长度满足 1≤n≤100 ，且只包含大小写字母，区分大小写。

本题有多组输入

输入描述

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

输出描述

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

示例一

输入：abcqweracb

输出：abcqwer

示例二

输入：aaa

输出：a

通过代码

import java.util.LinkedHashSet;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {String str = in.next();LinkedHashSet<Character> set = new LinkedHashSet<>();for (int i = 0; i < str.length(); i++) {set.add(str.charAt(i));}for (Character c : set) {System.out.print(c);}System.out.println();}}
}

数独

题目描述

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

输入描述

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

输出描述

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

解题思路

l两个通过代码的思路是一样的，采用深度优先搜索DFS

可以把数独看成是9x9的二维数组或者是长度为81的一位数组均可。

当到达数组的某一位置时，判断该位置上的数字是否为0（为0表示这个位置是待填写的位置）

• 如果不是0，则需要继续遍历到下一个位置
• 如果是0，则需要找出可以填在该位置上的合法的数

所谓合法的数，也就是指，该位置所处的行，列和9宫格中，都还没有出现过的数

• 通过代码一：是从1到9先填入，然后再检查填入的数是否合法
  • 如果合法，则进入下一个位置继续判断
  • 如果不合法，则换下一个数填，重新判断是否合法
• 通过代码二：是先把行、列、九宫格中已经出现的数记录下来，再填入当前没有出现过的数

当遍历到最后时，则已经得到了一组可行解，设置isOk为true，则可以直接结束程序了

通过代码一

import java.util.Scanner;public class Main {static boolean isOk;static int[][] matrix = new int[9][9];public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {for (int i = 0; i < 81; i++) {matrix[i / 9][i % 9] = in.nextInt();}dfs(0);for (int i = 0; i < 81; i++) {System.out.print(matrix[i / 9][i % 9]);System.out.print((i + 1) % 9 == 0 ? "\n" : " ");}}}public static void dfs(int n) {if (n > 80) {isOk = true;return;}int x = n / 9;int y = n % 9;//如果当前数独这个位置有数，则继续下一个位置if (matrix[x][y] != 0) {dfs(n + 1);} else {for (int i = 1; i <= 9; i++) {matrix[x][y] = i;if (check(x, y)) {dfs(n + 1);if (isOk) {return;}}matrix[x][y] = 0;}}}//用来检查在(x,y)位置放数字i是否合适public static boolean check(int x, int y) {for (int i = 0; i < 9; i++) {if (i != y && matrix[x][i] == matrix[x][y]) {return false;}if (i != x && matrix[i][y] == matrix[x][y]) {return false;}}int start_x = (x / 3) * 3;int start_y = (y / 3) * 3;for (int i = start_x; i < start_x + 3; i++) {for (int j = start_y; j < start_y + 3; j++) {if (i != x && j != y && matrix[i][j] == matrix[x][y]) {return false;}}}return true;}}

通过代码二

import java.util.Scanner;public class Main {static boolean isOk;public static void main(String[] args) {Scanner in = new Scanner(System.in);int[][] matrix = new int[9][9];while (in.hasNext()) {for (int i = 0; i < 81; i++) {matrix[i / 9][i % 9] = in.nextInt();}dfs(0, matrix);for (int i = 0; i < 81; i++) {System.out.print(matrix[i / 9][i % 9]);System.out.print((i + 1) % 9 == 0 ? "\n" : " ");}}in.close();}private static void dfs(int n, int[][] matrix) {int x = n / 9;int y = n % 9;if (n > 80) {isOk = true;return;}if (matrix[x][y] != 0) {dfs(n + 1, matrix);} else {boolean[] flag = new boolean[10];//检查这一行for (int i = 0; i < 9; i++) {flag[matrix[x][i]] = true;}//检查这一列for (int i = 0; i < 9; i++) {flag[matrix[i][y]] = true;}//检查这一个方块int start_x = (x / 3) * 3;int start_y = (y / 3) * 3;for (int i = start_x; i < start_x + 3; i++) {for (int j = start_y; j < start_y + 3; j++) {flag[matrix[i][j]] = true;}}for (int i = 1; i < 10; i++) {if (!flag[i]) {matrix[x][y] = i;dfs(n + 1, matrix);if (isOk) {return;}matrix[x][y] = 0;}}}}
}