牛客算法直播题目总结Day1T234
- 第二题:已知一个字符串都是由左括号(和右括号)组成，判断该字符串是否是有效的括号组合
- 基础： 有效的括号组合:()(),(()),(()()) 无效的括号组合：(,()),(()))))(( 进阶: 已知一个字符串都是由左括号(和右括号)组成，返回最长有效括号子串的长度。
前面的基础比较简单，就利用一个count进行计数， 当遇到左括号进行自加，遇到右括号进行自减，当扫描过程中出现了负数则是无效的，当扫描结果是为0，则是有效的括号组合，实现如下
1 public static boolean isValid(String str) {
2 if (str == null || str.equals("")) {
3 return false;
4 }
5 char[] chas = str.toCharArray();
6 int status = 0;
7 for (int i = 0; i < chas.length; i++) {
8 if (chas[i] != ')' && chas[i] != '(') {
9 return false;
10 }
11 if (chas[i] == ')' && --status < 0) {
12 return false;
13 }
14 if (chas[i] == '(') {
15 status++;
16 }
17 }
18 return status == 0;
19 }
进阶分析：自己设置一套规定，用一个数组dp来表示以第i个元素结尾时候的最大子字符串的长度.如图所示
以上是设定，那么若要进行顺推，如果可以由0..i推出i+1,则可以类似于dp一样利用数学归纳法进行解决。如:
求到下标为5的时候，需要对原来的进行+2操作。但是有一个问题需要注意:
这时候7所在的位置最长字串是8,不是简单地对来进行+2操作，这里知道和2匹配的时候还不够，还需要往前调一步，跳到1的位置去看是否存在字串，有的话进行+2操作。
所以在遍历字符串的时候，除了每次需要对dp[i]+2操作以外，还需要一个+dp[k]的操作，dp[k]就相当于上面描述的那个操作，但是这里的dp[k]包含了一个或多余一个的+2操作，这样的操作只需要依次，因为每次加了的dp[k]都会更新到新的dp[i+1]中，则在求dp[i+2]的时候，就仅需要往前跳一步即可，代码如下：
写博客效率好低 去看会儿欧洲史 待会来写
回来了:
1 public static int maxLength(String str) {
2 if (str == null || str.equals("")) {
3 return 0;
4 }
5 char[] chas = str.toCharArray();
6 int[] dp = new int[chas.length];
7 int pre = 0;
8 int res = 0;
9 for (int i = 1; i < chas.length; i++) {
10 if (chas[i] == ')') {
11 pre = i - dp[i - 1] - 1;
12 if (pre >= 0 && chas[pre] == '(') {
13 dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
14 }
15 }
16 res = Math.max(res, dp[i]);
17 }
18 return res;
19 }
利用pre这个下标来往回找。
- 1、给定一个数组，值全是正数，请返回累加和为给定值k的最长子数组长度。
值全是正数，则利用滑动窗口法来进行解决，左指针和右指针智能往右滑，过程是右指针先进行滑动，当达到k值的时候进行记录每一个length，当超过k值进行左指针右移动，依次求出返回记录的最长字串的长度。 自己的代码:
3 public class MaxSubSequence {
4 public static void main(String[] args) {
5 int[] a = {3,2,1,1,4,6};
6 int key = 4;
7 int left = -1;
8 int right = -1;
9 int sum = 0;
10 int length = 0;
11
12 while (true) {
13 if(sum <= key){
14 right++;
15 if(++right >= a.length){
16 break;
17 }
18 sum = sum(left,right,a);
19 if(sum == key){
20 length = Math.max(length, right - left + 1);
21 }
22 }
23
24 if(sum > key){
25 if(++left >= a.length){
26 break;
27 }
28 sum = sum(left,right,a);
29 if(sum == key){
30 length = Math.max(length, right - left +1);
31 }
32 }
33 }
34
35 System.out.println(length);
36
37 }
38
39 private static int sum(int left, int right, int[] a) {
40 int sum = 0;
41 for (int i = left < 0 ? 0 : left; i <= right; i++) {
42 sum = sum + a[i];
43 }
44 return sum;
45 }
46 }
左神代码:
1 package problems_2017_07_18;
2
3 public class Problem_02_LongestSumSubArrayLengthInPositiveArray {
4
5 public static int getMaxLength(int[] arr, int k) {
6 if (arr == null || arr.length == 0 || k <= 0) {
7 return 0;
8 }
9 int left = 0;
10 int right = 0;
11 int sum = arr[0];
12 int len = 0;
13 while (right < arr.length) {
14 if (sum == k) {
15 len = Math.max(len, right - left + 1);
16 sum -= arr[left++];
17 } else if (sum < k) {
18 right++;
19 if (right == arr.length) {
20 break;
21 }
22 sum += arr[right];
23 } else {
24 sum -= arr[left++];
25 }
26 }
27 return len;
28 }
29
30 public static int[] generatePositiveArray(int size) {
31 int[] result = new int[size];
32 for (int i = 0; i != size; i++) {
33 result[i] = (int) (Math.random() * 10) + 1;
34 }
35 return result;
36 }
37
38 public static void printArray(int[] arr) {
39 for (int i = 0; i != arr.length; i++) {
40 System.out.print(arr[i] + " ");
41 }
42 System.out.println();
43 }
44
45 public static void main(String[] args) {
46 int len = 20;
47 int k = 15;
48 int[] arr = generatePositiveArray(len);
49 printArray(arr);
50 System.out.println(getMaxLength(arr, k));
51
52 }
53
54 }
发现他和我的逻辑代码是一样的，但是写的更加简洁geek，while里面用right<arr.length来进行判断，总共分为两大个if，前面判读等于k时候挑出最大的len，等于的时候减去本次的left所在的元素，当下次判断是小于k时候，right++，判断一下right是否越界，然后加上即可。后面测试用了对数器，和之前代码是一样的。
- 进阶一：给定一个数组，值可以为正、负和0，请返回累加和为给定值k的最长子数组长 度。
因为本次中的元素不是全都为正数，不能用刚刚的方法，为了让这道题有迹可循，这里进行一个设定，要求必须求必须以每个位置结尾的情况下的累加和为k的最长子数组的长度。[这句话有点长，后面继续解释]。这里要有一个思维惯性，看到是子数组求累加和的问题，若不是全为正数的情况，而是此题中的有正有负数的情况，则应当思考以某元素结尾的情况，若是求小于k的最长子数组长度，则应该思考以某元素开头的情况(在进阶2中有)。 例如： <p align="center"> 
</p>
例如：有0-100个元素，总共的sum=1000 要求k=300 则为了要求k=300的最大子数组长度，那么反过来，可以求最早得到累加和未700的子数组长度，则后面剩下的就是累加和为300的字串。
策略：在java中利用map进行存储，因为map的CRUD操作的O(1)的，所以整个操作是O(n)复杂度，若数组如下，只需要记录每个以一个数value结尾的index，则在map中存储的为：
当加到index是2时候，发现map中已经有4这个value了，则不需要加进去，我们是要发现最早出现的累加和的下标。
这道题的主要顺序是，若需要k=6，
①第一次index=0是4，利用4-6=-2，则应该在map中找累加和为-2的第一次出现的位置，到4的位置肯定为6，但是没有，则将4，0加入map。
②第二次index=1累加和是7，利用7-6=1，则应该在map中找累加和为1的位置，到7的位置肯定为6，但是没有，则将7，1加入map。
③第二次index=2累加和是9，利用9-6=3，则应该在map中找累加和为3的位置，到9的位置肯定为6，但是没有，则将9，2加入map。
④③第二次index=3累加和是10，利用10-6=4，则应该在map中找累加和为4的位置，到10的位置肯定为6，发现map中有，则存入这次的len。
但是这里需要注意一个问题，例如代码中需要寻找k=4的数字，则找到index=0，4-4=0，要找到累加和为0的，但是找不到，这样就会漏掉4，反而找不到最早出现4的位置，所以在代码中间，我们要给map中put一个[0,-1]这样的初始。以防这种情况出现。
献上代码：
1 package com.Algorithm;
2
3 import java.util.HashMap;
4 import java.util.Map;
5
6 public class MaxSubSequenceWithNegative {
7 public static void main(String[] args) {
8 int[] a = {4,3,2,1,3};
9 int key = 4;
10 int len = -1;
11 int sum = 0;
12 if (a== null || a.length == 0) {
13 return;
14 }
15 Map<Integer,Integer> map = new HashMap<Integer,Integer>();
16 map.put(0, -1);
17
18 for (int i = 0; i < a.length; i++) {
19 sum += a[i];
20
21 if(!map.containsKey(sum)){ //if not contain sum,add it to the maop
22 map.put(sum, i);
23 }
24 if(map.containsKey(sum - key)){ //if contain sum-key then give the max len(NOTICE:i - ~)
25 len = Math.max(len, i - map.get(sum - key));
26 }
27 }
28 System.out.println(len);
29 }
30
31
32 }
代码比较简单，就不赘述。
- 进阶二：给定一个数组，值可以为正、负和0，请返回累加和小于等于k的最长子数组长度。
整个思路分为两个部分，首先，从数组的最末一个元素开始，求出以i开头的最小和，记录下它 到加到最后一个元素的右边界
如上图，当加到index=3的时候，因为有右边是正数，则仅仅加自己就是最小的和。这里于是就牵涉到，当min_sum[i+1]<=0时候，value[i] + min_sum[i+1].当min_sum[i+1]>0，则value[i]则不加。
当有了这个数据，仍然是用map进行存放，然后第二部进行滑动窗口的方法，我们可以把第一步得到的那些最小字串的部分看作是一个块，则整个过程可以变为。 <p align="center"> 
</p>这里如果从0为首得到的Sum小于等于k的最大字串是到i，则判断的依据就是当进行i+1加进去时，发现得到的k>Sum. 之后进行滑窗口，将最开始的0的位置向前跳到1，再进行一次步骤2.
代码如下：
New Text Document.java
1 public static int maxLengthAwesome(int[] arr, int k) {
2 if (arr == null || arr.length == 0) {
3 return 0;
4 }
5 int[] sums = new int[arr.length];
6 HashMap<Integer, Integer> ends = new HashMap<Integer, Integer>();
7 sums[arr.length - 1] = arr[arr.length - 1]; //start from the last element
8 ends.put(arr.length - 1, arr.length - 1);//save the right bound
9 for (int i = arr.length - 2; i >= 0; i--) {
10 if (sums[i + 1] < 0) { //if < 0
11 sums[i] = arr[i] + sums[i + 1]; //add
12 ends.put(i, ends.get(i + 1)); //NOTICE:save the right bound
13 } else { //if not
14 sums[i] = arr[i];
15 ends.put(i, i); //save the current index i
16 }
17 }
18 int end = 0;
19 int sum = 0;
20 int res = 0;
21 for (int i = 0; i < arr.length; i++) {
22 while (end < arr.length && sum + sums[end] <= k) {//traverse as block
23 sum += sums[end];
24 end = ends.get(end) + 1; //the actual index
25 }
26 sum -= end > i ? arr[i] : 0; //miuns the frontest one
27 res = Math.max(res, end - i);
28 end = Math.max(end, i + 1);
29 }
30 return res;
31 }
终于搞定第一周了，源代码：
2017年8月10日20:22:45
Enjoy Reading This Article?
Here are some more articles you might like to read next: