问个三脚架的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

问个三脚架的问题

问个三脚架的问题# PhotoGear - 摄影器材

M*e2010-04-02 07:04

1 楼

之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
3 1 8 1 9 1 5 => 2+7+4=13
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果

t*s2010-04-02 07:04

2 楼

Manfrotto 501HDV 能配 benro 268m8 的脚架不？也就想拍点娃的录像。
需要买一个 3/8 male to male thread adapter 不？
谢谢

p*22010-04-02 07:04

3 楼

我在这个帖子不是写过一个吗？

p*22010-04-02 07:04

4 楼

public class test2
{
static int water(int[] arr)
{
int i = 0;
int j = arr.length - 1;
int count = 0;
while (i < j)
{
while (i < j && arr[i] < arr[i + 1])
i++;
while (j > i && arr[j] < arr[j - 1])
j--;
if (i == j)
break;
int start;
int low;
boolean direct = true;
if (arr[i] <= arr[j])
{
start = i + 1;
low = arr[i];
direct = true;
}
else
{
start = j - 1;
low = arr[j];
direct = false;
}
while (arr[start] < low)
{
count += low - arr[start];
if (direct)
start++;
else
start--;
}
if (direct)
i = start;
else
j = start;
}
return count;
}
public static void main(String[] args)
{
int[][] q = new int[][]
{
{ 3, 1, 5 },
{ 3, 1, 0, 5 },
{ 1, 2, 3 },
{ 3, 2, 1 },
{ 1, 2, 3, 2, 1 },
{ 5, 4, 3, 6, 2, 3 },
{ 3, 1, 8, 1, 9, 1, 5 } };
int[] a = new int[]
{ 2, 5, 0, 0, 0, 4, 13 };
for (int i = 0; i < q.length; i++)
{
int r = water(q[i]);
if (a[i] == r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:" + a[i] + " actual:" + r);
}
}
}

w*x2010-04-02 07:04

5 楼

int CalculateContain(int a[], int n)
{
assert(a && n > 0);
int nRet = 0;
stack stk;
for (int i = 0; i < n; i++)
{
if (!stk.empty() && a[stk.top()] < a[i])
{
int nPrev = stk.top();
stk.pop();
while (!stk.empty() && a[stk.top()] <= a[i])
{
int nCur = stk.top();
stk.pop();
int nLimit = a[nCur] <= a[i] ? a[nCur] : a[i];
nRet += (nLimit - a[nPrev]) * (i - 1 - nCur);
nPrev = nCur;
}
// missing this logic!!
if (!stk.empty())
nRet += (a[i] - a[nPrev]) * (i - 1 - stk.top());
}
stk.push(i);
}
return nRet;
}

M*e2010-04-02 07:04

6 楼

没有看到你后面用start附回ij的那一段。
不过我想的是一边从左向右的扫描就把所有的interval找出来。
就是退栈的操作比较不好证明。
你这种左扫右扫可能还更容易说明一些。

【在 p*****2 的大作中提到】

: public class test2
: {
: static int water(int[] arr)
: {
: int i = 0;
: int j = arr.length - 1;
: int count = 0;
: while (i < j)
: {
: while (i < j && arr[i] < arr[i + 1])

i*e2010-04-02 07:04

7 楼

火鸡那解法是最好的，O(n) 时间 O(1) 空间又不容易出错：
http://www.mitbbs.com/article_t/JobHunting/31983619.html
我照着火鸡思路写的 C++:
int trap(int A[], int n) {
int h = 0;
for (int i = 1; i < n; i++) {
if (A[i] > A[h]) {
h = i;
}
}
int left = 0;
int total = 0;
for (int i = 0; i < h; i++) {
if (A[i] > A[left]) {
left = i;
} else {
total += A[left] - A[i];
}
}
int right = n-1;
for (int i = n-1; i > h; i--) {
if (A[i] > A[right]) {
right = i;
} else {
total += A[right] - A[i];
}
}
return total;
}
stack 的解法是 O(n) 时间 O(n) 空间，而且不容易写对。边界条件很多，要考虑很多情况，这里是一个我实现的：
int trap(int A[], int n) {
stack s;
int total = 0;
int h = 0;
for (int R = 0; R < n; R++) {
while (!s.empty()) {
int L = s.top();
total += (R-L-1) * (min(A[L], A[R]) - h);
h = A[L];
if (A[L] > A[R]) break;
s.pop();
}
s.push(R);
}
return total;
}

M*e2010-04-02 07:04

8 楼

写了一个扫一遍找出每个interval关键点，然后算水量的
int WaterInArray(vector data)
{
vector keys(data.size());
int open = -1;
for (int i=0; i{
while (open>0 && data[i]>data[keys[open]] && data[keys[open]]keys[open-1]])
open--;
keys[++open] = i;
}
int total = 0, pos = 0;
while (pos < open)
{
int min = (data[keys[pos]]data[keys[pos+1]];
for (int i=keys[pos]+1; i{
if (min > data[i])
total += min - data[i];
}
pos++;
}
return total;
}

【在 M*****e 的大作中提到】

: 没有看到你后面用start附回ij的那一段。
: 不过我想的是一边从左向右的扫描就把所有的interval找出来。
: 就是退栈的操作比较不好证明。
: 你这种左扫右扫可能还更容易说明一些。

h*l2010-04-02 07:04

9 楼

后两个for 应该从1 和n-2开始，估计你写顺手了

【在 i**********e 的大作中提到】

: 火鸡那解法是最好的，O(n) 时间 O(1) 空间又不容易出错：
: http://www.mitbbs.com/article_t/JobHunting/31983619.html
: 我照着火鸡思路写的 C++:
: int trap(int A[], int n) {
: int h = 0;
: for (int i = 1; i < n; i++) {
: if (A[i] > A[h]) {
: h = i;
: }
: }

l*82010-04-02 07:04

10 楼

Yes, logically the for loops should start from 1 and n-2.
But ihasleetcode's code can get the same results.

【在 h**********l 的大作中提到】

: 后两个for 应该从1 和n-2开始，估计你写顺手了

h*l2010-04-02 07:04

11 楼

不会把，如果最边上的短的话，假设是0，显然就多计算了阿

【在 l*********8 的大作中提到】

: Yes, logically the for loops should start from 1 and n-2.
: But ihasleetcode's code can get the same results.

l*82010-04-02 07:04

12 楼

int left = 0;
int total = 0;
for (int i = 0; i < h; i++) {
if (A[i] > A[left]) {
left = i;
} else {
total += A[left] - A[i];
}
}
In the loop, when i is 0,
total += A[left] - A[i]
is executed.
which is total += A[0] - A[0]. It has no influence to the result.

【在 h**********l 的大作中提到】

: 不会把，如果最边上的短的话，假设是0，显然就多计算了阿

C*U2010-04-02 07:04

13 楼

你这明显误导别人啊
左扫一遍右扫一遍就可以

【在 M*****e 的大作中提到】

: 之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
: 点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
: 不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
: 3 1 8 1 9 1 5 => 2+7+4=13
: X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
: E.G:
: 3,1,5 => 2
: 3,1,0,5 => 5
: 很假单的O(N)扫描就行
: 扩展是改成Online的算法，就是说：

d*n2010-04-02 07:04

14 楼

You can scan from left to right and from right to left.
int trap(int A[], int n) {

int total = 0;
int temp = 0;
int h = 0;
for (int i = 0; i < n; i++) {
if (A[i] < h) {
temp += h - A[i];
} else {
total += temp;
h = A[i];
temp = 0;
}
}

h = 0;
temp = 0;
for (int i = n-1; i >=0; i--) {
if (A[i] <= h) {
temp += h - A[i];
} else {
total += temp;
h = A[i];
temp = 0;
}
}

return total;
}

【在 C***U 的大作中提到】

: 你这明显误导别人啊
: 左扫一遍右扫一遍就可以

j*o2010-04-02 07:04

15 楼

没理解后面这个ONLINE是怎么解的。。
？

【在 M*****e 的大作中提到】

C*U2010-04-02 07:04

16 楼

对啊
我开始也觉得是这样
然后看了这个人说得我以为那样是不对
后来有人告诉我可以左右各走一边就可以
所以我说楼主的帖子坑爹
自己没搞懂。。。还误导别人

【在 d****n 的大作中提到】

: You can scan from left to right and from right to left.
: int trap(int A[], int n) {
:
: int total = 0;
: int temp = 0;
: int h = 0;
: for (int i = 0; i < n; i++) {
: if (A[i] < h) {
: temp += h - A[i];
: } else {

m*d2010-04-02 07:04

17 楼

我贡献一个只扫描一遍的算法把。首先用最左和最右计算一个最大可能的雨量。如果左
边比右边低，那么从左边前进一个。如果左边第二个比第一个要低，那么从总水量里减
去左边第二个的高度；否则，用左边第二个和最右边的计算一个新的最大可能的水量。
右边同理。
public class Solution {
public int trap(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length < 3){
return 0;
}
int l=0;
int r=A.length-1;
int left=A[l], right=A[r];
int sum = (A[l] < A[r] ? A[l] : A[r]) * (A.length - 2);

while(lif (left < right){
l++;
if (left < A[l]){
sum -= left;
sum += ((A[l] < right ? A[l] : right) - left) * (r-l-1);
left = A[l];
} else {
sum -= A[l];
}
} else {
r--;
if (right < A[r]){
sum -= right;
sum += ((A[r] < left ? A[r] : left) - right) * (r-l-1);
right = A[r];
} else {
sum -= A[r];
}
}

}
return sum;
}
}

z*e2010-04-02 07:04

18 楼

贴一个O（n）的，
#include
using namespace std;
int trap(int A[], int n) {
int max=A[0];
int int_max=0;
int area=A[0];
if(n<3) return 0;
for(int i=1;i{
area+=A[i];
if(A[i]>max)
{
max=A[i];
int_max=i;
}
}

int i=0;
int current=A[i];
int total=current;
i++;
while(i<=int_max)
{
while(current>=A[i])
{
i++;
total+=current;
}

current=A[i];
total+=current;
i++;
}
if(int_max==(n-1))
return total-area;
i=n-1;
current=A[i];
i--;
total+=current;
while(i>int_max)
{
while(current>=A[i])
{
i--;
total+=current;
if(i==int_max) break;
}
if(i==int_max) break;
current=A[i];
total+=current;
i--;
}
return total-area;
}
int main()
{
int A[] = {2, 0, 2};
int result=trap(A,3);
cout<return 0;
}