1，BFS解决 之前讲373，数据结构-6,树的时候，提到过二叉树的广度优先搜索，就是一层一层的访问，像下面这样二叉树的BFS代码如下 public static void treeBFS(TreeNode root) { //如果为空直接返回 if (root == null) return; //队列 Queue<TreeNode> queue = new LinkedList<>(); //首先把根节点加入到队列中 queue.add(root); //如果队列不为空就继续循环 whi...

1，快速排序 快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到他的右边，然后再以此方法对这两部分数据分别进行快速排序。先看一下代码 public int[] MySort(int[] arr) { quickSort(arr, 0, arr.length - 1); return arr; } private void quickSort(int[] array, int start, int end) { if (start < end) { int key =...

1，递归 这题最容易想到的就是递归，啥叫“递归”，也就是下面这张图开个玩笑，我们画个图来看下原理很简单，代码如下 public int maxDepth(TreeNode root) { return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1; } 2，BFS BFS的实现原理就是一层层遍历，统计一下总共有多少层，我们来画个图分析一下。代码如下 public int maxDepth(TreeNode root) { if (root == n...

之前在公众号写过和这题类似的的，有兴趣的也可以看下394，经典的八皇后问题和N皇后问题 1，4皇后问题，递归解决 我们来找规律，先看一下4皇后的问题 比如在下面的4*4的格子里，如果我们在其中一个格子里输入了皇后，那么在这一行这一列和这左右两边的对角线上都不能有皇后。 所以有一种方式就是我们一个个去试 第一行 比如我们在第一行第一列输入了一个皇后 第二行 第二行我们就不能在第一列和第二列输入皇后了，因为有冲突了。但我们可以在第3列输入皇后 第三行 第三行我们发现在任何位置输入都会有冲突。这说明我们之前选择的是错误的，再回到上一步，我们发现第二步不光能选择第3列，而且还能选择第4列，既然选择第3...

1，动态规划解决 定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。 当天交易完之后手里没有股票可能有两种情况，一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润。一种是把当天手里的股票给卖了，既然能卖，说明手里是有股票的，所以这个时候当天没有股票的利润要取前一天手里有股票的利润加上当天股票能卖的价格。这两种情况我们取利润最大的即可，所以可以得到 dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]); 当天交易完之...

1，暴力破解法 就是使用两个for循环，这种效率很差 public int[] twoSum(int[] nums, int target) { int length = nums.length; for (int i = 0; i < length - 1; i++) { for (int j = i + 1; j < length; j++) if (nums[i] + nums[j] == target) return new int[]{i...

1，位运算求解 题中的意思就是从数字[0,n]之间的n+1个数字少了一个，而其他的数字都存在。 如果我们把这个数组添加从0~n的n+1个元素，就变成了数组中只有一个数出现了一次，其他数字都出现了2次，让我们求这个只出现一次的数字。这题使用位运算是最容易解决的，关于位运算有下面几个规律 1^1=0; 1^0=1; 0^1=1; 0^0=0; 也就说0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到 a^a=0；自己和自己异或等于0 a^0=a；任何数字和0异或还等于他自己 a^b^c=a^c^b；异或运算具有交换律 有了这3个规律，这题就很容易解了，我们只需要把所有的...

1，反转后半部分链表 这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。 但这题判断的是链表，因为这里是单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转（关于链表的反转可以看下432，剑指 Offer-反转链表的3种方式），最后再用后半部分反转的链表和前半部分一个个比较即可。这里以示例2为例画个图看一下。 最后再来看下代码 pu...

1，递归的写法 这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的我们来分析一下： 当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1 当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2 当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)； 同理当等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。所以如果我们求上到n阶有多少种，代码很简单，直接递归就行 public static int JumpFloor(int n) {...