【1】題目： 給定一個(gè)無(wú)序數(shù)組，找到最長(zhǎng)的單調(diào)自增子序列（不一定連續(xù)，但是順序不能亂）的長(zhǎng)度；

【2】看個(gè)荔枝：給定數(shù)組??[10, 9, 2, 5, 3, 7, 101, 18] ? 輸出結(jié)果為?[2, 3, 7, 101]。。算法時(shí)間復(fù)雜度一般為 O(n^2) 也可以優(yōu)化到 O(nlgn)；

【3】算法思路：對(duì)無(wú)序數(shù)組做一次遍歷 并找出最小最大值v1, v2及其下標(biāo)i1, i2；下一次循環(huán)遍歷的范圍是在 [i1+1, i2-1] 這個(gè)范圍內(nèi)找出 最小最大值 及其下標(biāo)，每次循環(huán) counter += 2...... 算法結(jié)束標(biāo)志是 i1 小于i2；且當(dāng) i1等于i2時(shí) 表明 單調(diào)自增子序列的長(zhǎng)度是奇數(shù)，所以counter++；算法實(shí)現(xiàn)如下：下面算法的時(shí)間復(fù)雜度是 O(n^2)；

// input: [10, 9, 2, 5, 3, 7, 101, 18] // output: [2, 3, 7, 101]public class NiBiNuCycle {static int counter = 0;public static void main(String[] args) { // int[] array = {10, 9, 2, 5, 3, 7, 101, 18};int[] array = {10, 90, 76, 12, 25, 36, 78, 99, 177, 132, 156};find(array, 0, array.length-1);System.out.println("result = " + counter);}static void find(int[] array, int i1, int i2) {int ci1=0, ci2=0; // ci1, ci2 是 i1 和 i2 的 copy// v1 v2 作為在范圍 [i1, i2] 區(qū)域中的最小最大值.// while(i1<i2) {int v1 = Integer.MAX_VALUE, v2 = Integer.MIN_VALUE;ci1=i1; ci2=i2;for (int i = i1; i <= i2; i++) {if(array[i] > v2) {v2 = array[i];ci2 = i;} if(array[i] < v1) {v1 = array[i];ci1 = i;}}System.out.println("v1 = " + v1 + ", v2 = " + v2);i1 = ci1+1;i2 = ci2-1; counter += 2;}if(i1==i2) {counter++;} } } 【4】O(nlgn)的時(shí)間復(fù)雜度的思路是：利用分治思想，下面給出偽代碼，但源碼未實(shí)現(xiàn)，僅供參考；

// input: [10, 9, 2, 5, 3, 7, 101, 18] // output: [2, 3, 7, 101]// 此題的分治版本.(偽代碼，源碼未實(shí)現(xiàn)) class MinMax {int i1; // 最小值的對(duì)應(yīng)indexint i2; // 最大值的......public MinMax(int i1, int i2) {this.i1 = i1;this.i2 = i2;}public MinMax(){} } public class NiBiNuRecursion {static int counter = 0;static MinMax result;public static void main(String[] args) {int[] array = {10, 90, 76, 12, 25, 78, 99, 177, 132, 156};find(array, 0, array.length-1);System.out.println("result = " + counter);}// 分治算法.static MinMax find(int[] array, int i1, int i2) {if(i1<i2) {int center = (i1+i2)/2;MinMax a = find(array, i1, center);MinMax b = find(array, center+1, i2);merge(...); // 這里應(yīng)該要做一次merge.} else return new MinMax(i1,i1);return result;} }

總結(jié)

以上是生活随笔為你收集整理的2017尼毕鲁笔试算法题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。