leetcode刷题学习（6）

前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。

 

一、实现Trie（前缀树）（题号：208）

    描述：实现一个前缀树Trie，包含insert、search和startWith三个主要操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

 

    说明：

    1）你可以假设所有的输入都是小写字母a-z构成的。

    2）保证所有输入均为非空字符串。

 

    解题思路：前缀树的实现，基本算法数据结构，通常适用在字典单词搜索场景。

 

public class TestMain {


    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));//true
        System.out.println(trie.search("app"));//false
        System.out.println(trie.startWith("app")); //true
        trie.insert("app");
        System.out.println(trie.search("app"));//true
    }

    public static class TrieNode {

        char val;//值
        boolean isWord;
        //26个常规字符，每个字符为一个子节点。
        TrieNode[] children = new TrieNode[26];

        // Initialize your data structure here.
        public TrieNode() {
        }

        public TrieNode(char c) {
            this.val = c;
        }
    }

    /**
     * 多叉树
     * 每个节点，都有26个字母的子节点，有值的子节点表示word字符被覆盖。
     * word的长度，决定了树的深度
     * 前缀，只需要逐层一次比较，search的字符串每个字符依次在每层树上是否存在。
     * 需要注意，JAVA API中String.startWith方法并不是基于前缀树实现。（无需额外的使用空间）
     * 前缀树，主要用于做字典搜索。
     */
    public static class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
            root.val = ' ';//卫星节点为空
        }

        /**
         * 结构示意
         *                 root
         *           a  b  c  b  e ...
         *       a b c ...
         * 可以多次插入不同的word
         * @param word
         */
        public void insert(String word) {
            TrieNode node = root;//从root节点开始
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';//a为0号索引
                //如果此子节点尚未赋值
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode(word.charAt(i));
                }
                node = node.children[index];//每一个字符，占用树的一层。
            }
            //一个完整word结束，打标记
            //通过search，查找时，只有匹配一个完整word才返回true，即精确查询
            //startWith才支持前缀查询
            node.isWord = true;
        }

        //精确查询一个word是否在前缀树中
        public boolean search(String word) {
            TrieNode node = find(word);
            //存在一个完整的树路径，且路径的终点节点为word结束符。
            return node == null ? false : node.isWord;
        }

        private TrieNode find(String target) {
            TrieNode node = root;
            for (int i = 0; i < target.length(); i++) {
                int index = target.charAt(i) - 'a';
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }

        //前缀匹配
        public boolean startWith(String prefix) {
            TrieNode node = find(prefix);
            return node != null;
        }
    }
}

 

二、数组中的第K个最大元素（题号：215）

    在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

    说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

 

  解题思路：常规思路，排序队列。

public class TestMain {


    public static void main(String[] args) {
        int[] source = {3,2,1,5,6,4};
        System.out.println(execute(source,2));
    }

    public static int execute(int[] source,int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int i : source) {
            queue.offer(i);
        }
        while (k > 1) {
            queue.poll();
            k--;
        }
        return queue.poll();
    }
}

 

 

三、翻转二叉树（题号：226）

    描述：翻转一个二叉树。我们暂且假定，此二叉树为完全二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

 

    解题思路：就想先前遇到的题目一样，检测一个二叉树是否为镜像二叉树。此题的设计方式比较多，我们仅展示一种。

public class TestMain {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(7);
        TreeNode n3 = new TreeNode(1);
        TreeNode n4 = new TreeNode(3);
        TreeNode n5 = new TreeNode(6);
        TreeNode n6 = new TreeNode(9);

        root.left = n1;
        root.right = n2;

        n1.left = n3;
        n1.right = n4;

        n2.left = n5;
        n2.right = n6;

        execute(root.left,root.right);
        System.out.println(root);
    }

    private static void execute(TreeNode left,TreeNode right) {

        int t = left.value;
        left.value = right.value;
        right.value = t;

        TreeNode l1 = left.left;
        TreeNode r1 = right.right;
        if (l1 == null || r1 == null) {
            return;
        }
        execute(l1,r1);
        TreeNode l2 = left.right;
        TreeNode r2 = right.left;
        if (l2 == null || r2 == null) {
            return;
        }
        execute(l2,r2);
    }


    public static class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}

 

四、基本计算器（题号：227）

    描述：实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。

    说明：数字为0 -9个位数；你可以认为给定的表达式是有效的。

示例 1:

输入: "3+2*2"
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5

 

    解题思路：只需要注意，计算符是有优先级的，比如*、/比+、-优先级高；我们用栈来存储计算的过程和结果。

public class TestMain {

    public static void main(String[] args) {
        System.out.println(execute("3+2*2"));
        System.out.println(execute(" 3/2 "));
        System.out.println(execute(" 3+5 / 2 "));
    }
    /**
     * 需要注意，计算符为 +，-，*，/
     * 计算符是有优先级的，*，/优先级一样，且高于 +，-
     * 在迭代时，如果遇到 *，/则直接计算，遇到+，-则先入栈准备
     * 解析完毕完毕之后，队列（或者栈）只有 + ，-操作，即可直接计算。
     * 忽略其中的空格。
     * @param source
     * @return
     */
    private static int execute(String source) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < source.length(); i++) {
            char value = source.charAt(i);
            if (value == ' ') {
                continue;
            }
            //如果是计算符号，则直接存储在stack中
            if (!Character.isDigit(value)) {
                stack.push(value);
                continue;
            }
            //首个计算数字，直接存储。
            if (stack.isEmpty()) {
                stack.push(value);
                continue;
            }

            char sign = stack.peek();
            //如果当前计算符为+、-，因为优先级较低，则先暂存。
            if (sign == '+' || sign == '-') {
                stack.push(value);//减去0，就是原始的值
                continue;
            }
            //对于*、/计算符，则直接计算，从队列中弹出计算符和前一个数字
            stack.pop();//符号
            char x = stack.pop();
            //将计算结果入栈
            stack.push(calculate(x,value,sign));
        }

        //stack中剩下的元素，为+,-，直接计算就行
        //取出最后一个作为结果
        char result = stack.pop();
        while (!stack.isEmpty()) {
            char sign = stack.pop();
            char x = stack.pop();
            result = calculate(x,result,sign);
        }
        return Character.digit(result,10);//十进制数字
    }

    private static char calculate(char x, char y,char sign) {
        if (sign == '+') {
            return  (char)(x + y -'0'); // (x-'0') + (y-'0') + '0';
        }
        if (sign == '-') {
            return  (char)(x - y - '0');
        }
        if (sign == '*') {
            return  (char)((x - '0') * (y - '0') + '0');
        }
        if (sign == '/') {
            return  (char)((x - '0') / (y - '0') + '0');
        }
        return '0';
    }
}

 

五、二叉搜索树的最近公共祖先（题号：235）

    描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    说明：

    1）二叉搜索树

    2）节点值没有重复

    例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

 

   

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

  

    解题思路：二叉树为二叉搜索树，不过这个并不影响程序的实际设计，只不过可以减少查询的次数。我们分别在一个node上，对其左、右节点搜索p、q，如果都能找到，则此节点即为最近祖先。此外，如果二叉树为普通二叉树，我们只需要改进代码中，将左右节点都搜索即可。（题号：236）

public class TestMain {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(8);
        TreeNode n3 = new TreeNode(0);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(7);
        TreeNode n6 = new TreeNode(9);
        TreeNode n7 = new TreeNode(3);
        TreeNode n8 = new TreeNode(5);

        root.left = n1;
        root.right = n2;

        n1.left = n3;
        n1.right = n4;

        n2.left = n5;
        n2.right = n6;

        n4.left = n7;
        n4.right = n8;
        TreeNode result = execute(root,2,8);
        System.out.println(result.value);
    }

    private static TreeNode execute(TreeNode node,int x,int y) {
        if (node == null) {
            return null;
        }
        int value = node.value;
        if (value == x || value == y) {
            return node;
        }
        TreeNode ln = null;
        if (value > x || value > y) {
            ln = execute(node.left,x,y);
        }
        TreeNode rn = null;
        if (value <= x || value <= y) {
            rn = execute(node.right, x, y);
        }
        if (ln != null && rn != null) {
            return node;
        }
        return null;
    }

    public static class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}

 

    如果二叉树不是搜索树，而是普通的二叉树，此题的解题方式需要变化，当某个节点被扎到之后，仍然需要遍历其子节点。（题号：236，二叉树的最近公共祖先）

public class TestMain {


    /**
     * 如果二叉树不是搜索树，需要完全遍历左右子树
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode execute(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = execute(root.left, p, q);
        TreeNode right = execute(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    public static class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}

 

 

六、除自身以外数组的乘积（题号：238）

    描述：给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

    说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

    解题思路：“不能使用除法”，直接扼杀了我们一条极其简单的实现途径。这个题仔细思考，其实并不复杂，我们可以认为，结果数组的任何一个索引位置的值，都可以看成原始数组元素“左边所有数组的乘积” * “右边所有数组元素的乘积”，这样就把当前元素排除在外了。

public class TestMain {

    public static void main(String[] args) {
        int[] source = {1,2,3,4};
        int[] result = execute(source);
        System.out.println(result);
    }

    /**
     *
     * 我们期望得到的结果为,数字为索引号
     * [(1) * (2) * (3),(0) * (2) *(3),(0) * (1) * (3),(0) * (1) * (2)]
     * 每个结果元素为n -1个元素乘积。可以看成，结果值，等于此元素左边所有元素的乘积 * 右边所有元素的乘积。
     * 如果其左、右没有元素，则用1补位
     * 我们只需要通过从左到右、从右到左扫描一遍即可。
     * 从左到右，计算当前元素左右值的所有元素乘积
     * [1,(0),(0) * (1),(0) *(1) * (2)]
     * 从右到左
     * [(1) * (2) * (3),(2) *(3),(3),1]
     * @param source
     * @return
     */
    private static int[] execute(int[] source) {
        int n = source.length;
        int[] result = new int[n];
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * source[i - 1];
        }
        int right = 1;
        //从右到左，也是类似于从左到右
        //right = 此元素
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= source[i];
        }
        return result;
    }
}

 

七、对栈实现队列（题号：232）

    使用栈实现队列的下列操作：

    1）push(x) -- 将一个元素放入队列的尾部。

    2）pop() -- 从队列首部移除元素。

    3）peek() -- 返回队列首部的元素。

    4）empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

 

    说明：只能使用标准的栈API或者操作。

    解题思路：JAVA中提供了Stack API，栈为LIFO，队列为FIFO，元素的输出的顺序刚好相反。一个栈肯定无法完成要求，既然顺序相反，经过一次反转刚好；所以我们使用两个栈。

public class TestMain {

    public static void main(String[] args) {

    }

    public static class StackQueue<T> {

        private Stack<T> input = new Stack<>();

        private Stack<T> output = new Stack<>();

        public void push(T item) {
            input.push(item);
        }

        public T pop() {
            exchange();
            return output.pop();
        }

        private void exchange() {
            if (!output.isEmpty()) {
                return;
            }
            if (input.isEmpty()) {
                return;
            }
            //顺序颠倒一次
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        public  T peek() {
            exchange();
            return output.peek();
        }

        public boolean isEmpty() {
            exchange();
            return output.isEmpty();
        }

    }
}

 

八、滑动窗口最大值（题号：239）

    给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

 

    注意：你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。 

public class TestMain {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口，窗口尺寸为k。所以窗口期内只保存k个元素，窗口则向后移动1，则移除窗口左侧元素、在右侧增加一个新元素
     * 则需要计算一次最大值。这个特征非常像队列，既然求最大值，则还需要排序。
     * 这个特点非常符合java中的PriorityQueue.
     * 也能使用treemMap,不过对重复数据则很难处理
     * @param source
     * @param k
     * @return
     */
    public static int[] execute(int[] source, int k) {
        if (source == null || source.length == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        int[] result = new int[source.length - k + 1];
        for (int i = 0; i < source.length; i++) {
            //首个元素需要满足一个窗口期
            if (i < k) {
                queue.offer(source[i]);
                if (i == k - 1) {
                    result[0] = queue.peek();
                }
            } else {
                //移除左侧元素
                queue.remove(source[i - k]);
                //增加右侧元素
                queue.offer(source[i]);
                //计算最大值
                result[i - k + 1] = queue.peek();
            }
        }
        return result;
    }

}

 

 

九、丑数II（题号：264）

    描述：编写一个程序，找到第n个丑数。丑数就是只包含质因数2、3、5的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

 

    说明：1是丑数。

    解题思路：跟质数的计算有所不同，只有丑数质因数相乘才能得出丑数，一个现有的丑数与任意质因数相乘也是丑数。考虑到有序性，现有丑数与质因数相乘的结果时，需要比较大小。

public class TestMain {

    public static void main(String[] args) {
        System.out.println(execute(10));
    }

    /**
     * 丑数：只包含 2、3、5质因数的正整数，其中1为丑数。
     */
    private static int execute(int n) {
        //已经计算好的历史丑数
        //丑数 * 丑数质因数，才是丑数，这个原则决定了下面的计算方式
        int[] result = new int[n];
        result[0] = 1;
        // 2，3，5分别参与计算历史丑数的位置（被乘的位置）
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        //2，3，5作为质因数，各自参与累乘的值
        int f2 = 2;
        int f3 = 3;
        int f5 = 5;


        //规律，(参与乘法的，也必须为质因数，这些质因数来自历史的结果)
        // 2：(1) * 2，     (2) * 2，           (4) * 2 ..
        // 3:       (1) * 3        (2) * 3
        // 5:                  (1) * 5               (2) * 5
        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(f2, f3), f5);
            result[i] = min;
            //有可能某次的结果，会与f2,f3,f5中多个值相等
            // 比如6，2 * 3，和3 * 2相同，此时他们都需要向前推进。
            if (f2 == min) {
                f2 = 2 * result[++i2];
            }
            if (f3 == min) {
                f3 = 3 * result[++i3];
            }
            if (f5 == min) {
                f5 = 5 * result[++i5];
            }
        }
        return result[n - 1];
    }


}

 

十、缺失数字（题号：268）

    给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2
示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

 

    解题思路：这个题应该是个初、高中数学题，0 ~ n数字的累加和为 n * (n + 1) /2，给定的序列数字之和与n累加和的差值就是缺失的数字。

 

十一、H指数（题号：274）

    描述：给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”

示例:

输入: citations = [3,0,6,1,5]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

 

   说明：如果h有多种可能的值，h指数是其中最大的那个。（此条件决定，我们下文中遍历数组的顺序）

public class TestMain {


    public static void main(String[] args) {
        int[] source = {3,0,6,1,5};
        System.out.println(source);
    }

    /**
     * 至少H个数字值大于H。H可以不是source中存在的值。H是个"元素的个数"。
     *
     * 1）按照如下算法，排序之后，也可以使用二分查找来优化。
     * @param source
     * @return
     */
    private static int execute(int[] source) {
        if (source == null || source.length == 0) {
            return 0;
        }
        //排序，有时候我们做算法题，就不敢考虑排序，总感觉"不对路"
        //此题，排序之后，问题迎刃而解
        Arrays.sort(source);
        int length = source.length;
        for(int i = 0; i < length; i++) {
            int value = source[i];
            if (value >= length - i) {
                return length - i;
            }
        }
        return 0;
    }
}

 

十二、完全平方数（题号：279）

    描述：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

 

    解题思路：这个题最聪明的方式就是“四平方个数定理”；不过，比较理解的方式就是“动态规划”。

public class TestMain {

    public static void main(String[] args) {
        System.out.println(execute(12));
    }

    /**
     * 动态规划
     * @param n
     * @return
     */
    private static int execute(int n) {
        int result = n;//最大为n个1平方
        int i = 2;//每个余数都从2开始计算
        while (true) {
            //依次取平方
            int value = i * i;
            //超限则返回
            if (value > n) {
                break;
            }
            //t为i平方的个数，n = t * (i * i) + ?
            int t = n / (value);
            //余数，继续按照此规则
            int next = n % (value);
            result = Math.min(result, t + execute(next));
            i++;
        }
        return result;
    }
}

 
十三、移动零（题号：283）

    描述：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

 

    说明：

    1）必须在原数组上操作，不能拷贝额外的数组。

    2）尽量减少操作的次数。

 

   解题思路：乍一看，这题简直很难啊，似乎没什么思路；其实很简单，就是冒泡排序的一种变种嘛；我们设计一个指针，用于指向0元素的元素，将非零的与其交换，并将0向前推进即可。

public class TestMain {

    public static void main(String[] args) {
        int[] source = {0,1,3,0,5};
        execute(source);
        System.out.println(source);
    }

    private static void execute(int[] source) {
        int index = -1;
        for(int i = 0; i < source.length; i++) {
            int value = source[i];
            if (value == 0 && index == -1) {
                index = i;
                continue;
            }
            if (value != 0) {
                if (index == -1) {
                    continue;
                }
                source[index] = value;
                source[i] = 0;
                index++;
            }

        }
    }
}