小白最近NB了啊，都敢刷狗家的题了。哈哈！按照题目的难度先刷一下狗家，让泥萌感受一下，小白九阴真经的威力。真的是小白成长记录啊！这期是Easy。这个是lintcode阶梯，只有刷了easy，medium才能开。
阶梯传送门：
https://www.lintcode.com/ladder/18/
1. 766. Toeplitz Matrix
https://leetcode.com/problems/toeplitz-matrix/description/
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:
Input:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.
Example 2:
Input:
matrix = [
[1,2],
[2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.
Note:
matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].
Follow up:
What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
What if the matrix is so large that you can only load up a partial row into the memory at once?
第一版想了半天，感觉天衣无缝，结果过了400多个case之后fail了。。。结果是有个大漏洞。。。
没想好怎么斜着traverse，就用了笨方法，遍历每一列，从最后一行往上数，有不一样的返回false。这个方法在row 比col多的时候就错了。这时，要遍历每一row了。。。
其实traverse就还像我们正常用的那样，行列就行了，只是取的时候取出来自己和上一行和上一列的比较。。。
这个是正确答案：
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i > 0 && j > 0 && matrix[i][j] != matrix[i - 1][j - 1]){
return false;
}
}
}
return true;
}
}
follow up 很有意思，
第一个follow up只能load一行很好解决，我们的这function也是只需要自己和上面一行的那种。所以只需要每次查看然右下和左上是否一样，一眼的话把自己右下最上方的替代就好。画图！画图很明显。
第二个follow up我的想法是竖着划分矩阵，划分成memory大小，然后每次划分第二次的时候带着第一次的尾巴。但是这个肯定是不对的啊，太大了不行就切成小块。。。跟没说一样。
事实上是两种方法，一种是hash这个数组，然后对比两个hash值。
第二种，咳咳，两个指针，指向disk，每次拿一个数比较然后多动指针。以上都是个人想法哈，如果有出入，欢迎大家指正。
2.
3. 341. Flatten Nested List Iterator
https://leetcode.com/problems/flatten-nested-list-iterator/description/
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false,
the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false,
the order of elements returned by next should be: [1,4,6].
最简单无脑版本，把全世界都展平
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
int index;
List<Integer> flattenedList;
public NestedIterator(List<NestedInteger> nestedList) {
flattenedList = new ArrayList<Integer>();
flattenHelper(flattenedList, nestedList);
index = 0;
}
private void flattenHelper(List<Integer> list, List<NestedInteger> curList){
if(curList == null){
return;
}
for(int i = 0; i < curList.size(); i++){
NestedInteger cur = curList.get(i);
if(cur.isInteger()){
list.add(cur.getInteger());
}else{
flattenHelper(list, cur.getList());
}
}
}
@Override
public Integer next() {
return flattenedList.get(index++);
}
@Override
public boolean hasNext() {
return index < flattenedList.size();
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/
空间复杂度极其高。
第二种方法，每次只展开一层。从尾巴塞入stack，每次只对头上的元素进行操作，留着一个指针，指向即将要操作的下一个元素。如果是单个的元素，get之后就挪走。
leetcode 参考答案：
https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
Stack<NestedInteger> stack = new Stack<NestedInteger>();
public NestedIterator(List<NestedInteger> nestedList) {
for(int i = nestedList.size() - 1; i >= 0; i--){
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while(!stack.isEmpty()){
NestedInteger cur = stack.peek();
if(cur.isInteger()){
return true;
}else{
stack.pop();
for(int i = cur.getList().size() - 1; i >= 0; i--){
stack.push(cur.getList().get(i));
}
}
}
return false;
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/
但我感觉这个还不是最正宗的iterator，最正宗的应该是把没给tree的头放里的那种。
才发现 lintcode有阶梯啊，先做阶梯easy能解锁hard；
https://www.lintcode.com/ladder/18/
4. 1042. Toeplitz Matrix
https://www.lintcode.com/problem/toeplitz-matrix/description
打败96%
public class Solution {
/**
* @param matrix: the given matrix
* @return: True if and only if the matrix is Toeplitz
*/
public boolean isToeplitzMatrix(int[][] matrix) {
// Write your code here
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return true;
}
int m = matrix.length;
int n = matrix[0].length;
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(matrix[i][j] != matrix[i - 1][j - 1]){
return false;
}
}
}
return true;
}
}
5. 1017. Similar RGB Color
https://www.lintcode.com/problem/similar-rgb-color/description
答案在这里，
https://www.jiuzhang.com/solution/similar-rgb-color/
较劲脑汁都想到疯狂枚举了，结果，是一道数学题，这要考试就完蛋了。啊！抄了答案。。。
public class Solution {
/**
* @param color: the given color
* @return: a 7 character color that is most similar to the given color
*/
public String similarRGB(String color) {
// Write your code here
return "#" + closest(color.substring(1, 3)) + closest(color.substring(3, 5)) + closest(color.substring(5, 7));
}
private String closest(String s){
int result = Integer.parseInt(s, 16);
result = result / 17 + (result % 17 > 8 ? 1 : 0);
return String.format("%02x", result * 17);
}
}
6. 914. Flip Game
https://www.lintcode.com/problem/flip-game/description
超简单。。。
public class Solution {
/**
* @param s: the given string
* @return: all the possible states of the string after one valid move
*/
public List<String> generatePossibleNextMoves(String s) {
// write your code here
List<String> list = new ArrayList<String>();
if(s == null || s.length() < 2){
return list;
}
for(int i = 0; i < s.length() - 1; i++){
if(s.charAt(i) == '-'){
continue;
}
if(s.charAt(i + 1) == '+'){
char[] chars = s.toCharArray();
chars[i] = '-';
chars[i + 1] = '-';
list.add(new String(chars));
}
}
return list;
}
}
7. 888. Valid Word Square
https://www.lintcode.com/problem/valid-word-square/description
超时了，但算做出来了也
public class Solution {
/**
* @param words: a list of string
* @return: a boolean
*/
public boolean validWordSquare(String[] words) {
// Write your code here
if(words == null || words.length == 0){
return true;
}
int n = words.length;
for(int i = 0; i < n; i++){
int len = words[i].length();
for(int j = 0; j < len; j++){
char c = words[i].charAt(j);
if(j < n && words[j].length() > j && words[j].charAt(i) == c){
continue;
}else{
return false;
}
}
}
return true;
}
}
8. 655. Add Strings
https://www.lintcode.com/problem/add-strings/description
右超时。 基本功不牢固啊。
- while 里的or想了半天；
- carry 算的时候没加carry；
- edge case，最后carry是1 的时候忘了append！大错啊！
public class Solution {
/**
* @param num1: a non-negative integers
* @param num2: a non-negative integers
* @return: return sum of num1 and num2
*/
public String addStrings(String num1, String num2) {
// write your code here
if(num1 == null || num1.length() == 0 ){
return num2;
}
if(num2 == null || num2.length() == 0 ){
return num1;
}
int m = num1.length();
int n = num2.length();
int i = m - 1;
int j = n - 1;
int sum = 0;
int carry = 0;
StringBuilder sb = new StringBuilder();
while(i >= 0 || j >= 0){
int a = 0;
int b = 0;
if(i >= 0){
a = Integer.parseInt(num1.charAt(i) + "");
}
if(j >= 0){
b = Integer.parseInt(num2.charAt(j) + "");
}
sum = (a + b + carry) % 10;
carry = (a + b + carry) / 10;
sb.append(sum);
i--;
j--;
}
if(carry == 1){
sb.append("1");
}
return sb.reverse().toString();
}
}
9. 514. Paint Fence
https://www.lintcode.com/problem/paint-fence/description
Answer:
https://www.jiuzhang.com/solution/paint-fence/
错误答案！注意，是错误答案！不知道是哪错了。。。
Input
10
3
Output
36864
Expected
27408
Input
4
2
Output
12
Expected
10
public class Solution {
/**
* @param n: non-negative integer, n posts
* @param k: non-negative integer, k colors
* @return: an integer, the total number of ways
*/
public int numWays(int n, int k) {
// write your code here
if(n == 0){
return 0;
}
if(n == 1){
return k;
}
if(n == 2){
return k * k;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = k;
dp[2] = k * k;
for(int i = 3; i <= n; i++){
dp[i] = dp[i - 2] * (k - 1) + dp[i - 2] * (k - 1) * k;
}
return dp[n];
}
}
解释
https://blog.csdn.net/magicbean2/article/details/74725977
10. 156. Merge Intervals
https://www.lintcode.com/problem/merge-intervals/description
Description
Given a collection of intervals, merge all overlapping intervals.
Have you met this question in a real interview?
Example
Given intervals => merged intervals:
[ [
(1, 3), (1, 6),
(2, 6), => (8, 10),
(8, 10), (15, 18)
(15, 18) ]
]
Challenge
O(n log n) time and O(1) extra space.
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
就这么一道题竟然3遍才AC也是很服气！
两个坑1. 最后一个interval要自己加进去，for loop里不负责加最后一个。
2. 检查尾巴是否能合并的时候，是看两个interval 的最大尾巴，开始搞成第二个interval的尾巴了。。。。画个图就出来的，想偷懒失败。
public class Solution {
/**
* @param intervals: interval list.
* @return: A new interval list.
*/
class IntervalCompare implements Comparator<Interval>{
public int compare(Interval a, Interval b){
return a.start - b.start;
}
}
public List<Interval> merge(List<Interval> intervals) {
// write your code here
List<Interval> list = new ArrayList<Interval>();
if(intervals.size() == 0){
return list;
}
if(intervals.size() == 1){
return intervals;
}
Collections.sort(intervals, new IntervalCompare());
int lastStart = intervals.get(0).start;
int lastEnd = intervals.get(0).end;
for(int i = 1; i < intervals.size(); i++){
Interval cur = intervals.get(i);
if(cur.start <= lastEnd){
lastEnd = Math.max(cur.end, lastEnd);
}else{
list.add(new Interval(lastStart, lastEnd));
lastStart = cur.start;
lastEnd = cur.end;
}
}
list.add(new Interval(lastStart, lastEnd));
return list;
}
}
11. 407. Plus One
https://www.lintcode.com/problem/plus-one/description
20分钟才ac，而且3次才AC，代码机器丑陋。edge到都是提前想到了。下面是人家的答案，上面是我的。
public class Solution {
/**
* @param digits: a number represented as an array of digits
* @return: the result
*/
public int[] plusOne(int[] digits) {
// write your code here
if(digits == null || digits.length == 0){
return new int[]{1};
}
//ArrayList<Integer> result = new ArrayList<Integer>();
int sum = 0;
int carry = 0;
int n = digits.length;
sum = (1 + digits[n - 1]) % 10;
carry = (1 + digits[n - 1]) / 10;
if(carry == 0){
digits[n - 1] = sum;
return digits;
}
int[] result = new int[n];
result[n - 1] = sum;
for(int i = digits.length - 2; i >= 0; i--){
sum = (digits[i] + carry) % 10;
carry = (digits[i] + carry) / 10;
result[i] = sum;
}
if(carry == 1){
int[] nResult = new int[n + 1];
for(int i = 1; i < n + 1; i++){
nResult[i] = result[i - 1];
}
nResult[0] = 1;
return nResult;
}
return result;
}
}
这个优雅的代码，人家for loop循环 有个提前出来的机制。想也是嘛，你说，carry没有了，就直接返回了。还要再加干啥，费事嘛。
后面的起始跟我的恶心代码一样了。
public class Solution {
// The complexity is O(1)
// f(n) = 9/10 + 1/10 * O(n-1)
// ==> O(n) = 10 / 9 = 1.1111 = O(1)
public int[] plusOne(int[] digits) {
int carries = 1;
for(int i = digits.length-1; i>=0 && carries > 0; i--){ // fast break when carries equals zero
int sum = digits[i] + carries;
digits[i] = sum % 10;
carries = sum / 10;
}
if(carries == 0)
return digits;
int[] rst = new int[digits.length+1];
rst[0] = 1;
for(int i=1; i< rst.length; i++){
rst[i] = digits[i-1];
}
return rst;
}
}
easy的都OK了。解锁medium了。哈哈哈哈！小白终于成长了，春天来了呢！
