思路：最大路径和的产生：左子树的单路径、右子树的单路径、左右子树的单路径和根节点值这三者之一。因此，先用两个变量存储左右子树的单路径（单路径就是只有从下到上的一条路径，没有左右）的最大和，分别取最大值即可。需要注意的是，取某条单路径的最大和的时候，如果某子树单路径之和加上根节点的值比根节点小，那么该子树的单路径之和直接舍弃。 class Solution { public: int max_value = -32768; int maxPathSum(TreeNode* root) { return max(max_value,func(root)); } int func(TreeNode*...

C++：顺便回顾一下快速排序。最大乘积：负负得正再乘以最大，或者三个最大的数相乘。最大的数可能是这两者的一个。那么就好办了，排序一上就完成了。 class Solution { public: /** * 最大乘积 * @param A int整型一维数组 * @param ALen int A数组长度 * @return long长整型 */ long long solve(int* A, int ALen) { // write code here quickSort(A, ALen, 0, ALen-1); return max((long long)A[0]*A[1]*A[ALen-1...

儿童节那就刷两道easy开摆！

5.5月通过官网投递。   5.7号约了10号一面。   一面：   自我介绍   1、进程线程区别？   2、堆栈区别？   3、有遇到过栈上分配吗？   4、为什么出现了虚拟内存？   5、缓存置换算法？   6、事务ACID？   7、redis原理？   8、redis置换算法有哪些？   9、tcp三次握手四次握手介绍一下？   10、tcp粘包问题了解吗？   11、粘包的根本原因是什么？udp会出现这个问题吗？   12、说一说流量控制和拥塞控制？   13、熟悉linux编程吗？   14、docker和虚拟机有什么区别？   15、说说你比较熟悉的设计模式？   16、手撕：...

base北京，教育板块。   5月16日牛客通过内推投递，字节约面是真的快呢。   5.19一面   自我介绍   1、HashMap原理，是否安全？   2、HashMap为什么不安全？   3、高版本的HashMap后续做了哪些更改？  4、HTTPS的过程？中间人劫持了会怎么样？  5、MySql索引是什么？   6、介绍一下索引有哪些类型？   7、MySql索引底层是用的什么数据结构？   8、MySql查询数据怎么优化？   9、spring循环依赖是怎么解决？   10、spring三级缓存的数据结构是什么？   11、linux中软链接和硬链接的区别？   12、手撕代码：链表...

思路：本题乍一看可以用层序遍历？但是涉及到空节点的问题，层序遍历存在诸多麻烦，因此可以利用二叉树的特性：左叶子节点的序号为根节点的两倍，右叶子节点的序号为根节点的2倍加1.利用这个性质，我们把每一层的最左节点的序号加入一个map中（这个动作只进行一次即可），以后每次遍历到该层的时候，刷新该层的最大节点数即可。 public class Solution { int res = 0; Map<Integer, Integer> levelRecord = new HashMap<>(); public int widthOfBinaryTree (TreeNode roo...

思路：dfs。每次遇到岛屿就把岛屿清零，用size记住清除的次数即可。 public class Solution { int maxSize; int size; public int maxAreaIsland (int[][] grid) { for(int i=0;i<grid.length;++i) for(int j=0;j<grid[0].length;++j){ if(grid[i][j]==1){ clear(grid,i,j); } size = 0; } return maxSize; } public void clear(int[][]grid,int i...

思路：二进制不同位，直接采用异或，然后采用循环右移计算1的个数即可。 Java: public class Solution { public int countBitDiff (int m, int n) { int c = m^n; int count = 0; while(c != 0){ count += c & 1; c = c >> 1; } return count; } }  C++: class Solution { public: int countBitDiff(int m, int n) { int count = 0; m = m ^ n; for...

既然题目要求时间复杂度为O(n^2),那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，那么不可能是重复子串，因此，每次把j的下标增加2。由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，验证很简单，就是从中间截断，看前后两个串是否equals，如果是重复子串，则直接更新最大长度即可。 public class Solution { public int solve (String a) { int maxlen = 0; for(int i=0;i<a.length();i++){ for(int j=...

这个题看起来可以使用“合并区间”的解法，但题目已经告知了输入的数组是已经按start字段升序，那么我们仅需要找到插入点，然后向后合并即可。时间复杂度O(n)，空间复杂度O(n)(采用了list)。 public class Solution { public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) { List<Interval> list = new LinkedList<>(); boolean flag = false;//判断目标区间是否已经成功加入 for(i...

这个题的思路是和根据中前遍历重建二叉树类似的。因为后续遍历的最后一个元素总是根节点，那么只需要先找到后序遍历中的根节点，再把数组分为左右两个区间就能找到左子树与右子树。 public class Solution { public TreeNode buildTree (int[] inorder, int[] postorder) { if(postorder.length==0)return null; TreeNode root = new TreeNode(postorder[postorder.length-1]); for(int i=0;i<inorder.length;+...

分割子串，放入set.如果set中已经存在该子串，那么加入返回列表。再遍历set，找到最先出现的串即可。 public class Solution { Set<String> set =new LinkedHashSet<>(); public String[] repeatedDNA (String DNA) { List<String> list = new LinkedList<>(); while(DNA.length()>=10){ if(check(DNA.substring(0,10))){ if(set.contains(...

分享一个牛客网笔试的坑。上周在牛客上随便参加了一场笔试，10单选，10多选，1简答，3编程。编程题全a了，最后面试官那边给出的评价是，某些题可能用了投机方法，导致虽然ac了但是基本没分。（判断整数是否回文吧这个题？面试官反馈说，牛客判分，使用StringBuilder.reverse()这种，得分极低...然而正常用new char[]双指针的，得分就很正常，第二题是个给个数组和目标值，让求和为目标值的子序列，用递归居然都是满分。。。）牛客还有这种隐藏规则吗。。。各位以后长个心眼？😥😥😥

  为什么腾讯二面都结束了(面试过程很愉快，一面60min,二面45min，两次面试都写题了），官网还显示在初试?😥