剑指offer阅读（三）

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

<h3>面试题二十五：二叉树中和为某一值的路径</h3>

<blockquote>
题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树的定义如下：
</blockquote>

<pre><code class="java">class BinartTreeNode{
int m_nValue;
BinaryTreeNode left;
BinaryTreeNode right;
}
</code></pre>

<pre><code class="java">package offer;

import java.util.LinkedList;

/**

• Created by KiSoo on 2017/2/2.
  */
  public class Offer25 {
  public static void main(String... args) {
  TreeNode node = new TreeNode(10);
  TreeNode node1 = new TreeNode(5);
  TreeNode node2 = new TreeNode(4);
  TreeNode node3 = new TreeNode(7);
  TreeNode node4 = new TreeNode(12);
  node.left = node1;
  node.right = node4;
  node1.left = node2;
  node1.right = node3;
  findPath(node,22);
  }

  public static void findPath(TreeNode root, int expectedSum) {
  LinkedList<Integer> path = new LinkedList<>();
  int currentSum = 0;
  findPath(root, expectedSum, path, currentSum);
  }

  private static void findPath(TreeNode root, int expectedSum, LinkedList<Integer> path, int currentSum) {
  currentSum += root.value;
  path.add(root.value);
  boolean isLeaf = root.left == null && root.right == null;
  if (currentSum == expectedSum && isLeaf) {
  for (int i : path)
  Utils.syso(i);
  System.out.println("---");
  }
  if (root.left != null)
  findPath(root.left, expectedSum, path, currentSum);
  if (root.right != null)
  findPath(root.right, expectedSum, path, currentSum);
  path.removeLast();
  }

}

</code></pre>

思路：使用一个链表把所有路过的点都记录下来，使用前序遍历，当退出当前节点的时候，removelast，函数栈的思想。

<h3>面试题二十六：复杂链表的复制</h3>

<blockquote>
题目：请实现函数ComplexListNode* Clone(ComplexListNode* head)复制一个复杂链表，在复杂链表中，每个节点除了有一个next的指针指向下一个节点外，还有一个sibling指向链表中的任意节点或者NULL。节点的C++定义如下：
</blockquote>

<pre><code>struct ComplexListNode{
int value;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
}
</code></pre>

<pre><code> public static ComplexListNode cloneNode(ComplexListNode refrence) {
cloneNodes(refrence);
connectSiblingNode(refrence);
return reconnectNodes(refrence);
}

private static ComplexListNode reconnectNodes(ComplexListNode refrence) {
    ComplexListNode clonedHead = null;
    ComplexListNode clonedNode = null;
    if (refrence != null) {
        clonedHead = clonedNode = refrence.next;
        refrence.next = clonedHead.next;
        refrence = refrence.next;
    }
    while (refrence != null) {
        clonedNode.next = refrence.next;
        clonedNode = clonedNode.next;
        refrence.next = clonedNode.next;
        refrence = refrence.next;
    }
    return clonedHead;
}

private static void connectSiblingNode(ComplexListNode refrence) {
    while (refrence != null) {
        ComplexListNode cloned = refrence.next;
        if (refrence.sibling != null) {
            cloned.sibling = refrence.sibling.next;
        }
        refrence = cloned.next;
    }
}

private static void cloneNodes(ComplexListNode refrence) {
    if (refrence == null)
        throw new NullPointerException("invaild paramer");
    while (refrence != null) {
        ComplexListNode cloned = new ComplexListNode(refrence.value);
        cloned.next = refrence.next;
        cloned.sibling = null;
        refrence.next = cloned;
        refrence = cloned.next;
    }
}

</code></pre>

<h4>三次遍历</h4>

<blockquote>
思路：先遍历一便，在每个node后复制自身，然后，再次遍历，让node的clone指向node的随机node的下一个，再次遍历，连接所有node的clone，返回nodeHead。
</blockquote>

<h3>面试题二十七：二叉搜索树与双向链表（懵）</h3>

<blockquote>
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整数中节点指针的指向。
</blockquote>

<h4>思路</h4>

中序遍历+将真正的头节点和当前头节点存储在一起。

<pre><code> public class Solution {
TreeNode head = null;
TreeNode realHead = null;

    public TreeNode convert(TreeNode root) {
        convertSub(root);
        return realHead;
    }

    public void convertSub(TreeNode node) {
        if (node == null)
            return;
        convertSub(node);
        if (head == null) {
            head = node;
            realHead = node;
        } else {
            head.right = node;
            node.left = head;
            head = node;
        }
        convertSub(node.right);
    }
}

</code></pre>

<h3>面试题二十八：字符串的排列</h3>

<blockquote>
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出a、b、c所能排列出来的所有字符串。
</blockquote>

<pre><code>package offer;

/**

• Created by KiSoo on 2017/2/2.
  */
  public class Offer28 {

  /**

  • 题目：输入一个字符串，打印出该字符事中字符的所有排列。例如输入字符串abc。
  • 则打印出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
  • @param chars 待排序的字符数组
    */
    public static void permutation(char[] chars) {
    // 输入较验
    if (chars == null || chars.length < 1) {
    return;
    }
    // 进行排列操作
    permutation(chars, 0);
    }

  /**

  • 求字符数组的排列

  • @param chars 待排列的字符串

  • @param begin 当前处理的位置
    */
    public static void permutation(char[] chars, int begin) {
    // 如果是最后一个元素了，就输出排列结果
    if (chars.length - 1 == begin) {
    System.out.print(new String(chars) + " ");
    } else {
    char tmp;
    // 对当前还未处理的字符串进行处理，每个字符都可以作为当前处理位置的元素
    for (int i = begin; i < chars.length; i++) {
    // 下面是交换元素的位置
    tmp = chars[begin];
    chars[begin] = chars[i];
    chars[i] = tmp;

         // 处理下一个位置
         permutation(chars, begin + 1);
     }
    

    }
    }

  public static void main(String[] args) {
  char[] c1 = {'a', 'b', 'c'};
  permutation(c1);
  System.out.println();

   char[] c2 = {'a', 'b', 'c', 'd'};
   permutation(c2);
  

  }

}

</code></pre>

<h3>面试题二十九：数组中出现次数超过一半的数字</h3>

<blockquote>
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
</blockquote>

<pre><code><br />static int moreThanHalfNum(int[] numbers) {
int result = numbers[0];
int times = 1;
for (int i = 1; i < numbers.length; i++) {
if (times == 0) {
result = numbers[i];
times = 1;
} else if (numbers[i] == result) {
times++;
} else {
times--;
}
}
if (checkMoreThanHalf(numbers, result))
return result;
else
return 0;
}

private static boolean checkMoreThanHalf(int[] numbers, int result) {
    int times = 0;
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] == result)
            times++;
    }
    boolean isMoreThanHalf = true;
    if (times * 2 <= numbers.length) {
        isMoreThanHalf = false;
    }
    return isMoreThanHalf;
}

</code></pre>

<h4>思路</h4>

两种方式：

1. 快速排序，取中间值校验。
2. 根据数组的特点，选出出现次数最多的，然后校验。

<h3>面试题三十：最小的k个数</h3>

<blockquote>
题目：输入n个整数，找出其中最小的k个数，例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
</blockquote>

<h4>思路</h4>

<ol>
<li>基于数组左边的第K个数字进行快速排序，使得所有比第k个数字小的所有数字都位于数组的左边</li>
<li>使用一个容器，装填最小的k个数字，满了以后从其中找出最大数，删除。</li>
</ol>

<pre><code>/**

• Created by kangqizhou on 2017/2/4.
  */
  public class Offer30 {

  /**

  • @param krr
  • @param k
  • @return
    */
    public static int[] minK(int krr[], int k) {
    int arr[] = new int[k];
    for (int i = 0; i < k; i++)
    arr[i] = krr[i];
    buildHeap(arr);
    for (int j = k; j < krr.length; j++) {
    if (krr[j] < arr[0]) {
    arr[0] = krr[j];
    maxHeap(arr, 1, k);
    }
    }
    return arr;
    }

  /**

  • 建最大堆
  • @param arr
    */
    public static void buildHeap(int arr[]) {
    int heapsize = arr.length;
    for (int i = arr.length / 2; i > 0; i--)
    maxHeap(arr, i, heapsize);
    }

  /**

  • 调整为最大堆
  • @param arr
  • @param i
  • @param heapsize
    */
    public static void maxHeap(int arr[], int i, int heapsize) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;
    if (left <= heapsize && arr[i - 1] < arr[left - 1])
    largest = left;
    if (right <= heapsize && arr[largest - 1] < arr[right - 1])
    largest = right;
    if (largest != i) {
    int temp = arr[i - 1];
    arr[i - 1] = arr[largest - 1];
    arr[largest - 1] = temp;
    maxHeap(arr, largest, heapsize);
    }
    }

  public static void main(String[] args) {
  int krr[] = {1, 3, 4, 2, 7, 8, 9, 10, 14, 16};
  int arr[] = minK(krr, 4);
  for (int i = 0; i < arr.length; i++)
  System.out.println(arr[i]);

  }

}

</code></pre>

<h3>面试题三十一：连续子数组的最大和</h3>

<blockquote>
题目：输入一个整形数组，数组里有正数也有负数。数组中一个活连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(1)
</blockquote>

<h4>思路：</h4>

如果之前的子数组之和小于0，那就直接从新的数字开始做子数组，每次更改后，就比较，取大值。

<pre><code class="java">/**

• Created by kangqizhou on 2017/2/6.
  */
  public class Offer31 {
  public static void main(String... args){
  int[] data = {1,2,3,-34,-2,-45,3,-4,12,6};
  Solution solution = new Solution();
  Utils.syso(solution.getBiggestNum(data));
  }

  private static class Solution{
  boolean inVaild = false;
  public int getBiggestNum(int[] data){
  if (data == null){
  inVaild = true;
  return 0;
  }
  inVaild = false;
  int nCurSum = 0;
  int biggestNum = 0x80000000;
  for (int i = 0;i < data.length;i++){
  if (nCurSum<=0)
  nCurSum = data[i];
  else
  nCurSum += data[i];
  if (nCurSum > biggestNum)
  biggestNum = nCurSum;
  }
  return biggestNum;
  }
  }
  }

</code></pre>

<h3>面试题三十二：从1到n整数中1出现的次数</h3>

<blockquote>
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数，例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次
</blockquote>

<h4>思路：</h4>

<ol>
<li>不考虑时间复杂度的情况下，遍历每个数字，得到每个数字中1的个数，然后累加。</li>
<li>每次去掉最高位然后做递归，递归的次数和位数相同。一个数字n有O(logn)位，因此这种思路的时间复杂度是O(logn)，比前面的原始方法药好很多。</li>
</ol>

<pre><code class="java"> public static class Solution32II {
public int NumberOf1Between1AndN_Solution(int num) {
if (num < 10)
return 1;
int firstPosition = num;
int length = 0;
//求得首位数字
while (firstPosition > 10) {
firstPosition = firstPosition / 10;
length++;
}
//求得剩余数字
int other = num - firstPosition * powerBase10(length);

        int numFirstDight = 0;
        if (firstPosition > 1)
            numFirstDight = powerBase10(length);
        else if (firstPosition == 1)
            numFirstDight = other + 1;
        int numberOther = firstPosition * (length) * powerBase10(length - 1);
        return numFirstDight + numberOther + NumberOf1Between1AndN_Solution(other);
    }

    private int powerBase10(int n) {
        int result = 1;
        for (int i = 0; i < n; ++i)
            result *= 10;
        return result;
    }
}

</code></pre>

<h3>面试题三十三：把数组排成最小的数</h3>

<blockquote>
题目：输入一个正整数数组，把数组里的所有数字拼接起来排成一个数，打印出能拼接的所有数字中最小的一个。例如输入数组{3，32，321}，打印出最小的数字是{321323}；
</blockquote>

<h4>思路：</h4>

使用快速排序，更改判定条件即可

<pre><code class="java">package offer;

/**

• Created by KiSoo on 2017/2/6.
  */

public class Offer33 {
public static void main(String... args) {
int data[] = {321, 23, 1111};
Utils.syso(new Solution33().getNum(data));
}

public static class Solution33 {

    public String getNum(int[] data) {
        sort(data, 0, data.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i : data)
            sb.append(i);
        return sb.toString();
    }

    private void sort(int[] data, int left, int right) {
        if (left < right) {
            int position = partition(data, left, right);
            if (position == left)
                sort(data, left + 1, right);
            if (position == right)
                sort(data, left, right - 1);
            else {
                sort(data, left, position - 1);
                sort(data, position + 1, right);
            }
        }
    }

    private int partition(int[] data, int left, int right) {
        int value = data[right];
        int n = left;
        for (int i = left; i < right; i++) {
            if (isSmall(data[i], value)) {
                changeE(data, i, n);
                n++;
            }
        }
        changeE(data, n, right);
        return n;
    }

    public boolean isSmall(int m, int n) {
        String left = String.valueOf(m) + String.valueOf(n);
        String right = String.valueOf(n) + String.valueOf(m);
        for (int i = 0; i < left.length(); i++) {
            if (left.charAt(i) < right.charAt(i))
                return true;
            else if (left.charAt(i) > right.charAt(i))
                return false;
        }
        return false;
    }

    private void changeE(int[] data, int i, int n) {
        if (i == n)
            return;
        data[i] = data[i] + data[n];
        data[n] = data[i] - data[n];
        data[i] = data[i] - data[n];
    }
}

}

</code></pre>

<h3>面试题三十四：丑数</h3>

<blockquote>
题目：我们把只包含印子2、3、5的数称为丑数。求按从小到大的顺序的第1500个丑数，例如6，8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当作第一个丑数。
</blockquote>

<pre><code class="java">package offer;

/**

• Created by KiSoo on 2017/2/6.
  */
  public class Offer34 {
  public static void main(String... args) {
  Utils.syso(getUglyNum(4));
  }

  public static int getUglyNum(int index) {
  if (index <= 0)
  return 0;
  int[] uglyNum = new int[index];
  uglyNum[0] = 1;
  int nextUglyNumIndex = 1;
  int p2 = 0;
  int p3 = 0;
  int p5 = 0;
  while (nextUglyNumIndex < index) {
  int min = min(uglyNum[p2] * 2, uglyNum[p3] * 3, uglyNum[p5] * 5);
  uglyNum[nextUglyNumIndex] = min;
  while (uglyNum[p2] * 2 <= uglyNum[nextUglyNumIndex])
  p2++;
  while (uglyNum[p3] * 3 <= uglyNum[nextUglyNumIndex])
  p3++;
  while (uglyNum[p5] * 5 <= uglyNum[nextUglyNumIndex])
  p5++;
  nextUglyNumIndex++;
  }
  return uglyNum[index - 1];
  }

  private static int min(int i, int i1, int i2) {
  int min = i < i1 ? i : i1;
  return min < i2 ? min : i2;
  }

}

</code></pre>

<h3>面试题35：第一次只出现一次的字符。</h3>

<blockquote>
题目：在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b'。
</blockquote>

<pre><code class="java">package offer;

import java.util.HashMap;

/**

• Created by KiSoo on 2017/2/6.
  */
  public class Offer35 {
  public static void main(String... args) {
  char[] str = {'a', 'b', 'c', 'a', 'b', 'a'};
  Utils.syso(firstNotRepeatingChar(str));
  }

  static char firstNotRepeatingChar(char[] str) {
  if (str == null)
  return '\0';
  HashMap<Character, Integer> hashMap = new HashMap<>();
  for (char c : str) {
  Integer times = hashMap.get(c);
  hashMap.put(c, times == null ? 1 : times + 1);
  }
  for (char c : str) {
  int i = hashMap.get(c);
  if (i == 1)
  return c;
  }
  return '\0';
  }
  }

</code></pre>

思路：

使用hashmap，遍历两次即可。

<h3>面试题三十六：数组中的逆序对</h3>

<blockquote>
题目：在数组中的两个数字如果前面一个大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
</blockquote>

<pre><code class="java">package offer;

/**

• Created by KiSoo on 2017/2/6.
  */
  public class Offer36 {

  public static void main(String... args) {
  int[] a = {7, 5, 6, 4};
  Utils.syso(inversePairs(a));
  }

  public static int inversePairs(int[] data) {
  if (data == null) {
  return 0;
  }
  int[] copy = new int[data.length];
  for (int i = 0; i < data.length; i++)
  copy[i] = data[i];

   return inversePairsCore(data, copy, 0, data.length - 1);
  

  }

  private static int inversePairsCore(int[] data, int[] copy, int start, int end) {
  if (start == end) {
  copy[start] = data[start];
  return 0;
  }
  int length = (end - start) / 2;
  int left = inversePairsCore(copy, data, start, start + length);
  int right = inversePairsCore(copy, data, start + length + 1, end);
  int i = start + length;
  int j = end;
  int indexCopy = end;
  int count = 0;
  while (i >= start && j >= start + length + 1) {
  if (data[i] > data[j]) {
  copy[indexCopy--] = data[i--];
  count += j - start - length;
  } else {
  copy[indexCopy--] = data[j--];
  }
  }
  while (i >= start) {
  copy[indexCopy--] = data[i--];
  }
  while (j >= start + length + 1) {
  copy[indexCopy--] = data[j--];
  }
  return left + right + count;
  }

}

</code></pre>

<h3>面试题三十七：两个链表的第一个公共节点。</h3>

<blockquote>
题目：输入两个链表，找出它们的第一个公共节点。
</blockquote>

<h4>思路：</h4>

先得出两个链表的长度差，然后，先在长链表中走k步，然后同时走，直到node相同。

<h3>面试题三十八：</h3>

<blockquote>
题目：统计一个数字在排序数组中出现的次数，例如输入排序数组{1，2，3，3，3，3，4，5}和数字3，由于3在这个数组中出现了4次，因此输出4
</blockquote>

思路：使用二分查找先找出最左边出现的k的下标，再找出最右边出现的k的下标。相减即可得到次数。

<pre><code>package offer;

/**

• Created by KiSoo on 2017/2/7.
  */
  public class Offer38 {
  public static void main(String... str) {
  int[] a = {1, 2, 3, 3, 3, 4, 5};
  Utils.syso(getFirstK(a, 3));
  }

  public static int getFirstK(int data[], int k) {
  if (data == null)
  return -1;
  return getFirstK(data, k, 0, data.length - 1) - getLastK(data, k, 0, data.length - 1);
  }

  private static int getLastK(int[] data, int k, int left, int right) {
  if (left < right)
  return 0;
  int middleIndex = (left + right) / 2;
  int middleData = data[middleIndex];
  if (middleData == k) {
  if (middleIndex < data.length - 1 && data[middleIndex + 1] != k || middleIndex == data.length - 1) {
  return middleIndex;
  } else
  left = middleIndex + 1;
  } else if (middleData < k)
  left = middleIndex + 1;
  else if (middleData > k)
  right = middleIndex - 1;
  return getLastK(data, k, left, right);
  }

  private static int getFirstK(int[] data, int k, int left, int right) {
  if (left > right)
  return 0;
  int middleIndex = (left + right) / 2;
  int middleData = data[middleIndex];
  if (middleData == k) {
  if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)
  return middleIndex;
  else
  right = middleIndex + 1;
  } else if (middleData > k)
  right = middleIndex - 1;
  else
  left = middleIndex + 1;
  return getFirstK(data, k, left, right);
  }

}

</code></pre>

<h3>面试题三十九：二叉树的深度</h3>

<blockquote>
题目一：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点形成的树的一条路径，最长路径的长度为树的深度。
</blockquote>

<pre><code> private static int getHeight(TreeNode firstNode) {
if (firstNode == null)
return 0;
int left = getHeight(firstNode.left);
int right = getHeight(firstNode.right);
return left > right ? left + 1 : right + 1;
}
</code></pre>

<h4>思路：通过递归，取左右子树的较大值加1。</h4>

<blockquote>
题目二：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树。
</blockquote>

<pre><code> static boolean isBalanced(TreeNode node, int[] depth) {
if (node == null) {
depth[0] = 0;
return true;
}
int[] left = new int[1], right = new int[1];
if (isBalanced(node.left, left) && isBalanced(node.right, right)) {
int diff = left[0] - right[0];
if (diff <= 1 && diff >= -1) {
depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);
return true;
}
}
return false;
}
</code></pre>

<h4>思路：</h4>

通过递归求出左右节点的深度差值。