第一题: 17. 电话号码的字母组合

LeetCode: 17. 电话号码的字母组合

描述:
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解题思路:

1. 首先使用哈希表将对应的数字和字符串放入哈希表中.
2. 然后使用回溯
3. 去遍历digits中数字对应的字符串, 然后进行拼接
4. 当拼接的字符串长度和digits.length()一样之后, 添加到结果集中.

代码实现:

class Solution {
    private List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return list;
        Map<Integer,String> map = new HashMap<>();
        map.put(2,"abc");
        map.put(3,"def");
        map.put(4,"ghi");
        map.put(5,"jkl");
        map.put(6,"mno");
        map.put(7,"pqrs");
        map.put(8,"tuv");
        map.put(9,"wxyz");
        StringBuilder res = new StringBuilder();
        backtracking(digits,map,0,res);
        return list;
    }

    public void backtracking(String digits, Map<Integer,String> map, int index, StringBuilder res) {
        if(index == digits.length()){
            list.add(res.toString());
            return;
        }
        String str = map.get(digits.charAt(index) - '0');
        for (int i = 0; i < str.length(); i++) {
            res.append(str.charAt(i));
            backtracking(digits,map,index+1,res);
            res.deleteCharAt(res.length()-1);
        }
    }
}

第二题: 108. 将有序数组转换为二叉搜索树

LeetCode: 108. 将有序数组转换为二叉搜索树

描述:
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路:

1. 首先这里给的数组已经按升序排序了, 使用二分查找就可以找到每个根节点.
2. 首先使用二分查找找到根节点, 再去找左子树, 找右子树.
3. 递归去查找, 直到 left > right ,

代码实现:

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return ToBST(nums,0,nums.length-1);
    }
    public TreeNode ToBST(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = ToBST(nums,left,mid-1);
        root.right = ToBST(nums,mid+1,right);
        return root;
    }
}

第三题: 116. 填充每个节点的下一个右侧节点指针

LeetCode: 116. 填充每个节点的下一个右侧节点指针

描述:
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解题思路:

1. 使用层序遍历
2. 把每一层的节点, 按顺序进行串联.
3. 注意为空的情况 要进行判断.

代码实现:

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size != 0) {
                Node top = queue.poll();
                if(size != 1){
                    top.next = queue.peek();
                }
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
        }
        return root;
    }
}

第四题: 162. 寻找峰值

LeetCode: 162. 寻找峰值

描述:
峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

解题思路:

1. 由于时间复杂度的限制, 这里使用二分查找
2. 如果 nums[mid] > nums[mid+1] , 峰值在左边, 让 right = mid
3. 如果 nums[mid] < nums[mid+1], 峰值在右边, 让 left = mid + 1
4. 循环去找, 直到 right <= left, 结束循环
5. left下标就是峰值

代码实现:

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid+1]){
                right = mid;;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
}

第五题: 171. Excel 表列序号

LeetCode: 171. Excel 表列序号

描述:
给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

解题思路:

1. 这里相当于26进制转成10进制
2. ans = (ans * 原进制数) + (10进制表示的数字) (ans初始为0)

代码实现:

class Solution {
    public int titleToNumber(String columnTitle) {
        int ans = 0;
        for(int i = 0; i < columnTitle.length() ;i++) {
            ans =(ans * 26) + (columnTitle.charAt(i)-'A'+1);
        }
        return ans;
    }
}

第六题: 172. 阶乘后的零

LeetCode: 172. 阶乘后的零

描述:
给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

解题思路:

1. 本题就是统计5的个数, 只有和5和5的倍数的数相乘才会出现0
2. 这里就循环的去查看n里5个数

代码实现:

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while( n / 5 != 0) {
            count += n/5;
            n /= 5;
        }
        return count;
    }
}