23、
public class VerifySquenceOfBST_23 {
/**
* 二叉搜索树的后序遍历
*
* 题目描述
* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
*
* 思路：
* BST 的中序 遍历是从小到大递增的， 所以我们是可以 排序 后续遍历序列，判断是否能还原成一棵树
* 但是太过麻烦。
*
* 后序遍历 ： [左子树 (小)][右子树（大）][根]
* 根据根节点找到分界， 然后判断右子树是否全比 根节点大，然后进入递归。
* 此法为 n^2解法，时间复杂度高。
*/
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence.length == 0) return false;
return judge(sequence,0,sequence.length-1);
}
private boolean judge(int[] arr, int left, int right){
if (left >= right) return true;
int gap = left;
for (int i = left; i <= right; i++) {
if (arr[i] > arr[right]) {
gap = i;
while (i < right) {
if ( arr[i] < arr[right]) return false;
i++;
}
break;
}
}
return judge(arr,left,gap-1) && judge(arr,gap,right-1);
}
}
24、
public class FindPath_24 {
/**
* 二叉树和为某一路径值
*
* 题目描述
* 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。
* 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
*
* 思路：
* 经典的路径搜索问题。 遍历一遍判断记录路径条件即可。
*
* 但是java实现这道题非常的麻烦， 主要是 ArrayList 的深拷贝需要重写clone方法，或者 实现序列化接口
* 导致记录已知路径需要重新遍历路径到一个新的对象，徒增时间复杂度。
*/
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
process(res, root, target, new ArrayList<>());
return res;
}
private void process(ArrayList<ArrayList<Integer>> res, TreeNode root, int target, ArrayList<Integer> curPath){
if (root == null)return;
target -= root.val;
curPath.add(root.val);
if (root.left == null && root.right == null && target == 0) {
ArrayList<Integer> temp = new ArrayList<>();
curPath.stream().forEach(e -> temp.add(e));
res.add(temp);
}
process(res,root.left, target, curPath);
process(res,root.right, target, curPath);
//回退路径
curPath.remove(curPath.size()-1);
}
}
25、
public class RandomListClone_25 {
/**
* 复杂链表复制
*
* 题目描述
* 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
* 另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。
* （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
*
*
* 思路：
* 参考LinkedHashMap ， 用哈希表key来保存原链表。
* 虽然浪费了空间，但减少一定的代码量
*/
public RandomListNode Clone(RandomListNode pHead)
{
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode cur = pHead;
while (cur != null){
map.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
cur = pHead;
while (cur != null){
RandomListNode temp = map.get(cur);
temp.next = map.get(cur.next);
temp.random = map.get(cur.random);
cur = cur.next;
}
return map.get(pHead);
}
}
26、
public class BSTConvertList_26 {
/**
* 二叉搜索树转双链表
*
* 题目描述
* 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
* 要求不能创建任何新的结点，只能调整树中结点指针的指向。
*
* 思路：
* 题目暗示非常明显了， 非递归版本的BST中序遍历，就可以按大小顺序输出节点
*
* 虽说不能要求创建任何节点， 为了找到头节点方便， 创建一个dummy吧！ （可以优化掉）
*
* 注：经典非递归版本中序遍历，实在太过巧妙
*/
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) return null;
TreeNode dummy = new TreeNode(0);
TreeNode cur = dummy;
TreeNode tmp = pRootOfTree;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || tmp != null){
if (tmp != null){
stack.push(tmp);
tmp = tmp.left;
}else {
tmp = stack.pop();
// 重构双向链表
tmp.left = cur;
cur.right = tmp;
cur = cur.right;
tmp = tmp.right;
}
}
cur = dummy.right;
cur.left = null;
return cur;
}
}
27、
public class Permutation_27 {
/**
* 字符排列
*
*题目描述
* 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
* 例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
*
* 思路 ：
* 思路1 （偏开发）， 转化为全排列问题， Set去重（string的hashcode 被重写过）。
* [p,q]的全排列，等于以p-q的各个元素为头结点， 其余[p+1,q]元素的全排列。这显然是一个递归过程。
*
* 思路2 （偏算法）， 枚举的过程中规避 重复的情况， 需要一定技巧
*
* 假如 aabc -> （）（a）（）（）
* 保证两个a 的相对位置不变，就能规避掉重复的情况！
* 如 a在 1位置， 则第二a 认为规定只在第一a后面才可以枚举
* 利用二进制数保证相对位置
*/
//全排列解法
public ArrayList<String> Permutation(String str) {
Set<String> set = new HashSet<>();
ArrayList<String> res = new ArrayList<>();
process(str.toCharArray(), 0, str.length() - 1, res, set);
Collections.sort(res);
return res;
}
//表示对 arr从 p到 q进行全排列
private void process(char[] arr, int p, int q, ArrayList<String> res, Set<String> set){
if (p == q){
String s = new String(arr);
if (!set.contains(s)){
res.add(s);
set.add(s);
}
}
for (int i = p; i <= q; i++) {
swap(arr, i, p);
process(arr, p + 1, q , res, set);
swap(arr, i, p);//回溯到之前的情况
}
}
private void swap(char[] arr, int i, int j){
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
28、
public class MoreThanHalfNum_28 {
/**
* 数组中超过一半的数字
*
* 题目描述
* 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
* 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
* 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
* 如果不存在则输出0。
*
* 思路：
* 统计个数 ， 标准解法是hashmap， 免不了要使用额外的空间复杂度。
*
* 给出偷鸡解法 ，题目输入为例：
* 2为最多元素， 假定 2 映射 1，其他映射 -1
* {1,2,3,2,2,2,5,4,2}
* {-1,1,-1,1,1,1,-1,-1,1} => 因为2超过一半，所以累加（count）一定 >0 , 5-3 > 0
*
* 用变量count 表示上述过程，规定val保存数组中超过一半的数, 而过程中“真正最多的数”存在身份转化。
* 假定 arr[i] 是假定“最多的数”val，那么跟它不同的数都是 count 的消耗者，（真正最多的数 2 此时也作为count的消耗者），
* 如果 count被消耗为负数了， 说明 假定的 val 不是 “最多的数”！
* 假定值 val 切换下一个 arr[i], 因为真实最多值 2 比其他所有数的个数和都多1，所以任何的假定值的count都不可能“活过”2的消耗！
* 所以val假定最多值最终一定会切换到 2 上。
* 那，我们不管 2 之前count被消耗的过程吗？其实，如果2之前作为消耗者被消耗的部分，
* 在2作为假定值val之后，自动转化为生产者被消耗的部分！
*/
public int MoreThanHalfNum_Solution(int [] array) {
int count = 0;
int val = array[0]; //假定最多值元素 array[0]
for (int i = 0; i < array.length; i++) {
if (count < 0) val = array[i];//切换假定值
if (val == array[i]){
count++;
}else {
count--;
}
}
return count > 0? val:0;
}
}
29、
public class GetLeastNumbers_29 {
/**
* 最小K个数
*
* 题目描述
* 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
*
* 思路：
* TopK的问题 ，解决方式是通过堆。
*
* 如果，用长度为K的小顶堆，那么heap中的元素就是最小的K个元素
*
* 反之，用长度为K的大顶堆，那么入堆的元素不能比堆顶大， 比堆顶大的元素需要被移除堆。（不推荐使用）
*/
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(input.length < k || k == 0)return res;
//创建堆传入比较器
PriorityQueue<Integer> heap = new PriorityQueue<>(k,Integer::compareTo);
Arrays.stream(input).forEach(e -> heap.add(e));
for (int i = 0; i < k; i++) res.add(heap.poll());
return res;
}
}
30、
public class FindGreatestSumOfSubArray_30 {
/**
* 连续子数组
*
* 题目描述
* HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
* 今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,
* 当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
* 并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
* 给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
*
* 思路 ：
* 动态规划 。一维dp[i] 表示 以arr[i]为结尾的 子序列最大和
*
* 当 dp[i-1] <= 0 , dp[i] = 0 + arr[i]
* 当 dp[i-1] > 0 , dp[i] = dp[i-1] + arr[i]
*
* 如果前一个数为结尾的 子序列最大和是负数， 舍弃前面的序列
*/
public int FindGreatestSumOfSubArray(int[] array) {
int res = Integer.MIN_VALUE;
int dp = 0;
for (int i = 0; i < array.length; i++){
if (dp < 0) dp = 0;
dp += array[i];
res = Math.max(res, dp);
}
return res;
}
}
31、
public class NumberOf1Between1AndN_31 {
/**
* 整数中1的个数
*
* 题目描述
* 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
* 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,
* 但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,
* 可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
*
*
* 思路：
* 这题非常难。
*/
public int NumberOf1Between1AndN_Solution(int n) {
int ones = 0;
for (long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
return ones;
}
}
32、
public class PrintMinNumber_32 {
/**
* 把数组排成最小的数
*
* 题目描述
* 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
* 打印能拼接出的所有数字中最小的一个。
* 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
*
* 思路：
* 按说 这是一道全排列的问题。先全排列，再比较排列数字大小。
* 太复杂了。 用比较器优化这个过程。
*
* 如何论证这个算法的正确性？
* 离散数学中， 自定义排序需要具有两个性质 ：
* 1） 自反性 2）传递性
* 需要用数学办法论证 ab， ba这两个数具有这两个性质。 -> 可以用来排序
*
* 还需要用反证法证明 ，最终序列是最小值！！！
*
* 所以将其理解为贪心问题，不要纠结证明过程。
*/
public String PrintMinNumber(int [] numbers) {
ArrayList<String> list = new ArrayList<>();
String res = "";
for (int i = 0; i < numbers.length; i++) list.add(String.valueOf(numbers[i]));
Collections.sort(list, (s1,s2) ->(s1+s2).compareTo(s2+s1));
for (String s: list) res += s;
return res;
}
}
33、
public class GetUglyNumber_33 {
/**
*
* 丑数
*
* 题目描述
* 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。
* 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
*
* 思路：很难想到的解法。
* 所有的丑数，都是由一个丑数 *2 *3 *5 得来的， 已知丑数的root 都是 1。
* 得出结论，任何一个丑数都可以通过只做一次乘法，派生出三个丑数1 -> 2 , 3, 5
* 丑数表示为 ， 2^i * 3^j * 5^k， 派生则对应ijk其中一个+1， 每个丑数分别 *2 *3 *5 就构成了丑数序列。
* 用 t2 t3 t5 表示丑数序列的索引，例如 t2 表示当前索引的丑数还没有完成 * 2的派生。
*
* 因为下一个丑数只能来自前一个丑数 *2 或 *3 或 *5 ，所以 它只能是 *2 *3 *5 待派生元素派生后的最小值。
* 随后推进派生索引。
*
* 注： 数字设计也是有规律的， 规避了 上一位丑数 res（i） 是 res（i-1）*3 得来的，
* 下一位丑数res（i+1） 不会是 res(i) * 2 = res（i-1）*3 * 2 = res(i-1) * 6 > res(i-1) * 5 !!
*
* 2 * 2 = 4 ， 3 < 4 < 5
* 2 * 3 = 6 ， 5 < 6
* 3 * 3 = 9 , 9 < 2*5
*/
public int GetUglyNumber_Solution(int index) {
if (index < 7)return index;
ArrayList<Integer> res = new ArrayList<>();
res.add(1);
int t2 = 0,t3 = 0, t5 = 0;
for (int i = 1; i < index; i++) {
res.add(Math.min(res.get(t2) * 2, Math.min(res.get(t3) * 3, res.get(t5) * 5)));
if (res.get(i) == res.get(t2) * 2) t2++;
if (res.get(i) == res.get(t3) * 3) t3++;
if (res.get(i) == res.get(t5) * 5) t5++;
}
return res.get(index - 1);
}
}
34、
public class FirstNotRepeatingChar_34 {
/**
* 第一个只出现一次的字符的位置
*
* 题目描述
* 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,
* 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
*
* 思路 ：
* 哈希表统计一下
*/
public int FirstNotRepeatingChar(String str) {
HashMap<Character,Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
Character key = str.charAt(i);
if (map.containsKey(key)){
map.put(key, map.get(key) + 1);
}else {
map.put(key, 1);
}
}
for (int i = 0; i < str.length(); i++) {
if (map.get(str.charAt(i)) == 1) return i;
}
return -1;
}
}
35、
public class InversePairs_35 {
/**
* 数组中逆序对的个数
*
* 题目描述
* 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
* 输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
* 即输出P%1000000007
*
* 思路：
* 将 n^2 算法通过归并排序优化成 nlogn ,否则时间复杂度过高过不了oj
* 总逆序对 = 左边的逆序对 + 右边的逆序对 + 左右重叠的逆序对
* 归并排序在 merge 左[l...i...mid]右[mid+1...j...h]的过程中，需要将min(temp[i],temp[j])放进 arr中，
* 只要 右边j要在左边的i之前插入 arr ， 那么愿数组arr中产生了[i,mid]个逆序对。
*
*/
public int InversePairs(int [] array) {
int[] temp = new int[array.length];
return merge(array,0,array.length-1,temp)%1000000007;
}
private int merge(int[] arr, int l, int h,int[] temp){
if (l >= h) return 0;
int mid = (l + h)>>1;
int res = merge(arr,l,mid,temp) + merge(arr,mid+1, h,temp);
for (int k = l; k <= h; k++) {
temp[k] = arr[k];
}
int i = l, j = mid+1;
for (int k = l;k <= h;k++){
//处理半边提前merge耗尽情况
if(i > mid){
arr[k] = temp[j++];
} else if(j > h){
arr[k] = temp[i++];
}else if (temp[i] < temp[j]){
arr[k] = temp[i++];
}else {
arr[k] = temp[j++];
res = (res + mid-i + 1)%1000000007;//牛客网OJ结果过大，必须在这里取模
}
}
return res;
}
}
36、
public class FindFirstCommonNode_36 {
/**
* 两个链表的第一个公共节点
*
* 题目描述
* 输入两个链表，找出它们的第一个公共结点。
* （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
*
* 思路：
* 经典的链表相交问题 ：双指针 + 分情况讨论 (输入数据情况)
* 1、根本没相交
* 2、相交
*
* 做法一 ：常规
* 求出两个链表的差 ， a b 同时走， 谁先到结尾谁停，未到结尾的标记为 mark。
* 判断mark 是 list a 还是 list b ，让其把mark到结尾的差值走完。
* 然后head a head b 一起前进， 找到相交点。 （规避了不相交情况）
*
* 做法二 ：灵活
* a 先遍历 list a ， 再遍历 list b，
* 先遍历 list b， 再遍历 list a 。
*
* 第二次遍历的时候他们一定会相遇
*
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode a = pHead1;
ListNode b = pHead2;
while (a != null && b != null){
a = a.next;
b = b.next;
}
ListNode mark = a == null? b: a;
if (mark == a) {
while (mark != null){
pHead1 = pHead1.next;
mark = mark.next;
}
}else {
while (mark != null){
pHead2 = pHead2.next;
mark = mark.next;
}
}
while (pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}
public ListNode pro(ListNode pHead1, ListNode pHead2) {
ListNode a = pHead1;
ListNode b = pHead2;
while (a != b){
if (a == null){
a = pHead2;
}else {
a = a.next;
}
if (b == null){
b = pHead1;
}else {
b = b.next;
}
}
return a;
}
}
37、
public class GetNumberOfK_37 {
/**
* 数字在排序数组中出现次数
*
* 题目描述
* 统计一个数字在排序数组中出现的次数。
*
* 思路 ：
* 经典二分问题 ，有很多解法 。
* 解法1 ： 二分找到 k 的最左边界a， 二分找到k的最右边界b ， 返回b-a+1
* 解法2 ：二分找到任意 k ， 数一下 k左边有a个k（含k）， k右边有b个k（含k），返回a+b-1
*
* （解法1可以复习二分变形题）
*/
public int GetNumberOfK(int [] array , int k) {
if (array.length == 0) return 0;
int l = 0;
int r = array.length - 1;
int index = (l + r)>>1;
while (l <= r){
int mid = (l + r)>>1;
if (array[mid] == k) {
index = mid;
break;
}
if (array[mid] < k){
l = mid + 1;
}else {
r = mid - 1;
}
}
if (l > r)return 0;
if (r == l && array[index] != k) return 0;
int count = 0;
for (int i = index; i < array.length && array[i] == k;i++) count++;
for (int i = index; i >= 0 && array[i] == k;i--) count++;
return count-1;
}
}
38、
public class TreeDepth_38 {
/**
* 二叉树的深度
*
* 题目描述
* 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
*
* 思路： 必会题，
* 左子树 右子树 最大深度 + 1
*/
public int TreeDepth(TreeNode root) {
return process(root, 0);
}
private int process(TreeNode root, int dept){
if (root == null) return 0;
return Math.max(process( root.left, dept), process( root.right, dept)) +1;
}
}
39、
public class IsBalanced_39 {
/**
* 判断二叉树的平衡性
*
* 题目描述
* 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
* 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
*
* 思路 :
*
* 用int[2]记录状态 ， 【是否平衡，当前深度】
*
* 平衡树 ： 左树平衡，右树平衡， 高度差 小于1
*/
public boolean IsBalanced_Solution(TreeNode root) {
return process(root)[0] == 1? true:false;
}
private int[] process(TreeNode root){
if (root == null) return new int[]{1,0};// [isBalance , depth]
int[] left = process(root.left);
if (left[0] == 0) return new int[]{0,0};
int[] right = process(root.right);
if (right[0] == 0) return new int[]{0,0};
if (Math.abs(left[1]-right[1]) > 1) return new int[]{0,0};
return new int[]{1,Math.max(left[1],right[1])+1};
}
}
40、
public class FindNumsAppearOnce_40 {
/**
* 数组中出现一次的数字
*
* 题目描述
* 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
*
* 思路： 这是一道 位运算的题目，笔试建议可以直接使用哈希表。
*
* 相同的数 ^ 异或操作是 0 。 如果数组中只有 一个出现一次的数字， 那么 数组的 异或和 就是0；
*
* 数组中有两个数 (x , y)是单个数字， 数组的异或和就是 x ^ y 假设 *** 1 000。
* 可以通过这个值是 1的某一位，表示 x 与 y的此位不同的。 用这个条件，将数组分成两部分，
* x 和 y 就各自在其中。
*
* 操作非常巧妙，优化了空间复杂度。
*/
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int sum = 0;
for (int e: array
) {
sum ^= e; // x ^ y
}
//找到分割位
int k = 0;
while ((sum>>k & 1) != 1 ) k++;
for (int e: array
) {
if ( (e>>k & 1) == 1){
num1[0] ^= e;
}else {
num2[0] ^= e;
}
}
}
}
网友评论