leetcode刷题学习（4）

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

 

一、从前序与中序遍历序列构造二叉树（题号：105）

    描述：根据一棵树的前序遍历与中序遍历构造二叉树。

    注意：我们假设树中没有重复的元素。

输入：
前序遍历：[3,9,20,15,7]
中序遍历：[9,3,15,20,7]

返回二叉树：
        3
      /   \
    9     20
          /   \
        15    7

 

    解题思路：前序遍历的首个元素，一定是根节点；然后从中序遍历中找到此根节点的位置，根节点左侧的所有元素为左子树，右侧为右子树。前序遍历的特征为左子树遍历完毕之后才会遍历右子树，所以我们可以根据中序遍历的结果、结合前序遍历，来判断左子树、右子树在前序遍历的位置；此外前序遍历的任何子树的第一个节点总是此子树的根节点。分析思路：

    1、从前序遍历中首个字符3，作为根节点。从中序遍历结果中，找到3个位置，并找到左子树、右子树的区间和区间长度。

    2、[9] 3 [15,20,7]；我们得知[9]为左子树，元素个数为1；[15,20,7]为右子树，元素个数为3。（主要用于计算左右子树的元素个数）

    3、前序遍历根节点开始，其后"1"元素为左子树，然后是3个元素右子树。因此[9]为左子树，[20,15,7]为右子树。

    4、根据3、，我们知道每个子树，在前序遍历中，第一个元素仍然是子树的根元素，即 9为左子树的根元素，20为右子树的根元素。

    5、递归方式1、,9元素所在子树没有其他元素，则终止。20作为根元素，根据中序遍历的子树（即[15,20,7]），其左子树为[15]，右子树为[7]。

 

public class TestMain {


    public static void main(String[] args) {
        int[] preOrder =  {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        TreeNode root = execute(preOrder,0,preOrder.length - 1,inorder,0,inorder.length - 1);
        System.out.println(root);
    }

    private static TreeNode execute(int[] preOrder,int ps,int pe,int[] inOrder,int is,int ie) {
        int rv = preOrder[ps];
        TreeNode root = new TreeNode(rv);
        int i = is;
        for (;i < ie + 1;i++) {
            if (inOrder[i] == rv) {
                break;
            }
        }
        //左右子树，均符合前序、中序的规则；每个子树递归处理
        //左子树
        if (ps < pe) {
            root.left = execute(preOrder, ps + 1, ps + (i - is), inOrder, is, i - 1);
        }
        //右子树
        if (i < ie) {
            root.right = execute(preOrder, ps + 1 + (i - is), pe, inOrder, i + 1, ie);
        }
        return root;
    }

    static class TreeNode {
        TreeNode left;
        TreeNode right;
        int value;
        TreeNode(int value) {
            this.value = value;
        }
    }
}

 

二、从中序和后序遍历序列中构造二叉树（题号：106）

    描述：给定一棵树的中序遍历和后序遍历构造二叉树。

    注意：你可以假定树中没有重复元素。

 

输入：
中序遍历：[9,3,15,20,7]
后序遍历：[9,15,7,20,3]
返回二叉树：
        3
      /   \
    9     20
          /   \
        15    7

 

   解题思路：可以参考上题（105）,实现上稍微有些不同，不过整体思路保持一致。

    1、后序遍历的特点，就是每个子树的最后一个元素为当前子树的根节点。比如，首次遍历3，为跟节点。

    2、然后从中序遍历中找到3，此值左边为左子树，右侧为右子树，我们可以知道左子树的元素个数为1，右子树元素个数为3。

    3、然后在根据后续遍历，3元素向前（左侧）3个元素为右子树，然后一个元素为左子树。即我们可以确定中序、后序遍历对应的左子树分别为[9]、[9]，右子树为[15,20,7]、[15,7,20]。

    4、根据3、继续使用1、规则开始遍历左右子树。

 

三、有序链表转换二叉搜索树（题号：109）

    描述：给定一个单链表，其中的元素按升序排列，将其转换成高度平衡的二叉搜索树。本题中，一个平衡二叉树是指一个二叉树的每个节点的左右两个子树的高度差的绝对值不超过1。

    提示：二叉搜索树，即任何一个节点，其左子节点值一定比其小，右子节点值大于等于其值。

    提示：单向链表中无重复节点值。

 

示例：
给定有序链表：[-10,-3,0,5,9]
一个可能的答案为：
         0
       /   \
     -3    9
     /      /
   10     5

 

    解题思路：既然链表是有序的，那么其中间节点即为根节点，根节点左侧所有元素为左子树，右侧为右子树；左、右子树继续二分，依次轮推。

 

public class TestMain {


    public static void main(String[] args) {
        ListNode root = new ListNode(-10);
        ListNode node = root;
        node = (node.next = new ListNode(-3));
        node = (node.next = new ListNode(0));
        node = (node.next = new ListNode(5));
        node = (node.next = new ListNode(9));
        TreeNode treeNode = execute(root,5);
        System.out.println(treeNode);
    }

    private static TreeNode execute(ListNode start,int length) {
        int m = length / 2;
        ListNode ps = start;
        for (int i = 0; i < m; i++) {
            ps = ps.next;
        }
        TreeNode root = new TreeNode(ps.value);
        if (m > 0) {
            root.left = execute(start, m);
        }
        if (length - m - 1 > 0) {
            root.right = execute(ps.next, length - m - 1);
        }
        return root;
    }

    static class ListNode {
        int value;
        ListNode next = null;
        ListNode(int value) {
            this.value = value;
        }
    }

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value) {
            this.value = value;
        }
    }

}

 

三、平衡二叉树（题目：110）

    描述：给定一个二叉树，判断它是否是高度平衡的二叉树。

    提示：平衡二叉树的定义为：一个二叉树的每个节点的左右两个子树的高度差的绝对值不超过1。

 

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

 

   解题思路：关键是”每个节点的左右子树的高度差不超过1“，所以每个节点的都遵守这个规则，即可判断。

 

public class TestMain {

    public static void main(String[] args) {

    }

    private static boolean execute(TreeNode node) {
        int x = count(node,0);
        return x > 0 ? true : false;
    }

    private static int count(TreeNode node,int count) {
        TreeNode left = node.left;
        TreeNode right = node.right;
        int l = 0;
        int r = 0;
        if (left != null) {
            l = count(left,count + 1);
        }
        if (right != null) {
            r = count(right,count + 1);
        }
        if (l == -1 || r == -1) {
            return -1;
        }

        int x = Math.abs(l - r);
        if (x > 1) {
            return -1;
        }
        return Math.max(l,r);
    }

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value) {
            this.value = value;
        }
    }
}

 

四、买卖股票的最佳时机（题号：121）

    描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易（即买入和卖出一只股票），设计一个算法来计算你所能获取的最大利润。

    提示：注意你不能在买入股票之前卖出股票。

 

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

 

    解题思路：动态规划，每个节点都有两种选择，买入或者卖出。

 

public class TestMain {

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

    /**
     *
     * @param source
     * @param b
     * @param i 当前索引
     * @return
     */
    private static int execute(int[] source,int b,int i) {
        if(i >= source.length) {
            return 0;
        }

        int v = source[i];//假定此时卖出

        //每个节点，都有两种选择：买、卖
        //如果已经买过，则可以卖。计算收益
        //如果没有买过，则可以买，并将收益计算传递到下一序列节点。

        //已经买过
        int p = source[b];//买入价格
        //后续买、卖的最大收益
        int x = execute(source, b, i + 1);
        int m = Math.max(x,v - p);//最大收益,v - p为现在就卖的收益

        //假定现在买
        int y = execute(source,i, i + 1);
        return Math.max(m,y);
        //
    }
}

 

五、分发糖果（题号：135）

    描述：老师给孩子们分发糖果，有N个孩子站成一条直线，老师根据每个孩子的表现，预先给他评分。你需要按照如下要求，帮助老师给这些孩子分发糖果：

    1）每个孩子至少分配到一个糖果。

    2）相邻的孩子中，评分高的孩子必须获得更多的糖果。（每次多分发一个）

    那么接下来，老师至少需要准备多少颗糖果呢？

 

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

 

    解题思路：每个孩子，首先获得一颗糖果，然后与其前后的孩子比较，如果高于前面的孩子则多分一个；如果还高于后面的孩子，继续多分一个。然后轮到下一个孩子，依次轮退，直到最后一个孩子。可以使用循环或者递归来解决。

 

public class TestMain {

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

    /**
     *
     * @param source
     * @param i 当前索引
     * @return
     */
    private static int execute(int[] source,int i) {
        if (i > source.length - 1) {
            return 0;
        }
        int v = source[i];
        int count = 1;//首先获得一个糖果，count表示当前小朋友获取的糖果数量
        if (i < source.length - 1) {
            int n = source[i + 1];
            if (v > n) {
                count++;//如果比后面的孩子评分高，则多获得一个
            }
        }
        if (i > 0) {
            int p = source[i - 1];
            if (v > p) {
                count++;//如果比前面的评分高，则多获得一个
            }
        }
        count += execute(source,i + 1);//总值相加
        return count;
    }
}

 

六、只出现一次的数字（题号：136）

    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

输入: [4,1,2,1,2]
输出: 4

 

    解题思路：位运算异或。

public class TestMain {

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

    /**
     * 异或，位运算，0 ^ 0 = 0,1 ^ 1 = 0, 1 ^ 0 = 1
     * 位相同，则为0，不同则为1，由此可见两个完全一样的数字，异或为0.
     * @param source
     * @return
     */
    public static int execute(int[] source) {
        int result = 0;
        for (int i = 0; i < source.length; i++) {
            result ^= source[i];
        }
        return result;
    }
}

 

 

七、单词拆分（题号：139）

    描述：给定一个非空字符串s和一个包含非空单词列表的字典wordDict，判断s是否可以被空格拆分为一个或者多个字典中出现的单词。

    说明：

    1）拆分时可以重复使用字典中的单词。

    2）你可以建设字典中没有重复的单词。

 

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

 

    解题思路：使用字典中的单词匹配s，如果匹配成功，那么s中剩余的子字符串也基于字典去匹配，直到s匹配结束。

 

public class TestMain {

    public static void main(String[] args) {
        String source = "leetcode";
        String[] wordDict = {"leet","code"};
        System.out.println(execute(source,0,wordDict));
    }

    /**
     *
     * @param source
     * @param i 当前索引
     * @return
     */
    private static boolean execute(String source,int i,String[] wordDict) {
        //如果已到结尾，则返回
        if (i >= source.length()) {
            return true;
        }
        boolean v = false;
        for (String dict : wordDict) {
            int l = dict.length();
            if (i + l <= source.length()) {
                String current = source.substring(i, i + l);
                if (!dict.equals(current)) {
                    continue;
                }
                //如果当前字典匹配，则比较剩余的子字符串是否仍然匹配
                boolean x = execute(source, i + l, wordDict);
                //只要有一个匹配，则认为成功
                if (x) {
                    return true;
                }
            }
        }
        return v;
    }
}

 

八、环形链表（题号：141）

    描述：给定一个链表，判断链表中是否有环。

    提示：节点值可能重复。

 

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

 

 

     解题思路：这个题相对比较简单，如果使用额外存储空间的话更简单；此题，有一个通用的解法，就是“快慢双指针”法，即前驱指针为快指针，每次向前2个（或者更多个）节点，慢指针每次向前一个节点，直到快指针结束或者快指针的next与慢指针吻合；原因是只要有环，即进入循环，快慢指针总会重合。

public class TestMain {

    public static void main(String[] args) {
        ListNode root = new ListNode(3);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(0);
        ListNode n4 = new ListNode(-4);

        root.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n2;
        System.out.println(execute(root));
    }

    /**
     *
     * @param i 当前索引
     * @return
     */
    private static boolean execute(ListNode node) {
        ListNode slow = node;
        ListNode fast = node;
        while (fast != null && fast.next != null) {
            if (slow == fast || slow == fast.next) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    static class ListNode {
        int value;
        ListNode next = null;
        ListNode(int value) {
            this.value = value;
        }
    }
}

 

九、LRU缓存机制（题号：146）

    描述：运用你掌握的数据结构，设计和实现一个LRU（最近最少使用）缓存机制。它应该支持如下操作：获取数据get和写入数据put。

    解题思路：这个题很实用，建议必备；重点为”最近最少使用“。使用合适的数据结构。JAVA中可以参考使用LinkedHashMap。

public class TestMain {

    public static void main(String[] args) {

    }

    public static class LRUCache {
        private LinkedHashMap<String,Object> mapper;
        private final int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            mapper = new LinkedHashMap<>(capacity * 2);
        }

        public void put(String key,Object value) {
            if (key == null) {
                return;
            }
            mapper.put(key,value);//先放入
            if (capacity > mapper.size()) {
                return;
            }
            synchronized (mapper) {
                if (capacity > mapper.size()) {
                    return;
                }
                Iterator<String> keys = mapper.keySet().iterator();
                int i = mapper.size() - capacity;
                while (i > 0) {
                    keys.next();
                    keys.remove();
                    i--;
                }
            }
        }

        public Object get(String key) {
            if (key == null || !mapper.containsKey(key)) {
                return null;
            }
            //最新访问的数据，放在最后
            synchronized (mapper) {
                Object value = mapper.get(key);
                mapper.remove(key);
                mapper.put(key, value);
                return value;
            }
        }
    }
}

 

十、对链表进行插入排序（题号：147）

    描述：给定一个无序、单向链表， 对链表进行插入排序。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

 

    解题思路：我们遵守“插入排序”的一般规律，即确定“有序区”和无序区；有序区位于链表的前端，无序区即为遍历区，每次从无序区中拿出首个节点插入到有序区，指导无序区全部遍历完毕。

public class TestMain {


    public static void main(String[] args) {
        ListNode root = new ListNode(-1);
        ListNode node = root;
        node = (node.next = new ListNode(4));
        node = (node.next = new ListNode(2));
        node = (node.next = new ListNode(1));
        node = (node.next = new ListNode(3));
        execute(root);
        System.out.println(root);
    }

    private static void execute(ListNode root) {
        //构建一个有序链表
        //其root与原链表一致
        ListNode tail = root.next;
        ListNode current = root.next.next;//当前比较值,即从第二值开始比较和交换
        tail.next = null;//断开有序链表的尾部
        //
        while (current != null) {
            //先获取下一个指针
            ListNode next = current.next;
            exchange(root,tail,current);
            current = next;
        }
        tail.next = null;
    }

    /**
     *
     * @param root 有序链表的根
     * @param tail 有序链表的尾部
     * @param target 需要比较和交换的节点
     */
    private static void exchange(ListNode root,ListNode tail,ListNode target) {
        int hv = root.next.value;
        int tv = tail.value;
        int v = target.value;
        //如果值，比tail值还大，则直接追加
        if (v >= tv) {
            target.next = tail.next;
            tail.next = target;
            return;
        }
        //如果比首个值还小
        if (v <= hv) {
            target.next = root.next;
            root.next = target;
            return;
        }

        //对于中间值，则循环比较
        ListNode previous = root.next;
        ListNode next = previous.next;
        while (previous != null) {
            if (v > previous.value) {
                if (v <= next.value) {
                    target.next = next;
                    previous.next = target;
                    return;
                }
            }
            previous = next;
            next = next.next;
        }
    }
    static class ListNode {
        int value;
        ListNode next = null;
        ListNode(int value) {
            this.value = value;
        }
    }

}

 

十一、逆波兰表达式求值（题号：150）

    描述：根据逆波兰表示法，求表达式的值。有效的运算符包括 + - * /。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

    说明：

    1）整数除法只保留整数部分。（避免小数）

    2）我们认为给定的逆波兰表达式总是有效的。换句话说，表达式钟会得出有效的数值且不存在除数为0的情况等。

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

 

    解题思路：表达式的规则，比较容易发现，即计算符总是在被计算数字的后面，即临近计算符（前面）是被计算的数字对象。我们使用栈来解决，遇到非计算符的元素则放入栈中，如果计算符，则从栈中弹出两个元素、并将计算结果重新入栈。最终栈中的唯一元素，就是结果值。

public class TestMain {


    public static void main(String[] args) {
        char[] source = {'2', '1', '+', '3', '*'};
        System.out.println(execute(source));
    }

    private static int execute(char[] source) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < source.length; i++) {
            char x = source[i];
            if (x == '+') {
                int i1 = stack.pop();
                int i2 = stack.pop();
                stack.push(i2 + i1);
            } else if (x == '-') {
                int i1 = stack.pop();
                int i2 = stack.pop();
                stack.push(i2 - i1);
            } else if (x == '*') {
                int i1 = stack.pop();
                int i2 = stack.pop();
                stack.push(i2 * i1);
            } else if (x == '/') {
                int i1 = stack.pop();
                int i2 = stack.pop();
                stack.push(i2 / i1);
            } else {
                stack.push(x - '0');
            }

        }
        return stack.pop();
    }

}

 

十二、最小栈（题号：155）

    设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

    1）push(x) -- 将元素 x 推入栈中。

    2）pop() -- 删除栈顶的元素。

    3）top() -- 获取栈顶元素。

    4）getMin() -- 检索栈中的最小元素。

 

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

 

 

public class TestMain {


    public static void main(String[] args) {

    }


    /**
     * 设计思路：如果当前值比历史最小值还小，则将历史最小值临近当前值一起加入stack。
     * 1
     * 2 //历史最小值
     * 5
     * 4
     * 2
     * 3 //历史最小值
     * 3
     *
     * 在弹出栈时，如果当前值是最小值，则弹出两个元素，第二个元素，就是剩余所有元素的最小值
     */
    public static class MinStack {
        private Stack<Integer> stack = new Stack<>();
        private int min = Integer.MAX_VALUE;

        public void push(int x) {
            //如果当前值比最小值小，则将最小值作为标记，加入栈
            if (x <= min) {
                stack.push(min);
                min = x;
            }
            //同时将当前元素加入栈
            stack.push(x);
        }

        public void pop() {
            //如果栈顶元素是最小值，则连续弹出2次
            //因为第二个元素是剩余元素的最小值--标记值
            if (min == stack.peek()) {
                stack.pop();
                min = stack.pop();
            } else {
                stack.pop();
            }
            if (stack.isEmpty()) {
                min = Integer.MAX_VALUE;
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min;
        }
    }
}