Wish 高频题翻转红绿灯

给出一个array， 比如[红, 绿, 绿, 红,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ay, 但不太确定该怎么写，求指教

绿灯是-1， 红灯是1， 找maximum subarray sum就好了吧。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

小A要当码农 发表于 2019-12-26 07:13
绿灯是-1， 红灯是1， 找maximum subarray sum就好了吧。

可以解释一下原理吗？

按照小A要当码农的思路我写了一下

1. def find_subarray(arr):
   
2.     max_, start, end = 0, 0, 0
   
3.     cur_sum = 0
   
4.    
   
5.     for i,c in enumerate(arr):
   
6.         n = 1 if c == 'R' else -1
   
7.             
   
8.         if n > cur_sum + n:
   
9.             start = i
   
10.             cur_sum = n
    
11.         else:
    
12.             cur_sum += n
    
13.             
    
14.         if cur_sum > max_:
    
15.             max_ = cur_sum
    
16.             end = i
    
17.    
    
18.     return arr[start: end+1] if max!=0 else []
    
19. 
    
20. print(find_subarray(['R', 'B', 'R', 'B', 'R', 'R', 'B']))
    
21. print(find_subarray(['R', 'B', 'R', 'B', 'B', 'B', 'R', 'R', 'B']))
    
22. print(find_subarray(['B', 'B', 'B']))
    
23. print(find_subarray(['R', 'R', 'B', 'R', 'R', 'B', 'B', 'R', 'R', 'B']))

复制代码

拿JAVA写了下应该对吧

1. 
   
2.     public int[] maxGreenLights(String s) {
   
3.         int[] result = new int[2];
   
4.         int count = 0, maxSum = 0, minSum = 0;
   
5.         int left = -1;
   
6.         for (int i = 0; i < s.length(); i++) {
   
7.             if(s.charAt(i) == 'R') count++;
   
8.             else count--;
   
9.             if(count < minSum) {
   
10.                 left = i;
    
11.                 minSum = count;
    
12.             }
    
13.             if(count - minSum > maxSum) {
    
14.                 result[0] = left + 1;
    
15.                 result[1] = i ;
    
16.                 maxSum = count - minSum;
    
17.             }
    
18.         }
    
19.         return result;
    
20.     }

复制代码

littleric 发表于 2020-3-1 09:13
应该是找一个array里面最小的sub sum，红灯为-1，绿灯为1的情况下你肯定是要让整个数组的合的值最大最好 ...

稍微转换一下，红灯为1，绿灯为-1，就是求maxSubArray吧？如果找到的maxSum不为正，这样子区间不存在

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

双指针滑动窗口也行 说白了就是找一个区间 in which红的多余绿的差最大

1.   public static int[] solve(int[] input) {
   
2.     int left = 0;
   
3.     int right = 0;
   
4.     int x = -1;
   
5.     int y = -1;
   
6.     int delta = Integer.MIN_VALUE;
   
7.     int count1 = 0;
   
8.     while (left < input.length && right < input.length) {
   
9.       if (input[right] == 0) {
   
10.         right++;
    
11.         continue;
    
12.       }
    
13.       count1++;
    
14.       while (left <= right && input[left] == 0) {
    
15.         ++left;
    
16.       }
    
17.       int tmpDelta = 2 * count1 - right + left - 1;
    
18.       if (tmpDelta > delta) {
    
19.         delta = tmpDelta;
    
20.         x = left;
    
21.         y = right;
    
22.       }
    
23.       ++right;
    
24.     }
    
25.     return new int[]{x,y};
    
26.   }

复制代码

题目什么意思？那把全部红灯变绿灯不就是最多绿灯了吗？