“Subset/Permutation/CombinationSum”

正在制作中/Working

“编程是一个让大脑变简单的过程/Programming is making your brain simple”

发现写代码，刷题，做项目，其实是一个剪枝的过程。 面对一个问题，作为新手的时候不知道怎么做的原因很多，其中一个就是方法的选择范围太广了。用什么框架，用什么库，用什么数据结构，这些都是一堆问题。 熟练了之后，再遇到问题就能迎刃而解了，基本上是因为你已经知道了哪条路走起来最方便，你不会再开始纠结哪条路更好或者哪条路不好，你的脑袋变简单了。w s s

“为什么我做不出算法题/Why I cannot solve algorithm questions”

看了下LeetCode刷题记录，开始刷题已经一年了，但是到现在如果遇到不明确/不熟悉的新题（eg：周赛），还是有很大的可能做不出来，不过做不出来的原因和一年前刚开始刷LeetCode已经有变化了。

一年前刚开始刷题的时候（也是刚开始学会写代码的时候），对数据结构有哪些都没什么了解，Java的API用的也不熟练，当时很多Easy题看答案都没办法理解，基本上全靠背。。。

一年过去了，对数据结构的掌握比以前要好不少，基本上遇到一道题能想出来大概可以用什么样的数据结构来解决。但是编程能力还是有问题，或者说是思维上还是不够严谨？比如说“星球坠落”那道题，看到题目的时候就想到了应该用Stack来解决不同方向的星球碰撞问题，但是两个星球相遇的时候，用什么样的逻辑来解决，思路上还不是很清晰，最后还是要靠看答案才能写出来，这应该是逻辑上思考的不够深入？

拿一年前不会做，但是现在可以比较流畅的做出来的题目来比较的话，这一年对刷题的领悟大概有三点：

1. 对题目的理解 - Two Sum。 刚开始刷题的时候只会用两层循环来做，后来看答案会了HashMap，但是实际上掌握的还是不够熟练。现在已经可以用Map+双指针来做了，感觉上最重要不是某种算法，而是对题目的理解，对题目的输入输出理解透彻之后，就可以得心应手的写出想要的答案。
2. 对数据结构的掌握 - Add Two Numbers。这是我亚马逊Intern面试的时候(19-2-26)被问到的题目。可以说在当时那个阶段，这道题完全靠背。我第一次接触到这个题目的时候是18年本科快毕业的时候的，当时看答案好久都没看明白（那个时候还没有学过算法，本科也几乎没有写过代码），难点就是根本就不懂数据是怎么保留住成功进入下一层的，当时答案区的三目表达式 ( val = node == null ? 0 : node.val) 也对我造成了很大的困扰。 后来在做完链表的专项训练之后，突然就感觉这道题很简单了，这一提升来自于对对应数据结构的掌握。同时，那段时间困扰我许久的LRU Cache也迎刃而解了，是在我想别的链表问题的时候突然醒悟到，LRU Cache不就是一个链表操作问题嘛？然后在白板上画了LRU Cache的结构图并且手写了代码，完美通过。
3. 对算法的熟悉 - Number of Islands/Course Schedule/Word Ladder/AlienDict。岛屿数量这道题第一次遇到是在18年刚入学的时候，yjx在做twitter的oa的时候遇到的。当时我对这个题目完全没法理解，甚至连满屏幕的000111001001的输入也看不明白，当时同学秒掉了这道题目之后，我想了一会儿没想懂，就没再看了。 后来再接触到这个题目，是19年实习结束后，看九章算法的课的时候才想明白的（其实18年我已经学过算法课并且学了BFS/DFS了），在熟悉了BFS的思路之后，这道题也几乎是迎刃而解了。对这道题目的第二次理解加深是学Union-Find算法的时候，同样也是在研究算法的过程中，突然想到这道题可以用Union-Find来做，然后写出了代码。并且那两天用Union-Find做了好多之前用BFS/DFS的题，几乎都没有看答案，很流畅的写了出来。这一切主要还是来源于我对一个新算法的掌握而不是对答案的理解。(同类的通过学会对应算法就会做的题目还有很多，Course Schedule，AlienDict这种)

但是实际上现在困扰我的问题还有很多，比如String，Array这种题目(eg: 字符串匹配，最长子数列的和等等等），真的是几乎每一道Hard我都无能为力，都要看答案之后才知道要往哪个方向努力，Recursion的题目也要靠不同的练习来保持手感，看答案很容易看懂，但是很难自己想Recursion的写法。最近的计划是复习一下算法书中的基本内容，过段时间再来看看，以前不会做的题目是不能能熟练的做出来。

Deisgn Inmemory File System

ls:

1. initialize t, and iterate it to the last point. (by spliting “path” using “/”)

2. Stop at either end level dir or file name, if it is file name, just return the file name. Otherwise if it is a dir, get its sub-dirs and add them into output;

3. sort the ouput list and return.

Mkdir:

1. iterate pointer to its end
2. if there is no esxisting path, add it

Search In Rotated Array

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Idea

1. We need to search in a sorted array, since it is sorted, so we could use binary search
2. the mid can be in two different situations (1) start – MID – Higest or (2) Lowest – MID – End
3. for situation (1), the target could be in one of two situations: target in [start, mid] or Other. if target is in [start, mid], we do binary search in this part, otherwise, transfer it into a sub SEARCH_IN_ROTATED_ARRAY problem. Same idea for situation (2). The target could be in [mid, end], we do binary search in this part. If target is not in [mid, end], we transfer it into another sub-problem.

Code

public int searchTarget(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] == target) return mid;

            if (nums[mid] > nums[end]) {
                if (nums[start] <= target && target <= nums[mid]) {
                    end = mid;
                } else
                    start = mid;
            } else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                } else
                    end = mid;
            }
        }

        if (nums[start] == target) return start;
        if (nums[end] == target) return end;
        return -1;
    }