Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?
Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it’s current position.
Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.
We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.
本期节目中我们介绍了Fenwick Tree/Binary Indexed Tree/树状数组的原理和实现以及它在leetcode中的应用。
In this episode, we will introduce Fenwick Tree/Binary Indexed Tree, its idea and implementation and show its applications in leetcode.
Fenwick Tree is mainly designed for solving the single point update range sum problems. e.g. what’s the sum between i-th and j-th element while the values of the elements are mutable.
Init the tree (include building all prefix sums) takes O(nlogn)