14 September 2019

LeetCode(8) -- 414, 415, 429

by Jerry Zhang

P414. Third Maximum Number (Easy)

给一个非空的整数数组，返回它第三大的数。如果不存在就返回最大的数。时间复杂度必须是O(n)。

这里第三大的数指的是不同的数，比如[1,2,2,2]就没有第三大的数。那么就返回最大的数。

我的思路

遍历数组时保存前三大的数。

我的代码

public class E_414_ThirdMaximumNumber {
    public int thirdMax(int[] nums) {
        Integer first = null, second = null, third = null;
        for (int i = 0; i < nums.length; i++) {
            if (first == null) {
                first = nums[i];
            } else if (second == null) {
                if (nums[i] > first) {
                    second = first;
                    first = nums[i];
                } else if (nums[i] < first) {
                    second = nums[i];
                }
            } else if (third == null) {
                if (nums[i] > first) {
                    third = second;
                    second = first;
                    first = nums[i];
                } else if (nums[i] > second && nums[i] < first) {
                    third = second;
                    second = nums[i];
                } else if (nums[i] < second) {
                    third = nums[i];
                }
            } else {
                if (nums[i] > first) {
                    third = second;
                    second = first;
                    first = nums[i];
                } else if (nums[i] > second && nums[i] < first) {
                    third = second;
                    second = nums[i];
                } else if (nums[i] > third && nums[i] < second) {
                    third = nums[i];
                }
            }
        }
        if (third == null) {
            return first;
        }
        return third;
    }
}

88.59%

写得很繁琐。大致意思就是设了三个Integer存前三个数。分别检验前三大的数是否为空。然后把新的数根据不同情况，填到相应的位置。

最优解

class Solution {
    public int thirdMax(int[] nums) {

        long first = Long.MIN_VALUE;
        long second = Long.MIN_VALUE;
        long third = Long.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            int currNum = nums[i];

            if (currNum > first) {
                third = second;
                second = first;
                first = currNum;
            } else if (currNum > second && currNum < first) {
                third = second;
                second = currNum;
            } else if(currNum > third && currNum < second) {
                third = currNum;
            }
        }

        return third == Long.MIN_VALUE ? (int)(first) : (int)(third);
    }
}

通过三个长整型的最小值作为初始值，这样就可以不管它是不是空也可以比较了，大大简化了代码。

P415. Add Strings (Easy)

用两个string表示两个整数，返回它们的和。它们的长度小于5100，只包含0-9。不能用BigInteger或者直接转化成整数。

我的思路

从个位数开始，把每个字符转化为数字加起来，然后看有没有进位。

我的代码

public class E_415_AddStrings {
    public String addStrings(String num1, String num2) {
        int index1 = num1.length() - 1;
        int index2 = num2.length() - 1;
        int carry = 0;
        StringBuilder stringBuilder = new StringBuilder();
        while (index1 >= 0 && index2 >= 0) {
            int digit1 = num1.charAt(index1--) - '0';
            int digit2 = num2.charAt(index2--) - '0';
            if (digit1 + digit2 + carry > 9) {
                stringBuilder.insert(0, digit1 + digit2 + carry - 10);
                carry = 1;
            } else {
                stringBuilder.insert(0, digit1 + digit2 + carry);
                carry = 0;
            }
        }
        while (index1 >= 0) {
            int digit1 = num1.charAt(index1--) - '0';
            if (digit1 + carry > 9) {
                stringBuilder.insert(0, 0);
                carry = 1;
            } else {
                stringBuilder.insert(0, digit1 + carry);
                carry = 0;
            }
        }
        while (index2 >= 0) {
            int digit2 = num2.charAt(index2--) - '0';
            if (digit2 + carry > 9) {
                stringBuilder.insert(0, 0);
                carry = 1;
            } else {
                stringBuilder.insert(0, digit2 + carry);
                carry = 0;
            }
        }
        if (carry == 1) {
            stringBuilder.insert(0, 1);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        new E_415_AddStrings().addStrings("4","69");
    }
}

38%

讨论区

class Solution {
    public String addStrings(String num1, String num2) {
        int n = num1.length() - 1;
        int m = num2.length() - 1;

        final StringBuilder builder = new StringBuilder();

        int carry = 0;
        while (n >= 0 || m >= 0) {
        final int x = n >= 0 ? num1.charAt(n--) - '0' : 0;
        final int y = m >= 0 ? num2.charAt(m--) - '0' : 0;
        final int z = x + y + carry;
        if (z > 9) {
            builder.append(z - 10);
            carry = 1;
        } else {
            builder.append(z);
            carry = 0;
        }
        }
        if (carry > 0) builder.append(carry);

        return builder.reverse().toString();
    }
}

95%

P429. N-ary Tree Level Order Traversal (Easy)

一棵普通树，按层级遍历。

我的思路

用Queue存一下每一个节点就行了

讨论区

public class E_429_NaryTreeLevelOrderTraversal {
    public List<List<Integer>> levelOrder(Node root) {
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayList<List<Integer>> lists = new ArrayList<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int numNodesInLevel = queue.size();
            List<Integer> level = new ArrayList<>(numNodesInLevel);
            for (int i = 0; i < numNodesInLevel; i++) {
                Node node = queue.remove();
                level.add(node.val);
                for (Node child : node.children) {
                    if (child != null) {
                        queue.add(child);
                    }
                }
            }
            lists.add(level);
        }
        return lists;
    }
}

因为遍历时每一层需要单独存到一个list里，所以需要记录一下该层级的size。遍历这一层的每一个节点，对每个节点都做以下两件事：

把该节点的值存到list里
把该节点的所有子节点添加到queue中

最优解

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root, 0, res);
        return res;
    }
    private void helper(Node root, int level, List<List<Integer>> list) {
        if (root == null) return;
        if (level == list.size()) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(root.val);
        for (Node child : root.children) {
            helper(child, level + 1, list);
        }
    }
}

用递归的方法，记录层级。如果当前的level和size相等，则说明需要添加新的一层。

P434. Number of Segments in a String (Easy)

求一个string里有几个由空格分开的部分。

我的思路

直接就split函数就行了。

最优解

class Solution {
    public int countSegments(String s) {
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' ') continue;
            if( (i + 1 < s.length() && s.charAt(i+1) == ' ') || i+1 == s.length()) {
                count++;
            }
        }
        return count;
    }
}

如果当前字符为空，就直接看下一个。如果后一个字符为空，或者后一个到了string的末尾，就认为这是一个单词。

答案

class Solution {
    public int countSegments(String s) {
        int segmentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s.charAt(i-1) == ' ') && s.charAt(i) != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }
}

P437. Path Sum III (Easy)

一个二叉树。给一个数sum，找出所有的路径，such that在这个路径上，所有数的和等于这个sum。求一共有多少条这样的路径。

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

我的思路

DFS，把每个节点向上回溯到任意层级的和，都用HashMap记录下来，这样我从这个节点再往下走时，如果上面有任意一个值，和当前值加起来等于sum，就说明找到了一个路径。但这样做的缺点是每往下走一个节点，都需要更新所有的HashMap，成本很高。而且这样有一个问题就是如果一条路径出现两次sum，这样做就会重复记录。

如果用递归的思路想，每个节点是否会产生一条新的路径，完全取决于它的子节点所能构成的sum。比如上图中的5，它之所以能生成两条路径，是因为它的左子节点能生成一个3，右子节点也能生成一个3。

讨论区

class Solution {
    public int pathSum(TreeNode node, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return pathSum(node, target, 0, map);
    }

    private int pathSum(TreeNode node, int target, int sum, Map<Integer, Integer> map) {
        if (node == null) {
            return 0;
        }
        sum += node.val;
        int result = map.getOrDefault(sum - target, 0);

        map.merge(sum, 1, Integer::sum);
        result += pathSum(node.left, target, sum, map);
        result += pathSum(node.right, target, sum, map);
        map.merge(sum, -1, Integer::sum);
        if (map.get(sum) == 0) { // Remove when 0 to reduce space usage
            map.remove(sum);
        }

        return result;
    }
}

最优解：

class Solution {
    //use int[] array to keep track of the path from root to the node
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        int depth = findDepth(root);
        int[] path = new int[depth];
        return helper(root, path, sum, 0);
    }

    private int helper(TreeNode cur, int[] path, int sum, int level) {
        if (cur == null) return 0;
        path[level] = cur.val;
        int counts = 0, path_sum=0;
        for (int i = level; i >= 0; i--) {
            path_sum += path[i];
            if (path_sum == sum) {
                counts++;
            }
        }
        counts += helper(cur.left, path, sum, level+1);
        counts += helper(cur.right, path, sum, level+1);
        return counts;
    }

    private int findDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return 1 + Math.max(findDepth(root.left), findDepth(root.right));
    }

    /* iterative in order tree travesal: still slow
    private int get_path_sum(Stack<List<Integer>> path_stack, List<Integer> parent_paths, TreeNode cur, int sum) {
        int result = 0;
        List<Integer> paths = new ArrayList<Integer>();
        paths.add(0);
        for (Integer v: parent_paths) {
            paths.add(v + cur.val);
            if (v+cur.val == sum)
                result++;
        }
        path_stack.push(paths);
        return result;
    }

    public int pathSum(TreeNode root, int sum) {
        int result = 0;
        if (root == null) return 0;

        Stack<TreeNode> node_stack = new Stack<TreeNode>();
        Stack<List<Integer>> path_stack = new Stack<List<Integer>>();
        node_stack.push(root);
        List<Integer> path = new ArrayList<Integer>();
        path.add(0);
        path.add(root.val);
        if (root.val == sum) result++;
        path_stack.push(path);

        while (!node_stack.isEmpty()) {
            TreeNode cur = node_stack.pop();
            List<Integer> parent_paths = path_stack.pop();
            if (cur.left != null) {
                node_stack.push(cur.left);
                result += get_path_sum(path_stack, parent_paths, cur.left, sum);
            }
            if (cur.right != null) {
                node_stack.push(cur.right);
                result += get_path_sum(path_stack, parent_paths, cur.right, sum);
            }
        }

        return result;
    }
    */

    /* recursive
    public int pathSum(TreeNode root, int sum) {
        ArrayList<Integer> previousSums = new ArrayList<Integer>();
        previousSums.add(0);
        return pathSumHelper(root, sum, previousSums);
    }

    private int pathSumHelper(TreeNode root, int sum,
                              ArrayList<Integer> previousSums) {
        if (root == null) return 0;
        int result = 0;
        ArrayList<Integer> newPrevious = new ArrayList<Integer>();
        newPrevious.add(0);
        for (Integer previous: previousSums) {
            if (previous + root.val == sum) result++;
            newPrevious.add(previous + root.val);
        }
        if (root.left != null) {
            result += pathSumHelper(root.left, sum, newPrevious);
        }
        if (root.right != null) {
            result += pathSumHelper(root.right, sum, newPrevious);
        }
        return result;
    }
    */
}

先求出树的深度。新建一个长度为该深度的数组。

tags: LeetCode

Jerry's Blog

Recording what I learned everyday

LeetCode(8) -- 414, 415, 429

P414. Third Maximum Number (Easy)

我的思路

我的代码

最优解

P415. Add Strings (Easy)

我的思路

我的代码

讨论区

P429. N-ary Tree Level Order Traversal (Easy)

我的思路

讨论区

最优解

P434. Number of Segments in a String (Easy)

我的思路

最优解

答案

P437. Path Sum III (Easy)

我的思路

讨论区

最优解：