本文共 1661 字，大约阅读时间需要 5 分钟。

腾讯2020-05春招补录笔试

我们有两种刷法，横着刷与竖着刷

核心思想就是利用上面两种方法把最短的刷完递归

①只利用横着刷把最短刷完然后递归

为什么要全用横着刷而不是横竖混刷?

因为如果第一次横着刷以后再竖着刷的话，接下来就是递归，

如果在子问题中先横着刷的话那么还不如在上一次中直接横着再刷一道，这样并不会影响总次数。

如果子问题竖着刷的话，接着递归在新的子问题中如果横着刷的话还不如在上一次的上一次中直接横着再刷一道，这样并不会影响总次数。

那么一直这样分析下去最后我们发现结果就是横着刷把最短刷完然后递归

②竖着一次刷完最短然后递归

import org.junit.Test;public class AVL {
      @Test    public  void Test()    {
           int array[]={
   1,1,9999,1,1};        System.out.println(BrushSticks(array,0,4,0));    }    //算法的思想就是分治法    //刷的方法分为两种横刷与竖刷代表将left-right范围内的值减去dx    //递归的出口是left>right    int BrushSticks(int array[],int left ,int right,int dx){
           if(left>right){
               return 0;        }else{
               //横着全部刷完            int min_index = Find_MiniIndex(array,left,right);            //由于这一下刷下去可能会存在一样的最小短板            int nums = 0;            int a,b;            int i = left;            //将各个子区间递归           while(i<=right){
                  while(i<=right&&array[i]==array[min_index]){
                      i++;               }               a=i;               while(i<=right&&array[i]>array[min_index]){
                      i++;               }               b=i-1;               nums+=BrushSticks(array,a,b,array[min_index]+dx);           }           nums+=array[min_index]-dx;            //直接竖着刷           int nums1=BrushSticks(array,left,min_index-1,dx)+BrushSticks(array,min_index+1,right,dx)+1;            return  (nums>nums1)?nums1:nums;        }    }    int Find_MiniIndex(int[] arr,int left,int right){
          int min = arr[left];       int min_index = left;       for(int i=left;i<=right;i++){
              if(arr[i]

转载地址：http://gplzi.baihongyu.com/