题意分析  这个题目题目意思很简洁，就是让我们求出一个数的开根号之后的数据，向下进行取整。  思路分析 解法一 二分  我们发现，最后的答案具有单调性，当我们求出某一个数字为mid的时候，我们可以和给出的数字进行比较，判断这个数字是大了还是小了，从而移动我们的边界。这样通过左右边界的移动我们最后就可以不断逼近最后的终点了。     代码如下, 二分的时间复杂度为O(logn) 只开了几个变量，空间复杂度为O(1)   class Solution { public: /** * * @param x int整型 * @return int整型 */ int sqrt(int x) { // w...

题意分析  首先，给我们一个数组，需要我们将这个数组进行一个排列，然后对数组的所有的数字按照排列的顺序进行拼接，拼接成字符串，问我们得到的最小的字符串。    思路分析 解法一 全排列  既然说了存在一种排列的方式使得最后的结果最小，那么就可以使用全排列进行求解，我们利用全排列来枚举所有的情况，然后我们对每种排列情况组成的字符串进行存储，最后对所有存储的字符串进行排序，选出最小的字符串就行了。对于全排列，C++已经有了现成的库函数可以调用，当然也可以自己利用DFS实现全排列。这里我就偷一点懒。同时要注意的是对动态数组的全排列需要我们先对动态数组进行升序排列。这样才会枚举出所有的情况。 代码如下...

题意分析  给出1-n之间的数字，我们需要找出所有的数里面的1个数位的个数有多少。  思路分析 解法一 暴力求解  直接暴力写法，从1-n开始进行遍历，我们对每个数进行数位的拆解，然后统计1的个数就行了。 代码如下  我们从1-n进行遍历直接判断，时间复杂度为O(n) 我们的代码只开了少部分变量存储值，空间复杂度为(1)   class Solution { public: int getsum(int x){ int sum=0; // 对每个数字进行数位的拆解，统计其中的1的个数 while(x){ // 进行数位的拆解 if(x%10==1){ sum++; } x/=10; } ret...

题意分析  需要我们使用两个栈来模拟队列的操作，比如入队和出队的操作。 前置知识，首先，我们来介绍一下栈和队列。 栈是一个先进后出的数据结构。 队列是一个先进先出的数据结构。     思路分析 写法一 C++版  现在，题目要我们用两个栈来模拟一个队列的入队和出队的操作。那么我们可以先看一下一个队列想要入队，那么就可以需要将这个数字保存到队伍的尾部。我们可以这样来看，当我们出队的时候，我们需要将目前队伍中最早入队的弹出去。我们规定两个栈，一个stack1,另一个是stack2,当我们入队的时候，我们先将数字正常放入我们的stack1里面，然后当我们出队的时候，那么此时我们的stack1的最下面...

题意分析  给出一个二叉树的先序遍历的序列和中序遍历的序列，需要我们对重建这棵二叉树。返回这个二叉树的根节点即可。 前置知识，我们首先需要知道什么是先序，后序和中序遍历。对于一个二叉树，我们按照根，左节点，右节点的顺序遍历就是先序遍历。按照左边节点，中间节点和右边节点的顺序就是后序遍历，按照左节点，右边节点和中间节点的序列遍历就是中序遍历。 如下图   解法分析 解法一   我们可以利用先需遍历和中序遍历的顺序，我们先找出这个二叉树的中序遍历序列里面中间节点，也可以说是一个根节点。然后，我么就可以知道这个二叉树的左右子树了，然后，我们先对左右子树进行重建，重建之后就会返回我们的得到我们的左右结...

思路分析  给出一个链表，需要我们从尾部到头部打印出这个链表的所有的节点的权值。    思路分析 解法一 直接遍历  题目很简单，很朴素。我们直接从这个链表的头节点开始进行遍历。然后我们记录下这个数组的每个节点的信息。最后反转一下整个数组，返回即可。 代码如下  需要直接遍历长度为n的链表的所有的结点，时间复杂度为O(n） 需要存储长度为n的链表的所有的结点，空间复杂度为O(n)   /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * }...

题意分析  这个题目的意思很简单，就是将一个字符串里面的空白字符替换成%20    解法分析 解法一 C++版  我们直接使用C++的string进行处理。我们发现C++里面有一个string还是很好用的，它重载了+=运算符。我们可以直接通过遍历整个字符串进行处理。 代码如下  我们需要对长度为n的字符串遍历一次，时间复杂度为O(n), 需要存储长度为n的字符串，空间复杂度为O(n)   class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return s...

题意分析  给我们一个二维数组，这个二维数组从上到下，从左到右都是递增的，需要我们判断这个二维数组中是否存在一个给定的数字。如果存在，那么直接返回true，否则返回false  思路分析 思路一 暴力法  我们可以对这个二维数组直接进行遍历，然后我们逐个进行判断是否存在，如果存在直接返回true，最后遍历完整个数组都没有退出，那么直接返回false。 代码如下  需要对二维数组的每个元素进行遍历，时间复杂度为O(n^2) 存储一个二维数组，空间复杂度为O(n^2)   class Solution { public: bool Find(int target, vector<vector...

题意分析  这个题目我们需要计算出一棵二叉树上面的所有的路径当中，找出路径的和最大的那个值。 这个题目的难点就是中途可能会存在权值为负数的情况，还有权值为0的情况不好处理。 这个题目还是有点意思的，我们可以用一个类似与树形DP的方法进行求解。 前缀知识，树形DP，树形DP就是我们假设我们知道了一棵二叉树的左右的子节点的最优值，然后我们可以传递到这个节点本身，最终传递到整棵树上面。  思路分析 解法一 DFS+树形DP  对于树的题目，很大程度上都可以使用搜索进行求解。这个题目也是一样的，使用一个先序遍历的思想，当我们进行递归的时候，我们先向左右子节点进行递归，求出左右子树的最优的情况返回，然后...

题目意思  这个题目的意思和JZ24的题目几乎一模一样，就是对于从根节点到叶子节点的所组成的路径中。选择路径中的所有的权值之和等于给定的某一个数的路径。并且将他们返回。 前置知识。这个题目我用的分别是DFS和BFS进行处理的。其中DFS用了一个回溯的方法进行处理。回溯法是一个DFS的技巧，就是当我们DFS遍历某一个子节点的时候，我们还需要回来遍历另一个子节点，为了消除之前遍历的时候的影响，我们需要将状态进行复原。结合下面的图理解回溯。    思路分析  好了我们知道了回溯和搜索的思想之后，这个题目就可以开始写了。  解法一 DFS  我们从根节点向下进行搜索。同时我们开一个二维的动态数组记录我...

题意分析  这个题目就是给我们一个数组，数组中的每个数字代表第i天某支股票的价格，我们需要选择一天买入，选择一天卖出。最后使我们的收益最大化。 题目难度：简单  思路分析 解法一 暴力枚举  这个思路就是对于每一天的股票的价格，我们假设这天我们卖出这个股票，那么我们可以枚举这天之前的股票价格作为买入的价格，然后用一个变量维护最大的收益就行了。 代码如下，时间复杂度为O(n^2)，空间复杂度是O(1)  class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vecto...

题意分析  这个题目就是要我们找出从根结点到叶子结点的所有的数字，然后我们需要将这些数字拼接成一个数，将所有的数相加起来就是我们的答案了。 前置知识，DFS。对于DFS我们可以想象成一棵树，我们需要不断递归到树的最下面的叶子节点。  思路分析 思路一 DFS  我们对整棵二叉树进行递归操作，同时我们将当前位置拼接成的数字记录下来，直到遇到根节点之后就累加到答案里面。这里判断叶子节点的时候需要同时判断这个节点没有左右叶子节点。如果这棵树很高的话，最后计算出来的结果很可能会需要高精度来写。但是我们发现返回的参数是int类型的。所以就没有必要了。 如下图  代码如下  在进行DFS的时候可能存在遍历...

题意分析  这个题目是NC3的弱化版，这个题目不需要我们求出环的入口结点，只需要我们判断是否存在环就可以。  思路分析  所以我们可以按照NC3那题的思路来写。  思路一 哈希处理  我们首先将所有的结点存入一个哈希表里面，然后我们需要遍历整个链表，如果存在相同的节点说明存在环，返回true即可。 代码如下  需要对整个链表进行遍历，时间复杂度为O(n) 用哈希方法存储整个链表的所有的结点的情况，空间复杂度为O(n)   /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *nex...

题意分析  这个题目给我们一个经过特殊处理的链表，这个链表分为两段，每一段包含一个链表的非环的部分和成环的部分。大多数人可能一开始看样例的时候会感觉不是很理解。其实你就只要知道它给你一个链表，这个链表中如果成环的话就说明这个链表里面存在相同的结点。也就是转化为问你给出一个链表，需要你判断这个链表里面是否存在相同的结点。返回这个相同的结点就行了。如果不存在环，那么就返回一个空指针。 样例可以结合这个图进行理解     前置知识，这个题目我们可以使用哈希算法进行处理，我们可以一边遍历整个链表，一边将所有的结点进行哈希处理。对于C++，有一个实现好的STL容器就是map，我们第一种写法就是利用这个来...