1、逆序想到 stack ; 比如 445. 两数相加 II,当然,可以用 stack 也是可以用 List,list 有序,因此也是可以当作 stack 用;
2、要求达到 O(n \log n)O(nlogn) 的时间复杂度和 O(1)O(1) 的空间复杂度,时间复杂度是 O(n \log n)O(nlogn) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n^2)O(n2)),其中最适合链表的排序算法是归并排序。
3、对于链表,有时候需要把头结点加入循环,可以在头结点前面在家一个节点,这样就可以用于判断了;
4、链表常用的操作逻辑,用 stack, 数组保存节点组成新的队列;用一个新节点来连接原来的节点,这样,即使对原有节点改变了,还是可以返回头结点。熟悉链表的反转,合并等逻辑。
5、关于二叉树,二叉树一般采用递归,一般是递归到最后一个的时候,在不断往前,因此你要做好最好一个判断到底是返回什么,比如深度的求解等等。
class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; // 这里加1,不断递归,数值就变大了 } } }
6、二叉树的递归调用其实就是存在一个隐藏的stack。只是大家平时熟悉了递归,没有去细想内部的逻辑。所以如果不采用递归方式来实现,就是得采用 stack 来维护这个顺序,但是要注意先入后出这个点。
7、如果给你一个数组 num1 足够空间,前部分已经存在值了,让你把另一个 num2 的值填到 num1 中。这种要么新建一个数组,填完后再挪到 num1 中,另一种是从合并后的长度开始填,这样确保不会覆盖 num1 前面已有的值。可参考 88. 合并两个有序数组
8、两个字符串找不同,对于字符串可以采用求和,位运算,以及一个数组来记录各个字母出现的个数,以此来找到不同。参考:389. 找不同
1 // 求和 2 class Solution { 3 public char findTheDifference(String s, String t) { 4 int as = 0, at = 0; 5 for (int i = 0; i < s.length(); ++i) { 6 as += s.charAt(i); 7 } 8 for (int i = 0; i < t.length(); ++i) { 9 at += t.charAt(i); 10 } 11 return (char) (at - as); 12 } 13 } 14 15 // 计数 16 class Solution { 17 public char findTheDifference(String s, String t) { 18 int[] cnt = new int[26]; 19 for (int i = 0; i < s.length(); ++i) { 20 char ch = s.charAt(i); 21 cnt[ch - 'a']++; 22 } 23 for (int i = 0; i < t.length(); ++i) { 24 char ch = t.charAt(i); 25 cnt[ch - 'a']--; 26 if (cnt[ch - 'a'] < 0) { 27 return ch; 28 } 29 } 30 return ' '; 31 } 32 } 33 34 // 位运算 35 class Solution { 36 public char findTheDifference(String s, String t) { 37 int ret = 0; 38 for (int i = 0; i < s.length(); ++i) { 39 ret ^= s.charAt(i); 40 } 41 for (int i = 0; i < t.length(); ++i) { 42 ret ^= t.charAt(i); 43 } 44 return (char) ret; 45 } 46 }两个字符串找不同