2016年小米校招筆試第一題（西安站）

1?給定一些線段，線段有起點和終點，求這些線段的覆蓋長度，重復的部分只計算一次。

參考解法（Java版）：

package XiaoMi;/********************************************************* 算法思想：將長線段細分為長度為1的小段，用布爾數組記錄每一個小段；* 遍歷所有長段，如果有覆蓋則在數組中把該索引處的布爾值標記為ture；* 最后，遍歷布爾數組中所有值為ture的小段個數，即為所求總覆蓋長度。* ******************************************************/ public class test13 {// 指定線段中點的最大范圍private final static int N = 99999;// 布爾數組用來記錄已覆蓋小段private static boolean b[];// 定義線段的數據結構class XianDuan {int start; //線段起點int end; //線段終點}// 遍歷布爾數組求總覆蓋長度static int sum(XianDuan[] xd) {b = new boolean[N];int start = 0;int end = 0;// 標記過程for (int i = 0; i < xd.length; i++) {for (int j = xd[i].start; j < xd[i].end; j++) {b[j] = true;//System.out.println("置為true");}// 找到boolean數組索引的最大值if (xd[i].end > end) {end = xd[i].end;}// 找到boolean數組索引的最小值if (xd[i].start < start) {start = xd[i].start;}}// 統計過程int count = 0;for (int i = start; i < end; i++) {if (b[i]) {count++;}} return count;}public static void main(String[] args) {/** A a = new A(); A.B b = a.new B(); //內部類實例化*/test13 tt = new test13();test13.XianDuan x1 = tt.new XianDuan();x1.start = 1;x1.end = 3;test13.XianDuan x2 = tt.new XianDuan();x2.start = 2;x2.end = 6;test13.XianDuan x3 = tt.new XianDuan();x3.start = 11;x3.end = 12;test13.XianDuan x4 = tt.new XianDuan();x3.start = 10;x3.end = 14;XianDuan xx[] = { x1, x2, x3, x4 };System.out.println(sum(xx));} }
運行結果：

9

總結

以上是生活随笔為你收集整理的【小米校招笔试】给定一些线段，线段有起点和终点，求这些线段的覆盖长度，重复的部分只计算一次的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。