Dave是只学习基

题目： 剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode） (leetcode-cn.com) 剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode） (leetcode-cn.com) 快速幂 例子： x11x^{11}x11 原理： 将要求的幂的指数转为二进制形式，如11转换为1011。因此x11=x23+21+20x^{11}=x^{2^{3}+2^{1}+2^{0}}x11=x23+21+20 由于x23+21+20=x23×x21×x20x^{2^{3}+2^{1}+2^{0}}=x^{2^{3}} \times x^{2^{1}} \times x^{2^{0}}x23+21+20=x23×x21×x20，也就是只需要将每一位1所对应的权重相乘 实现方法就是首先初始化long b = n和double res = 1.0，使用按位与1运算判断最小位是否为1。如果为1，则res乘上此时的底数x。操作完成后b需要右移一位。 在进入下一次循环之前，需要让底数的指数翻倍x *= x，以匹配右移后的b。 剑16代码： 1234 ...

柯西不等式 假设都相等的时候乘积最大 最后会转化成 y=x1xy = x^{\frac{1}{x}}y=xx1​求极大值 直接用wolfram求求 用2和3试一下 发现3的结果更大 2只能分成1x1 3只能分成1x1x1或者1x2 后者大 商为a 余数为b 做如下分类讨论 123456789class Solution { public int integerBreak(int n) { if(n <= 3) return n-1; int a = n / 3, b = n % 3; if(b == 0) return (int)Math.pow(3, a); if(b == 1) return (int)Math.pow(3, a-1) * 4; return (int)Math.pow(3, a) * 2; }}

基本上是围绕着这两题：297. 二叉树的序列化与反序列化 - 力扣（LeetCode） (leetcode-cn.com)和剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com) 补充：加入剑指offer32-II 力扣 (leetcode-cn.com) Leetcode 297: 序列化部分，需要充分理解队列的使用。 队列用于存储下一层广度优先遍历的节点。 当从队列中取出一个非空节点时，需要同时将该节点的左右子节点放入队列末尾。 从队列中依次取出节点并放在返回的序列（字符串）尾端。 如果当前取出节点为空，则字符串加入“null”以表示空节点。 需要的数据结构：StringBuilder构造字符串，队列存储下一步需要遍历的节点。 12345678910111213141516171819public String serialize(TreeNode root) { if(root == null) return "[]"; StringBuilder res = new Str ...

最基本的链表题目，需要注意的问题就是最后别忘了tail.next = null这样一回事… 12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode tail = new ListNode() ...

题目链接：https://leetcode-cn.com/problems/search-a-2d-matrix/ 题目比较简单，一上来的想法是二分，因为从题干可以看出这个矩阵其实可以看作一位数组处理。需要转换的逻辑只有mid的含义。由于题目输入是二维矩阵，此时的mid代表的其实是假设flatten到一维后的index，所以要转换成二维坐标(mid/n, mid%n)处理。 继续注意二分的各种边界问题～ 12345678910111213141516class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while(left < right) { int mid = left + right + 1 >> 1; ...

原题链接：https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/ 给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件： arr 中 第一个 元素必须为 1 。 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。 你可以执行以下 2 种操作任意次： 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。 重新排列 arr 中的元素，你可以以任意顺序重新排列。 请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。 易证满足上述条件的数组要满足非严格单调递增分布（脑补一下），排序数组后强制使第一位为1，后续元素如果与前一位差值超过题目要求就设为前一位+1。不知道这样说有没有毛病。 1234567891 ...

981. 基于时间的键值存储 题解：宫水三叶 先做HashMap+数组的基本解法和偷鸡解法。后面再看HashMap+树的做法。这里需要注意看题目，题目表明： ​ 所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。 因此可以利用二分查找达成“找到小于等于查询时间戳的最大时间戳的键值”这一要求。 1234567891011121314151617181920212223242526272829303132333435363738394041class TimeMap { class Node { String k, v; int t; Node(String k, String v, int t) { this.k = k; this.v = v; this.t = t; } } Map<String, List<Node>> ...

题目链接 https://leetcode-cn.com/problems/combination-sum/ 深度优先搜索、回溯、剪枝。 参照[liweiliwei1419的题解](回溯算法 + 剪枝（回溯经典例题详解） - 组合总和 - 力扣（LeetCode） (leetcode-cn.com))，如果candidates = [2,3,6,7], target = 7，先画出类似如下的树形图，边上的数值为candidates的元素，从根到所有为0的节点的路径就是合法路径。深度优先搜索到节点为0或者为负数时停止该分支上的搜索（后续可以排序candidates进行剪枝）。 存储搜索路径的数据结构使用双向队列，在递归完成对当前节点的深度优先搜索后需要removeLast来reset路径状态回到搜索之前。 在搜索某一节点时，每一个分支的搜索起始点需要在candidates中向后移动一个位置，以避免使用同一层已经使用过的元素导致结果出现重复。 12345678910111213141516171819202122232425262728class Solution { p ...

题目链接：31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com) 看看这个链接！评论区有人API一把梭…不行 我用的是Java 理解题解：两轮从尾部开始的扫描，第一轮找出第一个顺序对nums[i], nums[i+1]，以此为分界，之后为倒序。第二轮找出后面倒序的部分里从后往前第一个大于nums[i]的元素nums[j]，和nums[i]交换。此时后面还是倒序（因为nums[j]>nums[i]，nums[j+1]<nums[i]， nums[j-1]>nums[j]），所以只要用双指针往中央扫描、前后交换的方式排一下序就好了。一共涉及三次扫描操作，复杂度O(N)。 1234567891011121314151617181920212223242526272829class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while(i >= 0 && nu ...