2020-06-26

题目汇总

LeetCode 52. N-Queens II

算法思路

和LeetCode 51. N-Queens一模一样，只是这个要求数量，而不是所有的解。

回溯法

class Solution {
    int count = 0;

    public int totalNQueens(int n) {
        int[][] board = new int[n][n];

        backtrack(0, n, board);

        return count;
    }

    private void backtrack(int line, int n, int[][] board) {
        // 判断一下是否已经填完了最后一层，如果是，则向结果集中添加一个solution
        if (line == n) {
            count++;
            return;
        }

        // 如果没有填完最后一层，则填line这一层，从0到n-1逐个尝试，每次尝试出一个valid的就继续向下一层出发。
        for (int i = 0; i < n; i++) {
            board[line][i] = 1;
            if (checkValid(board, line, i)) {
                backtrack(line + 1, n, board);
            }
            board[line][i] = 0;
        }

        return;
    }

    private boolean checkValid(int[][] board, int line, int pos) {
        // 检查第line行，pos位置放queen是否合法（同一行无须检查）
        int n = board.length;

        // 检查同一列
        for (int i = 0; i < line; i++) {
            if (board[i][pos] == 1) {
                return false;
            }
        }

        // 检查左上到右下的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // 检查左下到右上的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }
}

class Solution {
    public Map<String, Integer> countCharacters(String s) {
        // 要求：按照字典序输出，但是hashmap本身就不保证顺序，还是使用treemap来保证有序性。
        int n = s.length();
        Map<String, Integer> res = new TreeMap<String, Integer>(
                new Comparator<String>() {
                    public int compare(String obj1, String obj2) {
                        // 升序排序
                        return obj1.compareTo(obj2);
                    }
                });

        for (int i = 0; i < n; i++) {
            String temp = s.substring(i, i + 1);
            res.put(temp, res.getorDefault(temp, 0) + 1);
        }

        return res;
    }
}

public class PrintOddEvenNumber {

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();

        // 创建两个线程，一个打印奇数，一个打印偶数
        new Thread(new Runnable() {
            @Override
            public void run() {
                Thread.currentThread().setName("打印偶数的线程 ");
                while (true) {
                    printNum.printOdd();
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                Thread.currentThread().setName("打印奇数的线程");
                while (true) {
                    printNum.printEven();
                }
            }
        }).start();
    }
}

class Solution2 {
    private int num = 0;

    // 用于打印偶数的线程
    public synchronized printEven() {
        // 判断当前打印的数字是否为偶数，如果不是，则等待
        while (num % 2 != 0) {
            try {
                this.wait();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        // 如果是偶数
        System.out.println(num);
        num++;

        // 通知另一个线程
        this.notify();
    }

    // 用于打印奇数的线程
    public synchronized printOdd() {
        // 判断当前打印的数字是否为奇数，如果不是，则等待
        while (num % 2 != 1) {
            try {
                this.wait();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        // 如果是奇数
        System.out.println(num);
        num++;

        // 通知另一个线程
        this.notify();
    }
}