题目的主要信息：  将一个字符串s中的每个空格替换成“%20” 保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种  方法一：字符串截取相加 具体做法：我们可以用下标遍历字符串，每次检查下标所在位置的字符是否为空格，如果不是空格，下标继续往后，如果是空格则调用substr函数将字符串从空格前后截断，然后中间添加"%20"后相连即可。  class Solution { public: string replaceSpace(string s) { int index = 0; //下标 while(index < s.length()){ //遍历字符串下标...

题目的主要信息：  Alice的牌里有p1张石头牌，q1张剪刀牌，m1张布牌，Bob的牌里有p2张石头牌，q2张剪刀牌，m2张布牌，每人都是n张 赢一局得1分，输一局扣1分，平局不得分，问Alice在每次知道Bob出什么牌的情况，怎么出牌最终得分最高  方法一：暴力模拟 具体做法：我们利用贪心的思想，Alice知道Bob每次出什么牌，如果她手里有可以赢的牌就出可以赢的牌去得分，如果没有再看有没有相同的牌争取平局不扣分，最后实在不行再出要输的牌扣分，这样得分才能最高。因为三种牌是相互克制的，出牌顺序并不影响得分，因此我们可以按照Bob先出石头再出剪刀最后出布的顺序来模拟。  class Solu...

题目的主要信息：  一个环形的食堂，个入口，入口处排队的人记录在数组a中 刚开始在第一个入口，如果有人在排队，花费1分钟走到下一个入口，如果下一个入口无人可直接进入，否则再花1分钟走到下一个入口，如此循环。（环形食堂，相当于数组a首尾相接） 每过1分钟每个入口排队的人会少1，问最终将从哪个入口进入  方法一：暴力模拟 具体做法：我们可以设置一个变量i记录下标，设置一个变量time记录过去的时间，从第一个入口即下标i为0且time为0开始，我们检查是否大于0，如果大于0，说明这个时间这个入口还有人在排队，否则这个口可以直接进入；如果不能直接进入，我们时间加1，下标加1（如果是到了数组a的末尾则置...

题目的主要信息：  Alice的牌里有p1张石头牌，q1张剪刀牌，m1张布牌，Bob的牌里有p2张石头牌，q2张剪刀牌，m2张布牌，每人都是n张 Alice直到Bob每次出什么牌的情况下如何出牌可以使Alice赢的局数最多，输出最多次数  方法一：暴力模拟 具体做法：因为剪刀石头布是相互克制的，你出一张牌，只要我有，必定能克制你的牌，因此出牌顺序是不影响赢的局数的，所以我们不妨假设Bob先出石头，再出剪刀，最后出布，每种牌都出完为止再出其他的牌。对于Bob出的一种牌，我们检查Alice手中还有无可以克制它的牌，如果有，双方手中的出的牌各自减1，Alice赢一局，如果没有剩余克制它的牌了，对于A...

题目的主要信息：  n个房间一共n-1个通道相连，每个房间可互相到达，这就是一棵无向树 牛牛一开始在1号房间，要到另一个房间去找牛妹，这个过程中每条痛道最多只能走两次，且如果当前牛牛有没走过的通道可以走，牛牛就不会去走走过一次的通道 每次走过一条通道花费1金币，一共m个查询，每次查询牛妹在xix_ixi​号房间，问最少要携带多少金币才能保证任何情况都能找到牛妹**（即每次查询的时候先走通往不了的牛妹房间的分支，最后走通往牛妹的房间的分支，这种情况都能满足，那任意情况都可以满足）** 题目的意思是每次查询都从1号房间开始  方法一：两次dfs 具体做法： 上面已经提到了，我们至少要满足任何情况都...

题目的主要信息：  n根木棒，长度为1到n 对于要求的排列：第根木棒要求或者 求满足条件的排列中从小到大第k个排列  方法一：暴力枚举（超时） 具体做法：我们首先构造一个从1到n的数组，这是这n个数排列的最小值，然后利用next_permutation函数依次构造其余的排列，它会从小到大构造。对于每个构造出来的排列，我们遍历数组检查是否满足上述要求，满足要求k减1直到k为0，返回这个排列。 class Solution { public: bool check(vector<int>& a){ for(int i = 1; i < a.size() - 1; i++)...

题目的主要信息：  一个的棋盘编号呈现螺旋状排列，一开始棋子在1号棋盘格上分数为0 一共q次询问，每次都是1-6数字中的一个，记为j，棋子会按照编号移动相应位数j（号会回到1号），按照公式来写：当前在序号i，移动j步后，下一次的位置是 我们要计算的分数，就是加上所有行号或者列号与当前格子相差小于上述移动位数j的所有格子的编号 得分是与前面累加的，且要对1000000007取模  方法一：暴力解法（超时） 具体做法：暴力解法分为两部分，一个是构建棋盘，另一个是对每次查询计算分数。构建棋盘部分：我们参照螺旋矩阵的输出，对其设置上下左右四个边界，每次都从左界到右界，然后降低上界，再从上界到下界，然后...

题目的主要信息：  一棵n个节点的完全二叉树，其dfs正序遍历（先左后右dfs）序列记录在a数组中 还原这棵树并返回加密后的答案，加密方式为这棵树的所有边的两个端点权值进行异或运算，然后全部相加 完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。  方法一：父到子的边计算 具体做法：对于完全二叉树，我们如果如果知道总节点个数，就会知道左子树和右子树分别有多少节点：这是左子树是满二叉树的情况。这是右子树为满二叉树的情况。 得到了各个子树的个数，根据dfs的遍历顺序，我们就可以得到每个节点在数组a中的下标，对于...

题目的主要信息：  n件带水的衣服，含水量记录在数组a中，干燥的方式有两种： 自然晾干每分钟是晾干1滴水，烘干每分钟是烤干k滴水 每次烘干只能放入一件衣服，烘干与自然晾干同步进行，问最少多少分钟能将衣服全部干燥  方法一：二分法 具体做法：按照题意，数组元素必有，且元素不为0，则一定有湿衣服，那么至少需要花费1分钟。同时，如果所有的衣服都采用自然晾干，这是最慢的方式了，则至多会花费分钟（当时也是这种情况）。我们就可以采用二分法，探讨中满足能够干燥全部衣服的最小值。找这个最小值，我们设置check函数，每次将两个边界的中值放入探讨：遍历数组a，如果，说明这个时间内它可以自然晾干，不需要烘干；如果...

题目的主要信息：  数组中n+1个元素，包括1到n的所有整数 找到重复的那个数字 额外要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1)  方法一：排序法（能通过，时间不符合要求） 具体做法： 利用sort函数对数组排序，遍历数组，相邻两个数相同则找到所求。 class Solution { public: int search(int n, vector<int>& a) { sort(a.begin(), a.end()); //排序 for(int i = 1; i <= n; i++){ //找相邻重复 if(a[i] == a[i ...

题目的主要信息：  一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树 计算从任意点出发并访问完所有节点经过边的权值之和的最小值  分析： 首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，因此两倍权值总和必定可以访问完所有的节点。因此我们要的是从一个点到其他所有节点经过路径权值和最小，我们就要让重复经过的部分最小，即非重复经过的部分最大。我们试想，如果我们从树的直径的一端到另一端开始访问，那我们回溯部分就会少了直径的长度，非重复部分就是树的一点到另一点的最长距离，这样我们就可以求得最...

思路： 题目的主要信息：  给出一个长为n的排列p，即1到n的任意一个组合 一共有m对，每对表示交换排列p中序号为和中的元素，注意是序号而不是下标 m对使用次数与顺序不受限制，求任意次操作之后能得到的字典序最小的排列是什么  方法一：并查集具体做法：可以用并查集的思想来解决，解释一下为何是并查集：假设排列p中两个位置a与b可以交换，如果b与c还可以交换，那么事实上a与c也可以交换，即我们只要找到每个独立的可以交换的集合，单独对集合内的元素排序，然后从小到大只排列集合中这些位置，就可以得到集合中我们要求的字典序最小。处理完每一个集合就是我们的全部字典序最小。 而要将所有单独的元素元素合并成各自的...

思路： 题目的主要信息：  n个节点n-1条边的无向连通图，即一棵无向树 两个节点a与b，其中a在节点1，b在节点x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数，需要包括1号节点在内  方法一：dfs具体做法：我们可以使用两次dfs分别求得树中每个节点到节点1和节点x的距离，然后遍历找到包含节点1的最大距离即是所经过的最多节点数。dfs时我们采用递归，子节点距离等于父节点距离加1，然后递归遍历该节点的所有子节点（不能是父节点）。 class Solution { public: void dfs(int cur, int pre, vector<int>& d...

思路： 题目的主要信息：  一棵以1为根节点的树，节点值为0或者1 最多经过两个值为1的节点的情况下，求有多少条从根达到叶结点的路径  方法一：dfs具体做法：我们首先根据题目给出的边信息构建邻接矩阵，可以访问某个节点的所有相邻节点。然后从根节点开始dfs递归，递归过程不断更新路径中1的数量count变量，只有count小于等于2才能继续遍历下去，维护答案。 class Solution { public: //dfs函数，其中cur是当前节点，pre是这个节点遍历过来的前序节点，count记录经过多少节点值为1 void dfs(int cur, int pre, int count, in...