刷題啦刷題啦，劍指offer好像比較有名，所以就在牛客網(wǎng)上刷這個(gè)吧~
btw，刷了一些題發(fā)現(xiàn)編程之美的題好典型?。?！有不少都在筆試遇到過(guò)或者是特別有名之前做過(guò)的題。后悔沒(méi)早點(diǎn)刷T T
1.二維數(shù)組中的查找
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
思路就是從右上角開(kāi)始，比target大就向左移一位找小一點(diǎn)的，比target小就向下移找大一點(diǎn)的，直到找到為止。
public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length == 0 || array[0].length == 0){
return false;
}
int row = array.length;
int col = array[0].length;
for(int i = 0, j = col - 1; i < row && j >= 0;){
if(target == array[i][j]){
return true;
}
else if(target > array[i][j]){
i++;
continue;
}
else{
j--;
continue;
}
}
return false;
}
}
2.替換空格
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer sb = new StringBuffer();
for(int i = 0; i < str.length(); i++){
if(' ' == str.charAt(i)){
sb.append("%20");
}else{
sb.append(str.charAt(i));
}
}
return sb.toString();
}
}
3.從尾到頭打印鏈表
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。
有幾種解法：
第一種是正序鏈表元素并存在list后反轉(zhuǎn)list；
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode head = listNode;
while(head != null){
list.add(head.val);
head = head.next;
}
int num = list.size();
for(int i = 0; i < num/2; i++){
int temp = list.get(i);
list.set(i,list.get(num-1-i));
list.set(num-1-i,temp);
}
return list;
}
}
第二種是使用棧，入棧再出棧就會(huì)使原順序反向；
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
ListNode head = listNode;
while(head != null){
stack.push(head.val);
head = head.next;
}
while(!stack.empty()){
list.add(stack.pop());
}
return list;
}
}
第三種方法是用遞歸。
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode head = listNode;
if(head != null){
list = printListFromTailToHead(head.next);
list.add(head.val);
}
return list;
}
}
4.重建二叉樹(shù)
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。
之前分析二叉樹(shù)的帖子已經(jīng)寫(xiě)過(guò)一次了，這次再寫(xiě)發(fā)現(xiàn)root.right那一行遞歸中最后一個(gè)參數(shù)（表明此時(shí)前序中的root位置）很容易寫(xiě)錯(cuò)。index-inFrom是在中序中當(dāng)前左子樹(shù)的結(jié)點(diǎn)數(shù)目，preIndex是指從此時(shí)的前序root算起。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(null == pre || pre.length == 0) return null;
return construct(pre, in, 0, in.length - 1, 0);
}
public TreeNode construct(int [] pre, int [] in, int inFrom, int inTo, int preIndex){
if(inFrom > inTo) return null;
TreeNode root = new TreeNode(pre[preIndex]);
int index = inFrom;
for(; index <= inTo; index++){
if(in[index] == pre[preIndex]){
break;
}
}
root.left = construct(pre, in, inFrom, index - 1, preIndex + 1);
root.right = construct(pre, in, index + 1, inTo, preIndex + index - inFrom + 1);
return root;
}
}
5.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。
棧那篇文章分析過(guò)，記得挺簡(jiǎn)單的就不再寫(xiě)了。
6.旋轉(zhuǎn)數(shù)組的最小數(shù)字
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。
典型二分法，分幾種情況討論就行。要注意的是當(dāng)元素變?yōu)?個(gè)的時(shí)候是個(gè)特殊情況，如果不拿出來(lái)單獨(dú)討論就會(huì)陷在low=mid<high這個(gè)循環(huán)里了。
很奇怪的是，這段代碼在我自己給的幾個(gè)測(cè)試用例還有l(wèi)eetcode下都是對(duì)的，可是?？途W(wǎng)上不對(duì)，不知道為什么。
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0) return 0;
int low = 0;
int high = array.length - 1;
int mid;
while(low < high){
if(low == high - 1) return array[low] > array[high] ? array[high] : array[low];
mid = (low + high) / 2;
if(array[low] <= array[high]){
return array[low];
}
else{
if(array[low] <= array[mid]){
low = mid;
}else{
high = mid;
}
}
}
return array[low];
}
}
7.斐波那契數(shù)列
public int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return Fibonacci(n-2) + Fibonacci(n-1);
}
8.跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
曾經(jīng)面試問(wèn)到過(guò)這題，我還很傻地說(shuō)我做過(guò)這題，然后就換了一道我不會(huì)的......
思路想明白了就很簡(jiǎn)單，要求跳n級(jí)臺(tái)階的跳法f(n)，最后一步如果跳1級(jí)，跳法是f(n-1)；如果跳2級(jí)，跳法是f(n-2)，總跳法就是他們相加。
public int JumpFloor(int target) {
if(target == 1) return 1;
if(target == 2) return 2;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
9.變態(tài)跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
按照上面一樣的思路，只是需要把所有情況累加起來(lái)。
public int JumpFloorII(int target) {
if(target == 0 || target == 1) return 1;
int res = 0;
for(int i = 0; i < target; i++){
res += JumpFloorII(i);
}
return res;
}
10.矩形覆蓋
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
跟跳臺(tái)階相似，f(n) = f(n-1) + f(n-2)。f(n-1)情況是加一塊豎矩形，f(n-2)情況是加兩塊橫矩形。
public int RectCover(int target) {
if(target == 0) return 0;
if(target == 1) return 1;
if(target == 2) return 2;
return RectCover(target-1) + RectCover(target-2);
}
11.二進(jìn)制中1的個(gè)數(shù)
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。
(n-1) & n 會(huì)讓從左往右第一個(gè)1變?yōu)?，一直操作直到整個(gè)數(shù)為0。
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
count++;
n = (n-1) & n;
}
return count;
}
12.數(shù)值的整數(shù)次方
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
關(guān)鍵是考慮到exponent為負(fù)的情況。
public double Power(double base, int exponent) {
if(exponent == 0) return 1;
if(exponent < 0){
return 1/base * Power(base,exponent + 1);
}
return base * Power(base,exponent - 1);
}
13.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
第一個(gè)做法是使用一個(gè)新數(shù)組，遍歷原數(shù)組按次序把奇數(shù)儲(chǔ)存在新數(shù)組中，再遍歷原數(shù)組把偶數(shù)儲(chǔ)存在后面，最后復(fù)制新數(shù)組給原數(shù)組。
public void reOrderArray(int [] array) {
int[] a = new int[array.length];
int j = 0;
for(int elem : array){
if(elem % 2 != 0){
a[j++] = elem;
}
}
for(int elem : array){
if(elem % 2 == 0){
a[j++] = elem;
}
}
for(int i = 0; i < array.length; i++){
array[i] = a[i];
}
}
第二種方法是采用插入排序的思想。
public void reOrderArray(int [] array) {
for(int i = 1; i < array.length; i++){
if(array[i] % 2 != 0){
int odd = array[i];
int j = i - 1;
for(; j >= 0; j--){
if(array[j] % 2 == 0){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = odd;
}
}
}
還可以采取冒泡排序的思路，不過(guò)差不多啦。
14.鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。
可以用快慢結(jié)點(diǎn)的思想，讓快結(jié)點(diǎn)先走k步，然后快慢同時(shí)走，快結(jié)點(diǎn)到頭了慢結(jié)點(diǎn)也就到倒數(shù)第k了。要注意k可沒(méi)確保是正確的，可能比鏈表結(jié)點(diǎn)數(shù)要大，所以在先走k步時(shí)就要時(shí)刻判null了。
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < k; i++){
if(fast == null) return null;
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
15.反轉(zhuǎn)鏈表
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode prev = head;
ListNode curr = head.next;
prev.next = null;
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode p = prev;
while(p != null){
System.out.println(p.val);
p = p.next;
}
return prev;
}
16.合并兩個(gè)排序的鏈表
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
之前寫(xiě)過(guò)iterative版本的，比較冗長(zhǎng)，用recursive版本更短更好理解。
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode head = null;
if(list1.val < list2.val){
head = list1;
head.next = Merge(list1.next, list2);
}else{
head = list2;
head.next = Merge(list1,list2.next);
}
return head;
}
17.樹(shù)的子結(jié)構(gòu)
輸入兩棵二叉樹(shù)A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）
?？途W(wǎng)的定義不是很清楚，我覺(jué)得應(yīng)該再加上兩點(diǎn)：1.結(jié)構(gòu)相同且對(duì)應(yīng)位置的值也相同；2.樹(shù)[1,2]是樹(shù)[1,2,3]的子結(jié)構(gòu)。
如果參考leetcode上判subtree那道題：
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSubtree(TreeNode root1, TreeNode root2) {
if(root2 == null || root1 == null) return false;
if(sameTree(root1, root2)) return true;
return isSubtree(root1.left, root2) || isSubtree(root1.right, root2);
}
public boolean sameTree(TreeNode root1, TreeNode root2){
if(root1 == null && root2 == null) return true;
if(root1 != null && root2 != null && root1.val == root2.val) return sameTree(root1.left, root2.left) && sameTree(root1.right, root2.right);
return false;
}
}
如果是牛客網(wǎng)上的思路，應(yīng)該把判相同的函數(shù)改為判子結(jié)構(gòu)函數(shù)，當(dāng)對(duì)應(yīng)位置子結(jié)構(gòu)沒(méi)了而復(fù)結(jié)構(gòu)不一定沒(méi)了，仍然為真。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2 == null || root1 == null) return false;
return isSubTree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
public boolean isSubTree(TreeNode root1, TreeNode root2){
if(root2 == null) return true;
if(root1 == null) return false;
if(root1.val == root2.val) {
return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
}
return false;
}
}
18.二叉樹(shù)的鏡像
二叉樹(shù)里寫(xiě)過(guò)不說(shuō)了。
19.順時(shí)針打印矩陣
構(gòu)造一個(gè)數(shù)組step來(lái)記錄上下左右的單位偏移量，用對(duì)應(yīng)的multiple來(lái)記錄偏移量數(shù)目，count%4作為數(shù)組索引。這樣讓上下左右在代碼中都能一視同仁?？墒遣粚?duì)，也沒(méi)調(diào)出來(lái)結(jié)果，先貼在這里吧。
public static ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(matrix.length == 0 || matrix[0].length == 0) return list;
int[] step = {1,1,-1,-1}; //right, down, left, up
int[] limit = {matrix[0].length, matrix.length, 0, 0}; //jHigh, iHigh, jLow, iLow
int count = 0;
int i = 0, j = 0;
while(limit[2] < limit[0] || limit[3] < limit[1]){
int[] multiple = {0,0,0,0};
multiple[count]++;
while(i >= limit[3] && i < limit[1] && j >= limit[2] && j < limit[0]){
//System.out.println("i = " + i + ", j = " + j);
list.add(matrix[i][j]);
i += step[1]*multiple[1] + step[3]*multiple[3];
j += step[0]*multiple[0] + step[2]*multiple[2];
}
limit[count%4] -= step[count%4];
count = (count+1) % 4;
}
return list;
}
20.包含Min函數(shù)的棧
棧的帖子中寫(xiě)過(guò)，筆試題也遇到過(guò)。
public class Solution {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
stack.push(node);
if(minStack.empty() || node < minStack.peek()) minStack.push(node);
else minStack.push(minStack.peek());
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return minStack.peek();
}
public int min() {
return minStack.peek();
}
}
21.棧的壓入、彈出序列
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）
又是在棧文章里面寫(xiě)過(guò)的題，重新寫(xiě)了一遍，簡(jiǎn)化了一個(gè)步驟：可以不用先把popA里面元素Push進(jìn)去再與popA比較，而是直接比較當(dāng)前的popA和pushA元素，相等就直接跳過(guò)。
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int j = 0;
for(int i = 0; i < pushA.length;i++){
if(popA[j] == pushA[i]){
j++;
}else{
stack.push(pushA[i]);
}
}
while(j < popA.length){
if(stack.pop() != popA[j++]) return false;
}
return true;
}
22.從上往下打印二叉樹(shù)
層序遍歷（廣度優(yōu)先），二叉樹(shù)里寫(xiě)過(guò)的，這次兩分鐘一次通過(guò)！
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(queue.peek() != null){
int len = queue.size();
for(int i = 0; i < len; i++){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left != null) queue.offer(temp.left);
if(temp.right != null) queue.offer(temp.right);
}
}
return list;
}
23.二叉搜索樹(shù)的后續(xù)遍歷
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
因?yàn)槭呛笮虮闅v，所以最后一個(gè)數(shù)是根節(jié)點(diǎn)。根節(jié)點(diǎn)比左子樹(shù)所有結(jié)點(diǎn)大，比右子樹(shù)所有結(jié)點(diǎn)小，所以先找到第一個(gè)比根結(jié)點(diǎn)大的結(jié)點(diǎn)，以此位置區(qū)分左子樹(shù)和右子樹(shù)，左子樹(shù)已經(jīng)保證了都比根小了，再一個(gè)個(gè)判斷右邊是不是都比根結(jié)點(diǎn)大，如果不是，肯定是false。再遞歸對(duì)左子樹(shù)和右子樹(shù)判斷。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0) return false;
return isPostOrder(sequence, 0, sequence.length - 1);
}
//end inclusive
public boolean isPostOrder(int[] postOrder, int start, int end){
if(start < end){
int root = postOrder[end];
int index = start;
for(; index < end; index++){
if(root < postOrder[index]){
break;
}
}
for(int i = index + 1; i < end; i++){
if(root > postOrder[i]) return false;
}
return isPostOrder(postOrder, start, index - 1) && isPostOrder(postOrder, index, end - 1);
}
return true;
}
}
24.二叉樹(shù)中和為某一值的路徑
輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。
用遞歸解決，臨界條件是葉節(jié)點(diǎn)剛好等于某值，說(shuō)明這是一條有效路徑，所以開(kāi)一個(gè)新list添加進(jìn)結(jié)果；遞歸時(shí)不斷把路徑上的點(diǎn)加到list最前面（combine函數(shù)）。
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>();
if(root == null) return l;
if(root.val == target && root.left == null && root.right == null){
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(root.val);
l.add(temp);
return l;
}
ArrayList<ArrayList<Integer>> left = combine(root.val, FindPath(root.left, target - root.val));
ArrayList<ArrayList<Integer>> right = combine(root.val, FindPath(root.right, target - root.val));
l.addAll(left);
l.addAll(right);
return l;
}
public ArrayList<ArrayList<Integer>> combine(int first, ArrayList<ArrayList<Integer>> l){
for(int i = 0; i < l.size(); i++){
l.get(i).add(0, first);
}
return l;
}
}
25.復(fù)雜鏈表的復(fù)制
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
關(guān)鍵是random指向任意一個(gè)節(jié)點(diǎn)，所以不能按原鏈表節(jié)點(diǎn)的random值新建它。先使用HashMap建立原鏈表主鏈（不含random）節(jié)點(diǎn)和對(duì)應(yīng)復(fù)制的鏈表結(jié)點(diǎn)之間的映射，再遍歷鏈表通過(guò)HashMap來(lái)確定各節(jié)點(diǎn)的random。
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null) return null;
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
RandomListNode newHead = new RandomListNode(pHead.label);
RandomListNode r = newHead;
RandomListNode p = pHead;
map.put(p,r);
while(p.next != null){
r.next = new RandomListNode(p.next.label);
p = p.next;
r = r.next;
map.put(p,r);
}
p = pHead;
r = newHead;
while(p != null){
r.random = map.get(p.random);
p = p.next;
r = r.next;
}
return newHead;
}
26.二叉搜索樹(shù)與雙向鏈表
輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
函數(shù)返回的是鏈表頭結(jié)點(diǎn)（最小值），根據(jù)二叉搜索樹(shù)的特點(diǎn)，遞歸得出右子樹(shù)的最小值應(yīng)緊跟在在根結(jié)點(diǎn)后。左子樹(shù)有些不一樣，遞歸得出的是左子樹(shù)的最小值，而我們應(yīng)找到左子樹(shù)最大值，調(diào)整指針讓它在根結(jié)點(diǎn)前。所以再用一個(gè)函數(shù)求最大值結(jié)點(diǎn)。
要注意是先convert后調(diào)整指針指向，否則convert的對(duì)象是一棵已被破壞的樹(shù)。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
TreeNode res = pRootOfTree;
if(pRootOfTree == null || (pRootOfTree.left == null && pRootOfTree.right == null)) return res;
if(pRootOfTree.left != null){
res = Convert(pRootOfTree.left);
TreeNode big = biggest(pRootOfTree.left);
big.right = pRootOfTree;
pRootOfTree.left = big;
}
if(pRootOfTree.right != null){
TreeNode small = Convert(pRootOfTree.right);
pRootOfTree.right = small;
small.left = pRootOfTree;
}
return res;
}
public TreeNode biggest(TreeNode root){
if(root.right == null) return root;
return biggest(root.right);
}
}
27.字符串的排列
輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
又是全排列.......注意這次要字典順序而且結(jié)果不重復(fù)。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
if(str == null || str.length() == 0) return new ArrayList<String>();
ArrayList<String> res = new ArrayList(new HashSet(helper(str.toCharArray(),0)));
Collections.sort(res);
return res;
}
public void swap(char[] array, int i, int j){
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public ArrayList<String> helper(char[] array, int start){
ArrayList<String> list = new ArrayList<String>();
if(start == array.length - 1){
list.add(String.valueOf(array[start]));
}
for(int i = start; i < array.length; i++){
swap(array,start,i);
ArrayList<String> temp = helper(array, start + 1);
list.addAll(combine(array[start],temp));
swap(array,start,i);
}
return list;
}
public ArrayList<String> combine(char ch, ArrayList<String> list){
for(int i = 0; i < list.size(); i++){
list.set(i, String.valueOf(ch) + list.get(i));
}
return list;
}
}
28.數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出2。如果不存在則輸出0。
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int elem: array){
if(map.containsKey(elem)){
int count = map.get(elem);
map.put(elem,map.get(elem) + 1);
}else{
map.put(elem,1);
}
}
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
if(entry.getValue() > array.length / 2) return entry.getKey();
}
return 0;
}
}
29.最小的k個(gè)數(shù)
輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。
冒泡排序的前k次排序即可。算法復(fù)雜度O(kn)。
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(k > input.length) return list;
for(int i = 0; i < k; i++){
for(int j = input.length - 1; j > i; j--){
if(input[j] < input[j - 1]){
int temp = input[j];
input[j] = input[j - 1];
input[j - 1] = temp;
}
}
list.add(input[i]);
}
return list;
}
31.連續(xù)子數(shù)組的最大和
HZ偶爾會(huì)拿些專業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開(kāi)完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問(wèn)題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開(kāi)始,到第3個(gè)為止)。你會(huì)不會(huì)被他忽悠住？(子向量的長(zhǎng)度至少是1)
32.整數(shù)中1出現(xiàn)的次數(shù)
求出113的整數(shù)中1出現(xiàn)的次數(shù),并算出1001300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)。
腦袋都要想破了，有點(diǎn)點(diǎn)麻煩的一道題。
思路是先統(tǒng)計(jì)個(gè)位數(shù)出現(xiàn)1的次數(shù)，再統(tǒng)計(jì)十位數(shù)出現(xiàn)1的次數(shù)......
while循環(huán)里每次對(duì)一個(gè)位數(shù)統(tǒng)計(jì)，要注意的是quotient2%10計(jì)算的是當(dāng)位數(shù)的數(shù)字，如果大于1，要加一個(gè)位數(shù)的滿輪次；如果等于1，不滿一個(gè)位數(shù)但有剩余，要單獨(dú)算出這個(gè)extra。
public int NumberOf1Between1AndN_Solution(int n) {
int num = 0;
int quotient1 = -1;
int count = 0;
while(quotient1 != 0){
int dividend2 = (int)Math.pow(10.0,(double)count++);
int dividend1 = 10 * dividend2;
quotient1 = n/dividend1;
int quotient2 = n/dividend2;
int extra = 0;
int extra1 = 0;
if(quotient2%10 == 1){
extra = n % dividend2 + 1;
}else if(quotient2%10 != 0){
extra1 = 1;
}
num += (quotient1 + extra1) * dividend2 + extra;
}
return num;
}
33.把數(shù)組排成最小的數(shù)
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。
就排前排后而言，這些數(shù)之間是有相對(duì)大小的。對(duì)兩個(gè)數(shù)而言，把他們拼接起來(lái)，拼在前面更小說(shuō)明這個(gè)數(shù)更“小”。Arrays有一個(gè)
sort(T[] a, Comparator<? super T> c) 函數(shù)，可以通過(guò)自定義compare方法來(lái)排序a。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
String s = "";
if(numbers == null || numbers.length == 0) return s;
String[] sArray = new String[numbers.length];
for(int i = 0; i < numbers.length; i++){
sArray[i] = String.valueOf(numbers[i]);
}
Arrays.sort(sArray, new Comparator<String>(){
public int compare(String s1, String s2){
return (s1+s2).compareTo(s2+s1);
}
});
for(String elem: sArray){
s += elem;
}
return s;
}
}