剑指offer阅读（二）

<h2>剑指offer(二)</h2>

<h3>面试题九：斐波那契数列</h3>

<blockquote>
题目一：写一个函数，输入n，求斐波那契数列的第n项，裴波纳契数列的定义如下:
</blockquote>

$$f(n)=0 | n = 0$$
$$f(n)=1 | n = 1$$
$$f(n)=f(n-1)+f(n-2) | n > 1$$

<blockquote>
斐波那契数列使用循环效率比递归效率高，每一次函数调用，都需要在内存栈中分配空间保存参数
</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级台阶，也可以跳上2级，求该青蛙跳上一个n级的台阶，总共有多少种跳法。
</blockquote>

第一次跳的时候有两种选择，跳1级和跳2级，可以换算成斐波那契数列。代码与上面相同。

<h3>面试题十：二进制中1的个数</h3>

<blockquote>
题目： 请实现一个函数，输入一个整数，输出该数二进制中1的个数。例如把9表示成二进制是1001，有两位是1，因此如果输入9，该函数输出2.
</blockquote>

常规解法:

<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>

思路：把一个数减1，与之前的数，最后一位1就会变为0，有多少个1，就能做多少次与运算。

<h3>面试技巧</h3>

代码的完整性，从3个方面确保代码的完整性

1. 功能测试
2. 边界测试
3. 负面测试

<h3>面试题十一：数值的整数n次方</h3>

<blockquote>
题目：实现函数double Power(double base,int exponent)求base得exponent次方，不使用库函数，同时不需要考虑大数问题
</blockquote>

公式
$a^n = a^{n/2}·a{n/2} $ <strong>n为偶数</strong>
$a^n=a{(n-1)/2}·a^{(n-1)/2}·a$ <strong>n为奇数</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);//无论是奇数还是偶数，右移以后都为n/2或者(n-1)/2
  result *= result;
  if ((exponent & 0x1) == 1) {//代表为奇数，再乘以base
  result *= base;
  }
  return result;
  }
  }

</code></pre>

<h3>面试题十二：打印从1到最大的n位数</h3>

<blockquote>
题目：输入数字n，按顺序打印出从1到最大的n位十进制数，比如输入3，则打印1，2，3一直到最大的3位数即999
</blockquote>

思路：不能直接使用int来循环，如果n是一个大数，很容易溢出，最直观的就是，使用数组中的每位来表示0到9的某一个字符。对于n位的字符，我们需要准备一个n+1的字符串

<pre><code>/**

• Created by kangqizhou on 2017/1/30.
  */
  public class Offer12 {
  public static void main(String... args) {
  printNumbers(2);
  }

  public static void printNumbers(int n) {
  

  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) {
// 说明所有的数据排列选择已经处理完了
if (n >= arr.length) {
// 可以输入数组的值
printArray(arr);
} else {
// 对
for (int i = 0; i <= 9; i++) {
arr[n] = i;
printOneToNthDigits(n + 1, arr);
}
}
}
</code></pre>

<h3>面试题十三：在O(1)时间删除链表结点</h3>

<blockquote>
题目：给定单向链表的头指针和结点指针，定义一个函数，在O(1)时间删除该结点。链表结点与函数的定义如下：
</blockquote>

<pre><code class="cpp">struct ListNode{
int m_nValue;
ListNode* m_pNext;
};

void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);
</code></pre>

思路：如果是中间的结点，用下一个结点的value和next覆盖掉当前的结点，如果是头结点，直接删除，如果是尾结点，就循环删除。不一定要真的释放掉目标结点的内存，可以释放目标节点的下个节点的内存。

<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>

平均时间复杂度为$[(n-1)*O(1)+O(n)]/n$，结果还是O(1)

<h3>面试题十四：调整数组顺序使奇数位于偶数前面</h3>

<blockquote>
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分
</blockquote>

<h4>初级解法</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];
  }

   }
  

  }
  //将独立的功能解耦，提高了代码的重用性
  private static boolean isOdd(int number){
  return number % 2==1;
  }

}

</code></pre>

<h3>面试题十五：链表中倒数第K个结点</h3>

<blockquote>
题目：输入一个链表，输出该链表中倒数第K个结点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第一个节点，例如一个链表有6个结点，从头结点开始，他们的值依次是1、2、3、4、5、6.这个链表倒数第3个结点是值为4的结点。
链表结点的定义如下
</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>

定义两个指针，第一个移动到k-1时，开始移动第一个指针。直到第二个的next为null。

<h3>面试题十六：反转链表</h3>

<blockquote>
题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
</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>面试题十七： 合并两个排序的链表</h3>

<blockquote>
题目：输入两个递增排序的列表，合并这两个链表并使新链表并使新链表中的节点仍然是按照递增排序的。例如输入图3.7中的链表1和链表2，则合并之后的升序链表如链表3所示。链表结点定义如下：
</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>面试题十八：树的子结构</h3>

<blockquote>
题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下
</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>面试题十九：二叉树的镜像</h3>

<blockquote>
题目：请完成一个函数，输入一个二叉树，该函数输出他的镜像。
</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>面试题二十：顺时针打印矩阵</h3>

<blockquote>
题目：输入一个矩阵，按照 从外向里以顺时针的顺序一次打印出每一个数字。例如：如果输入如下矩阵：
</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函数的栈</h3>

<blockquote>
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数，在该栈中，调用min，push，pop的时间复杂度都是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>
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1，2，3，4，5是某栈的压站序列，序列4，5，3，2，1是该栈的一个弹出序列，而4，3，5，1，2则不可能是该压站序列对应的弹出序列。
</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>面试题二十三：从上到下打印二叉树</h3>

<blockquote>
题目：从上到下打印出二叉树的每一个节点，同一层的结点按照从左到右的顺序打印。例如输入图4.5中的二叉树，则一次打印出8，6，10，5，7，9，11。
</blockquote>

思路：使用一个链表，将结点逐层添加入数据结构，然后遍历。

<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>面试题二十四：二叉搜索树的后序遍历序列</h3>

<blockquote>
题目：输入一个整数数组，判断该数组是不是某二叉搜索数的后序遍历的结果，如果输入的数组是{7,4,6,5}，由于没有哪棵二叉树的后序遍历的结果就是这个序列，因此返回false；
</blockquote>