ING的面试题：一排硬币翻一个找最大连续相同面（语言：Javascript）

cloud226

是我大意 看错题目了 题目要求是通过翻转一个硬币 找出最多几个相同的pair 我却错看成最多几个连续相同



原题代码
function solution(A){
        var n = A.length;
        var result = 0;
        var i;
        for(i=0; i<n-1; i++){
                if(A==A[i+1])
                        result = result+1;
        }        
        
        var r=0;
        for(i=0; i<n; i++){
                var count=0;
                if(i>0){
                        if(A[i-1]!=A)
                                count++;
                        else
                                count--;
                }
                if(i<n-1){
                        if(A[i+1]!=A)
                                count++;
                        else
                                count--;        
                }
                r= Math.max(r,count);
        }
        
        return result+r;
}

mzbac

这个 只要删除
    else
    count=count-1;

这个bug 应该就答题完事了吧

shadowfiend

现在用codility 笔试的还挺多的嘛

cloud226

mzbac 发表于 2015-12-23 17:05
这个 只要删除
    else
    count=count-1;

哦？哪一个count = count - 1呢？ 有两个

而且count = count - 1 有存在的意义吧 和相邻相同的硬币flip后就是减了一个吧

mzbac

你是对的 = =

cloud226

mzbac 发表于 2015-12-23 17:28

有两个地方有你说的
else
  count = count - 1
题目要求最多更改3行code

不过这个和binary search差很多吧 binary search数列要先sort好 而且是self recursive的

mzbac

cloud226 发表于 2015-12-23 17:34
有两个地方有你说的
else
  count = count - 1

后一个有个bug 如果左侧相同 右侧不同 count 减回去没有了 比如 1110000 会返回3 实际应该返回4
我之前想到二分法查找确实有问题 二分法 找到的 不一定是最大的

yzh1999

Var r= -1;

cjc

你们每次去赌场都带着电脑和类似的软件算一算，是不是就哗哗哗的赚钱呀？

mzbac

我的可能不止N2....

function search(A) {
  var n = A.length;
  var result = [];
  for (var i = 0; i < Math.floor(n / 2); i++) {
    var count = 0;
    if (i > 0) {
      if (A[i - 1] != A)
        count = count + 1;
    }
    if (i < n - 1) {
      if (A[i + 1] != A)
        count = count + 1;

    }
    if (count == 2)
      result.push(i);

  }

  return result;
}

function solution(A) {
  var n = A.length;
  var indexs = search(A);
  var r=0;
  for (var index = 0; index < indexs.length; index++) {
    if (A[indexs[index]] == 1) {
      A[indexs[index]] = 0;
    }
    else {
      A[indexs[index]] = 1;
    }

    var result = 0;
    var i;
    for (i = 0; i < n - 2; i++) {
      if (A == A[i + 1] && A[i + 1] == A[i + 2])

        result = result + 1;
    }
    r=Math.max(r,result + 2);
  }
  
  return r;
}
var A = [];
A[0] = 1;
A[1] = 1;
A[2] = 0;
A[3] = 1;
A[4] = 1;
A[5] = 1;
A[6] = 1;
A[7] = 0;
A[8] = 1;
console.log('result :' + solution(A));

CITYLOOK

is this so called ma nong?
so des nei....

cloud226

抱歉 误导你了 我大意看错题目

cloud226

抱歉 误导你了 我大意看错题目

xmj

既然是js，楼主能不能把原始代码copy到jsfiddle共享个link出来？我也来试一试
https://jsfiddle.net/5L2k5c1f/2/

改

1. var r = -1;

复制代码

首先如果让我在线coding，我做不出来的
但是给我google下其实不难理解
题目问题有多少adjacent，其实是问你有多少pairs，比如 [0 0 1 0 1 1]答案是2,因为数组中有2对 0 0和1 1

接下去就好办了
三种情况
1. 数组中所有元素相同 0 0 0 0，这样子最好的情况是reverse最两边的元素，对数-1
2. 数组中只有一个元素一边不同，比如 1 1 1 1 0 0 0，这种理想情况是reverse中间的界限元素1或者0，对数不变
3.含有一个元素2边都不同，比如 0 0 1 0 0，元素1和两边元素都不同，对数+2

三种情况优先级往下优先

xmj

cloud226 发表于 2015-12-23 23:30
很遗憾 好像还是错的

试试这个array [1,1,0,1,1,0]

这个答案是对的，问你有多少对，这个数组答案是4

xmj

yzh1999 发表于 2015-12-23 18:42
Var r= -1;

大牛就是这样子，只改一个数值，还不带解释，可惜没分了

cloud226

xmj 发表于 2015-12-24 00:12
既然是js，楼主能不能把原始代码copy到jsfiddle共享个link出来？我也来试一试
https://jsfiddle.net/5L2k5c ...

感谢

我太大意 直接想当然的去找最大连续相同数了