第一题: 零矩阵

LeetCode: 面试题 01.08. 零矩阵
描述:
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

解题思路:

题目意思是只要第 i 行 第 j 列某个元素为0, 则该行该列所有元素都为0
这里使用标记法,

1. 首先遍历一次, 如果当前元素为0, 记录当前 i 和 j 的坐标.
2. 再次遍历, 如果当前 i 和 j 的坐标被标记, 就让当前元素等于0

代码实现:

class Solution {
    public void setZeroes(int[][] matrix) {
    	// 使用两个boolean数组来进行标记
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];
        // 第一次遍历用来标记
        for(int i = 0; i < matrix.length ; i++) {
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        // 第二次遍历, 用来置零
        for(int i = 0; i < matrix.length ; i++) {
            for(int j = 0; j < matrix[0].length; j++){
                if(row[i] || col[j]){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

第二题: 合法二叉搜索树

LeetCode: 面试题 04.05. 合法二叉搜索树
描述:
实现一个函数，检查一棵二叉树是否为二叉搜索树。

解题思路:

判断是否是二叉搜索树, 就相当于判断中序遍历是不是有序的
这里使用 中序遍历递归的方式进行.

1. 判断左子树是否小于根节点
2. 判断右子树是否大于根节点
3. 防止右子树出现的值小于最开始的根节点
4. 防止左子树出现的值大于最开始的根节点

代码实现:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isBST(TreeNode root,long min,long max) {
    	// 为空返回true
        if(root == null) return true;
        // 不满足这个范围就返回false [min,max]
        if(root.val <= min || root.val >= max) return false;
		// 遍历左子树右子树
        return isBST(root.left,min,root.val) && isBST(root.right,root.val,max);
    }
    
}

第三题: 特定深度节点链表

LeetCode: 面试题 04.03. 特定深度节点链表
描述:
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

解题思路:

这里就相当于是层序遍历, 把每一层的节点用链表连起来
注意这里的转链表的过程

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        if(tree == null) return null;
        // 首先使用list来存放节点
        List<ListNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        while(!queue.isEmpty()) {
        	// 用tmp来链接这一层的节点
            ListNode tmp = new ListNode(-1);
            // 用ret标记初始tmp节点位置
            ListNode ret = tmp;
            int size = queue.size();
            while(size != 0) {
                TreeNode top = queue.poll();
                // 链接节点
                tmp.next = new ListNode(top.val);
                tmp = tmp.next;
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
            // 因为最初的节点是-1, 他的下一节点之后的内容才是需要的.
            list.add(ret.next);
        }
        // 将list的内容转化成数组
        ListNode[] ans = new ListNode[list.size()];
        for(int i = 0; i < list.size(); i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

第四题: 检查平衡性

LeetCode: 面试题 04.04. 检查平衡性
描述:
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

解题思路:

1. 对于当前遍历到的节点, 先判断他的左右子树是否平衡, 再判断以当前节点为根的树是否平衡
2. 如果子树平衡, 返回子树的高度
3. 如果子树不平衡, 那么整个树都不会平衡, 返回-1

代码实现:

class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) >= 0 ;
    }
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftHigh = maxDepth(root.left);
        int rightHight = maxDepth(root.right);
        // 首先判断子树是否平衡, 平衡返回高度.
        if(leftHigh >= 0 && rightHight >= 0 && Math.abs(leftHigh-rightHight) <= 1){
            return Math.max(leftHigh,rightHight)+1;
        }else{
            return -1;
        }
    }
}

第五题: 回文排列

LeetCode: 面试题 01.04. 回文排列
描述:
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。

解题思路:

1. 使用一个数组来记录当前字符出现的次数
2. 如果字符为出现次数为奇数, 那么出现奇数的次数的字符不能超过1个
3. 超过就是false

代码实现:

class Solution {
    public boolean canPermutePalindrome(String s) {
        int count = 0;
        int[] arr = new int[128];
        for(char c : s.toCharArray()){
            arr[c]++;
        }
        for(int val : arr){
            // 记录奇数次数字符的个数
            if(val % 2 == 1){
                count++;
            }
            // 超过一个就是false;
            if(count > 1) {
                return false;
            }
        }
        return true;
    }
}

第六题: 判定字符是否唯一

LeetCode: 面试题 01.01. 判定字符是否唯一
描述:
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

解题思路:

这里不使用额外的数据结构, 那么可以使用数组的方式进行判定
用数组的方式记录下当前的字符个数
如果超过1个就返回false;

代码实现:

class Solution {
    public boolean isUnique(String astr) {
        int[] arr = new int[26];
        for(int i = 0;i < astr.length();i++){
            arr[astr.charAt(i) - 'a']++;
            if(arr[astr.charAt(i)-'a']>1){
                return false;
            }
        }
        return true;
    }
}