剑指Offer三天挑战赛32~45
文章目录
- 剑指 Offer 32 - III. 从上到下打印二叉树 III
- ==剑指 Offer 33. 二叉搜索树的后序遍历序列==
- 剑指 Offer 34. 二叉树中和为某一值的路径
- ==剑指 Offer 35. 复杂链表的复制==
- 剑指 Offer 36. 二叉搜索树与双向链表
- 剑指 Offer 37. 序列化与反序列化二叉树(非递归)
- 剑指 Offer 37. 序列化与反序列化二叉树(递归)
- 剑指 Offer 38. 字符串的排列
- 剑指 Offer 39. 数组中出现次数超过一半的数字
- 剑指 Offer 40. 最小的k个数
- 剑指 Offer 41. 数据流中的中位数
- 剑指 Offer 42. 连续子数组的最大和
- 剑指 Offer 43. 1~n 整数中 1 出现的次数
- 剑指 Offer 45. 把数组排成最小的数
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 这道题硬写也能写出来, 但是使用技巧性就很方便, 比如对返回值ans判断是不是偶数, 如果是偶数,那么就不需要反转链表数据, 如果是奇数就需要使用Collections.reverse来反转链表中的数据,其他操作和层序遍历一样
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return ans;
}
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> temp = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode cur = queue.poll();
temp.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
if (ans.size() % 2 != 0) {
Collections.reverse(temp);
}
ans.add(temp);
}
return ans;
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 这道题很有意思, 要清楚后序遍历结果的最后一个元素肯定是每一颗子树的根节点,它前面的数据最前边是左子树数据, 中间部分的数据是右子树数据
- 那么我倒叙遍历数组中的数据, 并附加一个栈配合,如果此时数组下标数据大于根节点数据root说明有错误, 然后如果此时栈不为空,并且此时栈底数据大于数据下标数据,说明此时栈底数据是数组坐标的父节点,但是要找到最亲父节点所以要使用while循环,最后所有的数据都要入栈
class Solution {
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i >= 0; i--) {
if (postorder[i] > root) {
return false;
}
while (!stack.isEmpty() && (stack.peek() > postorder[i])) {
root = stack.pop();
}
stack.push(postorder[i]);
}
return true;
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 很机智的一道题, 采用先序遍历的思路, 每次只要节点不为空就加入到linkedList中, 只要此时sum为0并且此时这个节点是叶子节点, 那么说明这是一个结果,保存他, 否则先用先序遍历访问其左子树和右子树, 最后不要忘了删除一开始加进去的这个数据,
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<List<Integer>> ans;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
ans = new ArrayList<>();
fun(new LinkedList<>(), sum, root);
return ans;
}
private void fun(LinkedList<Integer> list, int sum, TreeNode root) {
if (root == null) {
return;
}
list.add(root.val);
sum -= root.val;
if (sum == 0 && root.left == null && root.right == null) {
ans.add(new ArrayList<>(list));
}
fun(list, sum, root.left);
fun(list, sum, root.right);
list.removeLast();
}
}
剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 使用一个map用于建立原先链表节点和新建链表节点的映射关系, 然后用原先链表节点通过map的get操作来设置新建链表节点的复杂联系关系.
- 注意最后返回也是map.get后新建的链表节点
/*
// 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) {
if (head == null) {
return null;
}
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 这道题是原先将二叉搜索树改为双向链表, 那道题的话只需要使用中序遍历,然后保存head节点,处理per节点就可以
- 这道题比上面说到的题难了一点, 就是他是双向循环式的, 你还得保存队尾节点, 而队尾节点也是就最大值的那个节点, 最后让头节点的left指向尾节点, 尾节点的rigth指向头节点即可
/*
// 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 {
private Node head, per, tail;
public Node treeToDoublyList(Node root) {
if (root == null) {
return root;
}
fun(root);
head.left = tail;
tail.right = head;
return head;
}
private void fun(Node root) {
if (root == null) {
return;
}
treeToDoublyList(root.left);
if (head == null) {
head = root;
}
if (per != null) {
root.left = per;
per.right = root;
}
per = root;
treeToDoublyList(root.right);
if (tail == null || tail.val < root.val) {
tail = root;
}
}
}
剑指 Offer 37. 序列化与反序列化二叉树(非递归)
题目描述
请实现两个函数,分别用来序列化和反序列化二叉树
二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。
二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。
例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树
示例1
输入
复制
{8,6,10,5,7,9,11}
返回值
复制
{8,6,10,5,7,9,11}
解
- 下面这是一种非递归的写法, 序列化的过程是使用一个队列,每次在队列中取一个节点, 如果不为null则拼接其val和, 并且将其左节点有右节点放入队列, 如果此时节点为null, 则拼接#和,
- 对于反序列化,首先将字符串使用,分割, 然后初始化好节点数组用于存放节点,只要对应的parts位置不为# 就初始化该节点, 然后使用一个for循环构建二叉树,使用双下标,一个表示0开始, 一个在1开始, 1开的用于建立每个0开始下标左子树和右子树
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
String Serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
if (root == null) {
return builder.toString();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
builder.append(cur.val);
builder.append(',');
queue.offer(cur.left);
queue.offer(cur.right);
} else {
builder.append("#,");
}
}
String str = builder.toString();
return str.substring(0, str.length() - 1);
}
TreeNode Deserialize(String str) {
if (str == null || str.length() == 0) {
return null;
}
String[] parts = str.split(",");
return fun(parts);
}
private TreeNode fun(String[] parts) {
TreeNode[] nodes = new TreeNode[parts.length];
for (int i = 0; i < parts.length; i++) {
if (!parts[i].equals("#")) {
nodes[i] = new TreeNode(Integer.parseInt(parts[i]));
}
}
for (int i = 0, j = 1; j < parts.length; i++) {
if (nodes[i] != null) {
nodes[i].left = nodes[j++];
nodes[i].right = nodes[j++];
}
}
return nodes[0];
}
}
剑指 Offer 37. 序列化与反序列化二叉树(递归)
解
- 对于递归版本来说, 序列化的过程就是如果为null就拼接#, 如果不为null就拼接他的val, 然后在拼接他的左子树和右子树, 最后返回string
- 对于反序列化的过程就是先将其分割,判断是否越界, 然后递归初始化节点
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
String Serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
if (root == null) {
builder.append("#,");
return builder.toString();
}
builder.append(root.val).append(",");
builder.append(Serialize(root.left));
builder.append(Serialize(root.right));
return builder.toString();
}
private int index = 0;
TreeNode Deserialize(String str) {
String[] parts = str.split(",");
return fun(parts);
}
private TreeNode fun(String[] parts) {
if (index >= parts.length) {
return null;
}
if (parts[index].equals("#")) {
index++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(parts[index++]));
node.left = fun(parts);
node.right = fun(parts);
return node;
}
}
剑指 Offer 38. 字符串的排列
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = “abc”
输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 这是一道典型的全排列问题, 利用dfs思想来实现, 而且得使用HashSet保存交换过的字符,避免字符串重复
class Solution {
public String[] permutation(String s) {
List<String> list = new ArrayList<>();
char[] chars = s.toCharArray();
fun(chars, 0, list);
Collections.sort(list);
String[] ans = new String[list.size()];
for (int i= 0; i < ans.length; i++) {
ans[i] = list.get(i);
}
return ans;
}
private void fun(char[] chars, int index, List<String> list) {
if (index == chars.length) {
list.add(String.valueOf(chars));
}
HashSet<Character> set = new HashSet<>();
for (int i = index; i < chars.length; i++) {
if (set.contains(chars[i])) continue;
set.add(chars[i]);
swap(chars, i, index);
fun(chars, index + 1, list);
swap(chars, i, index);
}
}
private void swap(char[] arr, int index, int i) {
char temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 题意只是为了寻找众数一种是使用map统计找到数量大于一般的那个数据, 再就是使用众数的定义, 众数一定是在排序好的数组的中间
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length >> 1];
}
}
剑指 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个数字也可以,但是效率低所以使用我在这里使用堆排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int num : arr
) {
queue.offer(num);
}
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
ans[i] = queue.poll();
}
return ans;
}
}
剑指 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]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 维护俩个优先级队列和一个计数器, big优先级队列是大堆, 放置较小的数据, small是小堆,放置较大的数据,这样小堆的堆顶和大堆的堆顶就是中位数, 但是还要判断数据的个数, 如果是奇数那定在大堆中, 如果是偶数那就是俩个堆顶的数据的平均值
class MedianFinder {
/** initialize your data structure here. */
private PriorityQueue<Integer> big = new PriorityQueue<>((o1, o2) -> o2 - o1);
private PriorityQueue<Integer> small = new PriorityQueue<>();
private int size = 0;
public MedianFinder() {
}
public void addNum(int num) {
if (size % 2 == 0) {
small.offer(num);
big.offer(small.poll());
} else {
big.offer(num);
small.offer(big.poll());
}
size++;
}
public double findMedian() {
if (size % 2 == 0) {
return (small.peek() + big.peek()) * 1.0 / 2;
} else {
return big.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 最经典的一道动态规划,ret初始化为数组下标0的数据,从数组1开始遍历数据, 如果前一个下标数据小于0那么加起来肯定是让和变小了,那么就加0即可, 最后使用ret保存最大累加和
//时间和空间复杂度全为O(N)
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int ret = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
ret = Math.max(ret, dp[i]);
}
return ret;
}
}
//优化空间复杂度为O(1)
class Solution {
public int maxSubArray(int[] nums) {
int ret = nums[0];
for (int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
ret = Math.max(ret, nums[i]);
}
return ret;
}
}
剑指 Offer 43. 1~n 整数中 1 出现的次数
输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12
输出:5
示例 2:
输入:n = 13
输出:6
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
class Solution {
public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while(high != 0 || cur != 0) {
if(cur == 0) res += high * digit;
else if(cur == 1) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解
- 这个采用分治的思想, 每次对比俩个数据的正反拼接的大小, 使用compareTo判断是否需要互换位置, 我使用的是冒泡排序的思想,也就是最开始放的肯定是最小的数据
class Solution {
public String minNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
String num1 = "" + nums[i] + nums[j];
String num2 = "" + nums[j] + nums[i];
if (num1.compareTo(num2) > 0) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
StringBuilder ans = new StringBuilder();
for (int num: nums) {
ans.append(num);
}
return ans.toString();
}
}
本文地址:https://blog.csdn.net/Shangxingya/article/details/112779043
上一篇: 用Qt学着做个界面
推荐阅读
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)
-
剑指Offer JZ45 扑克牌顺子(Java)
-
剑指offer32题:整数中1出现的次数(从1到n整数中1出现的次数)
-
整数中1出现的次数(从1到n整数中1出现的次数)(剑指offer第32题)
-
剑指offer:(32)时间效率 :整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指Offer三天挑战赛32~45
-
剑指offer JZ45 扑克牌顺子 Python 解
-
【剑指 Offer 45】 把数组排成最小的数
-
剑指offer系列(45)扑克牌顺子
-
剑指offer JZ45 扑克牌顺子 Python 解