d***n
发帖数: 65 | 1 第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i
{
while(B[i]<=max(maxL, maxR) && i
{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]
{
if(B[j]>maxR)
... 阅读全帖 |
|
d***n
发帖数: 65 | 2 第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i
{
while(B[i]<=max(maxL, maxR) && i
{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]
{
if(B[j]>maxR)
... 阅读全帖 |
|
k****n
发帖数: 369 | 3 code:
int testOneWay(int b[], int size, int start, int step, int w[], int diff);
int longest01(int b[], int n) {
int n0=0, n1=0;
count(b, n, &n0, &n1);
if (n0==n1) return n;
int w[2];
w[0]=1, w[1]=-1, more=0;
if (n0
int l1 = testOneWay(b, n, 0, 1, w, abs(n0-n1));
if (l1 == 2*MIN(n0,n1)) return l1;
l1 = testOneWay(b, n, n-1, -1, w, abs(n0-n1));
if (l1 == 2*MIN(n0,n1)) return l1;
int lc=0, rc=n-1;
int diff = abs(n0-n1);
while (b[lc+1] != m... 阅读全帖 |
|
c*****e
发帖数: 3226 | 4 那也不需要阿。 比如：((()
扫描到 最后一个"(", count = 3; len = 3;
扫描下一个")", count = 2; len = 4;
因此，最长的字串就应该是 len - count = 2;
再比如：((()()
接着上面的例子，
扫描到 最后一个"(", count = 3; len = ５;
扫描下一个")", count = 2; len = ６;
因此，最长的字串就应该是 len - count = ４;
因此扫描２遍似乎不需要,只要cout < 0 的时候重新reset 就好了。
ｃｏｄｅ:
public static int longestValidParentheses(String s) {
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s.charAt(i) == '('){
count++;
len++... 阅读全帖 |
|
c*****e
发帖数: 3226 | 5 那也不需要阿。 比如：((()
扫描到 最后一个"(", count = 3; len = 3;
扫描下一个")", count = 2; len = 4;
因此，最长的字串就应该是 len - count = 2;
再比如：((()()
接着上面的例子，
扫描到 最后一个"(", count = 3; len = ５;
扫描下一个")", count = 2; len = ６;
因此，最长的字串就应该是 len - count = ４;
因此扫描２遍似乎不需要,只要cout < 0 的时候重新reset 就好了。
ｃｏｄｅ:
public static int longestValidParentheses(String s) {
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s.charAt(i) == '('){
count++;
len++... 阅读全帖 |
|
w***o
发帖数: 109 | 6 这解法是O(n),空间是O(1):
大概的意思就是用左右两个指针，比较两个指针所指的值，从小的那个往中间移，移的
过程中要么增加maxL（或者maxR），要么tap water。直道两个指针相遇，其实两个相
遇在最大值。
if (bars == null || bars.length <= 2)
return 0;
int area = 0;
int l = 1, r = bars.length - 2;
int maxL = bars[0], maxR = bars[bars.length - 1];
while(l <= r)
{
if (maxL <= maxR)
{
if (bars[l] < maxL)
area += maxL - bars[l];
else
maxL = bars[l];
l++;
}
else
{
if (bars[r] < maxR)
area += maxR - bar... 阅读全帖 |
|
l*********8
发帖数: 4642 | 7 int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
}
0 |
|
l*********8
发帖数: 4642 | 8 写错了， 谢谢指出。
loop 里面第三行少了个 加1
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
} |
|
l*********8
发帖数: 4642 | 9 赞！
还是出bug啊，
改正了：
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
++changed[x];
++noChange[x];
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
maxL = max(maxL, changed[x]);
maxL = max(maxL, changed[1-x]);
}
return maxL;
} |
|
l***i
发帖数: 1309 | 10 assume all nodes are distinct
1. recursively find maxL and minR, which are max element in root->left
subtree and min element in root->right subtree
2. if maxL > minR, then these two are swapped elements
3. if maxL > root value, then maxL is swapped with root
4. if root value > minR, then minR is swapped with root
5. the only case remain is maxL < root < minR, in this case recurse on both
root->left and root->right because the two swapped nodes must be in the same
subtree now. |
|
i**********e
发帖数: 1145 | 11 My code:
// precondition: B is sorted
// returns the index i of B such that Bi-1 < key <= Bi.
int binarySearch(int B[], int key, int L, int R) {
while (L < R) {
int M = L + (R-L)/2;
if (B[M] >= key)
R = M;
else
L = M+1;
}
assert(L == R);
assert(L >= 1);
assert(B[L-1] < key && key <= B[L]);
return L;
}
// returns the length of the longest increasing subsequence.
// Assumption is that A[i] does not contain INT_MIN or INT_MAX.
// INT_MIN and INT_MAX are simple no... 阅读全帖 |
|
a*********0
发帖数: 2727 | 12 class Solution {
public:
int longestValidParentheses(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s[i] == '('){
count++;
len++;
}
if(s[i] == ')') {
count--;
len++;
}
if(count == 0 ... 阅读全帖 |
|
a**********0
发帖数: 422 | 13 我来解释一下？
int changed[2] = {0, 0};
记录 0或者1组成的连续串最长是多少 此串变化过一次
int noChange[2] = {0, 0};
记录 0或者1组成的连续串最长是多少 此串没有变化过
change【1】 可以理解为 1的通过俘虏0的连续串得到的 so far的连续串长度
扫描每一个数 有几种操作
此数必定破坏原来对手的unchange过的串 也就是使之归零
此数可以变化为对手 这样 对手的change = 对手unchange +1
无论如何情况 都破坏了对手的unchange的串 必须归零 因为即使第二种情况 对手的
unchange的串也不再是unchange了
当然此数也做 这么两件事
使自己change的串长度加一
使自己未经change的串长度加一
如果可以把这部分逻辑从max函数中拿出来会清晰很多吧
两个max是如果不去change应该如何
后边的两个语句是如果x变成对手应该如何
longway太牛了 其实这是dp
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noCh... 阅读全帖 |
|
h****j
发帖数: 15 | 14 Here are my 5 cents.
It will be easier to understand if we denote the position explicitly in the
iteration.
Let g_k[x] be the longest continuous `x` ending at position k, (exactly, not
at most) one change has been made.
Let f_k[x] represent the longest continous `x` ending at position k, no
change has been made.
Then we have the following iterative equations.
Update changed
g_{k+1} [x] = g_k [x] + 1
g_{k+1} [1-x] = f_k [1-x] + 1
Update unchanged
f_{k+1} [x] = f_k[x] + 1
f_{k+1} [... 阅读全帖 |
|
s***5
发帖数: 2136 | 15 O(n) space, O(n) time.
bool equal_bits(bool input[], int n, int& sta, int& end) {
// check if all elements are all 1's or all 0's
int sum = 0;
for(int i = 0; i < n; i++)
sum += input[i];
if(sum == 0 || sum == n) return false;
unordered_map freq;
int counter = 0, maxL = 0;
freq[counter] = -1;
for(int i = 0; i < n; i++) {
if(input[i])
counter++;
else
counter--;
if(freq.count(... 阅读全帖 |
|
b***e
发帖数: 1419 | 16 /*
Transform the array:
1 -> -1
0 -> 1
Then find max sum for substring (consecutive).
Spent 10 min coding and 2 min posting.
*/
var LR = function(a) {
for (var i = 0; i < a.length; i++) {
a[i] = a[i]? -1: 1;
}
console.log(a);
var L = a.length - 1;
var R = L;
var maxL = L;
var maxR = R;
var maxI = a[L];
var max = maxI;
for (var i = a.length - 2; i >= 0; i--) {
L = i;
if (maxI > 0) {
maxI += a[i];
} else {
R = L;
... 阅读全帖 |
|
w***y
发帖数: 6251 | 17 i c
那就是：
第一个位子（0,0)开头的words,肯定要搜完所有可能
后面的就是利用了当前的maxL word 和当前prefix可能延长的maxL去剪枝
所以比找所有valid words需要的计算还是少一些的 |
|
l*********8
发帖数: 4642 | 18 怎么找maxL 和 minR？ 遍历一遍？
both
same |
|
b***k
发帖数: 654 | 19 用 priority international 邮寄个大箱子回国, 结果黑小二说你这个尺寸
超标, 但可以用 express 寄. 给我看屏幕:
max L 42" , MaxL+Girth 79".
说你这个长不到 42", 但周长加长就过了 79".
俺一下蒙了, 还真以为太大. 回来想想不对啊, 79"是给长于 42" 的盒子留个
活路的 --- 如果长于 42", 但加上周长如果不大于 79" 还是可以地, 也就
是给寄长条盒子用的.
于是, 打印网上的有关规定, 再次回到邮局.
黑小二不见了, 剩下两个白的, 一男一女. 俺说有个问题关于盒子大小的限制.
结果两个白人跟黑小二一个调子. 那我就不客气了, 说这样, 你把你的名字写
下来, 把不给我寄的理由写下来, 我周一找你们经理谈. 小二一听要写他名字,
开始发毛, 说不是我不给你寄啊, 是黑小二啊. 我说那好, 你给我寄,咱啥事儿
也没有, 如果你坚持尺寸超了不给寄, 你就写下名字工号, 我再找你经理.
他还嘴硬, 说好, 我写下来, 你见了经理也是一样的. 结果人写的是黑小二
不给我寄, 我说你的名字捏? 他吱吱唔唔还 |
|
t********l
发帖数: 42 | 20 波版撕逼的事情看多了，一直懒得发言，觉得大家都还有是非观的，这次撕到自己人头
上了，我看这个MAXL真是活的太潇洒了，你喜欢你MAX，你当初就别征求AH的意见啊，
人家给你意见了，你这个缩头乌龟就开始怂了，MAX这么个不要脸的人你还敢接盘，你
也是真够了。MAX疯狂发微信，你也不维护下你的朋友，这真是什么朋友！！！！
交友不慎啊，交友不慎啊！！！ |
|
S*******e
发帖数: 186 | 21 我刚想到，有一种可能，是X 盗用了 MAXL 的这个用户名在这里
发言。这不是 L 本人发的。 |
|
