https://leetcode.com/problems/wiggle-subsequence/
题意
求数组中最长子序列满足wiggle subsequence要求（即一大一小错开）解法
DFS对数组进行循环，第一个数时下一个数可以比它大也可以比它小，之后依次递推。直接DFS肯定会TLE，需要记录中间结果
class Solution {
int dp[][];
public int wiggleMaxLength(int[] nums) {
//dp用来记录中间结果
dp = new int[3][nums.length];
int max =...
https://leetcode.com/problems/combination-sum-iv/
题意
给一个数组，求结果为target的组合数，数字可重复解法
DFS，直接算会TLE，缓存中间结果后可以通过class Solution {
HashMap<Integer, Integer> cache = new HashMap<>();
public int combinationSum4(int[] nums, int target) {
if (target == 0) {
return 1;
} else ...
https://leetcode.com/problems/largest-divisible-subset/
题意
求一个数组中最长子序列，子序列中任意两个数满足i % j == 0 || j % i == 0思路这个问题相当于对数组进行排序，求一个子序列，其中每一个数都是前一个的整数倍。
开始想的是从每一个数开始向后遍历，记下最大值时的结果。时间复杂度为O(n!)，基本上无法计算出来，加上缓存后在最后一个用例还是TLE，最后再加上另一处优化总算是没有超时。
class Solution {
HashMap<Integer, List<Integer>> ...
https://leetcode.com/problems/russian-doll-envelopes/
题意
求大众套娃，咦，是俄罗斯套娃的最大层数解法
dfs+cache，从每个位置开始搜索，并记下中间结果，否则会超时
class Solution {
HashMap<int[], Integer> cache = new HashMap<>();
public int maxEnvelopes(int[][] envelopes) {
int length = envelopes.length;
if (length =...
一段时间没做题了，发现真的没有天赋
题意
还是买卖股票，不限次数，但是卖出后第二天不能做任何交易解法
感觉是dp吧
双重循环，i表示买入，j表示卖出，第j天时的最大收益为
当天未交易的结果dp[j - 1]
当天完成交易的结果prices[j] - prices[i] + dp[i-2]
非i天买入，j天时的结果dp[j]
3种情况取最大值class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
...
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
题意
求二维数组中上下左右延伸的最长序列长度思路
这类题首先想到的就dfs，从一个数开始搜索，查找这个数开始的最大序列，最终结果就是就是每一个位置的结果取最大值。
开始想的比较复杂，写了很多没用的逻辑，比如判断这个数是否用过还开了新数组来记录并回溯（因为是递增的，同样的数肯定不会用两次）。写完之后发现第135个case超时了，因为每个数都需要向4个方向搜索，时间复杂度基本上就是O($4^{n^2}$)，n稍大就不可能计算出来。
后来看了别人的解，思路基本上...
https://leetcode.com/problems/integer-break/
题意
将一个整数n分为若干数，求这些数的最大乘积思路
BFS
class Solution {
Map<Integer, Integer> cache = new HashMap<>();
public int integerBreak(int n) {
if (n == 1) {
return 1;
}
if (cache.containsKey(n)) {
return cache.g...
https://leetcode.com/problems/bulb-switcher/
题意
有n个灯，从1到n，每次对第i*[1,2,3,4…]个灯进行操作，求最终亮灯的个数思路
https://www.cnblogs.com/grandyang/p/5100098.html这道题给了我们n个灯泡，第一次打开所有的灯泡，第二次每两个更改灯泡的状态，第三次每三个更改灯泡的状态，以此类推，第n次每n个更改灯泡的状态。让我们求n次后，所有亮的灯泡的个数。此题是CareerCup 6.6 Toggle Lockers 切换锁的状态。那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5...
https://leetcode.com/problems/count-of-smaller-numbers-after-self/
题意
求一个数组中每个位置之后比当前元素小的元素的个数思路
暴力递归居然也能AC～～～
参考别人思路采用二叉搜索树，在构建树的同时计算比当前节点小的个数
当前节点root为空，则构建一个新节点，新节点smaller为0，返回新节点
当前值比当前节点小，那么当前节点smaller++，返回插入当前节点左子树的结果
当前值不小于当前节点值，那么返回插入当前节点右子树的结果+当前结点的smaller+当前值大于当前节点值?1:0（因为此时节点需要插入右子树，所以...
https://leetcode.com/problems/maximum-product-of-word-lengths/
题意
求字符串数组中不含相同字母的字符串的长度的乘积的最大值（好拗口～～）思路
由于只有26个字母，因此可以用一个int的每一位表示该字符串是否含有某个字符，两个数&的结果为0则表示没有相同的字母
开始以为暴力求解两两相乘的话时间复杂度为O($n^2$)，可能会有更好的解法，结果好像并没有//将 整数 num 的第 i 位的值 置为 1
private static int getBit(int num, int i)
{
return...
