跳台阶：最直观的想法是，经典斐波拉契数列变形，递推公式为f(n)=f(n-1)+f(n-2)。接下来分别使用四种方法实现：递归、记忆化搜索、动态规划、滚动数组。其整体思路为：跳一级台阶一种跳法，跳两级台阶两种跳法，跳n级台阶可以是n-1级台阶再跳一级或者是n-2级台阶再跳两级。 int jumpFloor(int number) { // 跳一级台阶一种跳法 if(number==1) return 1; // 跳两级台阶两种跳法 if(number==2) return 2; // 跳n级台阶 可以是n-1级台阶再跳一级 也可以是n-2级台阶再跳两级 return jumpFloor(num...

二叉搜索树的最近公共祖先：最直观的想法是，二叉搜索树的特点是左子树数值<中间节点数值<右子树数值，那么我们可以根据这一特性来遍历二叉搜索树，分别得到从根节点到节点p的路径数组pathp以及从根节点到节点q的路径数组pathq，然后遍历两个数组得到最后一个相同的节点值，其即为二叉搜索树的最近公共祖先。遍历路径具体实现方法如下：首先将当前值加入路径数组，然后比较当前值和目标值，如果当前值大于目标值，则在当前节点的左子树寻找目标值，反之如果当前值小于目标值，则在当前节点的右子树寻找目标值，当找到当前目标值即返回，注意，是先加入再返回这样的顺序喔！ vector<int> pa...

把字符串转换成整数(atoi)：最直观的想法是，从字符串高位向低位遍历，然后逐个取字符串元素，先将字符转换为整型，再利用数位关系将其转换为数值。在纯数字的情况下，当然可以像这样做，但是本题中含有非法字符，且明确说明，在若干空格后，可能会存在符号，接着出现的一连串数字才是转换为数值的重要部分，如果后面再出现非法字符需要被舍弃。也就是说，字符串1234hello转换为数字则为1234，而字符串hello1234转换为数字是为0，即其是非法的，那么我们就不能从后向前遍历字符串，而应该从前向后遍历字符串。(试错)idea：使用index标记字符串下标，其初始化为0；使用flag标记正负数，其true表...

构建乘积数组：最直观的想法是，将数组a中的所有元素进行相乘得到multiply，然后数组b中的每一个元素则等于multiply除以对应下标的a元素。但是存在一个问题，即数组元素可能为0，可能一个0也可能多个0，所以在计算乘积时需要进行单独计算，在处理元素时也需要进行单独处理。 vector<int> multiply(const vector<int>& A) { // multiply_nozero表示A数组所有非零元素的乘积 long long int multiply_nozero=1; // zero_num表示0元素的个数 避免求B[i]时有多个0 int z...

不用加减乘除做加法：最直观的想法是，一般这种题目都是考察的位运算。回顾最初学习的竖式加法，其加的是数值十进制的每一位，其实位运算也类似，只不过区别在于其加的是数值二进制的每一位。如果依次是一位一位的加，其有些慢，但是不变的是，异或运算产生当前位，与运算产生进位，只不过进位需要左移一位再参加运算，这样就可以将一位一位的加转换为整体加。具体实现方法如下：首先将num1作为当前位和，将num2作为进位和，当进位不为0时进行运算，将num1与num2的异或运算结果sum作为新的当前位和，将num1与num2的与运算结果add左移一位作为新的进位和，直至进位和num2等于0结束，最后返回当前位和num1...

求1+2+3+...+n：最直观的想法是，循环或者递归。但是，题目中明确说了，不能使用关键字乘除法、for、while、if、else、switch、case等及条件判断语句（A?B:C），所以我们只能考虑其他方法了。在考虑其他方法时，我们先从原来的解法出发考虑，然后再看看原来的解法中我们可以使用什么方法来替换那些被禁用的方法。下面以原始的递归解法出发。 int Sum_Solution(int n) { if(n==1) return 1; return n+Sum_Solution(n-1); } idea：我们可以看到，上述递归解法中，只有一个被禁关键字if，那么可以有什么方法来替换该被...

买卖股票的最好时机(一)：最直观的想法是，动态规划。交易一次*是否持股一共有两种状态，分别使用dp[i][0]表示第i天持股，使用dp[i][1]表示第i天不持股，然后根据常识对第一天的两种状态进行初始化，接着从第二天开始遍历，分别更新递推公式，其中第i天持股可能是第i-1天就持股或者第i-1天不持股而第i天买入，由于只能买卖一次，故此处为0而不是dp[i-1][1]，第i-1天不持股可能是第i-1天就不持股或者第i-1天持股而第i-1天卖出，最后返回第n-1天不持股状态即为最大收益。 int maxProfit(vector<int>& prices) { int n=price...

孩子们的游戏(圆圈中最后剩下的数)：最直观的想法是，约瑟夫环。首先创建一个bool类型的大小为n的数组people用于存储当前序号是否出列，初始均未出列，故将其初始化为false，然后使用一个变量i表示当前的序号，其范围为0~n-1，初始为-1，使用一个变量s表示当前这一轮报数中报了几个数，其范围为0~m，初始为0，使用一个变量num表示出列人数，其范围为0~n，初始为0，使用一个变量res保存结果序号。首先采用环形方式统计当前序号，然后如果当前序号未出列则统计报数，接着如果当前这一轮已经报数m个，则标记出列以及出列个数并且重置报数s为0，最后如果当前出列人数等于n则记录结果序号并且退出循环，...

扑克牌顺子：最直观的想法是，首先想想顺子的特点是什么。首先顺子中不能出现相同的元素，其次顺子中各元素相差值为1，如果相差值大于1，可以使用万能牌0进行补齐，同时要考虑元素之间相差值过大从而导致万能牌无法补齐的情况。具体做法如下：首先对数组进行排序，然后统计数组中0出现的次数，即可用的万能牌张数，接着遍历剩余非0元素，如果剩余元素出现相等情况，则直接返回false，即不能构成顺子，反之统计元素之间的差值，注意，此处的差值是大于正常差值1的差值，最后根据万能牌的张数与元素之间的差值比较来判断返回true还是false。 bool IsContinuous( vector<int> nu...

滑动窗口的最大值：最直观的想法是，两层for循环，外层i表示每次窗口的起始位置，内层j表示每次窗口的结束位置，遍历窗口内的每一个元素，然后取窗口内的最大值，并加入到结果数组中。注意，当数组为空时或者滑动窗口值大于数组长度，要返回空数组。(牛客这个暴力方法居然过啦) vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> res; // 数组为空 或者 滑动窗口值大于数组长度 if(num.size()==0||size>num.size()) r...

和为S的两个数字：最直观的想法是，两层for循环，分别表示两个数，如果两个数之和等于S，则将其加入结果数组res，退出循环并返回。(超时) vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> res; bool flag=false; for(int i=0;i<array.size();i++) { for(int j=i+1;j<array.size();j++) { if(array[i]+array[j]==sum) { res.push_back...

数组中只出现一次的两个数字：最直观的想法是，使用res表示结果，使用umap存储元素以及元素出现的次数，然后遍历array数组，记录各元素以及各元素出现的次数，接着遍历umap，找到只出现过一次的元素，并将其加入到res中，最后由于res中只有两个元素，直接判断排序即可。 vector<int> FindNumsAppearOnce(vector<int>& array) { vector<int> res; // 元素 元素出现的次数 unordered_map<int,int> umap; for(int i=0;i<array.siz...

二叉树的深度：最直观的想法是，深度指的是从根节点到叶子节点的垂直距离，其使用的是前序遍历，而高度指的是从叶子节点到根节点的垂直距离，其使用的是后序遍历，那么可以将求二叉树的深度转换为求二叉树的高度，根节点的高度等于左子树与右子树的最大高度加一。 // 将二叉树的深度转换为二叉树的高度 高度采用后序遍历 根节点的高度等于左子树高度与右子树高度最大值加一 int PostOrder(TreeNode* cur) { if(cur==nullptr) return 0; int left=PostOrder(cur->left); int right=PostOrder(cur->rig...

二叉搜索树的第k个节点：最直观的想法是，中序遍历二叉搜索树，这样得到的遍历结果是有序的，使用一个变量num表示当前距离第k个节点还剩几个节点，其初始为k，使用一个变量value表示第k个节点值，其初始为-1。在中序遍历的过程中，将num减一，并且判断当前num是否等于0，如果是则返回当前节点对应的值，即value等于cur->val，最后返回value即可。 int num=0; int value=-1; void InOrder(TreeNode* cur) { // 空节点返回 if(cur==nullptr) return; InOrder(cur->left); // 中...