牛客算法直播题目总结Day2T1234

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

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

</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 }

 

  • 第四题:题目有点长,直接上图 <p align="center"> screenshot

</p>

这里有一个比较有意思的结论,如果数组中没有重复的元素,那么能相互观察到的岗哨的对数是2N-3.下面简单说明一下这个结论:

screenshot

先规定由低到高进行查找,之后:

screenshot

每一个非高与次高的数总能在两边找到比自己大的数则是(n-2)2=2n-4,最后加上此高找到高这一对,则是2*n-3对。证毕。

我一直以头发过度浓密而烦恼

若是不考虑是否重复还是不重复来解题的话,我们需要引入单调栈的概念,单调递增或单调减的栈,跟单调队列差不多,但是只用到它的一端。这里我们利用从栈底到栈顶依次变小的栈,例如。

screenshot

这里的左右指的是,在这个数组中,每一个元素左边最近离他最近比他大的数,右边离他最近比他大的数。这里的左指的是它底下的数,右指的是让它pop出来的那个数。这样才能编程一个依次变小的单调栈。

环中找到最大值不止一个,但是找到一个即可压栈(假设逆时针找),若有以下的情况。

screenshot

则在计算对数的时候,压栈的时候,计算对数,之后3个2内部两两一对,321/2*1=3,最后当3进入的时候,弹出的时候又可以计算对数,最后当栈中只剩下4和5时候,若4有7个,5一个,内部的4是C7上2,与5产生的是7个。具体的思想就是这样,不可能有栈为空的情况。具体的代码如下;




    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • What is Mathematics: Solution Chapter 3
  • What is Mathematics: Solution Chapter 2
  • What is Mathematics: Solution Chapter 1
  • A small guide to supplements: What you need to know
  • 混乱与秩序