完成剑指offer第6章😅

暴力出所有的可能集合，再与要求的限制作比较。最终求出能组成的新集合数量。 有n个元素,每个元素都有取与不取的两种可能,所以应该是2^n个. 因为n<=20，故至多有10^6个集合，我们可以采用暴力搜索。 因为要遍历出所有的取值情况，我们使用回溯来解决此类问题。回溯类型的题目有一套通用的模板。 回溯法 result = [] dfs backtrack(路径，选择列表): if(满足结束条件): result.add(路径) return 做选择 backtrac...

新建一个数组res，用于保存结果。 新建一个pos下标，用于指向数组res的最新元素的位置。 循环遍历一次输入数组str：     1.当res的第pos个元素和str的第i个元素都等于1，删除res的第pos个元素 并pos减一；     2.当res的第pos个元素和str的第i个元素都等于0，替换res的第pos个元素为1，         2.1此时需要再判断 若res的第pos-1个元素存在并且为1，则删除res的第pos-1...

看完剑指offer第五章😏

完成剑指offer第四章😄

我们知道，只想知道一棵树的前序遍历和后序遍历是求不出中序遍历的。但是，因为题目多了一个条件【若某节点只有一个子结点，则此处将其看作左儿子结点】。所以可以求出唯一的一个中序遍历。 在二叉树的前序遍历中，第一个数字总是树的根结点，根结点右边的第一个结点总是左儿子结点。在该二叉树的后序遍历中，知道了该根结点和其左儿子在后序遍历中的下标后，夹在根结点和其左儿子之间的结点是根结点的右子树。在左儿子的左边部分结点是该左儿子的子树。 既然我们已经找到了左、右子树的前序遍历和中序遍历，我们可以用同样的方法分别取构建左右子树。也就是说，接下来可以用递归的方法完成。 import java.util.*; ...

对于每个r找到一个l使得【l,r】中0的个数小于等于m，当r右移的时候，l可能不动可能会跟着右移。当滑动窗口内黑色段的长度大于m时【清洗剂最多只能清洗m段】，l 需要右移。并随时更新当前窗口内的能获得的纯白色木板的最大长度和区间内黑色段的长度。时间复杂度为O(n)。 import java.util.*; public class Solution { /** * * @param n int整型 长度为n的白木板 木板被等分成了n段 * @param m int整型 清洗剂最多只能清洗m段 * @param a int整型一维数组 长度为n...

这道题最直观的解法并不难，需要我们分情况判断一下所有的情况。 举个例子“1234567”。循环右移的所有情况为7123456、6712345、5671234、4567123、3456712、2345671、1234567。 我们来看看所有情况所需的最少区间反转次数。 1234567->6543217->7123456 先在[1,6]之间反转，最后整体[1,7]反转。至少2次 1234567->6543217->6712345 先在[1,6]之间反转，最后在[2,7]之间反转。至少2次 1234567->4321567->4321765->...

完成剑指offer第二章😁