LeetCode Weekly Contest 19

作者 QIFAN 日期 2017-02-12
LeetCode Weekly Contest 19

第一题:Base 7

十进制转七进制,并将结果以字符串形式输出。
使用一个 stack 存余数再一个个 pop 就好了,注意负数。

第二题:Find Left Most Element

返回一颗二叉树中最后一行最左的节点的值。
我采用了最直白的层级遍历方式,到最后一层的时候返回第一个元素。这个时间空间复杂度都是 $O(N)$ 。
不需要额外空间的解法如下(source)。因为一直遍历左边再遍历右边,所以每一层下来一定有且只有最左边的节点会出现 h < depth 的情况。

public class Solution {
int ans=0, h=0;
public int findLeftMostNode(TreeNode root) {
findLeftMostNode(root, 1);
return ans;
}
public void findLeftMostNode(TreeNode root, int depth) {
if (root==null) return;
if (h<depth) {ans=root.val;h=depth;}
findLeftMostNode(root.left, depth+1);
findLeftMostNode(root.right, depth+1);
}
}

第三题:Find Largest Element in Each Row

返回每一列中最大的节点的值。
也是层级遍历。嗖嗖嗖。

第四题:Reverse Pairs

给定一个数组 nums ,返回数组中满足 i < j 且 nums[i] > 2 * nums[j] 的对数。
这题花了一个小时,最后也还是 TLE ,一开始准备用 BST ,后面花了太多时间弄边界,最后用的是 $O(n^2)$ 的粗暴方法。不应该的地方在于一开始没有考虑到 integer overflow 的情况,但实际上这个可以直接用 float 解决。挺好玩的一点在于刚好今天 15513 看了各种整型的运算,就实战运用了一下。
满足条件的有下面几种情况:

  1. nums[j] * 2 不溢出。 nums[j] >= lo && nums[j] <= hi && nums[i] > nums[j] << 1
  2. nums[i] 非负,nums[j] 为负。 nums[i] >= 0 && nums[j] < 0
  3. nums[i] , nums[j] 均为负且 2 * nums[j] overflow : nums[i] / 2 > nums[j]nums[i] < 0 && nums[j] < lo && ((nums[i] + nums[i] & 1) >> 1) > nums[j]

BST 解法,先从后往前建树,每个树节点保存的变量有值 val ,比它小的节点数 less ,和它一样的节点数 same。每次增加节点时,先找对于这个 nums[i] 目前树中有多少满足。然后将该点加入数,如果往左边走,当前节点,less++ ,相同 same++ 。最后只需要 $O(NlonN)$ 。
代码(source):

public int reversePairs(int[] nums) {
Node root = null;
int[] cnt = new int[1];
for(int i = nums.length-1; i>=0; i--){
search(cnt, root, nums[i]/2.0);//search and count the partially built tree
root = build(nums[i], root);//add nums[i] to BST
}
return cnt[0];
}
private void search(int[] cnt, Node node, double target){
if(node==null) return;
else if(target == node.val) cnt[0] += node.less;
else if(target < node.val) search(cnt, node.left, target);
else{
cnt[0]+=node.less + node.same;
search(cnt, node.right, target);
}
}
private Node build(int val, Node n){
if(n==null) return new Node(val);
else if(val == n.val) n.same+=1;
else if(val > n.val) n.right = build(val, n.right);
else{
n.less += 1;
n.left = build(val, n.left);
}
return n;
}
class Node{
int val, less = 0, same = 1;//less: number of nodes that less than this node.val
Node left, right;
public Node(int v){
this.val = v;
}
}

这题数据结构想清楚了应该挺快的。