發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        l = len(num);
        if l < 3:
            return False
        for i in range(1, l - 1):
            first = int(num[:i])
            for j in range(i + 1, l):
                if num[i] == "0" and i + 1 != j:
                    continue
                second = int(num[i:j])
                for k in range(j + 1, l + 1):
                    if num[j] == "0" and j + 1 != k:
                        continue
                    third = int(num[j:k])
                    if first + second == third:
                        if k == l or self.isAdditiveNumber(num[i:]):
                            return True
            if num[0] == "0" and i == 1:
                break
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        return self.my(0, 0, 0, 0, num)
    def my(self, first, second, first_len, second_len, num):
        l = len(num);
        if l < 3:
            return False
        if first == 0 and second == 0:
            for i in range(1, l - 1):
                first = int(num[:i])
                first_len = i
                for j in range(i + 1, l):
                    if num[i] == "0" and i + 1 != j:
                        continue
                    second = int(num[i:j])
                    second_len = j - i
                    for k in range(j + 1, l + 1):
                        if num[j] == "0" and j + 1 != k:
                            continue
                        third = int(num[j:k])
                        third_len = k - j
                        if third_len < first_len or third_len < second_len:
                            continue
                        if first + second == third:
                            #print first, second, third
                            if k != l and l - k + 1 < third_len:
                                continue
                            if k == l or self.my(second, third, second_len, third_len, num[first_len:]):# == second + third or second + third == int(num[k:]) or self.my(num[j:]) == third:
                                return True
                if num[0] == "0" and i == 1:
                    break
            return False
        else:
            third_expected = first + second
            third_expected_str = str(third_expected)
            third_expected_len = len(third_expected_str)
            #third = num[sl + tl:third_expected_len + sl + tl]
            return num[first_len+second_len:].startswith(third_expected_str) and \
                    (third_expected_len + first_len + second_len == l or \
                    self.my(second, third_expected, second_len, third_expected_len, num[first_len:]))

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        leng=len(strs[0])
        shortest_index=0
        if len(strs) == 1:
            return strs[0]
        #find shortest
        for i,str in enumerate(strs):
            if len(str)<leng:
                shortest_index=i
                leng=len(str)
        pref=strs[shortest_index]
        #find most common prefix
        for str in strs:
            while str.startswith(pref) == False:
                leng-=1
                pref=pref[:leng]
        return pref

發表於   |   分類於   |   0 comments

不知是有被我安利到還是感興趣台灣的人本身很多，遇到許多向我要攻略的小夥伴（為什麼當初卻沒人有空陪我去，還被放過鴿子，罰你們交五毛錢稿費啦ww）。不過話說回來其實自己本來也期待一個人遠行一次，可以得到鍛煉，同時跟世界的接觸面積更大，不會局限在同行的小圈子裡，也更加自在隨心。一路上得到很多人的關心照顧，謝謝你們。在墾丁和從墾丁到花蓮路上陪伴我的四位學長學姐、旅行途中認識或通過網路認識的幾位觀光客都和我一樣，回大陸前每個人都感到悲傷、不捨、希望留下，這大概就是台灣的魅力吧。

下面先上乾貨——

閱讀全文 »

發表於   |   分類於   |   0 comments 
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        tokens = ["+", "-", "*", "/"]
        token1 = ["+", "-"]
        token2 = ["*", "/"]
        operators = []
        operands = []
        res = 0
        cur = 0
        for x in range(len(s)):
            if s[x] in tokens:
                operators.append(int(s[cur:x]))
                if len(operators) < 2:
                    operands.append(s[x])
                else:
                    if operands[-1] in token2:
                        tmp = cal(operands[-1], operators[-2], operators[-1])
                        operators = operators[:-2]
                        operators.append(tmp)
                        operands = operands[:-1]
                    elif operands[-1] in token1 and s[x] in token1:
                        tmp = cal(operands[0], int(operators[0]), int(operators[1]))
                        operators = operators[1:]
                        operators[0] = tmp
                        operands = operands[1:]
                    operands.append(s[x])
                cur = x+1
            if x == len(s) - 1:
                operators.append(int(s[cur:]))
                if len(operands) != 0 and operands[-1] in token2:
                    tmp = cal(operands[-1], int(operators[-2]), int(operators[-1]))
                    operators = operators[:-2]
                    operators.append(tmp)
                    operands = operands[:-1]
        while len(operands) != 0 or len(operators) != 0:
            if len(operators) == 1 and len(operands) == 0:
                return operators[0]
            tmp = cal(operands[0], int(operators[0]), int(operators[1]))
            operators = [tmp] + operators[2:]
            operands = operands[1:]

def cal(operand, operator1, operator2):
    if operand == "+":
        return operator1 + operator2
    if operand == "-":
        return operator1 - operator2
    if operand == "*":
        return operator1 * operator2
    if operand == "/":
        return operator1 / operator2

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        N = len(citations)
        d = []
        t = 0
        for x in range(N+1):
            d.append(0)
        for x in citations:
            if x <= N:
                d[x] += 1
            else:
                t += 1
        for x in range(N+1):
            xx = N - x
            t += d[xx]
            if t >= xx:
                return xx
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        N = len(citations)
        if N == 0:
            return 0
        citations.sort(reverse = True)
        mid = N / 2
        begin = 0
        end = N - 1
        while True:
            if begin >= end:
                if citations[mid] >= mid + 1:
                    return mid + 1
                else:
                    return mid
            if citations[mid] < mid + 1:
                end = mid - 1
                mid = (begin + end) / 2
            elif citations[mid] > mid + 1:
                begin = mid + 1
                mid = (begin + end) / 2
            else:
                return mid + 1

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        d = {}
        for x in nums:
            d[x] = x
        return len(d) != len(nums)

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> p;
        helper(p, target, candidates, 0);
        return res;
    }
    void helper(vector<int> &partial, int target, vector<int>& candidates, int start) {
        int l = candidates.size();
        if (!target) res.push_back(partial);
        for (int i = start; i < l; i++) {
            int w = candidates[i];
            if (w<=target)  {
                partial.push_back(w);
                helper(partial, target-w, candidates, i);
            }
            else break;
            partial.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        d = {}
        for i in range(target+1):
            d[i] = []
        for i in range(len(candidates)):
            d[candidates[i]] = [[candidates[i]]]
        for i in range(target+1):
            for j in range(len(candidates)):
                if i-candidates[j] in d and d[i-candidates[j]] != []:
                    for x in d[i-candidates[j]]:
                        a = sorted(x + [candidates[j]])
                        if a not in d[i]:
                            d[i].append(a)
        return d[target]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
struct cmp{bool operator()(const int &x,const int &y) const{return x<y;}};
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<vector<int>>> d;
        for(int i = 0; i <= target; i++){
            vector<vector<int>> tmp;
            d.push_back(tmp);
        }
        for(int i = 0; i < candidates.size(); i++){
            vector<int> tmp;
            tmp.push_back(candidates[i]);
            if(candidates[i]<=target)
                d[candidates[i]].push_back(tmp);
        }
        for(int i = 0; i <= target; i++){
            for(int j = 0; j < candidates.size(); j++){
                if(i-candidates[j]<0) continue;
                if(!d[i-candidates[j]].empty()){
                    for(int k = 0; k < d[i-candidates[j]].size(); k++){
                        vector<int> t;
                        
                        t = d[i-candidates[j]][k];
                        t.push_back(candidates[j]);
                        sort(t.begin(), t.end(), cmp());
                        int l;
                        for(l = 0; l < d[i].size(); l++){
                            if(d[i][l]==t) break;
                        }
                        if(l == d[i].size()){
                            d[i].push_back(t);
                        }
                    }
                }
            }
        }
        return d[target];
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Queue {
public:
    stack<int> s1,s2;
    void transfer(){
        if(s2.empty()){
            while(!s1.empty()){
                int x = s1.top();
                s1.pop();
                s2.push(x);
            }
        }
    }
    // Push element x to the back of queue.
    void push(int x) {
        s1.push(x);
    }
    
    // Removes the element from in front of queue.
    void pop(void) {
        transfer();
        s2.pop();
    }
    
    // Get the front element.
    int peek(void) {
        transfer();
        return s2.top();
    }
    
    // Return whether the queue is empty.
    bool empty(void) {
        return s1.empty() && s2.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @constructor
 */
var Queue = function() {
    this.queue1 = [];
    this.queue2 = [];
};
Queue.prototype.transfer = function(){
    if (this.queue2.length === 0) {
        while (this.queue1.length !== 0){
            var x = this.queue1[this.queue1.length-1]
            this.queue1.pop()
            this.queue2.push(x)
        }
    }
}
/**
 * @param {number} x
 * @returns {void}
 */
Queue.prototype.push = function(x) {
    this.queue1.push(x)
};
/**
 * @returns {void}
 */
Queue.prototype.pop = function() {
    this.transfer()
    this.queue2.pop()
};
/**
 * @returns {number}
 */
Queue.prototype.peek = function() {
    this.transfer()
    return this.queue2[this.queue2.length-1]
};
/**
 * @returns {boolean}
 */
Queue.prototype.empty = function() {
    return this.queue1.length === 0 && this.queue2.length === 0
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.queue1 = []
        self.queue2 = []
        
    def transfer(self):
        if len(self.queue2) == 0:
            while not len(self.queue1) == 0:
                x = self.queue1[-1]
                self.queue1 = self.queue1[:-1]
                self.queue2.append(x)
            
    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.queue1.append(x)
        
    def pop(self):
        """
        :rtype: nothing
        """
        self.transfer()
        self.queue2 = self.queue2[:-1]
        
    def peek(self):
        """
        :rtype: int
        """
        self.transfer()
        return self.queue2[-1]
        
    def empty(self):
        """
        :rtype: bool
        """
        return self.queue1 == [] and self.queue2 == []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MyQueue{
		ArrayList<Integer> queue1 = new ArrayList<Integer>();
		ArrayList<Integer> queue2 = new ArrayList<Integer>();
		public void transfer(){
			if(queue2.isEmpty()){
				while(!queue1.isEmpty()){
					int lastIdex = queue1.size()-1;
					Integer x = queue1.get(lastIdex);
					queue1.remove(lastIdex);
					queue2.add(x);
				}
			}
		}
	    public void push(int x) {
	    	queue1.add(x);
	    }
	    // Removes the element from in front of queue.
	    public void pop() {
	        transfer();
	        queue2.remove(queue2.size()-1);
	    }
	    // Get the front element.
	    public int peek() {
	    	transfer();
	    	return queue2.get(queue2.size()-1);
	    }
	    // Return whether the queue is empty.
	    public boolean empty() {
	        return queue1.isEmpty() && queue2.isEmpty();
	    }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MyQueue {
		ArrayList<Integer> queue = new ArrayList<Integer>();
		//Queue queue;
		//Stack<Integer> queue;
		// Push element x to the back of queue.
	    public void push(int x) {
	    	queue.add(x);
	    }
	    // Removes the element from in front of queue.
	    public void pop() {
	        
	        queue.remove(0);
	    }
	    // Get the front element.
	    public int peek() {
	    	return queue.get(0);
	    }
	    // Return whether the queue is empty.
	    public boolean empty() {
	        return queue.size() == 0;
	    }
	
}

發表於   |   0 comments

趁着记忆还热，写下来这段日子是如何度过的吧。比较少写经验贴；我的备考过程和我的行事风格常常都是比较个性化而且只想做好眼前，没有提前做好宏伟计划并笃定执行的本事。这篇帖子仅供参考，没有四海皆准的methodology，但一些经验很可能有帮助。先说一下背景，我六月23日一战154+170+3.0，10月30日二战162+170+？，英语基础不错。十月初在家休养，陆续背了一些单词，复习从10.13正式开始。

閱讀全文 »

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int flag = 0;
    bool isUgly(int num) {
        if(num <= 0) return false;
        if(num % 2 == 0) {flag = 1; return isUgly(num/2);}
        if(num % 3 == 0) {flag = 1; return isUgly(num/3);}
        if(num % 5 == 0) {flag = 1; return isUgly(num/5);}
        if(num == 1 && flag ==0) return true;
        if(num == 1 && flag ==1) return true;
        return false;
    }
};