- #98 Validate Binary Search Tree
- #100 Same Tree
- #104 Maximum Depth of Binary Tree
- #122 Best Time to Buy and Sell Stock II
- #136 Single Number
- #150 Evaluate Reverse Polish Notation
- #169 Majority Element
- #171 Excel Sheet Column Number
- #217 Contains Duplicate
- #226 Invert Binary Tree
- #237 Delete Node in a Linked List
- #238 Product of Array Except Self
- #242 Valid Anagram
- #258 Add Digits
- #260 Single Number III
- #274 H-Index
- #283 Move Zeroes
- #292 Nim Game
- #318 Maximum Product of Word Lengths
- #338 Counting Bits
- #343 Integer Break
- #344 Reverse String
- #347 Top K Frequent Elements
- #349 Intersection of Two Arrays
- #350 Intersection of Two Arrays II
- #357 Count Numbers with Unique Digits
2016-06-20 今天开始刷LeetCode，先从AC最高的做起来。因为不想放弃java，所以决定用java来完成这些题目。
今晚做了两天题目练练手12
Detail:
- description: 检查一个二叉查找树是不是合法的。
第一反应很简单啊，这是我的第一版代码
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (root.left == null && root.right == null) return true;
return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean validate(TreeNode root, int min, int max) {
if (root == null) return true;
if (root.val <= min || root.val >= max) return false;
return validate(root.left, min, root.val) && validate(root.right, root.val, max);
}
} 可是就是跑不通测试，怎么看都不应该错啊。想了好久，又看了网上的讲解。原来不仅要看一个节点跟它的左右子树进行比较，还要看它的儿子和它的父亲之间的关系。 一个很好的方法就是中序遍历，把一棵树按照左根右的方式去排列，然后检查一遍是否合格，不过需要花费额外的空间。
网上看的一个不需要额外空间的优化解法，把代码列上来吧
public class Solution {
// Keep the previous value in inorder traversal.
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
// Traverse the tree in inorder.
if (root != null) {
// Inorder traversal: left first.
if (!isValidBST(root.left)) return false;
// Compare it with the previous value in inorder traversal.
if (pre != null && root.val <= pre.val) return false;
// Update the previous value.
pre = root;
// Inorder traversal: right last.
return isValidBST(root.right);
}
return true;
}
}Detail:
- description: 也是递归的方法，首先判断当前节点的val是否相同，如果相同则分别判断左右子节点
Detail:
- description: 没什么说的 直接递归
Detail:
- description: 这个题目怎么说呢。。怎么会出现在leecode中，可能大部分人第一遍读下来之后没看懂题目的意思。其实很简单，就是我从一段时间开始到结束，什么时候买，什么时候卖是最赚的而且卖只能在买之后。所用就从左到右遍历一遍数组，如果后一个大于前一个，则表示可以赚钱，于是就相加。
Detail:
- description: 异或，相同的数异或为0
运算法则：
1. a ⊕ a = 0
2. a ⊕ 0 = a
3. a ⊕ b = b ⊕ a
4. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
5. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
6. a ⊕ b ⊕ a = b.
Detail:
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
- description:考察的是怎么把逆波兰表示法给计算出来。用一个栈来压入所有的数，当遇到操作符时，取出栈顶的两个数，计算出结果后再压入栈内，最后的结果就是栈里的唯一的一个数。
Detail:
- description: 这个题目在校招复习的时候看过，找出一个数组中出现次数超过[n/2]的数。 从第一个数开始，与下一个数比较，记录出现次数最多的数和出现次数。如果相同，次数加1，如果不相同，次数减1，如果次数小于等于1，则变更这个出现次数最多的数。
Detail:
- description: 这个其实就是类似于十进制、十六进制，这里是二十六进制，然后利用ascii码与'A'的差值来计算。
Detail:
- description: 检查一个数组中，是否有两个数重复。
- 排序 O(NlogN) O(1)
- 一个个比较 O(N^2) O(1)
- set O(N) O(N)
Detail:
- description: 没什么说的 直接递归
Detail:
- description: 这个题之前在《剑指offer》上看到过。惯性思维是删除current节点，巧妙的方法是删除next节点，这样就不用去查找prev节点了。所以呢，把下一个节点的val复制过来，然后删除next节点就OK了。
Detail:
- description: 这题有点意思啊，好好分析一下。 首先读懂题目的意思，要求把所有的数都乘起来，并且除以自身，就是该位置的值。
一般人的第一反应就是按照上面的思路呗，可是题目给了要求
Solve it without division and in O(n)
不能用除法之后，只能用乘法操作，那么怎么样利用之前的结果，而不需要每次都做重复的乘法操作呢。 不多说了，直接看代码
for (int i = 1; i < nums.length; i++) {
res[i] = res[i-1] * nums[i-1];
}
第一次遍历，让数组中所有的数res[i] = res[0] * res[1] * ... * res[i-1]，等于它左边所有的数的乘积。但是题目的要求是除了自身所有的数，也就是所有左边的和所有右边的都要乘起来。 这时候我们就需要第二次遍历了
for (int i = nums.length - 1; i > 0; i--) {
res[i] = res[i] * res[0];
res[0] = res[0] * nums[i];
}
这里用了一个很巧妙的技巧，就是不断地让第一个数变大，而且是从右往左乘，这样res[i]需要再乘以 res[len-1], res[len-2], ..., res[i+1]，而res[0]就是在这个循环中不断地从右往左乘。
Detail:
- description: 我一开始的方法不知道为什么不行，testcase[33/34]每次都卡在这里简直无语了。笨方法就是分别用两个hashmap统计两个字符串中出现的所有字符，最后比较这两个hashmap是否相同。
没办法，我只能去看答案，原来真的简单，根本用不到hashmap，因为总共就只有26个英文字符，所以一个26长的数组就能完全覆盖了。
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : t.toCharArray()) {
count[c - 'a']--;
if (count[c - 'a'] < 0) return false;
}
两个循环，也是用ascii的值去计算字符在数组中的位置。 第二遍如果发现有小于0的，说明t中肯定有多的字符，那么就不是valid anagram啦。不过当然第一步还是要判断两个字符串的长度是否相同。
Detail:
- description: 这个好像可以看wikipedia上关于digital root的解释，给个链接吧 https://en.wikipedia.org/wiki/Digital_root
Detail:
- description: 这个题和#136有点相似，但是是有两个数不是为双的。
- 先找出这两个数的异或结果。
- 既然有了这两个数的异或结果res，那么res中取第n位为1，就表示在这两个数中，有一个第n位为0，有一个第n位为1。
- 这样按照此区分，把所有的数分为两组，一组是第n位为0，一组是第n位为1，这样在两组中只存在一个不是双数的数，再按照#136的方法即可得出结果。
Detail:
- description: 找到一个数h，h个数大于等于h，剩下的n-h个数全部小于等于h。
最简单的方法是对数组进行排序，O(NlogN)的时间，然后从后往前遍历，找到最大的一个h。
如果仔细考虑h的特征可以发现，如果数组的长度为n，那么h大于n肯定不行，因为这将意味着有大于n个数大于等于h，所以对大于n的数可以一视同仁了。这样我们只需要考虑所有小于等于n的数和一个大于等于n的数。
代码如下
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int length = citations.length;
int h = 0;
int[] array = new int[length + 1];
// 考虑所有小于等于n的数`和`一个大于等于n的数
for (int i : citations) {
if (i > length) array[length] += 1;
else array[i] += 1;
}
// 从后向前遍历，找到最大的一个符合条件的数
for (int i = length; i >= 0; i--) {
h = h + array[i];
if (h >= i) return i;
}
return 0;
}
}Detail:
- description: 一个re标志位用来标记当前数组的位置，非0就将它复制到前面去。 最后再把0补齐即可。
Detail:
- description: 没啥了，每次只能取1-3，这样保证取出的是4的倍数即可。
Detail:
- description: 一个单词所有字母组合最多26个，用26位的二进制数来表示一个单词中所用到的所有字母，左移即可。
判断两个单词是否有相同字母，只需要将上面的两个数做与操作，判断是否为0即可，values[i] & values[j]) == 0。
Detail:
- description: counting bit相信大家都没有问题，那么counting bits就需要找规律了。 可以发现任意一个偶数n和n+1的关系
countingBit(n) = countingBit(n + 1) - 1
然后hint还提示了可以分组计算，[1, 2], [2, 3], [4, 7], [8, 16]，我没想太多，不过应该还是有可以重复利用的部分。
Detail:
- description: 把一个数拆分开，求最大的成绩，用几个简单的例子就可以发现，拆出来的数要么是2，要么是3，所以我的方法还算比较简单，列一下代码， 需要注意的是一个数不能是它自己，如2必须要拆成1*1，所以这里简单注意一下就OK
public class Solution {
public static int integerBreak(int n) {
return integerBreak(n, true);
}
public static int integerBreak(int n, boolean isFirst) {
if (n < 4)
{
if (isFirst)
return n-1 > 0 ? n-1 : 1;
else
return n > 0 ? n : 1;
}
if (n % 3 == 1)
return 4 * integerBreak(n - 4, false);
return 3 * integerBreak(n - 3, false);
}
}看了下答案，用的dp算法，状态和状态转移方程这里就不一一描述了，但我觉得这样的效率会比较低。
Detail:
- description: 这个直接用了Java中的StringBuilder，用来做字符串的运算会快很多，不需要每次重新建一个String。
Detail:
- description: 第一步必须是扫描，计入到hashmap中。 那么怎么从每个数字出现的次数来找到前k个最高频率相互此案的，这样是不是就必须再对frequent进行排序呢。 NO.NO.NO 因为总共只有n个数，那么即使所有的数字一样多，是不是出现的频率最高也就是n呢。从n到0循环遍历以频率为key的hashmap，看看是否有对应的数，如果有就取出来，直到取到了k个。
Detail:
- description: 我用的笨方法。
- 先把nums1中的数据放到一个map1中
- 再把nums2中的数据如果在map1中也有的话，放到map2中
- 再把map2中的读出来放进数组里。
Detail:
- description: 获取两个数组中相同的数字，不过这些数字可能是有重复的。 笨方法如下：
- 先获取一个数组中所有的数字和对应的次数
- 遍历第二个数组，看看第一个数组中是否存在，如果存在则记录下，并讲第一个数组中该数对应的次数减一。
- 所有记录下的值组合起来就是结果
- 耗时8ms
Detail:
- description:
动态规划 找规律
Let f(k) = count of numbers with unique digits with length equals k.