Hi there 👋

剑指 Offer 45. 把数组排成最小的数 medium 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 提示: 0 < nums.length <= 100 说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 Solution S1 直接排序, 对比合并后的大小. class Solution { public String minNumber(int[] nums) { int n = nums.length; String[] strs = new String[n]; for (int i = 0 ; i < n ; i++) { strs[i] = String.valueOf(nums[i]); } Arrays.sort(strs, (o1, o2) -> (o1+o2).compareTo(o2+o1)); StringBuilder sb = new StringBuilder(); for (int i = 0 ; i < n ; i++) { sb.append(strs[i]); } return sb.toString(); } }

剑指 Offer 42. 连续子数组的最大和 easy 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 提示： 1 <= arr.length <= 10^5 -100 <= arr[i] <= 100 注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/ Solution S1 时间复杂度为 O(n), 考虑动态规划。 思考递推关系： 第一反应：求最大数，那么设置 dp[i] 为当前最大和。但是题目说要求连续子数组。 所以，dp[i] 表示为 nums[i] 为结尾的连续子数组最大和。 那么 dp[i] 就为 max(nums[i], dp[i-1]+nums[i]) class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int dp[] = new int[n]; dp[0] = nums[0]; int ans = dp[0]; for (int i = 1 ; i < n ; i++) { dp[i] = Math.max(nums[i], dp[i-1]+nums[i]); ans = Math.max(ans, dp[i]); } return ans; } } 执行用时：2 ms, 在所有 Java 提交中击败了6.92%的用户 内存消耗：45 MB, 在所有 Java 提交中击败了32.63%的用户 ...

剑指 Offer 41. 数据流中的中位数 hard 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [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] 限制： 最多会对 addNum、findMedian 进行 50000 次调用。 注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/ Solution S1 求中位数，需要数据有序，第一想法，利用优先队列保存数据。 为了快速取到计算中位数用的数据，可以把他们分开两个堆。 一个大顶堆，存储数据较小的部分，那么，堆顶的数据就是前半部分的最后(最大)一个数据。 一个小顶堆，存储数据较大的部分，那么，堆顶的数据就是后半部分的最小的一个数据。 计算时： 判断是否是奇数 如果是，直接返回奇数的堆顶。 如果不是，获取他们的堆顶数据，计算中位数 class MedianFinder { private Queue<Integer> big; private Queue<Integer> small; public MedianFinder() { big = new PriorityQueue();//小顶堆，保存大的 small = new PriorityQueue(new Comparator<Integer>() {//大顶堆，保存小的 @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); } public void addNum(int num) { if (big.size() > small.size()) { big.add(num); small.add(big.poll()); } else { small.add(num); big.add(small.poll()); } } public double findMedian() { if (big.size() != small.size()) { return big.peek(); } return (big.peek() + small.peek())/2.0; } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */ 执行用时：105 ms, 在所有 Java 提交中击败了42.41%的用户 内存消耗：67.7 MB, 在所有 Java 提交中击败了18.39%的用户 ...

剑指 Offer 40. 最小的k个数 easy 输入整数数组 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] 限制： 0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000 Solution S1 不限定返回的顺序，考虑快排的划分方法。 class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k >= arr.length) return arr; if (k == 0) return new int[0]; return quick(arr, k, 0, arr.length - 1); } private int[] quick(int[] arr, int k, int left, int right) { int l = left, r = right; while (l < r) { while (l < r && arr[r] >= arr[left]) r--; while (l < r && arr[l] <= arr[left]) l++; swap(arr, l, r); } swap(arr, l, left); if (l > k) return quick(arr, k, left, l - 1); if (l < k) return quick(arr, k, l + 1, right); return Arrays.copyOf(arr,k); } private void swap(int[] arr, int l, int r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; } } 执行用时：2 ms, 在所有 Java 提交中击败了97.40%的用户 内存消耗：39.8 MB, 在所有 Java 提交中击败了37.21%的用户 ...

剑指 Offer 39. 数组中出现次数超过一半的数字 easy 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/ Solution S1 摩尔投票： 超过一半，所以投票的总数肯定 > 0 前面 n 个的票数的和为 0, 则剩余的数字票数一定还是 > 0 class Solution { public int majorityElement(int[] nums) { int x = 0, votes = 0; for(int num : nums){ if(votes == 0) x = num; votes += num == x ? 1 : -1; } return x; } }

剑指 Offer 38. 字符串的排列 medium 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 输入：s = “abc” 输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制： 1 <= s 的长度 <= 8 Solution S1 class Solution { public String[] permutation(String s) { char[] cs = s.toCharArray(); Set<String> list = new HashSet(); boolean visisted[] = new boolean[cs.length]; backtrack(cs, list, new StringBuilder(), visisted); String[] res = new String[list.size()]; int index = 0; for (String str : list) { res[index++] = str; } return res; } private void backtrack(char[] cs, Set<String> res, StringBuilder strBuilder, boolean visisted[]) { if (strBuilder.length() == cs.length) { res.add(strBuilder.toString()); return; } for (int i = 0; i < cs.length ; i++) { if (visisted[i] == true) continue; strBuilder.append(cs[i]); visisted[i] = true; backtrack(cs, res, strBuilder, visisted); strBuilder.deleteCharAt(strBuilder.length() - 1); visisted[i] = false; } } } 执行用时：33 ms, 在所有 Java 提交中击败了32.27%的用户 内存消耗：42.7 MB, 在所有 Java 提交中击败了74.25%的用户 ...

剑指 Offer 36. 二叉搜索树与双向链表 medium 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/ 注意：此题对比原题有改动。 Solution S1 二叉搜索树，带排序 不能创建任何节点 返回数值最小的 Node 二叉搜索树，中序遍历就是有序数组了，数组再替换一下他们的指向就可以了。 /* // 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 { public Node treeToDoublyList(Node root) { if (root == null) return null; List<Node> list = new ArrayList(); traver(list, root); Node pre = list.get(0); Node head = pre; Node node = null; for (int i = 1 ; i < list.size() ; i++) { node = list.get(i); node.left = pre; pre.right = node; pre = node; } pre.right = head; head.left = pre; return head; } private void traver(List<Node> list, Node node) { if (node == null) return; traver(list, node.left); list.add(node); traver(list, node.right); } } 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：37.9 MB, 在所有 Java 提交中击败了15.51%的用户 ...

剑指 Offer 37. 序列化二叉树 hard 请实现两个函数，分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 示例： 输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5] 注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/ Solution S1 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) return ""; LinkedList<TreeNode> queue = new LinkedList(); StringBuilder sb = new StringBuilder(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node != null) { sb.append(node.val); sb.append(','); queue.add(node.left); queue.add(node.right); } else { sb.append("#,"); } } sb.deleteCharAt(sb.length() - 1); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.isEmpty()) return null; String[] nodeArray = data.split(","); LinkedList<TreeNode> queue = new LinkedList(); TreeNode head = new TreeNode(Integer.valueOf(nodeArray[0])); queue.add(head); int index = 1; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if (!nodeArray[index].equals("#")) { node.left = new TreeNode(Integer.valueOf(nodeArray[index])); queue.add(node.left); } index++; if (!nodeArray[index].equals("#")) { node.right= new TreeNode(Integer.valueOf(nodeArray[index])); queue.add(node.right); } index++; } return head; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root)); 执行用时：14 ms, 在所有 Java 提交中击败了72.23%的用户 内存消耗：39.8 MB, 在所有 Java 提交中击败了92.62%的用户 ...

剑指 Offer 35. 复杂链表的复制 medium 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 Solution S1 深复制 random 和 next 都在同一个链表中出现 那我们可以先构建所有的新节点，通过 HashMap 保存，然后再一一赋值 /* // 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) { Map<Node, Node> mapper = new HashMap(); Node n = head; while (n != null) { Node newNode = new Node(n.val); mapper.put(n, newNode); n = n.next; } n = head; while (n != null) { Node newNode = mapper.get(n); Node next = mapper.get(n.next); Node random = mapper.get(n.random); newNode.next = next; newNode.random = random; n = n.next; } return mapper.get(head); } } 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：38.3 MB, 在所有 Java 提交中击败了36.99%的用户 ...

剑指 Offer 34. 二叉树中和为某一值的路径 medium 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] 提示： 节点总数 <= 10000 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/ Solution S1 从根节点开始 需要注意，除了 sum == target, 最后的节点还需要没有下一个节点了。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<List<Integer>>(); backtrack(result, new ArrayList<Integer>(), root, 0, targetSum); return result; } private void backtrack(List<List<Integer>> result, List<Integer> subList, TreeNode node, int sum, int target) { if (node == null) return; int value = node.val; sum += value; subList.add(value); if (sum == target && node.left == null && node.right == null) { result.add(new ArrayList(subList)); } else { backtrack(result, subList, node.left, sum, target); backtrack(result, subList, node.right, sum, target); } sum -= value; subList.remove(subList.size() - 1); } } 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户 内存消耗：38.8 MB, 在所有 Java 提交中击败了54.20%的用户 ...