O(N), O(N) 只需要借助新数组，遍历两次，分别将奇数和偶数，添加即可 public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] reOrderArray (int[] array) { // write code here int[] res = new int[array.length]; int idx = 0; for(...

双指针，O(N),O(1) i即right指向奇数，left有两种可能，可能left == right, 或者left指向偶数，此时swap(left, right)即可 public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] reOrderArrayTwo (int[] array) {//双指针 // write code here int left =...

O(N), O(1) 分类讨论，切记中序遍历，为左根右，因为需求给定结点的下一个结点，所以我们只需要讨论给定结点的右子树部分。同样扩展来说，要求给定的结点的上一个结点，只需要讨论给定结点的左子树部分 分析基于题中此图 (1), pNode.right == null, 例如g结点，我们应该是沿着next往回找，且要保证往回找的结点都是遍历过的，所以加上这一判别条件，pNode.next.right == pNode，因为中序遍历-左中右，沿着next往回找的结点其实是“中”，所以是遍历过的。最后找到结点a,返回a.next即null。 可以用l结点对比来看，为什么要加那一判别条件. (2...

O(N) 双指针操作，因为是连续正数序列，所以可以有一个循环变量curSum来计算左右指针所夹的和（左闭右闭），并且一直迭代变化。 举例，1,2,3,4,5,6 sum = 9,left = 1, rigth = 3时 curSum = 6 < sum, 所以 right++, 更新之后，left = 1, right = 4, curSum = 10 > sum，所以left++, 再次更新，left = 2, right = 4, cursum = 9 == sum, 记录结果，left++ 时间复杂度，left，right指针每次循环，一定有一个往前走一步，所以 次数 &lt...

O(N), O(N) 不用库函数，分别使用双指针和快慢指针操作 新建一新方法，双指针实现字符数组翻转，然后利用快慢指针，对每一个单词进行翻转，最后进行整体的翻转 时间复杂度，(双指针操作)整体翻转 n / 2， 所有单词的翻转也近似于 n / 2 ，故时间复杂度 O(N) public class Solution { public String ReverseSentence(String str) {//整体翻转+局部翻转 char[] chs = str.toCharArray(); int slow = 0; for(int fast = 0; fas...

中序和前序或后序，唯一确定一个二叉树 以中序和前序举例，前序[1,2,4,7,3,5,6,8],中序[4,7,2,1,5,3,8,6] 前序遍历规律-根左右可知，第一个数一定是此树的根节点即“1”，又中序遍历规律-左根右，所以找到“1”在中序中的索引，就可以一分为二，左子树中序和右子树中序，基于中序中根节点的索引，同样也可以将前序一分为二 根节点 1 左子树 前序 [2,4,7] ，中序 [4,7,2] 右子树 前序 [3,5,6,8]，中序[5,3,8,6] 递归此步骤即可以建立二叉树 public class Solution { public TreeNode reConstructB...

O(N),穷举 在递归过程中，递归终止条件很重要，因为只有叶子节点的时候，才可以返回 return； 此代码中，每次减去遍历过的数值expectNumber - root.val，但是切记要回溯 import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res; LinkedList<Integer> path; public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int exp...

此问题的暴力解法，O(N*M),不能通过 O(N), O(N) 需要借助于双端队列进行操作，维护队列中元素为不严格单调递降，即单调队列 思路分析：打个比方，给定num = [1,3,3,2,1 ],size = 3,第一个窗口中，1,3,3 中最大值为3，然后滑动到第二个窗口，3,3,2最大值为3，我们只需要在队列中维护，窗口滑动过程中，最有可能成为最大值的可能，即不严格单调递降。因此，第一窗口时，队列中维护3,3，第二个窗口时，队列3,3,2，第三个窗口时，队列3,2,1，最大值都是队列的第一个 题外话，此题求窗口最大值，所以维护不严格单调递降，若是窗口最小值，维护队列为不严格单调递增即可 ...

暴力解法，可以用HashSet记录重复的元素，一个一个删除，但是要遍历链表两次，O(N),O(N) O(N), O(1) 链表题目，最好都加一虚拟头结点，有利用统一操作，不需要分开单独处理头结点 只需要一次遍历的时候，如果cur,cur.next指针的元素值相等，就一直向后移动cur指针，直到cur指针和此重复值不相等，结束，然后可以一起删除这些重复值（此时pre和cur指针中间的值） 如果cur,cur.next指针的元素值不相等，pre和cur都向后移动一次即可 因为有虚拟头结点的缘故，所以最后要去掉此虚拟结点，即返回dummy.next import java.util.*; publi...

穷举，排列 排列之后，字符串有些是一样的，所有要有重操作 import java.util.ArrayList; public class Solution { //穷举 ArrayList<String> res; String path; int[] used; public ArrayList<String> Permutation(String str) { res = new ArrayList<>(); path = ""; used = new int[str.length()]; if(str.length()...

O(N), O(N) 同层序遍历的方法，但是不同的是顺序交替，只能通过别的容器辅助完成，这里选栈，如果继续选择队列，从右到左时，不能辅助完成。通过mark变量标记遍历顺序 代码中，对于二叉树中的每个节点，都会进栈出栈，进队列出队列，所以4N时间,空间即为2N.满足时间和空间复杂度 import java.util.*; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { //栈和队列的混合运用 ArrayList<ArrayLis...

用迭代法中序遍历得到升序数组，然后索引得到,此时空间复杂度为O(N2) 但是同样采用中序遍历，不需要得到最后的升序数组，只需要一个变量记录第几个数，等到等于k时，即返回，此时空间复杂度可以提升到O(N) O(N),O(N) public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param proot TreeNode类 * @param k int整型 * @return int整型 */ public int KthNode (TreeNode proot, int k) { ...

O(N)，此题中N代表二维数组中的元素个数 似乎只有模拟，就顺时针打印，循环不变量很重要，确保左闭右开，左闭右闭也行，反正每次循环保持一致 此题中最后要处理不够循环一周的情况，三种情况，1，剩一个，2剩一行，3剩一列，但是情况1包含在情况2和3中。用loop来标记循环周数的情况，且此题没有说明一定是方阵，所以行列分别有两个变量进行约束 import java.util.*; public class Solution { public ArrayList<Integer> printMatrix(int [][] matrix) { //模拟，循环不变量 ArrayL...

O(N), 双指针 由于数组升序，左右指针指向首尾 左右指针相加大于sum，则右指针左移，小于sum，左指针右移使得相加等于sum 剪枝操作表示此次循环left和right指向的数值和上次循环相等，没有计算的必要，直接continue，当然也可以不用，但是这种操作可以去重（很重要），此题不要求去重，直接计算得到一个就跳出 此题有暴力解法，O(N2) import java.util.ArrayList; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum)...