时间复杂度O(n),空间复杂度O(n)的做法：开辟一个新的数组arr，长度为nums.length+1，遍历nums数组，如果非负且值小于nums的长度，则把arr[nums[i]]置1。然后遍历辅助数组，找到下标不为1的第一个元素即可。 public class Solution { public int minNumberDisappeared (int[] nums) { int []arr = new int [nums.length+1]; for(int i=0;i<nums.length;++i){ if(nu...

遍历数组，由于矩阵从上到下，从右到左有序，因此可以从第0行第m-1列开始遍历，若mat[i][j]>x则左移，否则下移，直到找到目标元素。越界则直接返回空数组。时间复杂度O(m+n)。 public class Solution { public int[] findElement(int[][] mat, int n, int m, int x) { int i=0,j=m-1; while(i>=0&&i<n&&j>=0&&j<m){ if(mat[...

#岛屿数量#解题思路：按行遍历矩阵，遇到‘1’则使用广度优先移除已经参与计数的岛屿。使用递归删除左右上下相邻的grid[i][j]=='1'的格子即可。此方法时间复杂度o(n^2)。 public class Solution { public int solve (char[][] grid) { int count = 0; for(int i=0;i<grid.length;++i){ for(int j =0;j<grid[0].length;++j){ if(grid[i][j...

#输出二叉树的右视图# 分成两步走:1、递归重建二叉树（参考NC12重建二叉树）时间复杂度O(n),空间O(n)2、层序遍历（使用一个last指针记录每一层的最后一个节点，遍历到每层最后一个节点时，将其加入数组即可)时间复杂度O(n),空间O(n)，总时间复杂度O(n),总空间复杂度O(n) public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型一维数组 先序遍历 * @param zhongxu i...

主要是相加的过程。相加后的结果由当前两位和低位的进位组成。进位初始化为0.为了避免链表中操作的复杂性（翻转、对齐等操作还需要增加额外的代码），可以直接用StringBuilder构造两个序列。依次完成翻转、对齐、相加操作，最后把字符串中的序列还原到链表中即可。 public class Solution { public ListNode addInList (ListNode head1, ListNode head2) { StringBuilder s1 = new StringBuilder(); StringBuilder s2 = new S...

寻找两个链表的第一个公共节点，提供两种解法:解法1、使用哈希，把第一个链表的所有节点用哈希保存起来，之后进行第二个链表的扫描，如果第二个链表的某个节点的哈希映射冲突(在map中已经存在)，则该节点为第一个公共节点。空间复杂度O(max(m,n)),事件复杂度O(m+n)(有可能把两个链表都扫描完了)解法2、遍历两个链表，找出较长的那个链表，忽略较长链表的头部多出的一截（多出的一截不可能存在公共节点）然后依次对比节点是否相等，返回第一个节点相等的指针即可。空间复杂度O(1)事件复杂度O(m+n)(两个链表都进行了遍历，找出长度) public class Solution { publi...

注意和最长子序列的区别：最长子序列要求序列可以不连续，子串要求必须连续，中间不能间隔其它字符串。因此，把状态方程改一下即可，dp[i][j]只能来自dp[i-1][j-1],并且用一个max记录当前最长的公共子串。至于最后截取字符串的时候为什么要加个1呢？那是因为公共子串若存在，那么最小值为1，在最后加个1可以免去定义dp数组进行初始化全体赋1的操作。 public class Solution { public String LCS (String str1, String str2) { int len1 = str1.length(); int l...

该题可以使用队列来完成，与普通的层序遍历不一样，之形层序遍历需要新加两个变量，其一是level表示当前层数，其二是last表示当前层次最后一个节点。每次遍历到最后一个节点时，把层数加1，如果层数是奇数，则直接把当前层次的结果加入res，如果层数是偶数，把当前层次的节点序列逆转即可。事件复杂度O(n)遍历了树，空间复杂度O(n) public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { int rear = 0;//队尾 ...

采用插入法：首先找出两个链表哪个作为返回链表的表头（节点值较小的那个），然后设置一个前驱pre，根据值的大小比较进行合适的位置插入即可。这个方法记录了每次插入的前驱，每次进行插入时无需遍历链表，因此时间复杂度为O(n) public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; ListNode head1,p; ListNode head2,q; ...

基于快排：每次划分之后返回该次划分的基准索引，比较索引和K的大小，K大，则往右继续划分，K小，则往右划分。直到求解为止。该算法不会把快排执行完毕，也就是说数组中还有没有排好序的一些元素。 public class Solution { public int findKth(int[] a, int n, int K) { quicksort(a,0,n-1,K); return a[K-1]; } public void quicksort(int[] a, int low,int high , int K){ if(l...

简单直接的版本：把两个树合并到t1。若两个树都存在，直接把和放在t1中，然后再合并子树。合并子树之前进行一下t1的空节点判断即可 import java.util.*; public class Solution { public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if(t1!=null&&t2!=null){ t1.val = t1.val+t2.val; if(t1.left!=null&&t2.left!=null)...

解题思路： 1.判断正负。判断输入的数是正数还是符数，设置一个flag表示符号位，flag=0为正，flag=1为负。 2.划分区间。把input的绝对值划分成小于1和大于1的两个区间，如果input小于1，设置二分的初始下界为0，上界为1.input大于1，则设置下届为0，上界为input。 3.循环求解。设置一个误差d,使d=input/(target*target)-target.如果d绝对值在0到0.1之间，则说明已经找到这个input的立方根了。打印然后退出循环。如果d>0.1说明当前的target偏大，需要把上界调小；如果d<-0.1说明target偏小，需要把下界调大...

这个题目用链表就过于复杂了。可以先用字符串读入输入的序列，然后转化成数组，用快慢指针解决问题即可。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(in.hasNextInt()){ int len = in.nextInt(); StringBuilder s = new StringBu...

递归比较左右子树即可。 import java.util.*; public class Solution { public int maxDepth (TreeNode root) { if(root==null)return 0; if(root.left==null&&root.right==null)return 1; int leftDepth = maxDepth(root.left)+1; int rightDepth = maxDepth(root.right)+1; r...