https://leetcode.com/problems/burst-balloons/
题意
给你一个数组,你要爆掉所有数字，爆某个数字的时候会获得它现在相邻的两个数字和它的乘积。如果这个数字没有左相邻或右相邻，则乘1代替，问爆掉所有数字的最高分数。思路
暴力计算的话复杂度为O(n!)肯定会超时
看到别人的解法是区间dp
dp[i][j]表示只爆掉[i,j]里所有数字后能获得的最大分数,那么我们枚举[i,j]里最后一个爆掉的数字的位置k.由于我们只爆掉[i,j]里的元素,因此最后爆掉k的时候,k的左右邻居一定是i-1和j+1.初始化为:dp[i][i]=arr[i-1]arr[i]...
https://leetcode.com/problems/additive-number/
题意
求解一个字符串是否是类似fibonacci，即每个数是否前两个数构成解法
看不懂题意～～看懂以后发现好像并不难，先求出前两个数，再往后推算即可
class Solution {
public boolean isAdditiveNumber(String num) {
int len = num.length();
//先取第一个数
for (int i = 1; i <= len; i++) {
//从第一个数之后取第二...
https://leetcode.com/problems/longest-increasing-subsequence/
题意
求序列中最长可不连接递增序列😂解法
双重遍历，复杂度$O(n^2)$
动态规划，以nums[i]结束的最大递增序列，即从nums[i]向前遍历，如果nums[j]小于nums[i]那么nums[i]=Math.max(nums[i], nums[j] + 1)```javaclass Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) ...
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
题意
实现Codec中序列化与反序列二叉树方法解法
序列化时采用按层次遍历，其中左右子结点为空时也加入结果
反序列化时
将第一个结点加入queue
queue中出列，如果结点不为null，刚从结果中取两个结点，分别赋值给结点的左右子树
重复2直至queue为空
class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {...
https://leetcode.com/problems/find-median-from-data-stream/
题意
实现一个MedianFinder，实现添加数字和查找中位数的功能，中位数定义为当数字个数位奇数时，返回中间的数，否则返回中间两个数的平均值解法
完全不知道怎么解，看了网上的解法才知道大小堆😂
大顶堆表示元素从小到大排列，大的元素在顶，小顶堆表示元素从大到小排列，小的元素在顶。且大堆中所有元素均小于小堆中元素。
解法中用PriorityQueue实现大小堆
class MedianFinder {
//小顶堆，元素从小到大排列，先取到小的元素
Prior...
https://leetcode.com/problems/nim-game/
题意
两个人依次取数，每次可以取1，2，3，给出一个数，求先取的能否获胜解法
获胜的人肯定是最后一个取数，可能取1，2，3，f(n)时只要f(n-1)，f(n-2)，f(n-3)中有一个不能取胜，那么f(n)就能取胜，类似于斐波那挈数列的求法。但是当n很大的时候递归肯定会StackOverFlow，因此用一个数组来保存中间结果，结果Memory Limit Exceeded😂😂
后来再一想，f(n)依赖于f(n-1)，f(n-2)，f(n-3)。其中f(1)，f(2)，f(3)是false，f(4)是tr...
https://leetcode.com/problems/perfect-squares/
题意
给一个数，将它分解成整数的平方数之和，求最小的平方数的数量解法
BFS，采用queue计算中间结果，current表示当前值，count表示最小数量
将n入列
queue中取值赋给current，计算1到current之间的所有平方数
遍历1到current之前的平方数num，假如current等于平方数，因为是BFS，每一次都会遍历所有的可能结果，那么此时肯定是count最小值，返回结果，否则将current-num加入临时结果集
直到queue为空，说明这一层已经遍历结束，coun...
https://leetcode.com/problems/single-number-iii/
题意
数组中除了两个数出现一次，其它的数都出现两次，求解要求满足时间复杂度O(n)，空间复杂度O(1)解法
所有的数异或的结果就是两个数异或的结果，因为两个相同的数异或肯定是0，而0跟任何数异或都是那个数本身
最终结果转换成二进制的结果中为1的位，必然有其中一个数该位为1，另一个数该位为0，只有0，1异否才是1
将数组中的所有数与二进制中仅一位为1的数resInt异或，那么所有结果为0的数异或就是其中一个数，为1的是另外一个数。此时不需要考虑出现两次的数，因为他们与restInt的异或结果相...
https://leetcode.com/problems/number-of-digit-one/
题意
求1到n之间所有数中1的出现次数解法
先计算出位数与n相同且为10的倍数的数，根据n的最大位digit分为两种情况
digit == 1，刚f(n) = 1 + n%k + f(n%k) + f(k-1)，即以1开头位数与n相同的数共有n%k+1个，再加上n%k里1的出现次数再加上0到k-1里1的出现次数即是最后结果
digit != 1，则f(n) = f[k, n] + f(k-1)，即结果为k到n的数里1的出现次数加上0到k-1里1的出现次数2.1 其中f[k, n] =...
