LeetCode第144场周赛 2019-07-07

> IP地址.变 [.]

思路

遍历即可，遇到.则加上[ ]。

 

代码

class Solution {
    public String defangIPaddr(String address) {
        char[] str = new char[address.length()+6];
        char arr[] = address.toCharArray();
        int index = 0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]!='.'){
                str[index++] = arr[i];
            }else{
                str[index++] = '[';
                str[index++] = arr[i];
                str[index++] = ']';
            }
        }
        return new String(str);
    }
}

 

 

> 飞机票预订

 

题意及思路（超时限的思路）

有n航班，它们都标1有n。

我们有一份航班预订清单。第i- 次预订  bookings[i] = [i, j, k] 意味着我们k从标i有j包含的航班预订了座位。

返回一个answer长度数组n，表示按照标签顺序在每个航班上预订的座位数。

 

思路；遍历m次预订，将i 到 j 的每一个航班都加上 k 个预订票数。

 

思路（正确、聪明的思路）

> 大佬的思路

　

因为bookings.length <= 20000，n<=20000，直接暴力应该会超时。

 

对于预定记录[i，j，k]，我们可以用一个数组记录在i 的地方加上k，在j + 1 的地方减去k，最后统计一遍数组即可。

 

想法很妙，我这脑瓜子。。。哈哈

 

代码

 

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] order = new int[n];
        for(int[] v:bookings){
            order[v[0]-1] += v[2];
            if(v[1]<n) order[v[1]] -= v[2];
        }
        for(int i=1;i<n;i++) order[i] += order[i-1];
        return order;
    }
}

 

 

> 删点成林

 

 

 

题意及思路

题意：删除给定数组中元素在树中对应的节点（每一个节点含有唯一的val值）。删除之后，将形成的森林的根节点加入到结果集中。

思路：这个解法，我还没想好怎么描述思路，先放放。。。

 

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<TreeNode> list = new ArrayList<TreeNode>();
    private HashSet<Integer> set = new HashSet<Integer>();
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for(int i:to_delete){
            set.add(i);
        }
        TreeNode head = new TreeNode(to_delete[0]);
        head.left = root;
        helper(head,null,true);
        return list;
    }
    
    private void helper(TreeNode root,TreeNode parent,boolean left){
        if(root==null) return;
        if(set.contains(root.val)){
            if(left==true && parent!=null){
                parent.left = null;
            }else if(left!=true && parent!=null){
                parent.right = null;
            }
            if(root.left!=null && !set.contains(root.left.val)) list.add(root.left);
            if(root.right!=null && !set.contains(root.right.val)) list.add(root.right);
            helper(root.left,null,true);
            helper(root.right,null,false);
        }else{
            helper(root.left,root,true);
            helper(root.right,root,false);
        }
        
    }
    
}

 

 

Loading ...