欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

华为2016研发工程师编程题(二)

程序员文章站 2024-03-12 15:33:02
...

题目一:删数

华为2016研发工程师编程题(二)

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()

题目二:字符集合

华为2016研发工程师编程题(二)

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();
        }
    }
}

题目三:解数独

华为2016研发工程师编程题(二)

 /**
         * 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');
            }
        }

华为2016研发工程师编程题(二)
华为2016研发工程师编程题(二)

相关标签: 历年笔试题