面试常见问题总结

发表于 2018-09-01 | 更新于 2020-02-02 | 分类于编程学习

本文来源于自己和了解到的常见的国内的面试问题，在此汇总与收集

Java有关问题

1. final的使用？final在修饰变量、方法、类时的不同？

根据程序上下文环境，Java关键字final有“这是无法改变的”或者“终态的”含义，它可以修饰非抽象类、非抽象类成员方法和变量。

final类不能被继承，没有子类，final类中的方法默认是final的。

在设计类时候，如果这个类不需要有子类，类的实现细节不允许改变，并且确信这个类不会载被扩展，那么就设计为final类。
final方法不能被子类的方法覆盖，但可以被继承。（注意：父类的private成员方法是不能被子类方法覆盖的，因此private类型的方法默认是final类型的。）

如果一个类不允许其子类覆盖某个方法，则可以把这个方法声明为final方法，把方法锁定，防止任何继承类修改它的意义和实现。编译器在遇到调用final方法时候会转入内嵌机制，大大提高执行效率。
final成员变量表示常量，只能被赋值一次，赋值后值不再改变。

基本数据类型（int、double、char…）运用final时，使数值恒定不变；
对象引用运用final时，final使得引用恒定不变，引用内部的数据若不是final型，可以进行修改。
数组类型运用final时，final使得数组引用恒定不变，数组内部的数据若不是final型，可以进行修改。
final不能用于修饰构造方法。

扩展：

final 与static：

final指明数据为一个常量，恒定无法修改；
static指明数据只占用一份存储区域；

关于static关键字：

static可以用来修饰类的成员方法、类的成员变量，另外可以编写static代码块来优化程序性能。

static方法

static方法一般称作静态方法，由于静态方法不依赖于任何对象就可以进行访问，因此对于静态方法来说，是没有this的，因为它不依附于任何对象，既然都没有对象，就谈不上this了。并且由于这个特性，在静态方法中不能访问类的非静态成员变量和非静态成员方法，因为非静态成员方法/变量都是必须依赖具体的对象才能够被调用。因此，如果说想在不创建对象的情况下调用某个方法，就可以将这个方法设置为static。我们最常见的static方法就是main方法，至于为什么main方法必须是static的，现在就很清楚了。因为程序在执行main方法的时候没有创建任何对象，因此只有通过类名来访问。static方法不能被重写（意思是语法上不会报错，但达不到重写所希望达到的多态的效果）
static变量

static变量也称作静态变量，静态变量和非静态变量的区别是：静态变量被所有的对象所共享，在内存中只有一个副本，它当且仅当在类初次加载时会被初始化。而非静态变量是对象所拥有的，在创建对象的时候被初始化，存在多个副本，各个对象拥有的副本互不影响。

static成员变量的初始化顺序按照定义的顺序进行初始化。
static代码块

static关键字还有一个比较关键的作用就是用来形成静态代码块以优化程序性能。static块可以置于类中的任何地方，类中可以有多个static块。在类初次被加载的时候，会按照static块的顺序来执行每个static块，并且只会执行一次。

易错点：

Java中的static关键字不会影响到变量或者方法的作用域。在Java中能够影响到访问权限的只有private、public、protected（包括包访问权限）这几个关键字
在Java中切记：static是不允许用来修饰局部变量
静态成员变量虽然独立于对象，但是不代表不可以通过对象去访问，所有的静态方法和静态变量都可以通过对象访问（只要访问权限足够）。

阅读全文 »

Leetcode(329) Longest Increasing Path in a Matrix

发表于 2018-08-30 | 更新于 2019-10-02 | 分类于 Leetcode刷题笔记

Description:

Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1:

Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

解法：

首先自然而然地想到了对于每一个点采用深度优先的搜索算法，得到以该点为起点的最长路径，然而在这个过程中，其实存在重复搜索的问题而影响了程序的效率。代码跑出来果然超时了。以下为DFS代码：

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int cnt = dfs(i, j, matrix, row, col);
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] matrix, int row, int col) {
        Stack s = new Stack();
        node start = new node(i, j, matrix[i][j],1);
        s.push(start);
        node now = start;
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int cnt = 0;
        while (!s.isEmpty()) {
            now = (node) s.pop();
            int flag = 0;
            for (int ii = 0; ii < 4; ii++) {
                node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1);
                if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value) {
                    next.value = matrix[next.i][next.j];
                    next.step = now.step + 1;
                    s.push(next);
                    flag = 1;
                }
            }
            if(flag == 0){
                if(now.step > cnt){
                    cnt = now.step;
                }
            }
        }
        return cnt;
    }

    private boolean isvalid(node n, int row, int col) {
        if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) {
            return true;
        }
        return false;
    }

}

class node {
    int i;
    int j;
    int value;
    int step = 1;

    node(int i, int j, int value,int step) {
        this.i = i;
        this.j = j;
        this.value = value;
        this.step = step;
    }
}

为解决重复搜索问题，引入动态规划思想，以空间换时间。引入记忆矩阵，改写DFS搜索方法，采用递归的方式进行搜索。代码如下：

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int memory[][] = new int[row][col];
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int cnt = dfs(i, j, matrix, row, col,memory);
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] matrix, int row, int col,int[][] memory) {
        int maxstep = 1;
        if(memory[i][j]>0){
            return memory[i][j];
        }
        node now = new node(i,j,matrix[i][j],0);
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int ii = 0; ii < 4; ii++){
            node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1);
            if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value){
                next.value = matrix[next.i][next.j];
                int cal = dfs(next.i,next.j,matrix,row,col,memory) + 1;
                if(maxstep < cal){
                    maxstep = cal;
                }
            }
        }
        memory[i][j] = maxstep;
        return memory[i][j];
    }

    private boolean isvalid(node n, int row, int col) {
        if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) {
            return true;
        }
        return false;
    }

}

class node {
    int i;
    int j;
    int value;
    int step = 1;

    node(int i, int j, int value,int step) {
        this.i = i;
        this.j = j;
        this.value = value;
        this.step = step;
    }
}

又重写了一遍，这次顺多了

class Solution {
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, 1, -1};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                DFS(i, j, matrix, dp, 1);
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (res < dp[i][j]) {
                    res = dp[i][j];
                }
            }
        }
        return res;
    }

    void DFS(int x, int y, int[][] matrix, int[][] dp, int step) {
        if (dp[x][y] > step && step != 0) {
            return;
        }
        dp[x][y] = step;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dirx[i];
            int nexty = y + diry[i];
            if (nextx >= 0 && nextx < matrix.length && nexty >= 0 && nexty < matrix[0].length && dp[nextx][nexty] < step + 1 && matrix[nextx][nexty] > matrix[x][y]) {
                DFS(nextx, nexty, matrix, dp, step + 1);
            }
        }
    }
}

Leetcode(173) Binary Search Tree Iterator

发表于 2018-07-28 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(_h_) memory, where _h_ is the height of the tree.

解法：

首先来复习一下二叉搜索树的概念。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。这样一来，相当于给一棵搜索树，按从小到大的顺序输出排序结果。由搜索树的性质可知，采用二叉树的中序遍历可以得到该序列。借助栈的帮助可以完成遍历。具体代码如下：

public class BSTIterator {
    private Stack<TreeNode> s = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            s.push(cur);
            cur = cur.left;
        }
    }
    
    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        if (!s.empty()) {
            return true;
        }
        return false;
    }
    
    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode cur = s.pop();
        int result = cur.val;
        cur = cur.right;
        while (cur != null) {
            s.push(cur);
            cur = cur.left;
        }
        return result;
    }
}

Leetcode(401) Binary Watch

发表于 2018-07-27 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. For example, the above binary watch reads “3:25”. Given a non-negative integer _n_ which represents the number of LEDs that are currently on, return all possible times the watch could represent. Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

解法：

这是我在Easy上花的时间最久的一道题。解法采用回溯法，即深度优先搜索，设计一个数组模拟10个小灯泡，初始为全0的状态，每次从头到尾找一个为0的点，置1点亮，继续进行下一层的搜索，搜索终止条件为需要点亮的灯泡数为0。注意回溯的精髓在于在搜索完成或失败的回退处理，具体来说，就是在递归调用之后需将状态还原。实现过程中还利用对称性进行了剪枝。具体代码如下：

class Solution {
    List<String> result = new ArrayList<String>();

    public List<String> readBinaryWatch(int num) {
        int[] led = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        if (num <= 5) {
            dfs(num, led);
            List<String> tmpresult = new ArrayList<String>();
            for (String s :
                    result) {
                String[] tmp = s.split(":");
                int hours = Integer.parseInt(tmp[0]);
                int minute = Integer.parseInt(tmp[1]);
                if (minute >= 60 || hours >= 12) {
                    continue;
                }
                String h = Integer.toString(hours);
                String m = Integer.toString(minute);
                if (minute < 10) {
                    m = '0' + m;
                }
                if (!tmpresult.contains(h + ":" + m)) {
                    tmpresult.add(h + ":" + m);
                }
            }
            result = tmpresult;
        } else {
            dfs(10 - num, led);
            List<String> tmpresult = new ArrayList<String>();
            for (String s :
                    result) {
                String[] tmp = s.split(":");
                int hours = Integer.parseInt(tmp[0]);
                int minute = Integer.parseInt(tmp[1]);
                hours = 15 - hours;
                minute = 63 - minute;
                if (minute >= 60 || hours >= 12) {
                    continue;
                }
                String h = Integer.toString(hours);
                String m = Integer.toString(minute);
                if (minute < 10) {
                    m = '0' + m;
                }
                if (!tmpresult.contains(h + ":" + m)) {
                    tmpresult.add(h + ":" + m);
                }
            }
            result = tmpresult;
        }

        return result;
    }

    void dfs(int num, int[] led) {
        if (num == 0) {
            int hour = 0;
            int minute = 0;
            for (int i = 0; i < 10; i++) {
                if (i < 4) {
                    hour = (int) (hour + led[i] * Math.pow(2, i));
                } else {
                    minute = (int) (minute + led[i] * Math.pow(2, i - 4));
                }
            }
            String h = Integer.toString(hour);
            String m = Integer.toString(minute);
            if (minute < 10) {
                m = '0' + m;
            }
            if (!result.contains(h + ":" + m)) {
                result.add(h + ":" + m);
            }
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (led[i] == 0) {
                led[i] = 1;
                dfs(num - 1, led);
                led[i] = 0;
            }
        }
    }
}

Leetcode(103) Binary Tree Zigzag Level Order Traversal

发表于 2018-07-25 | 更新于 2019-10-06 | 分类于 Leetcode刷题笔记

Description:

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

解法：

这道题需要仔细一点，虽然思路很简单，但是有点绕。要实现之字形走位，因为相邻行的方向不同，考虑使用两个栈进行操作，并且两个栈的进栈顺序也不同，一个先进右节点，一个先进左节点，具体代码如下：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(root);
        while (!s1.empty() || !s2.empty()) {
            if (s2.empty()) {
                List<Integer> tmp = new ArrayList<Integer>();
                while (!s1.empty()) {
                    TreeNode now = s1.pop();
                    if (now.left != null) {
                        s2.push(now.left);
                    }
                    if (now.right != null) {
                        s2.push(now.right);
                    }
                    tmp.add(now.val);
                }
                result.add(tmp);
            } else {
                List<Integer> tmp = new ArrayList<Integer>();
                while (!s2.empty()) {
                    TreeNode now = s2.pop();
                    if (now.right != null) {
                        s1.push(now.right);
                    }
                    if (now.left != null) {
                        s1.push(now.left);
                    }
                    tmp.add(now.val);
                }
                result.add(tmp);
            }
        }
        return result;
    }
}

另一种思路：层序遍历，然后对于某些层在输出时翻转list即可：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        int level = 1;
        Queue<TreeNode> q = new LinkedList<>();
        Stack<TreeNode> s = new Stack<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> tmplist = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode tmp = q.poll();
                tmplist.add(tmp.val);
                if(tmp.left!=null){
                    q.offer(tmp.left);     
                } 
                if(tmp.right!=null){
                    q.offer(tmp.right);      
                }
            }
            if(level%2==0){
                for(int i = 0;i<tmplist.size()/2;i++){
                    int tmp = tmplist.get(i);
                    tmplist.set(i,tmplist.get(tmplist.size() - i - 1));
                    tmplist.set(tmplist.size() - i - 1,tmp);
                }
                res.add(tmplist);
            }
            else{
                res.add(tmplist);
            }
            level++;
        }
        return res;
    }
}

Leetcode(61) Rotate List

发表于 2018-07-22 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a linked list, rotate the list to the right by _k_ places, where _k_ is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2

Output: 4->5->1->2->3->NULL

Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4

Output: 2->0->1->NULL

Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL

解法：

考虑到是移动链表题，而单向链表不太好进行回退操作，故考虑将其先变为循环链表，然后根据原链表的长度与移动的次数确定在哪个位置进行断开和指定谁为右移后的头指针。经过分析可得，从原始链表头指针往后走n- 1 - k % n个节点就到达新链表的头结点前一个点（n为链表长度）。具体实现代码如下：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int count = 0;
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
            count++;
        }
        tmp.next = head;
        tmp = head;
        for (int i = 1; i <= count - k % (count + 1); i++) {
            tmp = tmp.next;
        }
        head = tmp.next;
        tmp.next = null;
        return head;
    }
}

Leetcode(74) Search a 2D Matrix

发表于 2018-07-22 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Write an efficient algorithm that searches for a value in an _m_ x _n_ matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

解法：

搜索题，如果遍历整个矩阵一定是超时的，不过因为矩阵的排列存在大小规律，可以根据这一特点调整搜索策略，先根据大小关系定位目标可能在的行，然后再遍历该行查找目标。值得注意的是需要考虑边界条件。具体实现的代码如下：

class Solution {
    public boolean searchMatrix(int\[\]\[\] matrix, int target) {
        if (matrix.length == 0 || matrix\[0\].length == 0) {
            return false;
        }
        int resulti = 0;
        boolean result = false;
        for (int i = 0; i < matrix.length; i++) {
            if (target < matrix\[i\]\[0\]) {
                resulti = i - 1;
                result = true;
                break;
            } else if (target == matrix\[i\]\[0\]) {
                return true;
            }
            if (i == matrix.length - 1) {
                resulti = i;
                result = true;
            }
        }
        if (!result) {
            return result;
        }
        if (resulti == -1) {
            return false;
        }
        for (int j = 0; j < matrix\[resulti\].length; j++) {
            if (matrix\[resulti\]\[j\] == target) {
                return true;
            }
        }
        return false;
    }
}

Leetcode(106) Construct Binary Tree from Inorder and Postorder Traversal

发表于 2018-07-21 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

解法：

根据后序和中序遍历还原二叉树，解法与Leetcode(105) Construct Binary Tree from Preorder and Inorder Traversal类似。代码如下：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode res = mybuild(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        return res;
    }

    private TreeNode mybuild(int[] inorder, int startin, int endin, int[] postorder, int startpost, int endpost) {
        if (startin > endin || startpost > endpost) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[endpost]);
        for (int i = startin; i <= endin; i++) {
            if (inorder[i] == root.val) {
                root.left = mybuild(inorder, startin, i - 1, postorder, startpost, startpost + i - startin - 1);
                root.right = mybuild(inorder, i + 1, endin, postorder, startpost + i - startin, endpost - 1);
            }
        }
        return root;
    }
}

Leetcode(105) Construct Binary Tree from Preorder and Inorder Traversal

发表于 2018-07-21 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

解法:

题意简洁明了，即根据二叉树的前序遍历结果与中序遍历结果还原二叉树。（倒吸一口凉气啊，我真的对递归有阴影）。首先分析各顺序遍历的特点，具体如下：

特性A，对于前序遍历，第一个肯定是根节点；
特性B，对于后序遍历，最后一个肯定是根节点；
特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；

我们以一个例子做一下这个过程，假设：

前序遍历的顺序是: CABGHEDF
中序遍历的顺序是: GHBACDEF

第一步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。

1
2
3

    C
 /     \
GHBA   DEF

第二步，取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。

第三步，使用同样的方法，前序是BGH，中序是GBH，得出父节点是B，G和H分别是左右节点。

第四步，回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。

           C
        /     \
       A        E
      /       /    \
     B       D      F
   /    \
  G      H

到此，我们得到了这棵完整的二叉树，因此，它的后序遍历就是：GHBADFEC。

那么，思路变得简单了（0.0），即对于现有的序列，先确定根节点，根节点的左子树，根节点的右子树序列，然后在各子树中递归建树。递归的终止条件为序列为空（体现在起始值与终止值上）。

具体实现如下：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode res = mybuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return res;
    }

    private TreeNode mybuild(int[] preorder, int startpre, int endpre, int[] inorder, int startin, int endin) {
        if (startpre > endpre || startin > endin) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[startpre]);
        for (int i = startin; i <= endin; i++) {
            if (inorder[i] == root.val) {
                root.left = mybuild(preorder, startpre + 1, startpre + i - startin, inorder, startin, i - 1);
                root.right = mybuild(preorder, startpre - startin + i + 1, endpre, inorder, i + 1, endin);
            }
        }
        return root;
    }
}

Leetcode(36) Valid Sudoku

发表于 2018-07-20 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid. The Sudoku board could be partially filled, where empty cells are filled with the character '.'. Example 1:

Input:
[
[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],
[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],
[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],
[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],
[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],
[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],
[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]
]
Output: true

Example 2:

Input:
[
[“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],
[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],
[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],
[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],
[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],
[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],
[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.

解法：

此题无需判断数独是否有解，只需要保证3个基本条件，即每一行的元素不重复，每一列的元素不重复，每一个子格的元素不重复。对于重复的判断，借用数据结构Map（因为Map的Key不允许重复）。

整体上来看，判断是否重复的对象为9行，9列，9个子格，故外层需循环9次。而内层循环针对外层循环的内部元素进行循环。对于行，列，子格，其内部都有9个最小单位元素。

对于行而言，第i行对应的元素为

1	board[i][j]

对于列而言，第i列对应的元素为

1	board[j][i]

对于子格元素的对应

观察行号规律：

第0个九宫格：000111222; 第1个九宫格：000111222; 第2个九宫格：000111222;

第3个九宫格：333444555; 第4个九宫格：333444555; 第5个九宫格：333444555;

第6个九宫格：666777888; 第7个九宫格：666777888; 第8个九宫格：666777888;

可见对于每三个九宫格行号增3；对于单个九宫格，每三个格点行号增1。

因此第i个九宫格的第j个格点的行号可表示为i/3*3+j/3

观察列号规律：

第0个九宫格：012012012; 第1个九宫格：345345345; 第2个九宫格：678678678;

第3个九宫格：012012012; 第4个九宫格：345345345; 第5个九宫格：678678678;

第6个九宫格：012012012; 第7个九宫格：345345345; 第8个九宫格：678678678;

可见对于下个九宫格列号增3，循环周期为3；对于单个九宫格，每个格点行号增1，周期也为3。

周期的数学表示就是取模运算mod。

因此第i个九宫格的第j个格点的列号可表示为i%3*3+j%3

故为：

1	board[i/33 + j/3][i%33 + j%3]

具体代码如下：

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            Map<Character, Boolean> judge_row = new HashMap<Character, Boolean>();
            Map<Character, Boolean> judge_col = new HashMap<Character, Boolean>();
            Map<Character, Boolean> judge_sub = new HashMap<Character, Boolean>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (judge_row.containsKey(board[i][j])) {
                        return false;
                    }
                    judge_row.put(board[i][j], true);
                }
                if (board[j][i] != '.') {
                    if (judge_col.containsKey(board[j][i])) {
                        return false;
                    }
                    judge_col.put(board[j][i], true);
                }
                if (board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] != '.') {
                    if (judge_sub.containsKey(board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3])) {
                        return false;
                    }
                    judge_sub.put(board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3], true);
                }
            }
        }
        return true;
    }
}