不用加减乘除做加法：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。考点：进制转化  思路： & 按位与运算：相同位的两个数字都为1，则为1；若有一个不为1，则为0。两个数相与，并左移一位：相当于求得进位  如：1&1=1 将1左移一位变成了10，相当于拿到了进位。 ^ 按位异或运算：相同位置不同则为1，相同则为0。相当于每一位相加，而不考虑进位。  第一步 异或——无进位相加得result1 (a^b) 第二步 与+左移一位——求得进位result2 （a&b）<<1 第三步 result = result1 + result...

和1 与 为1，则为1，否则为0，因此用 与 操作来判断是否为1 思路1：首先应该想到的是，先判断最右边的是否为1，然后整体右移一位，这样原来右边第二个数就被移动到最右边了，再判断；反复这样，就可以得到1的个数。关键是这样的想法，在进行负数的个数统计时，会有问题，因为负数的二进制首位为1，移位后，为了保证还是负数，计算机会在首位再补1，这样不管你怎么移动，首位永远是1，陷入死循环。因此需要转变思路。 public class Solution { public int NumberOf1(int n) { int count = 0; while (n != 0) { if ((n &...

首先搞清楚意思，本题的重点在于树是否平衡，左右子树的深度不超过1。而不关注于是否将其排序，成为平衡二叉搜索树。因此在只考虑平衡的情况下解题。 思路1：（由二叉树的深度的解法转换过来（55-1题就是求二叉树深度））在使用递归求的深度后，其实可以在递归中，直接判断左右子树的差值。这时候就相当于多一个变量。 public class Solution { boolean isBalanced=true;//用于判断的变量 public boolean IsBalanced_Solution(TreeNode root) { TreeDepth(root); return isBalanced; } ...

思路1：递归写法构思：传入某节点，调用该方法，返回的应该是以传入节点为根节点的树的深度，而树的深度，肯定和左右子树深度有关，所以进入这个方法后，就包含了左右子树的深度（而要得到左右子树的深度，肯定又是以左右子节点为根节点，再次调用该方法深度获取的，因此此时进行递归），并且还有由一个左右深度比较的过程，然后取较大值，这个较大值就是该节点左右子树深度较深的值，以该值+1作为返回值，就是该节点的深度。  因此，方法名TreeDepth，在方法中，申明两个变量分别记录得到的左右子树深度。 int left = node.TreeDpth(Root.left);// 显然需要把当前节点的左节点传入，进行...

二叉树的镜像（翻转二叉树） 解法1：最容易想到的做法，递归调用。根据写法的不同，又可以分为，遍历到某个节点时，先调用递归，再交换该节点的左右节点，或者是遍历到某个节点时，先交换左右节点，再进行递归调用（这一种方式是可行的，但理解起来稍微困难一点）。 public class Solution { public void Mirror(TreeNode root) { if (root == null) { return ; } TreeNode temp = root.left; root.left = root.right; root.right = temp; Mirror(root.le...

一共n阶台阶，而青蛙的一步是从1到n都可以选择。 思路：虽然解的结果不是斐波那契数列，但是需要能观察出：青蛙第一次可以跳1级，则还剩n - 1级台阶，即F(n - 1)青蛙第一次可以跳2级，则还剩n - 2级台阶，即F(n - 2)...青蛙第一次可以跳n - 1级，则还剩1级台阶，即F(1)青蛙第一次可以跳n级，即1种跳法则F(n) = F(n - 1) + F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1而F(n-1) = F(n - 2) + F(n - 3) + F(n - 4) + F(n - 5) + ... + F(1) + 1可以得...

将题目等价到青蛙跳台阶，类似于斐波那契数列。动态规划的两种写法 public class Solution { public int RectCover(int target) { if(target<1) return 0; if(target ==1||target ==2) return target; int first =1; int second =2; int result = 0; for(int i=3;i<=target;i++){ result = first + second; first = second; second = result; } retur...

题目描述现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。  有一道跳台阶的与本题相似，只是初始条件不同。(关于青蛙跳台阶那题，我在牛客先做的，因此那个题解的思考过程可能比本篇详细)斐波那契数列的初始条件是f(0)=0,f(1)=1f(2)=f(0) + f(1) 从角标2就可以开始递推，而跳台阶（只能跳1阶或2阶）的方式，递推是从f(3)开始，因此除了初始条件不同，思路完全可以借鉴   思路1：暴力解法，标记出初始条件后，就可以进行递归调用了。 public class Solution { public int Fibonacci(int n) { if (n ...

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。提供3种思路及4种解法  思路1：递归暴力解法n级有f(n) 种方法，要么跳一步，要么跳两步。假如此时跳一步，那么剩余n-1就有f(n-1) 种方法，如果跳两步，那么剩余n-2就有f(n-2) 种方法。则f(n) = f(n-1) + f(n-2)。再考虑n=1和n=2的特殊情况 f(1) = 1，f(2) = 2。 public class Solution { public int JumpFloor(int target) { if (target < 1)...

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。思路：栈是先进后出，队列是先进先出。想象我们一直向左边口袋装东西（并且只能向左边装），当我们左边口袋装了很多东西，而右边口袋是空的，想取左边口袋最下面的的东西时，可以把东西全部挪到右边口袋，这样左口袋最下边的东西就暴露在右边口袋最上面，可以直接取走了。这样就实现了先进先出。（pop取东西时，此时左边口袋已空，从右边口袋表面取）值得注意的是：再次取东西时，直接从右边口袋取，因为顺序已经换过来了，和当初压栈的顺序一样，所以此时再压栈放东西时，直接装左边口袋，直到右边口袋取完了，再想取时，就要重复倒一次，这样...

题目描述：连续子数组的最大和（连续最大公共子序列） 或许其实只有4个解法（看最后总结）思路1：复杂度最高也是最直观的，求得所有的子序列，进行比较。时间复杂度O(n^3)思路2：对第一个算法进行改进。有些重复计算的值，避免再次计算，因此时间复杂度O(n^2)思路3：使用分治的思想，同时也使用了递归。时间复杂度O(n*logn)思路4：动态规划，时间复杂度O(n)思路5：叫不出名字的解法，有的称扫描法？而且时间复杂度也仅为O(n)思路1实现代码： public class Solution { public int FindGreatestSumOfSubArray(int[] array) { ...

题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0] * A[1] * ... * A[i-1] * A[i+1] *... * A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）背景：B数组有n个值，每个值要进行一次连乘，因此正常连乘的话时间复杂度为O(n^2)，效率非常低。考虑到计算每个B[i]时都会有重复，思考B[i]之间的联系，找出规律，提高效率。 PS:盗张图思路：B[i]的左边和...

题目：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。先给自己普及大佬们口中的短路求值是什么。作为"&&"和"||"操作符的操作数表达式，这些表达式在进行求值时，只要最终的结果已经可以确定是真或假，求值过程便告终止，这称之为短路求值（short-circuit evaluation）。假如expr1和expr2都是表达式，并且expr1的值为0，在下面这个逻辑表达式的求值过程中：  expr1 && expr2 expr2将不会进行求值，因为整个逻辑表达式的值已经可以确...