剑指offer阅读（三）

2017-04-12 本文已影响293人桥寻

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

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

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

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

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

<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 &lt; numbers.length; i++) {
        if (numbers[i] == result)
            times++;
    }
    boolean isMoreThanHalf = true;
    if (times * 2 &lt;= numbers.length) {
        isMoreThanHalf = false;
    }
    return isMoreThanHalf;
}

</code></pre>

两种方式：

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

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

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

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

如果之前的子数组之和小于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>

<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 &gt; 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 &lt; n; ++i)
            result *= 10;
        return result;
    }
}

</code></pre>

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

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

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

<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 &lt; 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 &lt; 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 &lt; left.length(); i++) {
            if (left.charAt(i) &lt; right.charAt(i))
                return true;
            else if (left.charAt(i) &gt; 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>

先得出两个链表的长度差，然后，先在长链表中走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>

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

剑指offer阅读（三）

思路：

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

猜你喜欢

热点阅读