發表於   |   分類於   |   0 comments

我想这大概不会是一篇典型的游记或攻略，它更像我独家的回忆，景点和美食介绍之外，更多关乎这一路的遇见。我写下它只是因为，这段经历如此精彩，而我抵抗遗忘的唯一方式便是记录。相比忙碌略微乏味的第一学期，这段时光添加了太多亮色。果然生活是需要一段时间从现实抽身而出的。而世界永远值得一看。

我不喜欢和太多人一起旅行，因为计划会圈住我的脚步，而且只有人少的时候我跟世界的接触面才会更大。随机地结识朋友，倾听故事，或者和他们一起展开冒险，会带来意想不到的惊喜。而伤感的一面是，每个人都会回到现实继续自己的生活，即便有些人也能够把旅行当生活本身，所有遇见的人和事都会是一次性的。此生我跟这个人在这个地方创造的回忆，是如此不可复制、独一无二的快乐，因此它的反面也有着些许昙花一现的落寞。这些相遇便也有了更加奇妙的色彩。

閱讀全文 »

發表於   |   分類於   |   0 comments

被“优秀是一种习惯”的bollocks骗了好多年，我现在想说，这是个坑。如果说出国以后我的心态有任何转变的话，大概是我一点也不想再迷信排名、万人冲独木桥、要跟人比较来获得幸福感这码子事。因为有着优秀的惯性，会觉得自己如果不去big name的学校或公司是不是太有失形象，会想自己成绩变糟了会不会很难看而不关心学的东西是不是喜欢是不是真的有搞懂，会贪恋安逸地一条路走下去不敢推翻自己曾经的选择（我暂时倒不想换条职业道路，只是觉得我没法确定这是自己的最终归宿，以及我没法割舍其他的可能性；尽管不是每个人都需要，我却试图找到那份热情和使命感，在那之前我对自己的动机不够满意）。其实这里出问题的是优秀的定义，许多人把光鲜亮丽的外表，一份好看的履历或成绩单、工作与工资这类看得太重要，所有努力都为了换一张好看的皮供人艳羡；我倒是会对有意思的人的本心更感兴趣，认真的思考者、冒险家与实验家、有许多兴趣爱好或只有一件钟爱的事情，我笃信人生不一定要多金但要开心，精神丰富的人最酷了。这份新的迷信名字大概叫，自由。

發表於   |   分類於   |   0 comments

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    vector<int> plusOne(vector<int>& digits) {
        vector<int> res;
        int l = digits.size()-1;
        res = helper(digits, l);
        return res;
    }
    vector<int> helper(vector<int> d, int i) {
        if (d[i] < 9) {
            vector<int> v(d.begin(), d.begin()+i);
            v.push_back(d[i]+1);
            return v;
        }
        else {
            vector<int> v;
            if(i>0) v = helper(d, i-1);
            else v.push_back(1);
            v.push_back(0);
            return v;
        }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> res(digits);
        int l = digits.size();
        for (int i = l-1; i >= 0; i--) {
            if (digits[i] == 9)
                res[i] = 0;
            else {
                res[i]++;
                return res;
            }
        }
        res[0] = 1;
        res.push_back(0);
        return res;
    }
};

發表於   |   分類於   |   0 comments

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "")   return 0;
        if (haystack == "") return -1;
        int l = haystack.length();
        int ll = needle.length();
        int i = 0;
        while (i <= l-ll) {
            int j = i;
            while (j < l && j-i < ll && haystack[j] == needle[j-i]) {
                j++;
            }
            if (j-i == ll)  return i;
            i++;
        }
        return -1;
    }
};

發表於   |   分類於   |   0 comments

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> mp;
        int mx = INT_MIN;
        for (int i:nums) {
            if (!mp[i]) {
                mp[i] = mp[i+1] + mp[i-1] + 1;
                mp[i+mp[i+1]] = mp[i];
                mp[i-mp[i-1]] = mp[i];
                if (mp[i] > mx) mx = mp[i];
            }
        }
        return mx;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        int i = 0;
        while (i <= r) {
            while(nums[r] == 2) r--;
            while(nums[l] == 0) l++;
            while (nums[i] == 2 && i < r) {  
                swap(nums[i], nums[r--]);
            }
            while (nums[i] == 0 && i > l)  {
                swap(nums[i], nums[l++]);
            }
            i++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = nums.size();
        int a[3] = {0,0,0};
        for (int i = 0; i < l; i++) {
            a[nums[i]]++;
        }
        for (int i = 0; i < a[0]; i++) {
            nums[i] = 0;
        }
        for (int i = a[0]; i < a[0]+a[1]; i++) {
            nums[i] = 1;
        }
        for (int i = a[0]+a[1]; i < l; i++) {
            nums[i] = 2;
        }
    }
};

發表於   |   分類於   |   0 comments

Suppose a sorted array 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).

Find the minimum element.

You may assume no duplicate exists in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while (l<r-1) {
            if (nums[l] < nums[r])  return nums[l];
            int mid = (l+r)/2;
            if (nums[mid]>nums[l] && nums[r]<nums[l]) 
                l = mid;
            else //if (nums[mid]>nums[l] && nums[r]<nums[l]) 
                r = mid;
        }
        return nums[l]<nums[r]?nums[l]:nums[r];
    }
};

發表於   |   分類於   |   0 comments

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

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 {
public:
    int maxArea(vector<int>& height) {
        int l = height.size();
        int left = 0, right = l-1;
        int mx = 0;
        while (left<right) {
            if (height[left]<height[right]) {
                int tmp = height[left]*(right-left);
                if (tmp>mx)
                    mx = tmp;
                left++;
            }
            else {
                int tmp = height[right]*(right-left);
                if (tmp>mx)
                    mx = tmp;
                right--;
            }
        }
        return mx;
    }
};

發表於   |   分類於   |   0 comments

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int l = nums.size();
        vector<int> res(l,1);
        int prod = 1;
        for (int i = 0; i < l; i++) {
            res[i] = prod;
            prod *= nums[i];
        }
        prod = 1;
        for (int i = l-1; i >= 0; i--) {
            res[i] *= prod;
            prod *= nums[i];
        }
        return res;
    }
};

發表於   |   分類於   |   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
class Solution {
public:
    int trap(vector<int>& height) {
        int l = height.size();
        stack<pair<int, int> > stk;
        int res = 0;
        vector<int> prev(l, 0);
        for (int i = 0; i < l; i++) {
            if (!height[i]) continue;
            if (!stk.empty()) {
                pair<int, int> last = stk.top();
                while (!stk.empty() && last.second <= height[i]) {
                    stk.pop();
                    res += (last.second - prev[last.first]) * (i-last.first-1);
                    // cout << i << " res="<<res<<endl;
                    if (!stk.empty())   prev[stk.top().first] = last.second;
                    if (!stk.empty())   last = stk.top();
                }
                if (last.second > height[i]) {
                    res += (height[i] - prev[last.first]) * (i-last.first-1);
                    // cout << i << " res="<<res<<endl;
                    prev[last.first] = height[i];
                }
            }
            stk.push(make_pair(i, height[i]));
        }
        return res;
    }
};

偷看答案，two pointers的方法太机智了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int trap(vector<int>& height) {
        int l = height.size();
        int res = 0;
        int left = 0, right = l-1;
        int mx = 0;
        while (left < right) {
            int lower;
            if (height[left]<height[right]) lower = height[left++];
            else lower = height[right--];
            mx = max(mx, lower);
            res += mx-lower;
        }
        return res;
    }
};