0°

面试算法知识梳理七:数组第四部分

内容预览:
  • 乐乐有话说不要做廉价的自己,不要随意去付出,不要一厢情愿去迎合别人...~
  •   面试算法代码知识梳理系列 阅读目录 1.概要 2.代码实现 2.1 求数...~
  •    static int mergeArea(Area areas = lastArea;   &nb...~

始发于微信公众号: 程序员小乐

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!


每日英文
don’t corrupted themselves, life is not only an opportunity, try to.
不要堕落了自己,人生并不只有一次机会,努力把握。

乐乐有话说
不要做廉价的自己,不要随意去付出,不要一厢情愿去迎合别人,圈子不同,不必强融!将时间浪费在别人身上,倒不如专心做自己喜欢的事情。不断去学习,提高个人品质、气质和魅力,这才是值得自己去努力的事情。 

面试算法代码知识梳理系列


阅读目录

  • 1.概要

  • 2.代码实现

  • 2.1 求数组当中的最长递增子序列

  • 2.2 区间重合判断

  • 2.3 一个整数数组,长度为 n,将其分为 m 份,使各份的和相等,求 m 的最大值

一、概要

本文介绍了有关数组的算法第四部分的Java代码实现,所有代码均可通过 在线编译器(https://tool.lu/coderunner/) 直接运行,算法目录:

求数组当中的最长递增子序列(求数组当中的最长递减子序列)
区间重合判断
一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值

二、代码实现

2.1 求数组当中的最长递增子序列

代码实现

class Untitled {
   //查找最长递增子序列。
   static void searchMaxIncSubArray(int p[], int length) {
       //maxValue[i]表示长度为i的递增子序列的最大元素的最小值。
       int[] maxValue = new int[length+1];
       maxValue[1] = p[0];
       int k=1;
       for (int i=1; i<length; i++) {
           if (p[i] > maxValue[k]) {
               k++;
               maxValue[k] = p[i];
           } else if (p[i] == maxValue[k]) { //如果p[i]和maxValue[k],那么越过。
               continue;
           } else { //如果p[i]小于maxValue[k]。
               if (p[i] < maxValue[1]) {
                   maxValue[1] = p[i];
                   continue;
               }
               int first = 1;
               int last = k;
               //二分查找:目的是在maxValue数组中找到大于p[i]的第一个元素,如果它大于p[i],那么就替换它。
               while (first < last) {
                   int mid = (last-first) >> 1;
                   if (maxValue[first+mid] < p[i]) {
                       first=first+mid+1;
                   } else if (maxValue[first+mid] > p[i]) {
                       last=first+mid;
                   } else {
                       first=first+mid+1;
                   }
               }
               //进行替换。
               if (p[i] < maxValue[first]) {
                   p[i] = maxValue[first];
               }
           }
       }
       System.out.println("k=" + k);
   }
   public static void main(String[] args) {
       int[] p = {1,2,31,4,20,-7,8};
       searchMaxIncSubArray(p, p.length);
   }
}

运行结果

k=3

2.2 区间重合判断

代码实现

class Untitled {
   static class Area {
       int start;
       int end;
       Area(int start, int end) {
           this.start = start;
           this.end = end;
       }
   }
   //首先对区间进行排序,按照start进行递增排序。
   static void sortArea(Area areas[], int start, int end) {
       if (start==end) {
           return;
       }
       int mid = start;
       Area midValue = areas[start];
       for (int i=start+1; i<=end; i++) {
           Area data = areas[i];
           if (data.start < midValue.start) {
               mid++;
               areas[i] = areas[mid];
               areas[mid] = data;
           }
       }
       Area temp = areas[mid];
       areas[mid] = areas[start];
       areas[start] = temp;
       if (mid > start) {
           sortArea(areas, start, mid-1);
       }
       if (mid < end) {
           sortArea(areas, mid+1, end);
       }
   }
   //合并区间,使得两个区间之间互不重合。
   static int mergeArea(Area areas[], int len) {
       int lastIndex = 0;
       Area lastArea = areas[0];
       for (int i=1; i<len; i++) {
           Area cur = areas[i];
           if (cur.start <= lastArea.end) {
               if (cur.end > lastArea.end) {
                   lastArea.end = cur.end;
                   areas[lastIndex] = lastArea;
               }
           } else {
               lastArea = cur;
               lastIndex++;
               areas[lastIndex] = lastArea;
           }
       }
       return lastIndex+1;
   }
   //通过二分查找,确定目标区间是否在其范围之内。
   static boolean searchArea(Area areas[], int areasLen, Area target) {
       int startIndex = 0;
       int endIndex = areasLen-1;
       while (startIndex <= endIndex) {
           int mid = (startIndex+endIndex) >> 1;
           Area midValue = areas[mid];
           if (target.start < midValue.start) {
               if (target.end > midValue.end) {
                   return false;
               } else {
                   endIndex=mid-1;
               }
           } else if (target.start >= midValue.start && target.start <= midValue.end) {
               if (target.end <= midValue.end) {
                   return true;
               } else {
                   return false;
               }
           } else {
               startIndex = mid+1;
           }
       }
       return false;
   }
   static void printArea(Area areas[], int len) {
       for (int i=0; i<len; i++) {
           Area area = areas[i];
           System.out.println("start=" + area.start + ",end=" + area.end);
       }
   }
   public static void main(String[] args) {
       Area areas[] = new Area[] {
               new Area(1, 3),
               new Area(5, 9),
               new Area(2, 4),
               new Area(10, 11),
       };
       sortArea(areas, 0, areas.length-1);
       System.out.println("- 排序结果 -");
       printArea(areas, areas.length);
       int mergeLen = mergeArea(areas, areas.length);
       System.out.println("- 合并结果 -");
       printArea(areas, mergeLen);
       Area target = new Area(3, 4);
       System.out.println("处于区间内=" + searchArea(areas, mergeLen, target));
   }
}

运行结果

排序结果
start=1,end=3
start=2,end=4
start=5,end=9
start=10,end=11
合并结果
start=1,end=4
start=5,end=9
start=10,end=11
处于区间内=true

2.3 一个整数数组,长度为 n,将其分为 m 份,使各份的和相等,求 m 的最大值

代码实现

class Untitled {
   static Boolean testGroup(int p[], int aux[], int pLen, int groupLen, int curSum, int groupSum, int groupID){
       if (curSum < 0)
           return false;
       if (curSum == 0){
           groupID++;
           curSum = groupSum;
           if (groupID == groupLen+1) {
               return true;
           }
       }
       for (int i=0; i<pLen; i++){
           if (aux[i] != 0) {
               continue;
           }
           aux[i] = groupID;
           if (testGroup(p, aux, pLen, groupLen, curSum-p[i], groupSum, groupID)) {
               return true;
           }
           aux[i] = 0;
       }
       return false;
   }
   static void maxGroup(int p[], int len) {
       int aux[] = new int[len];
       int sum = 0;
       for (int i=0; i<len; i++) {
           aux[i] = 0;
           sum += p[i];
       }
       for (int m=len; m>=2; m--) {
           if (sum%m != 0) {
               continue;
           }
           if (testGroup(p, aux, len, m, sum/m, sum/m, 1)) {
               System.out.println("m=" + m);
               for (int i=0; i<len; i++) {
                   System.out.println("aux[" + i + "]=" + aux[i]);
               }
           }
       }
   }
   public static void main(String[] args) {
       int a[] = {3,2,4,3,6};
       maxGroup(a, a.length);
   }
}

运行结果

m=3
aux[0]=1
aux[1]=2
aux[2]=2
aux[3]=1
aux[4]=3

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!

如何您想进技术群交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:泽毛

链接:https://www.jianshu.com/p/f5cb05737802

著作权归作者所有,欢迎投稿。

面试算法知识梳理七:数组第四部分


推荐阅读






看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:面试算法知识梳理七:数组第四部分 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论