<h2>劍指offer(二)</h2>
<h3>面試題九:斐波那契數(shù)列</h3>
<blockquote>
題目一:寫(xiě)一個(gè)函數(shù)闷煤,輸入n朋截,求斐波那契數(shù)列的第n項(xiàng),裴波納契數(shù)列的定義如下:
</blockquote>
$$f(n)=0 | n = 0$$
$$f(n)=1 | n = 1$$
$$f(n)=f(n-1)+f(n-2) | n > 1$$
<blockquote>
斐波那契數(shù)列使用循環(huán)效率比遞歸效率高,每一次函數(shù)調(diào)用恃慧,都需要在內(nèi)存棧中分配空間保存參數(shù)
</blockquote>
<pre><code> public static long Fibonacci(int n) {
if (n < 0)
throw new IllegalArgumentException("invaild parameters");
if (n <= 1)
return n;
long fibNMinusOne = 1;
long fibNMinusTwo = 0;
long fibN = 0;
for (int i = 2; i <= n; ++i) {
fibN = fibNMinusTwo + fibNMinusOne;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne= fibN;
}
return fibN;
}
</code></pre>
<blockquote>
題目二:一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)渺蒿,求該青蛙跳上一個(gè)n級(jí)的臺(tái)階痢士,總共有多少種跳法。
</blockquote>
第一次跳的時(shí)候有兩種選擇,跳1級(jí)和跳2級(jí)怠蹂,可以換算成斐波那契數(shù)列善延。代碼與上面相同。
<h3>面試題十:二進(jìn)制中1的個(gè)數(shù)</h3>
<blockquote>
題目: 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)城侧,輸入一個(gè)整數(shù)易遣,輸出該數(shù)二進(jìn)制中1的個(gè)數(shù)。例如把9表示成二進(jìn)制是1001嫌佑,有兩位是1豆茫,因此如果輸入9,該函數(shù)輸出2.
</blockquote>
常規(guī)解法:
<pre><code>int NumberOf(int n){
int count = 0;
unsigned int flag = 1;
while(flag){
if(n & flag)
count ++;
flag = flag<<1;
}
return count;
}
</code></pre>
驚喜解法:
<pre><code class="java">public static int numberOf(int n) {
int count = 0;
while (n != 0) {
count++;
n = n &(n-1);
}
return count;
}
</code></pre>
思路:把一個(gè)數(shù)減1屋摇,與之前的數(shù)揩魂,最后一位1就會(huì)變?yōu)?,有多少個(gè)1炮温,就能做多少次與運(yùn)算火脉。
<h3>面試技巧</h3>
代碼的完整性,從3個(gè)方面確保代碼的完整性
- 功能測(cè)試
- 邊界測(cè)試
- 負(fù)面測(cè)試
<h3>面試題十一:數(shù)值的整數(shù)n次方</h3>
<blockquote>
題目:實(shí)現(xiàn)函數(shù)double Power(double base,int exponent)求base得exponent次方柒啤,不使用庫(kù)函數(shù)忘分,同時(shí)不需要考慮大數(shù)問(wèn)題
</blockquote>
公式
$a^n = a{n/2}·a{n/2} $ <strong>n為偶數(shù)</strong>
$an=a{(n-1)/2}·a^{(n-1)/2}·a$ <strong>n為奇數(shù)</strong>
<pre><code class="java">/**
-
Created by kangqizhou on 2017/1/30.
*/
public class Offer11 {
public static void main(String[] args) {
Utils.syso(PowerWithExport(2, 2));
}public static double PowerWithExport(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
double result = PowerWithExport(base, exponent >> 1);//無(wú)論是奇數(shù)還是偶數(shù),右移以后都為n/2或者(n-1)/2
result *= result;
if ((exponent & 0x1) == 1) {//代表為奇數(shù)白修,再乘以base
result *= base;
}
return result;
}
}
</code></pre>
<h3>面試題十二:打印從1到最大的n位數(shù)</h3>
<blockquote>
題目:輸入數(shù)字n妒峦,按順序打印出從1到最大的n位十進(jìn)制數(shù),比如輸入3兵睛,則打印1肯骇,2,3一直到最大的3位數(shù)即999
</blockquote>
思路:不能直接使用int來(lái)循環(huán)祖很,如果n是一個(gè)大數(shù)笛丙,很容易溢出,最直觀(guān)的就是假颇,使用數(shù)組中的每位來(lái)表示0到9的某一個(gè)字符胚鸯。對(duì)于n位的字符,我們需要準(zhǔn)備一個(gè)n+1的字符串
<pre><code>/**
-
Created by kangqizhou on 2017/1/30.
public static void printNumbers(int n) {
*/
public class Offer12 {
public static void main(String... args) {
printNumbers(2);
}
if(n < 1)
throw new RuntimeException("The input number must larger than 0");
int[] numbers = new int[n];
for (int i = 0; i < n; i++) {
numbers[i] = 0;
}
while (addOne(numbers) == 0) {
printAllNumber(numbers);
}
}private static int addOne(int[] numbers) {
int index = numbers.length;
int flag = 1;
do {
index--;
numbers[index] += flag;
flag = numbers[index] / 10;
numbers[index] %= 10;
} while (index > 0 && flag != 0);
if (index == 0 && flag == 1)
return 1;
return 0;
}private static void printAllNumber(int[] numbers) {
int index = 0;
while (index < numbers.length && numbers[index] == 0) {
index++;
}
for (int i = index; i < numbers.length; i++) {
System.out.print(numbers[i]);
}
System.out.println("");
}
}
</code></pre>
<h4>遞歸解法</h4>
<pre><code>public static void printOneToNthDigits(int n, int[] arr) {
// 說(shuō)明所有的數(shù)據(jù)排列選擇已經(jīng)處理完了
if (n >= arr.length) {
// 可以輸入數(shù)組的值
printArray(arr);
} else {
// 對(duì)
for (int i = 0; i <= 9; i++) {
arr[n] = i;
printOneToNthDigits(n + 1, arr);
}
}
}
</code></pre>
<h3>面試題十三:在O(1)時(shí)間刪除鏈表結(jié)點(diǎn)</h3>
<blockquote>
題目:給定單向鏈表的頭指針和結(jié)點(diǎn)指針笨鸡,定義一個(gè)函數(shù)姜钳,在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)與函數(shù)的定義如下:
</blockquote>
<pre><code class="cpp">struct ListNode{
int m_nValue;
ListNode* m_pNext;
};
void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);
</code></pre>
思路:如果是中間的結(jié)點(diǎn)形耗,用下一個(gè)結(jié)點(diǎn)的value和next覆蓋掉當(dāng)前的結(jié)點(diǎn)哥桥,如果是頭結(jié)點(diǎn),直接刪除激涤,如果是尾結(jié)點(diǎn)拟糕,就循環(huán)刪除。不一定要真的釋放掉目標(biāo)結(jié)點(diǎn)的內(nèi)存,可以釋放目標(biāo)節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)的內(nèi)存送滞。
<pre><code class="java">/**
-
Created by kangqizhou on 2017/1/30.
*/
public class Offer13 {
public static void main(String... args) {
ListNode node = new ListNode();
ListNode start = node;
ListNode preDeleted = null;
node.m_value = 0;
for (int i = 1; i < 10; i++) {
ListNode nextNode = new ListNode();
nextNode.m_value = i;
node.next = nextNode;
node = nextNode;
if (i == 5) {
preDeleted = node;
}
}
deleteNode(start, preDeleted);}
private static void deleteNode(ListNode start, ListNode preDeleted) {
if (start == null || preDeleted == null)
return;
if (preDeleted.next != null) {
System.out.println("delete node " + preDeleted.m_value);
ListNode node = preDeleted.next;
preDeleted.m_value = node.m_value;
preDeleted.next = node.next;
node = null;
} else if (start == preDeleted) {
System.out.println("delete node " + start.m_value);
}else {
ListNode node = start;
while (node.next!=preDeleted){
node = node.next;
}
node.next = null;
preDeleted = null;
}
}private static class ListNode {
int m_value;
ListNode next;
}
}
</code></pre>
平均時(shí)間復(fù)雜度為$[(n-1)*O(1)+O(n)]/n$侠草,結(jié)果還是O(1)
<h3>面試題十四:調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面</h3>
<blockquote>
題目:輸入一個(gè)整數(shù)數(shù)組,實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序犁嗅,使得所有奇數(shù)位于數(shù)組的前半部分梦抢,所有偶數(shù)位于數(shù)組的后半部分
</blockquote>
<h4>初級(jí)解法</h4>
<pre><code class="java">import java.util.Arrays;
/**
-
Created by kangqizhou on 2017/1/31.
*/
public class Offer14 {
public static void main(String... args) {
int a[] = {2, 1, 4, 5, 7, 3, 9, 3, 2, 4, 6, 8, 10};
changeArray(a);
Utils.syso(Arrays.toString(a));
}private static void changeArray(int[] a) {
if (a == null || a.length <= 0)
return;
int i = 0;
int j = a.length - 1;
while (i < j) {
while (i < 6 && isOdd(a[i])) {
i++;
}
while (j > 0 && !isOdd(a[j])) {
j--;
}
if (i > j) {
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];
}}
}
//將獨(dú)立的功能解耦,提高了代碼的重用性
private static boolean isOdd(int number){
return number % 2==1;
}
}
</code></pre>
<h3>面試題十五:鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)</h3>
<blockquote>
題目:輸入一個(gè)鏈表愧哟,輸出該鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)奥吩,為了符合大多數(shù)人的習(xí)慣,本題從1開(kāi)始計(jì)數(shù)蕊梧,即鏈表的尾結(jié)點(diǎn)是倒數(shù)第一個(gè)節(jié)點(diǎn)霞赫,例如一個(gè)鏈表有6個(gè)結(jié)點(diǎn),從頭結(jié)點(diǎn)開(kāi)始肥矢,他們的值依次是1端衰、2、3甘改、4旅东、5、6.這個(gè)鏈表倒數(shù)第3個(gè)結(jié)點(diǎn)是值為4的結(jié)點(diǎn)十艾。
鏈表結(jié)點(diǎn)的定義如下
</blockquote>
<pre><code class="cpp">stuct ListNode{
int m_nValue;
ListNode* m_pNext;
}
</code></pre>
<pre><code class="java">/**
-
Created by kangqizhou on 2017/1/31.
*/
public class Offer15 {
public static void main(String... args) {
ListNode start = new ListNode();
ListNode temp = start;
start.value = 0;
for (int i = 1; i < 10; i++) {
ListNode node = new ListNode();
node.value = i;
temp.next = node;
temp = node;
}
Utils.syso(getValue(start, 2).value);
}private static ListNode getValue(ListNode start, int k) {
if (start == null || k <= 0)
return null;
ListNode index1Node = start;
for (int i = 0; i < k - 1; i++) {
if (index1Node.next != null) {
index1Node = index1Node.next;
} else {
return null;
}
}
ListNode index2Node = start;
while (index1Node.next != null) {
index1Node = index1Node.next;
index2Node = index2Node.next;
}
return index2Node;
}private static class ListNode {
int value;
ListNode next;
}
}
</code></pre>
<h4>思路</h4>
定義兩個(gè)指針抵代,第一個(gè)移動(dòng)到k-1時(shí),開(kāi)始移動(dòng)第一個(gè)指針忘嫉。直到第二個(gè)的next為null荤牍。
<h3>面試題十六:反轉(zhuǎn)鏈表</h3>
<blockquote>
題目:定義一個(gè)函數(shù),輸入一個(gè)鏈表的頭結(jié)點(diǎn)庆冕,反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)康吵。
</blockquote>
<pre><code>/**
-
Created by kangqizhou on 2017/1/31.
*/
public class Offer16 {
public static void main(String... args){
Utils.syso(reverseList(ListNode.getSample()).value);
}public static ListNode reverseList(ListNode start){
if (start==null)
return null;
ListNode temp1 = start;
ListNode temp2 = null;
ListNode newStart = null;
while (temp1!=null){
ListNode temp3 = temp1.next;
if (temp3==null)
newStart = temp1;
temp1.next = temp2;
temp2 = temp1;
temp1 = temp3;
}
return newStart;
}
}
</code></pre>
<h3>面試題十七: 合并兩個(gè)排序的鏈表</h3>
<blockquote>
題目:輸入兩個(gè)遞增排序的列表,合并這兩個(gè)鏈表并使新鏈表并使新鏈表中的節(jié)點(diǎn)仍然是按照遞增排序的访递。例如輸入圖3.7中的鏈表1和鏈表2晦嵌,則合并之后的升序鏈表如鏈表3所示。鏈表結(jié)點(diǎn)定義如下:
</blockquote>
<pre><code>private static ListNode merge(ListNode node1, ListNode node2) {
if (node1 == null || node2 == null)
throw new NullPointerException("invaild arguments");
ListNode start = new ListNode();
ListNode temp = start;
while (node1 != null && node2 != null) {
if (node1.value < node2.value) {
temp.value = node1.value;
node1 = node1.next;
} else {
temp.value = node2.value;
node2 = node2.next;
}
temp.next = new ListNode();
temp = temp.next;
}
if (node2!=null)
temp.value = node2.value;
else temp.value = node1.value;
return start;
}
</code></pre>
<h3>面試題十八:樹(shù)的子結(jié)構(gòu)</h3>
<blockquote>
題目:輸入兩棵二叉樹(shù)A和B拷姿,判斷B是不是A的子結(jié)構(gòu)惭载。二叉樹(shù)結(jié)點(diǎn)的定義如下
</blockquote>
<pre><code class="cpp">struct BinaryTreeNode{
int m_nValue;
BinaryTreeNode* left;
BinaryTreeNode* right;
}
</code></pre>
<pre><code class="java"> public static boolean HasSubTree(TreeNode root, TreeNode root2) {
boolean result = false;
if (root != null && root2 != null) {
if (root.value == root2.value) {
result = doesTree1HaveTree2(root, root2);
}
if (!result)
result = HasSubTree(root.left, root2);
if (!result)
result = HasSubTree(root.right, root2);
}
return result;
}
private static boolean doesTree1HaveTree2(TreeNode root, TreeNode root2) {
if (root2 == null)
return true;
if (root == null)
return false;
if (root.value != root2.value)
return false;
return doesTree1HaveTree2(root.left, root2.left) && doesTree1HaveTree2(root.right, root2.right);
}
</code></pre>
<h3>面試題十九:二叉樹(shù)的鏡像</h3>
<blockquote>
題目:請(qǐng)完成一個(gè)函數(shù),輸入一個(gè)二叉樹(shù)跌前,該函數(shù)輸出他的鏡像棕兼。
</blockquote>
<pre><code class="java"><br /> public static void mirrorRecursively(TreeNode node) {
if (node == null)
return;
if (node.left == null && node.right == null)
return;
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left!=null)
mirrorRecursively(node.left);
if(node.right!=null)
mirrorRecursively(node.right);
}
</code></pre>
<h3>面試題二十:順時(shí)針打印矩陣</h3>
<blockquote>
題目:輸入一個(gè)矩陣陡舅,按照 從外向里以順時(shí)針的順序一次打印出每一個(gè)數(shù)字抵乓。例如:如果輸入如下矩陣:
</blockquote>
<pre><code class="java">/**
-
Created by kangqizhou on 2017/2/1.
*/
public class Offer20 {
public static void main(String... args) {
int[][] a = {{1, 2, 3, 4, 5, 6}, {2, 3, 4, 5, 6, 7}, {7, 8, 9, 10, 11, 12}};
printMatrix(a);
}private static void printMatrix(int[][] a) {
if (a == null)
return;
int start = 0;
while (a.length > start * 2 && a[0].length > start * 2) {
printMatrixInCircle(a, start);
start++;
}
}private static void printMatrixInCircle(int[][] a, int start) {
int endX = a[0].length - 1 - start;
int endY = a.length - 1 - start;
for (int i = start; i <= endX; i++) {
System.out.println(a[start][i]);
}
if (start < endX)
for (int i = start + 1; i <= endY; i++) {
System.out.println(a[i][endX]);
}if (start < endX && start < endY) for (int i = endX - 1; i >= start; i--) { System.out.println(a[endY][i]); } if (start < endX && start < endY - 1) for (int i = endY - 1; i >= start + 1; i--) { System.out.println(a[i][start]); }
}
}
</code></pre>
<h3>面試題二十一:包含min函數(shù)的棧</h3>
<blockquote>
題目:定義棧的數(shù)據(jù)結(jié)構(gòu),請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧的最小元素的min函數(shù),在該棧中灾炭,調(diào)用min茎芋,push,pop的時(shí)間復(fù)雜度都是O(1)
</blockquote>
<pre><code>/**
-
Created by kangqizhou on 2017/2/1.
*/
public class Offer21 {
public static void main(String... args) {
Stack stack = new Stack();
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(1);
stack.push(2);
System.out.println(stack.min());
stack.pop();
stack.pop();
System.out.println(stack.min());
}public static class Stack {
private java.util.Stack<Integer> stack = new java.util.Stack<>();
private java.util.Stack<Integer> supportStack = new java.util.Stack<>();public int push(int i) { if (supportStack.isEmpty()) supportStack.push(i); else if (supportStack.peek() > i) supportStack.push(i); else supportStack.push(supportStack.peek()); stack.push(i); return i; } public int pop() { supportStack.pop(); return stack.pop(); } public int min() { return supportStack.peek(); }
}
}
</code></pre>
<h3>面試題二十二:棧的壓入蜈出、彈出序列</h3>
<blockquote>
輸入兩個(gè)整數(shù)序列田弥,第一個(gè)序列表示棧的壓入順序,請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序铡原。假設(shè)壓入棧的所有數(shù)字均不相等偷厦。例如序列1,2燕刻,3只泼,4,5是某棧的壓站序列卵洗,序列4请唱,5,3过蹂,2十绑,1是該棧的一個(gè)彈出序列,而4酷勺,3本橙,5,1脆诉,2則不可能是該壓站序列對(duì)應(yīng)的彈出序列勋功。
</blockquote>
<pre><code class="java">import java.util.Stack;
/**
-
Created by kangqizhou on 2017/2/1.
*/
public class Offer22 {
public static void main(String... args) {
int[] a = {1, 2, 3, 4, 5};
int[] b = {4, 3, 5, 1, 2};
int[] c = {4, 3, 5, 2, 1};
Utils.syso(isOrder(a, c));
}public static boolean isOrder(int[] a, int[] b) {
if (a == null || b == null || a.length != b.length)
return false;
Stack<Integer> stack = new Stack<>();
int index1 = 0;
int index2 = 0;
while (index1 < a.length || index2 < b.length) {
if (!stack.isEmpty() && stack.peek() == b[index2]) {
stack.pop();
index2++;
} else if (index1 < a.length) {
stack.push(a[index1]);
index1++;
} else
return false;
}
return true;
}
}
</code></pre>
<h3>面試題二十三:從上到下打印二叉樹(shù)</h3>
<blockquote>
題目:從上到下打印出二叉樹(shù)的每一個(gè)節(jié)點(diǎn),同一層的結(jié)點(diǎn)按照從左到右的順序打印库说。例如輸入圖4.5中的二叉樹(shù)狂鞋,則一次打印出8,6潜的,10骚揍,5,7啰挪,9信不,11。
</blockquote>
思路:使用一個(gè)鏈表亡呵,將結(jié)點(diǎn)逐層添加入數(shù)據(jù)結(jié)構(gòu)抽活,然后遍歷。
<pre><code>import java.util.LinkedList;
/**
-
Created by kangqizhou on 2017/2/1.
*/
public class Offer23 {
public static void main(String... args) {
TreeNode node = new TreeNode();
node.value = 8;
TreeNode node1 = new TreeNode();
node1.value = 6;
node.left = node1;
TreeNode node2 = new TreeNode();
node2.value = 10;
node.right = node2;
TreeNode node3 = new TreeNode();
node1.left = node3;
node3.value = 5;
TreeNode node4 = new TreeNode();
node4.value = 7;
node1.right = node4;
TreeNode node5 = new TreeNode();
node5.value = 9;
TreeNode node6 = new TreeNode();
node6.value = 11;
node3.left = node5;
node3.right = node6;
getOrder(node);
}public static void getOrder(TreeNode node) {
LinkedList<TreeNode> linkedList = new LinkedList<>();
linkedList.add(node);
while (!linkedList.isEmpty()) {
TreeNode node1 = linkedList.removeFirst();
if (node1 != null) {
linkedList.add(node1.left);
linkedList.add(node1.right);
Utils.syso(node1.value);
}
}
}
}
</code></pre>
<h3>面試題二十四:二叉搜索樹(shù)的后序遍歷序列</h3>
<blockquote>
題目:輸入一個(gè)整數(shù)數(shù)組锰什,判斷該數(shù)組是不是某二叉搜索數(shù)的后序遍歷的結(jié)果下硕,如果輸入的數(shù)組是{7,4,6,5}丁逝,由于沒(méi)有哪棵二叉樹(shù)的后序遍歷的結(jié)果就是這個(gè)序列,因此返回false梭姓;
</blockquote>