这个题和剑指 Offer 上旋转数组的题有点像，但是不一样，因为剑指 offer 明确了是一个递增排序的数组，如果我们明确了递增的话就能取到 mid，然后通过 mid 与 left 以及 right 的相对大小来判断接下来的走向，但是现在的问题是这个题没有明确。首先分析本题要考察什么：数据结构数组，算法的是查找而且是有序数组查找。因此我们要利用这个有序，那么最合适也最常考察的就是二分了。也就是说本题本质上是考察的二分查找。二分查找最最主要的条件是1 明确数组有序，这决定了 mid 的含义2 明确数组是升序还是降序，这决定了 mid 接下来的走向.只要构造出一个有序的数组，我们就能用二分了，那么...

这算不算二分 public int sqrt (int x) { // write code here if(x==0 || x==1){ return x; } int mid=x/2+1; int res=0; for(int i=1;i<=mid;i++){ if(i*i>x && (i-1)*(i-1)<=x){ res=i-1;//向下取整 break; } } return res; }

先来分析：考察的数据结构是二叉树，考察的算法是二叉树的深度遍历。假设当前节点A，A到o1,o2的距离最小的条件限制有1 A 均能到o1,o22 A 到 o1，o2 的路程和最小所以思路变成先遍历外面的大树，通过遍历然后针对每一个节点进行可达性以及路程的计算，迭代更新路程最小的节点，其实对于树的遍历，相当于是我们在做 for 循环，然后针对循环到的每一个元素，再进行深入的探查，这是二叉树这类题的常用手段，那么如何进行探查尼？还是dfs.所以一般二叉树都要用两个“循环”，一次是以最顶上的根节点为开始的“循环”，一次是以大循环遍历到的点，再以这个点为根节点进行循环的子循环。 TreeNode[] r...

还记得前两天第一次做这个的时候真是打击了自己，没有什么好办法主要是考虑边界问题，顺着打，避免重复就可以了。 public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> res=new ArrayList<>(); if(matrix==null || matrix.length==0){ return res; } int m=matrix.length; int n=matrix[0].len...

没看清题，n和m 的范围是6次方以内还涉及不到大数，因为这两个相加最多结果就是一个7次方。但是利用大数相加的思路是没有问题的。先把链表转换成字符串，然后转化为大数相加的就可以了 public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // write ...

题刷多了就有很多相似的问题出现了，这种最长的系列都可以作为一个专题了1 最大连续子数组和2 最长无重复子串3 最长公共子串 几乎都是一样的，涉及到两个两个递推，一个是用来更新另一个的。主要是临界条件不好找，基于类似的思想，子串在清零的时候，不能立马清零，因为可能会出现新的子串。 这种比较尬的测试样例就明白了：acdem712345678xxx 与 m71a12345678c public String LCS (String str1, String str2) { // write code here if(str1==null || str2==null){ ...

分析：考察数据结构二叉树，考察的算法是 bfs。bfs 的核心就是用队列实现，主要常见的几种题型：1 什么要求都没有，只要求层序遍历（只要一个队列实现）2 要求按层打印（两个队列）3 要求之字形打印（两个队列）4 要求倒序打印，，，各种姿势打印。。 不外乎就是要记住每一层，只要理解了层序遍历本质：先进先出，队列空一层就结束了。各种题型就是手到擒来了。整个程序的可读性很强，就不写注释了。。。。 public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) { // write code...

0 总结 考察数组，没有什么好的办法，存粹就是暴力的解法，但是前提是要逆序一下，这样就好了很多，不逆序的话可以在短的前面补0也是一样的。但是硬用字符数组的话要判断谁先结束的问题，于是可以巧妙地转化成整型数组，整型数组默认值是0，0加上任何数不产生什么其他特殊意义，所以我们就不用判断谁先结束谁后结束了。至于要不要多+1，整上了也行，不弄的话要在最后一位判断，反正就算是最后一位相加有进位，那个进位肯定是1. 1 自己写的一版（通过） public String solve(String s,String t){ String str1=s; String str2=t; i...

0 总结 考察数组，没有什么好的办法，存粹就是暴力的解法，但是前提是要逆序一下，这样就好了很多，不逆序的话可以在短的前面补0也是一样的。但是硬用字符数组的话要判断谁先结束的问题，于是可以巧妙地转化成整型数组，整型数组默认值是0，0加上任何数不产生什么其他特殊意义，所以我们就不用判断谁先结束谁后结束了。至于要不要多+1，整上了也行，不弄的话要在最后一位判断，反正就算是最后一位相加有进位，那个进位肯定是1. 1 自己写的一版（通过） public String solve(String s,String t){ String str1=s; String str2=t; i...

倒数第n个节点其实就是顺数第 count-n+1 个节点，但是我们要删除这个节点就先要走到 第 count-n 个节点上去，p.next=p.next.next 就成功了。但是要注意的时候有可能 n == count 也就是说要删除链表头节点的时候要注意 public ListNode removeNthFromEnd (ListNode head, int n) { // write code here if(head==null){ return null; } ListNode p=head; int count=0; wh...

这是之前的最大连续子数组和的变种，代码差不多。只不过是递推公式发生了变化，不再是直接清零就好了，反而是要拿到前面重复数字的后一位开始继续 public int maxLength (int[] arr) { // write code here if(arr==null || arr.length==0){ return -1; } HashMap<Integer,Integer> map=new HashMap<>(); int dp[]=new int [arr.length]; for(int i...

这中类型的题主要是考察 图搜索，一般都是用类似 dfs,bfs 的尝试算法，其实某种程度上算是穷举法，这个比直接暴力可能要节约一点时间，但是dfs的递归调用栈内存也是不好扛的。，，虽然一开始我是想用 bfs 的，但是发现还要用个数据结构来存每一层的点的坐标。所以写成 dfs，，，，可能有点晕，，，把 bfs 改成 dfs 就好理解了。https://blog.csdn.net/yinchaoji_/article/details/51264837 贴一个4年前的我的一篇博文（chaode）....,现在来理解比当时理解肯定要深刻些，，， public int movingCount(...

原来真的有，，，，把刚刚之字形打印的代码改一个地方就可以了，就是不用翻转了 public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); LinkedList<TreeNode> list1=new LinkedList<>(); LinkedList<TreeN...

本题考查树的 BFS.BFS就是一层一层的遍历，我们用队列实现。一个队列的话我们没有层次的限制，直到这个队列为空，说明我们遍历完了。但是现在我们要记录下每一层的节点。相当于问题转为给定一棵二叉树，麻烦打印一下第n层的所有节点。所以为了让每一层都有明显的分开，我们用两个队列来实现互相保存。 之字形的话无非就是要将其中一个队列反转一下顺序。 可读性来了： public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> r...