1、陣列中的逆序對
(學習影片推薦:java課程)
【題目】
在數組中的兩個數字,如果前面一個數字大於後面的數字,則這兩個數字組成一個逆序對。輸入一個數組,求這個數組中的逆序對的總數 P。並將 P 對 1000000007 取模的結果輸出。即輸出P 00000007
題目保證輸入的陣列中沒有的相同的數字
資料範圍:
对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
程式碼:
/** *在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。 * 输入一个数组,求出这个数组中的逆序对的总数 P。 * 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007 * * 利用归并排序的思想(倒序) * 当得到left和right两个待归并的数组时,由于二者已经排好顺序 * 当left中的A元素大于right中的B元素, * 那么right.length-b_index 个逆序对 * */ int count; public int InversePairs(int [] array) { return Merge(array,0,array.length-1); } public int Merge(int[] a, int start, int end) { if (start >= end) return count; int i,j,mid,index; int[] temp; mid = (start + end) / 2; Merge(a,start,mid); Merge(a,mid+1,end); i = start; j = mid + 1; temp = new int[end-start+1]; index = 0; while (i<=mid && j<=end) { if (a[i] > a[j]) { count = (count +end - j + 1) % 1000000007; temp[index++] = a[i++]; } else { temp[index++] = a[j++]; } } while (i<=mid) temp[index++] = a[i++]; while (j<=end) temp[index++] = a[j++]; index = start; for (i=0;i<temp.length; i++) { a[index++] = temp[i]; } return count; }
【思考】
在歸併排序的過程中後一個數組的數如小於前一個數組的數,則一定能夠構成逆序對且逆序對的數組可計算,因為待歸併的兩個數組提前已經歸併排序過,所以不會出現像前面那樣少統計或多統計的情況出現。
[A,B] 中的逆序對=[A] 的逆序對[B] 中的逆序對將A,B 混排在一起的逆序對
注意:題目中有一個特殊要求,需要取模,這個取模不只在結果取模,還要在過程計算中取模。
2、陣列中只出現一次的數字
【題目】
一個整數陣列裡除了兩個數字之外,其他的數字都出現了兩次。請寫程式找出這兩個只出現一次的數字。
【程式碼】
/** * 一个整型数组里除了两个数字之外,其他的数字都出现了两次。 * 请写程序找出这两个只出现一次的数字。 * * 位运算中异或的性质: * 两个相同数字异或 = 0,一个数和 0 异或还是它本身。 * a ⊕ a = 0 * a ⊕ b ⊕ a = b. * a ⊕ 0 = a * * 当只有一个数出现一次时,我们把数组中所有的数,依次异或运算, * 最后剩下的就是落单的数,因为成对儿出现的都抵消了。 * * 当出现两个数只出现一次时,依旧是依次异或运算, * 剩下的结果是两个只出现一次的数的异或结果 * 因为这两个数不同,所以我们通过二进制的异或把二者分开,在依次异或即可分别得到 * */ public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int i,n,res,count,res1,res2; n = array.length; if (n == 0 || array == null) return; res = 0;// 记录两个不同的数的异或结果 for (i=0; i<n; i++) { res = res ^ array[i]; } // 找到异或结果的二进制的的从右向左的第一个1 count = 1; while ((count & res) == 0) count = count << 1; // 通过找到的二进制结果来区分两个只出现第一次的数 res1 = 0; res2 = 0; for (i=0; i<n; i++) { if ((count & array[i]) == 0) { res1 = res1 ^ array[i]; } else { res2 = res2 ^ array[i]; } } num1[0] = res1; num2[0] = res2; }
【思考】
首先:位元運算中異或的性質:兩個相同數字異或= 0,一個數字和0 異或還是它本身。
當只有一個數出現一次時,我們把數組中所有的數,依次異或運算,最後剩下的就是落單的數,因為成對兒出現的都抵消了。
依照這個思路,我們來看兩個數(我們假設是 AB)出現一次的陣列。我們首先還是先異或,剩下的數字肯定是 A、B 異或的結果,這個結果的二進位中的 1,表現的是 A 和 B 的不同的位。我們就取第一個 1 所在的位數,假設是第 3 位,接著把原數組分成兩組,分組標準為第 3 位是否為 1。如此,相同的數肯定在一個組,因為相同數字所有位都相同,而不同的數,肯定不在一組。然後把這兩組依照最開始的思路,依序異或,剩餘的兩個結果就是這兩個只出現一次的數字。
(更多相關面試題推薦:java面試題目及答案)
#3、和為S 的兩個數字
【題目】
輸入一個遞增排序的陣列和一個數字S,在陣列中找出兩個數,使得他們的和剛好是S,如果有多對數字的和等於S,輸出兩個數的乘積最小的。
對應每個測試案例,輸出兩個數,小的先輸出。
【程式碼】
/** * 输入一个递增排序的数组和一个数字 S, * 在数组中查找两个数,使得他们的和正好是 S, * 如果有多对数字的和等于 S,输出两个数的乘积最小的。 * */ public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) { int mid,i,index,n,j; ArrayList<Integer> list; n = array.length; if (n == 0 || array == null || sum == 0) return new ArrayList<>(); mid = sum >> 1; if (array[0] > mid) return new ArrayList<>(); // 前两个元素和为sum list = new ArrayList<>(); if (array[0] == mid) { if (array[0] + array[1] == sum) { list.add(array[0]); list.add(array[1]); } return list; } // 获得mid在array的索引 index = 0; for (i=0; i<n; i++) { if (array[i] >= mid) { index = i; break; } } i = 0; j = index + 1; while (i<=index) { while (array[i] + array[j] < sum) { j++; } if (array[i] + array[j] == sum) { list.add(array[i]); list.add(array[j]); break; } else { i++; j = index + 1; } } return list; }
4、和為S 的連續正數序列
【題目】
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16 的和,他馬上就寫出了正確答案是100。但是他並不滿足於此,他在想究竟有多少種連續的正數序列的和為 100 (至少包括兩個數)。沒多久,他就得到另一組連續正數和為 100 的數列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為 S 的連續正數序列? Good Luck!
輸出所有和為S的連續正數序列。序列內依照從小至大的順序,序列間依照開始數字從小到大的順序
【程式碼】
/** * 输出所有和为S的连续正数序列。 * 序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序 * * 思路:回溯 * 算子,paths,path * */ TreeSet<Integer> path; ArrayList<ArrayList<Integer>> paths; ArrayList<Integer> list; public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { if (sum < 3) return new ArrayList<>(); int n,i,j,mid,count; paths = new ArrayList<>(); if (sum == 3) { list = new ArrayList<>(); list.add(1); list.add(2); paths.add(list); return paths; } // n代表sum这个数最多由几个数字构成 n = (int)Math.sqrt(sum) + 1; for (i=n; i>=2; i--) { count = 0; mid = sum / i; count += mid; path = new TreeSet<>(); path.add(mid); j = 1; while (count < sum) { count += mid+j; path.add(mid+j); count += mid-j; path.add(mid-j); j++; } if (count == sum) { list = new ArrayList<>(); list.addAll(path); paths.add(list); } else { int last = path.last(); int first = path.first(); if (count-last == sum) { path.remove(last); list = new ArrayList<>(); list.addAll(path); paths.add(list); } if (count-first == sum) { path.remove(first); list = new ArrayList<>(); list.addAll(path); paths.add(list); } } } return paths; }
【想法】
雙指標法
左右指標不斷圈定連續序列的範圍
輸入sum=20(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
1,定義兩個指針,左指針從1開始,右指針從2開始
循環開始
2,求和(1 2 = 3
3,如果判斷3小於20,右指針, 2變為3,求和3 3=6。循環一直到右指針=6,和為21。
4,else if 判斷21大於20,左指針,1變為2,和減去左指針值,和為21-1=20。
5,else 和與輸入一樣,存數。【再把右指針,求和,求剩餘組合】
循環結束
5、撲克牌順子
【題目】
LL 今天心情特别好,因为他去买了一副扑克牌,发现里面居然有 2 个大王,2 个小王 (一副牌原本是 54 张 _)… 他随机从中抽出了 5 张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心 A, 黑桃 3, 小王,大王,方片 5”,“Oh My God!” 不是顺子…LL 不高兴了,他想了想,决定大 \ 小 王可以看成任何数字,并且 A 看作 1,J 为 11,Q 为 12,K 为 13。上面的 5 张牌就可以变成 “1,2,3,4,5”(大小王分别看作 2 和 4),“So Lucky!”。LL 决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们 LL 的运气如何, 如果牌能组成顺子就输出 true,否则就输出 false。为了方便起见,你可以认为大小王是 0。
【代码】
/** * 判断顺子,大小王为0 * * 计算0的个数 * 计算非0的差 * */ public boolean isContinuous(int [] numbers) { if (numbers.length == 0 || numbers == null) return false; Arrays.sort(numbers); int n,i,count,minus; n = numbers.length; count = 0; minus = 0; for (i=0; i<n-1; i++) { if (numbers[i] == 0) { count++; } else { minus += numbers[i+1] - numbers[i]; } } // 除了最后一个其他都是0 if (count == n-1) return true; // 存在相同的值 if (minus != (numbers[n-1] - numbers[count])) return false; if (minus == 0) return false; return (minus - (n-count-1)) > count ? false : true; }
【思考】
可以考虑使用treeset这个结构,本身带有排序功能,并且不会存储相同元素,可以方便判断。
相关推荐:java入门
以上是java面試中常見的陣列題目總結(四)的詳細內容。更多資訊請關注PHP中文網其他相關文章!