剑指Offer（40-49Java语言描述）

不知不觉已经快十月份了，还剩不多啦，最近也是一直跑宣讲会，笔试，面试，没有什么时间去刷题。

40. 数组中出现次数超过一半的数字

题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路：
一：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length == 0) return 0;
        int cnt = 1;
        //最多出现的数字
        int num = array[0];
        for (int i = 1; i < array.length; i++) {
            if (num == array[i]) {
                cnt++;
            } else {
                cnt--;
            }
            if (cnt == 0) {
                num = array[i];
                cnt = 1;
            }

        }
        // 这里还需要再判断是否符合条件
        cnt = 0;
        for (int i : array) {
            if (num == i) {
                cnt++;
            }
        }
        return cnt > array.length / 2 ? num : 0;
    }
}

二：本题也可以用HashMap来求解，不过空间复杂度比较高。

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length == 0) return 0;
        int HalfLen = array.length / 2;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : array) {
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for (Map.Entry<Integer,Integer> entry :map.entrySet()) {
            if (entry.getValue() > HalfLen) {
                return entry.getKey();
            }
        }
        return 0;

    }
}

41. 最小的K个数

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路：
第一种：
用快速排序中的partion方法，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。调整之后，位于数组左边的k个数字就是最小的k个数字。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input.length == 0 || k > input.length || k < 0) return list;
        getKthNum(input,k);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
    //调整数组位置为第K个
    private void getKthNum(int [] arr,int k) {
        int R = arr.length - 1 ;
        int L = 0;  
        while (L < R){
            int i = partition(arr,L,R);
            if (i == k) break;
            if (i > k) {
                R = i - 1;
            } else {
                L = i + 1;
            }
        }
    } 
    //切分方法      
    private int partition(int [] arr,int L,int R) {
        int num = arr[L];
        int less = L + 1, more = R;
        while (true) {
            while (less < R && arr[less] < num) less++;
            while (more > L && arr[more] > num) more--;
            if (less >= more) break;
            swap(arr,less++,more--);
        }
        swap(arr,L,more);
        return more;
    }
    private void swap(int [] arr,int i ,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;      
    }
}

第二种：使用堆排序

import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k <= 0 || k > input.length) return list;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : input) {
            queue.add(i);
        }
        for (int i = 0; i < k; i++) {
            list.add(queue.poll());
        }
        return list;
    }
}

42. 数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路：
使用两个堆来解决问题，minQueue 为最小堆，maxQueue为最大堆，要保证最小堆中的值都比最大堆的值大，然后最后求结果的时候，如果count为偶数，那么中间值就是最大堆和最小堆之和的平均值，如果count是奇数，中间值就是最小堆中的堆顶元素。

import java.util.PriorityQueue;
public class Solution {
    //最小堆，存大值
    private PriorityQueue<Integer> minQueue = new PriorityQueue<>();
    //最大堆，存小值
    private PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1,o2) -> (o2 - o1));
    //数量
    private int count = 0;
    public void Insert(Integer num) {
        if (count % 2 == 0) {
            maxQueue.add(num);
            // 将最大堆中的最大值插入到最小堆中
            minQueue.add(maxQueue.poll());
        } else {
            minQueue.add(num);
            maxQueue.add(minQueue.poll());
        }
        count++;
    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            double d = (minQueue.peek() + maxQueue.peek()) / 2.0;
            return d;
        } else {
            return (double)minQueue.peek();
        }
    }


}

43. 字符流中第一个不重复的字符

题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路：
一： 使用LinkedHashMap 存入的键是有序的特点来解决。

import java.util.*;
public class Solution {
    private Map<Character,Integer> map = new LinkedHashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        map.put(ch,map.getOrDefault(ch,0) + 1);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        for (Map.Entry<Character,Integer> entry: map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return '#';
    }
}

二：也可以使用队列来做，先声明一个256长度的数组，足以存储所有char类型的字符，然后利用队列先进先出的特点。

import java.util.*;
public class Solution {
    private Queue<Character> queue = new LinkedList<>();
    private int arr[] = new int[256];
    //Insert one char from stringstream
    public void Insert(char ch)
    {  
        arr[ch]++;
        queue.add(ch);
        while (!queue.isEmpty() && arr[queue.peek()] > 1) {
            queue.poll();
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        return queue.isEmpty()? '#' : queue.peek();
    }
}

44. 连续子数组的最大和

题目描述：
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

解题思路：
max用来记录包含array[i]的最大值，result用来记录最大连续子数组的最大值

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        // 记录结果的最大值
        int result = array[0];
        //记录包含array[i]的最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(array[i] + max,array[i]);
            result = Math.max(result,max);
        }
        return result;
    }
}

45. 整数中1出现的次数（从1到n整数中1出现的次数）

题目描述:
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解题思路：
原谅我一如既往的暴力，其实用数学的角度来求问题的话更简单，更聪明的做法参考
LeetCode

import java.lang.StringBuffer;
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= n; i++) {
            sb.append(i);
        }
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '1')
                cnt++;
        }
        return cnt;

    }
}

46. 把数组排成最小的数

题目描述：
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路：应该联想到排序，比较两个字符串o1, o2大小的时候，先将它们转为字符串，比较o1+o2,和o2+o1那个大，如果o1+o2大，o2应该放前面，o2就应该排在o1前面。若o1 + o2 < o2 + o1,则o1在前面。
这里的Lambda表达式用的很巧妙。

import java.util.Arrays;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        String arr[] = new String[numbers.length];
        String str = "";
        for (int i = 0; i < numbers.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(arr,(o1,o2) -> (o1+o2).compareTo(o2+o1));
        for (String s : arr) {
            str += s;
        }
        return str;

    }
}

47. 第一个只出现一次的字符

题目描述：
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解题思路：
可以使用HashMap来存储每个字符出现的频率，不过那样空间复杂度比较大，这里使用整型数组。

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }
        int arr[] = new int[255];
        for (int i = 0; i < str.length(); i++) {
            arr[str.charAt(i)]++;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[str.charAt(i)] == 1) {
                return i;
            }
        }
        return -1;
    }
}

48. 两个链表的第一个公共结点

题目描述
输入两个链表，找出它们的第一个公共结点。

解题思路：
参考某cyc大佬的解题思路，很清晰。

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }
}

49. 二叉树的深度

题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路：
使用递归，左右子树哪个大就加1

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }
}