牛客算法直播题目总结Day2T1234

刚回来几天心情不好，天气暴雨乌云密布，还差几天要回学校了，心情甚好，天气也跟着我晴朗,阳光明媚，看我多有面子。

闲言少叙，进入正题。第一题: 一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1.将这个栈转后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其它的数据结构。 <p align="center">

</p> 这题其实并不难，要有递归，则必须要有重复的一个步骤，可以想象地出我们需要每次从栈底取出元素，压入另一个栈中，这个步骤是重复的，结束标志就是栈中没有元素即可。这里需要完成一个函数f，函数f传入的是stack，需要执行的是移除栈底元素，具体实现办法：

1 private static int f(Stack stack) { 2 int result = (Integer) stack.pop(); 3 if(stack.isEmpty()) 4 return result; 5 else{ 6 int last = f(stack); 7 stack.push(result); 8 return last; 9 } 10 }

这里需要注意的是，每一次的递归，系统都会自动开辟一个新的栈来保存里面的值，会进行保留现场的一个操作，在第6行开始一直进行递归，则每一次递归的值result都会被保存进各次开辟的空间，当递归完之后，进行push的时候是当时开辟空间时储存的result。

screenshot

最后返回的是子过程一步一步返回的last=5 ，最后再添加一个reverse函数，取得每一步的栈底的值，然后下一行进行push，原理和上面图例一样。代码实现为：

1 package problems_2017_07_26; 2 3 import java.util.Stack; 4 5 public class Problem_01_ReverseStackUsingRecursive { 6 7 public static void reverse(Stack stack) { 8 if (stack.isEmpty()) { 9 return; 10 } 11 int i = getAndRemoveLastElement(stack); 12 reverse(stack); 13 stack.push(i); 14 } 15 16 public static int getAndRemoveLastElement(Stack stack) { 17 int result = stack.pop(); 18 if (stack.isEmpty()) { 19 return result; 20 } else { 21 int last = getAndRemoveLastElement(stack); 22 stack.push(result); 23 return last; 24 } 25 } 26 27 public static void main(String[] args) { 28 Stack test = new Stack(); 29 test.push(1); 30 test.push(2); 31 test.push(3); 32 test.push(4); 33 test.push(5); 34 reverse(test); 35 while (!test.isEmpty()) { 36 System.out.println(test.pop()); 37 } 38 39 } 40 41 }

这一题然我重新很深刻地理解了递归的原理，在递归的下一行的代码，实际上是存储的每一次开辟空间保留的值进行工作的一步。

解放区的学生是勤劳的学生看着我心欢喜

第二题数组小和的定义如下：例如，数组[1,3,5,2,4,6].在s[0]左边小于或等于s[0]的数的和为0，在s[1]左边小于或等于s[1]的数的和为1，在s[2]…的和是 1+3=4,在s[3]….的和是1，在s[4]的左边小于或等于s[4]的数和和为1+3+2=6,在s[5]的左边小于或等于s[5]的数和和为1+3+5+2+4=15.所以s的小和为0+1+4+1+6+15=27。给定一个数组s。实现函数返回s的小和。

这一题首先需要的是会MergeSort，这里先贴出来归并排序的代码，归并排序实际上也是利用递归来进行，前两步的递归merge进行分操作，后面的mergesort进行合操作，由于每次递归都保留现场了，所以传入mergesort的长度都不一致。其实mergesort也很好地表现了递归的本质。

mergesort代码

1 package day2; 2 3 import org.omg.CORBA.IRObject; 4 5 public class MergeRevie { 6 7 8 9 10 //归并排序操作 11 private static void merge(int[] arr, int l, int r) { 12 if(l < r){ 13 int m = (l + r)/ 2; 14 merge(arr, l, m); 15 merge(arr, m+1, r); 16 mergesort(arr,l,m,r); 17 } 18 } 19 //合操作 20 private static void mergesort(int[] arr, int l, int m, int r) { 21 22 23 //计算左右两边的数组大小 24 int n1 = m - l + 1; 25 int n2 = r - m; 26 27 //创建两个数组 28 int L[] = new int[n1]; 29 int R[] = new int[n2]; 30 31 //拷贝元素进去 32 for (int i=0; i<n1; ++i) 33 L[i] = arr[l + i]; 34 for (int j=0; j<n2; ++j) 35 R[j] = arr[m + 1+ j]; 36
37 int i =0,j=0,k=l; 38 //进行比较 39 while(i < n1 && j < n2){ 40 if(L[i] <= R[j]){ 41 arr[k] = L[i]; 42 i++; 43 k++; 44 }else{ 45 arr[k] = R[j]; 46 j++; 47 k++; 48 } 49 } 50
51 //将剩下的拷贝进去 52 while(i < n1){ 53 arr[k] = L[i]; 54 i++; 55 k++; 56 } 57 while(j < n2){ 58 arr[k] = R[j]; 59 j++; 60 k++; 61 } 62 } 63 64 //打印 65 private static void printArray(int[] arr) { 66 for (int i = 0; i < arr.length; i++) { 67 System.out.print(arr[i]+” “); 68 } 69 } 70 71 public static void main(String[] args) { 72 int arr[] = {12, 11, 13, 5, 6, 7}; 73 74 System.out.println(“Given Array”); 75 printArray(arr); 76
77 78 merge(arr, 0, arr.length-1); 79
80 System.out.println(“nSorted array”); 81 printArray(arr); 82 } 83 84 }

这个题目若是有了归并排序就变得十分简单了，只需要在归并排序之中多加一行就可以了，递归之后，整个数组已经是被打散得了，则在合的mergesort哪个函数中，多加一个判断：

1 package day2; 2 3 import org.omg.CORBA.IRObject; 4 5 public class MergeRevie { 6 7 8 9 10 //归并排序操作 11 private static int merge(int[] arr, int l, int r) { 12 if (l == r) { 13 return 0; 14 } 15 int m = (l + r)/ 2; 16 17 return merge(arr, l, m)+ merge(arr, m+1, r)+ mergesort(arr,l,m,r); 18 19 } 20 //合操作 21 private static int mergesort(int[] arr, int l, int m, int r) { 22 23 24 //计算左右两边的数组大小 25 int n1 = m - l + 1; 26 int n2 = r - m; 27 28 //创建两个数组 29 int L[] = new int[n1]; 30 int R[] = new int[n2]; 31 32 //拷贝元素进去 33 for (int i=0; i<n1; ++i) 34 L[i] = arr[l + i]; 35 for (int j=0; j<n2; ++j) 36 R[j] = arr[m + 1+ j]; 37
38 int i =0,j=0,k=l; 39 int smallSum = 0; 40 //进行比较 41 while(i < n1 && j < n2){ 42 if(L[i] <= R[j]){ 43 smallSum += L[i] * (n2 - j); 44 arr[k] = L[i]; 45 i++; 46 k++; 47 }else{ 48 arr[k] = R[j]; 49 j++; 50 k++; 51 } 52 } 53
54 //将剩下的拷贝进去 55 while(i < n1){ 56 arr[k] = L[i]; 57 i++; 58 k++; 59 } 60 while(j < n2){ 61 arr[k] = R[j]; 62 j++; 63 k++; 64 } 65
66 return smallSum; 67 } 68 69 //打印 70 private static void printArray(int[] arr) { 71 for (int i = 0; i < arr.length; i++) { 72 System.out.print(arr[i]+” “); 73 } 74 } 75 76 public static void main(String[] args) { 77 int arr[] = {1, 3, 5, 2, 4, 6}; 78 79 System.out.println(“Given Array”); 80 printArray(arr); 81
82 83 int smallSum = merge(arr, 0, arr.length-1); 84
85 System.out.println(smallSum); 86 //printArray(arr); 87 } 88 89 }

第三题:给定一个数组，返回子数组的最大累加和。例如，arr=[1,-2,3,5,-2,6,-1],所有的子数组中，[3,5,-2,6]可以累加出的最大和12，所以返回12. 这题十分简单，两个参数，cur参数记录累加和，一旦累加和小于0，重置为0，每一步只要大于原来max进行更新max。

1 package day2; 2 3 public class MaxSum { 4 5 private static int maxSum(int[] arr) { 6 if (arr == null || arr.length == 0) { 7 return 0; 8 } 9 int max = Integer.MIN_VALUE; 10 int cur = 0; 11 for (int i = 0; i < arr.length; i++) { 12 cur += arr[i]; 13 max = Math.max(cur, max); 14 cur = cur < 0 ? 0 : cur; 15 } 16 return max; 17 } 18 19 public static void main(String[] args) { 20 int[] arr1 = { -2, -3, -5, 40, -10, -10, 100, 1 }; 21 System.out.println(maxSum(arr1)); 22 23 int[] arr2 = { -2, -3, -5, 0, 1, 2, -1 }; 24 System.out.println(maxSum(arr2)); 25 26 int[] arr3 = { -2, -3, -5, -1 }; 27 System.out.println(maxSum(arr3)); 28 29 } 30 31 32 }