剑指offer刷题笔记（五）
剑指 Offer 33. 二叉搜索树的后序遍历序列
- 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
递归，后序遍历节点是按左-右-中的顺序来遍历树，因此数组中最后一个节点就是根节点。然后在二叉搜索树中左子树的任意节点都比根节点以及右子树的任意节点小，因此可以在数组中分割出左子树部分和右子树部分，继续往下遍历，右子树的节点一定大于根节点。当有节点违背这个状态的话，就违反了二叉搜索树的定义，返回false
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder.length<=2){
return true;
}
boolean flag=isTree(postorder,0,postorder.length-1);
return flag;
}
public boolean isTree(int[] postorder,int start,int end){
if(start>=end){
return true;
}
int root=postorder[end];
int i=start;
for(;i<end;i++){
if(postorder[i]>root){
break;
}
}
int j=i;
for(;j<end;j++){
if(postorder[j]<root){
return false;
}
}
return isTree(postorder,start,i-1)&&isTree(postorder,i,end-1);
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
- 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
可以考虑用回溯法来，从根节点出发，一直到叶子节点，如果没有符合条件，则往回退一个阶段，继续匹配其他路径，由于答案中需要这个树中所有匹配路径，所以不是找到一条路径就结束了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> list=new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null){
return result;
}
getPath(root,sum);
return result;
}
public void getPath(TreeNode node,int target){
if(node==null){
return;
}
list.add(node.val);
target-=node.val;
if(target==0&&node.left==null&&node.right==null){
result.add(new ArrayList<>(list));//浅拷贝，优化内存
}
getPath(node.left,target);
getPath(node.right,target);
list.remove(list.size()-1);
}
}
剑指 Offer 35. 复杂链表的复制
-
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
image
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
image
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
image
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
首先复制链表，在原有链表的每一个节点后面追加一个复制节点，第二步在追加节点的随机节点赋值为原追加节点的复制节点，既copy.random=original.random.next，第三部断链，奇数节点为原链表，偶数节点为复制后的链表
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
copy(head);
find(head);
return result(head);
}
Node copy(Node head){
Node node = head;
while (node!= null) {
Node cloneNode =new Node(node.val);
cloneNode.next=node.next;
cloneNode.random=null;
node.next=cloneNode;
node= cloneNode.next;
}
return head;
}
Node find(Node head){
Node node=head;
while(node!=null){
if(node.random!=null){
node.next.random=node.random.next;
}
node=node.next.next;
}
return head;
}
Node result(Node head){
Node node=head;
Node result=null;
Node cloneNode=null;
if(node!=null){
cloneNode=result=node.next;
node.next=cloneNode.next;
node=cloneNode.next;
}
while(node!=null){
cloneNode.next=node.next;
cloneNode=cloneNode.next;
node.next=cloneNode.next;
node=node.next;
}
return result;
}
}
剑指 Offer 36. 二叉搜索树与双向链表
-
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
image
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
image
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head=null,tail=null,pre=null;
public Node treeToDoublyList(Node root) {
if(root==null) return root;
//中序遍历访问节点并连接
tree(root);
//连接头尾节点
head.left=tail;
tail.right=head;
return head;
}
public void tree(Node root){
if(root==null){
return;
}
tree(root.left);
if(pre==null){
head=root;
}
else{
pre.right=root;
}
root.left=pre;
pre=root;
tail=root;
tree(root.right);
return;
}
}
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
序列化根据它给的顺序来看可以看出是对二叉树的层次遍历，关于这点可以参考刷题（四），主要是对队列的运用，同时反序列化也是如此。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
Queue<TreeNode> queue=new LinkedList<>();
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null){
return "[]";
}
List<String> list=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node=queue.poll();
if(node==null){
list.add("null");
continue;
}
list.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
}
String result=new String();
result="\"[";
for (int i = 0; i <list.size() ; i++) {
result+=list.get(i)+",";
}
result=result.substring(0,result.length()-1);
result+="]\"";
return result;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.length()<=2){
return null;
}
data=data.substring(2,data.length()-2);
String[] split = data.split(",");
Queue<TreeNode> queue=new LinkedList<>();
TreeNode head=new TreeNode(Integer.valueOf(split[0]));
queue.offer(head);
int i=1;
while(!queue.isEmpty()){
if(i>split.length-1){
break;
}
TreeNode node=queue.poll();
if(split[i].equals("null")){
node.left=null;
}
else{
TreeNode left=new TreeNode(Integer.valueOf(split[i]));
node.left=left;
queue.offer(left);
}
i++;
if(split[i].equals("null")){
node.right=null;
}
else{
TreeNode right=new TreeNode(Integer.valueOf(split[i]));
node.right=right;
queue.offer(right);
}
i++;
}
return head;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
剑指 Offer 38. 字符串的排列
- 输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
class Solution {
//集合，去重
Set<String> set=new HashSet<>();
public String[] permutation(String s) {
if(s.length()==0){
return new String[]{};
}
boolean[] visted=new boolean[s.length()];
getString(s,"",visted);
return set.toArray(new String[s.length()]);
}
void getString(String s,String md,boolean[] visted){
if(s.length()==md.length()){
set.add(md);
return;
}
for (int i = 0; i <s.length() ; i++) {
char tmp=s.charAt(i);
if(visted[i]){
continue;
}
visted[i]=true;
getString(s,String.valueOf(tmp)+md,visted);
//回溯，回归初始状态
visted[i]=false;
}
}
}
剑指 Offer 39. 数组中出现次数超过一半的数字
- 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
1 <= 数组长度 <= 50000
由于题目假设数组非空并总是存在多数元素，因此可以省去对特殊条件的判断。由于寻找的是一个数字出现最多的次数超过数组长度的一半，可以转化成寻找数组中出现最多次的元素，因此可以用times来表示出现次数，当出现元素相等时，times++，不等时，times--，当times为0时，就计数当前元素。
class Solution {
public int majorityElement(int[] nums) {
int result=nums[0];
int times=1;
for (int i = 1; i <nums.length; i++) {
if(result==nums[i]){
times++;
}
else{
times--;
if(times==0){
result=nums[i];
times=1;
}
}
}
return result;
}
}
剑指 Offer 40. 最小的k个数
- 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对数组进行快排，当在基准值左边的数为k个时，就满足条件寻找最小的k个数。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr.length==0||k==0){
return new int[0];
}
return quickSearch(arr,0,arr.length-1,k-1);
}
int[] quickSearch(int[] nums,int start,int end,int target){
int j=quick(nums,start,end);
if(j==target){
return Arrays.copyOf(nums,j+1);
}
return j>target?quickSearch(nums,start,j-1,target):quickSearch(nums,j+1,end,target);
}
int quick(int[] nums,int start,int end){
int open=nums[start];
int i=start;
int j=end+1;
while(true){
while(--j>=start&&nums[j]>open);
while(++i<=end&&nums[i]<open);
if(i>j){
break;
}
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
nums[start]=nums[j];
nums[j]=open;
return j;
}
}
剑指 Offer 41. 数据流中的中位数
- 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
参考leetcode题解 用java的PriorityQueue优先级队列实现最大堆最小堆，求中卫数其实可以理解为中位数左边的最大值以及中位数右边的最小值的平均值。因此用最大堆存储左边的数，最小堆存储右边的数，保持最大堆的节点个数比最小堆多一个，总节点个数为奇数的话就是从最大堆中取，偶数则是两者平均数。
作者：jerry_nju
https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/you-xian-dui-lie-wu-fei-hua-jian-dan-yi-dong-by-je/
class MedianFinder {
PriorityQueue<Integer> maxheap,minheap;
/** initialize your data structure here. */
public MedianFinder() {
maxheap=new PriorityQueue<>(Comparator.reverseOrder());
minheap=new PriorityQueue<>();
}
public void addNum(int num) {
maxheap.offer(num);
minheap.offer(maxheap.poll());
if(minheap.size()>maxheap.size()){
maxheap.offer(minheap.poll());
}
}
public double findMedian() {
int size=maxheap.size()+minheap.size();
//奇数
if(maxheap.size()==minheap.size()){
return (maxheap.peek()+minheap.peek())*0.5;
}
return maxheap.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
