剑指offer java版（三）
剑指offer java版（三）
二叉搜索树的后序遍历
问题描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路
对于后序遍历来说，序列数组的最后一个元素一定是根节点,根据这个元素，将前面的数组分为左、右两个部分，左侧部分都比该元素小，右侧部分都比该元素大，如果右侧部分有比该根节点小的元素，那么就不是后序遍历，如此递归进行。
public boolean isEndOrder(int[] orders) {
if (orders.length == 0) return false;
if (orders.length == 1) return true;
return just(orders, 0, orders.length - 1);
}
public boolean just(int[] orders, int start, int root) {
if (start > root) return true;
int i = start;
// 找第一个比更结点大的位置
while (i < root && orders[i] < orders[root]) {
i++;
}
for (int j = i; j < root; j++) {
if (orders[j] < orders[root]) {
return false;
}
}
return just(orders, start, i - 1) && just(orders, i, root - 1);
}二叉树中和为某值的路径
问题描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路
用前序遍历的方式访问到某一结点时，把该结点添加到路径上，并用目标值减去该节点的值。 如果该结点为叶结点并且目标值减去该节点的值刚好为0，则当前的路径符合要求，我们把加入res数组中。 如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。 因此我们在函数退出之前要在路径上删除当前结点，以确保返回父结点时路径刚好是从根结点到父结点的路径。
public ArrayList<ArrayList<TreeNode>> findRood(TreeNode root, int k) {
if (root == null) return null;
ArrayList<ArrayList<TreeNode>> roods = new ArrayList<>();
ArrayList<TreeNode> temp = new ArrayList<>();
temp.add(root);
k = k - root.value;
if (k == 0 && root.left == null && root.right == null) {
roods.add(new ArrayList<TreeNode>(temp));
} else {
findRood(root.left, k);
findRood(root.right, k);
}
// 注意最后回退一个
temp.remove(temp.size() - 1);
return roods;
}复杂链表的复制
问题描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
1、逐个复制，变为AABBCCDD 2、复制random 3、拆分
public RandomLinkNode copy(RandomLinkNode phead) {
if (phead == null) return null;
// 逐个复制，变为AABBCCDD
RandomLinkNode head = phead;
while (head != null) {
RandomLinkNode node = new RandomLinkNode(head.value);
node.next = head.next;
head.next = node;
head = node.next;
}
// 复制random
head = phead;
while (head != null) {
if (head.random != null) {
head.next.random = head.random.next;
}
head = head.next;
}
// 拆分
head = phead;
RandomLinkNode newHead = head.next;
while (head != null) {
newHead.next = head.next.next;
head.next = head.next.next;
head = head.next;
}
return newHead;
}二叉搜索树与双向链表
问题描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
TreeNode head = null;
TreeNode end = null;
public LinkNode swap(TreeNode root) {
if (root == null) return null;
LinkNode fornt = swap(root.left);
LinkNode left = null;
LinkNode right = null;
LinkNode mid = new LinkNode(root.value);
if (root.left != null) {
left = new LinkNode(root.left.value);
left.next = mid;
}
if (fornt != null) {
fornt.next = (left == null ? mid : left);
}
if (root.right != null) {
right = new LinkNode(root.right.value);
mid.next = right;
}
swap(root.right);
if (right != null) {
return right;
} else {
return mid;
}
}求1+2+3+…+n
问题描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
解题思路
累加不能用循环的话，那就试试递归吧。判断递归的终止条件不能用 if 和 switch，那就用短路与代替。(n > 0) && (sum += Sum_Solution(n-1))>0只有满足n > 0的条件，&&后面的表达式才会执行。
public int sum(int n) {
int sum = n;
boolean b = (n > 0) && (sum += sum(n - 1)) > 0;
return sum;
}二叉树深度
问题描述
求二叉树深度
解题思路
采用递归方式 结束条件是传入结点为null。注意最后返回的深度要+1。
public int deap(TreeNode node) {
if (node == null) return 0;
int left = deap(node.left);
int right = deap(node.right);
return left > right ? left + 1 : right + 1;
}字符数组的所有组合
问题描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路
第一步求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）；第二步固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。这样，我们就可以用递归的方法来解决。
Set<String> set = new HashSet<>();
public void group(char[] chars, int begin) {
if (begin == chars.length - 1) {
set.add(String.valueOf(chars));
return;
}
for (int i = 0; i < chars.length - begin; i++) {
char temp = chars[chars.length - begin - 1];
chars[chars.length - begin - 1] = chars[i];
chars[i] = temp;
group(chars, begin + 1);
// 再次还原，以供下次再循环
temp = chars[chars.length - begin - 1];
chars[chars.length - begin - 1] = chars[i];
chars[i] = temp;
}
}把数组排列成最小的数
问题描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路
类似于冒泡排序 先将数组转换成字符串数组，然后对字符串数组按照规则排序，最后将排好序的字符串数组拼接出来。 关键就是制定排序规则：
若ab > ba 则 a > b 若ab < ba 则 a < b 若ab = ba 则 a = b
public String group(int[] nums) {
if (nums == null || nums.length == 0) return null;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
int a = Integer.valueOf(nums[j] + "" + nums[j + 1]);
int b = Integer.valueOf(nums[j + 1] + "" + nums[j]);
if (a > b) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
StringBuilder str = new StringBuilder();
for (int i : nums) {
str.append(i);
}
return str.toString();
}数组中个数超过一半的数字
问题描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路
- 排序，找中间值
public int method1(int[] nums) {
Arrays.sort(nums);
int mid = nums.length / 2;
int count = 0;
for (int i : nums) {
if (i == nums[mid]) count++;
}
if (count > mid) {
return nums[mid];
} else {
return 0;
}
}- 借助HashMap
public int method2(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
if (map.containsKey(i)) {
int n = map.get(i);
map.put(i, n + 1);
} else {
map.put(i, 1);
}
}
for (int i : map.keySet()) {
if (map.get(i) >= nums.length / 2) {
return i;
}
}
return 0;
}最小的k个数
问题描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解题思路
- 排序以后找出前k项
public ArrayList<Integer> method1(int k) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (nums == null || k == 0 || k > nums.length)
return res;
Arrays.sort(nums);
for (int i = 0; i < k; i++)
res.add(nums[i]);
return res;
}- 借助大顶堆
public ArrayList<Integer> method2(int k) {
ArrayList<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0 || nums.length < k) {
return res;
}
int[] heap = new int[k];
for (int i = 0; i < k; i++) {
heap[i] = nums[i];
}
// 将前k个数据构建大顶堆
for (int i = heap.length - 1; i >= 0; i--) {
adjustHeap(heap, i);
}
// 从第k项开始逐个遍历，比堆顶数据小的直接替换，再重新构建大顶堆
for (int i = k; i < nums.length; i++) {
if (nums[i] < heap[0]) {
heap[0] = nums[i];
adjustHeap(heap, 0);
}
}
for (int i : heap) {
res.add(i);
}
return res;
}
public void adjustHeap(int[] nums, int root) {
int temp = nums[root];
int index = root * 2 + 1;
while (index < nums.length) {
if (index + 1 < nums.length && nums[index + 1] > nums[index]) {
index++;
}
if (nums[index] < temp) {
break;
}
nums[root] = nums[index];
root = index;
index = root * 2 + 1;
}
nums[root] = temp;
}连续子数组的最大和
问题描述
求整型数组中最大的连续子数组的和.
解题思路
对于一个数组中的一个数x，若是x的左边的数加起来非负，那么加上x能使得值变大，这样我们认为x之前的数的和对整体和是有贡献的。如果前几项加起来是负数，则认为有害于总和。我们用cur记录当前值, 用max记录最大值，如果cur<0,则舍弃之前的数，让cur等于当前的数字，否则，cur = cur+当前的数字。若cur和大于max更新max。
public int getMaxSum() {
if (nums == null || nums.length == 0) return 0;
int cur = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = cur > 0 ? cur + nums[i] : nums[i];
if (cur > max) {
max = cur;
}
}
return max;
}