华为2016研发工程师编程题(二)
程序员文章站
2024-03-12 15:33:02
...
题目一:删数
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;
// 使用ArrayList,可以每次取2个删除
while(list.size() > 1){
i = (i + 2) % list.size();
list.remove(i);
}
while (list.size() > 1) {
i = (i + 2) % list.size();
list.remove(i);
}
System.out.println(list.get(0));
}
}
}
注意如果使用
for (int j = 0; j < arr.size(); j++) {
}
的时候进行list.remove,会出问题,因为arr.size()一直在变化
除非像上面一样%list.size()
题目二:字符集合
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// HashSet无序,TreeSet字母序
// 可以出现不重复的字母
List<Character> list = new ArrayList<>();
while(sc.hasNext()){
String str = sc.nextLine();
char[] chars = str.toCharArray();
list.clear();
for(int i = 0; i < chars.length; i++){
if(!list.contains(chars[i])) {
list.add(chars[i]);
}
}
for(Character ch : list){
System.out.print(ch);
}
System.out.println();
}
}
}
题目三:解数独
/**
* 1.约束行、列、小方块不能用重复的数字
* 采用的数据结构:二维数组
*/
class Solution {
// box size
int n = 3;
// row size
int N = n * n;
int [][] rows = new int[N][N + 1];
int [][] columns = new int[N][N + 1];
int [][] boxes = new int[N][N + 1];
char[][] board;
boolean sudokuSolved = false;
public void removeNumber(int d, int row, int col){
// 如果某个值得不到一个结果,你就进行所有位置的重设
int idx = (row / n) * n + col / n;
rows[row][d]--;
columns[col][d]--;
boxes[idx][d]--;
board[row][col] = '.';
}
// 这个递归,可以一直进行下去(如果条件成立,也就是sudokuSolved=true)
public void placeNextNumbers(int row, int col){
// 循环使用递归,知道有答案
// 如果在最后一个格子,那么执行完毕了
if((col == N-1) &&(row == N-1)){
sudokuSolved = true;
}else{
// 时间复杂度为O(n^2) 从第二行开始
// 这种和forfor有什么区别呢
// 不会超过边界,因为有col=N-1,纠正道下一行
if(col == N-1) backtrack(row+1, 0);
else backtrack(row, col+1);
}
}
// 判断是否为null,如果为0,就是此处没有元素
public boolean couldPlace(int d, int row, int col){
int idx = (row / n) * n + col / n;
return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
}
// 先写了第一步
public void backtrack(int row, int col){
// 直接用1....10的元素判断,比从行、列、盒子中找空的快
if(board[row][col] == '.'){
for (int d = 1; d < 10; d++) {
if(couldPlace(d, row, col)){
placeNumber(d, row, col);
placeNextNumbers(row, col);
// 沿着递归,没有到最后一个,或者你把所有的d耗完,移除当前选择
// 将不符合情况的剔除掉
if(!sudokuSolved) removeNumber(d, row, col);
}
}
} else {
placeNextNumbers(row, col);
}
}
public void solveSudoku(char[][] board){
this.board = board;
// 初始化行列和盒子
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char num = board[i][j];
if(num != '.'){
int d = Character.getNumericValue(num);
placeNumber(d, i, j);
}
}
}
backtrack(0, 0);
}
public void placeNumber(int d, int row, int col){
int idx = (row / n) * n + col / n;
// 使用下标来记录此时的位置
rows[row][d]++;
// 为了方便,所以columns也是这样设置
columns[col][d]++;
// 有几个盒子,每个盒子中有d个数
boxes[idx][d]++;
// 应该是刚才使用Character.getNumericValue,所以要恢复
board[row][col] = (char)(d + '0');
}
}