再一次被OneNote击退了

印象笔记前段时间调整了收费策略, 免费账户只能同时登录两个设备, 这个就有点不爽了. 而且我也不是重度用户, 觉得并不值得为高级账户付钱, 所以想起了被传的神乎其神的OneNote.

我在装Office的时候一起装了OneNote, 所以直接打开试试, 不得不说功能可以的, 但是同步实在太过于艰难了, 在移动设备上同步更改要等很久很久, 这还是在Wi-Fi下, 在网络不好的时候岂不是完全不能用了? 而且我从印象笔记使用微软官方提供的工具导入笔记, 但是同步的时候却告诉我格式错误. Exo me? 这不是你自己导入的吗? 因为OneNote是基于OndDrive来同步的, 所以OneNote的同步问题就是OneDrive的同步问题, 我在Win10中彻底禁用OneDrive就是因为这个同步功能过于坑爹.

难道我跟微软的东西都是相性不合? 微软做的东西我就没几个是用的舒心的(少数的几个有VS, OutLook邮箱不是客户端, Windows和VS Online的Git服务), 尤其是跟网络沾边的东西, 不过这大概也不全是巨硬的锅, 毕竟我现在还生活在一个不正常国家. 另外, 相比于OneNote的类Word的编辑体验, 我更喜欢纯文本的编辑(比如Markdown), 大概是因为这给了我更大的自主性吧, 而且一些其他的高级功能我也用不上. 我现在还是用Markdown+Git来写东西和同步(BTW, 我的私人Git服务是用的微软的, 不过这该算是Git好用还是难得我用巨硬的东西用的舒服呢), 我喜欢这种每一个环节都可以彻底掌控的感觉, 只不过手机和平板上就没办法了.

最后, 折腾了几个小时OneNote最后还是浪费时间. 暂时还是用着印象笔记吧.

LeetCode 33. Search in Rotated Sorted Array

题目描述:

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).

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.

首先找到有序序列平移了多少位, 然后根据target在哪个范围内使用二分搜索.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int start = 0, end = nums.size();
        for(int i = 0; i < nums.size() - 1; i++){
            if(nums[i] > nums[i + 1]){
                start = i + 1;
                break;
            }
        }
        if(target < nums[0]){
            return binSearch(nums, start, nums.size(), target);
        }
        else{
            return binSearch(nums, 0, start ? start : nums.size(), target);
        }
    }
    
    int binSearch(vector<int> &nums, int left, int right, int target){
        int low = left, high = right, mid = (low + high) / 2;
        while(low < high){
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                high = mid;
            else
                low = mid + 1;
            
            mid = (low + high) / 2;
        }
        return -1;
    }
};

LeetCode 32. Longest Valid Parentheses

题目描述:

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

求最长的合法括号的长度, 采用先求匹配, 再求长度的方法.

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        vector<int> pStack;
        vector<bool> pMatch(s.length(), false);
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '('){
                pStack.push_back(i);
            }
            else if(pStack.empty() || s[pStack.back()] == ')'){
                pStack.push_back(i);
            }
            else{
                pMatch[i] = pMatch[pStack.back()] = true;
                pStack.pop_back();
            }
        }
        int maxLen = 0, curLen = 0;
        for(int i = 0; i < len; i++){
            if(pMatch[i]){
                curLen++;
                if(curLen > maxLen) maxLen = curLen;
            }
            else{
                curLen = 0;
            }
        }
        return maxLen;
    }
};

LeetCode 31. Next Permutation

题目描述:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

提要求输入一个数组, 返回下一个字典序比它大的排列, 如果不存在比它大的就返回最小的排列. 首先解决判断一个排列是不是最大的问题, 这个问题比较简单: 只要是这个序列是从大到小排列的, 那么它就是最大的序列. 然后再思考比较两个序列大小的问题: 从前到后逐个比较数组中的数字, 出现第一个不相等的位置, 较大的那一个序列就是字典序较大的. 然后再考虑给定一个序列获得它的下一个序列的方法, 因为随着数组下标增加, 该下标位置的数对于整个序列大小的影响是越来越小的, 因此要获得下一个排列, 应该修改尽量靠后位置的元素, 同时这个元素应该变为一个较大的值, 但是这个较大的值要在该元素之后, 因为要是与该位置之前的较大元素交换位置这个排列是变小了; 而且这个变换的目标值应该尽量小, 也就是找到该位置之后比该位置元素大的最小值. 然后是该位置之后的序列要最小, 把它们从小到大排序就可以了.

因此算法如下:

  • 判断是不是最大值
  • 从后向前查找第一个在它之后有比它大的值的元素
  • 在这个元素之后找到比它大的最小值
  • 交换之后对于该元素之后的序列从小到大排序
class Solution {
public:
    bool isBiggest(vector<int>& nums){
        if(nums.size() <= 1)
            return true;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > nums[i - 1])
                return false;
        }
        return true;
    }
    int findCloestBiggerBehind(vector<int>& nums, int pos){
        int index = pos, n = INT_MAX;
        for(int i = pos + 1; i < nums.size(); i++){
            if(nums[i] > nums[pos] && nums[i] < n){
                index = i;
                n = nums[i];
            }
        }
        return index;
    }
    void nextPermutation(vector<int>& nums) {
        if(isBiggest(nums)){
            sort(nums.begin(), nums.end());
            return;
        }
        int maxNum = INT_MIN;
        for(int i = nums.size() - 1; i >= 0; i--){
            if(nums[i] < maxNum){
                int pos = findCloestBiggerBehind(nums, i);
                int t = nums[i];
                nums[i] = nums[pos];
                nums[pos] = t;
                sort(nums.begin() + i + 1, nums.end());
                break;
            }
            maxNum = nums[i];
        }
    }
};

LeetCode 30. Substring with Concatenation of All Words

题目描述:

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:

s: “barfoothefoobarman”

words: [“foo”, “bar”]

You should return the indices: [0,9].

(order does not matter).

首先使用暴力法, 将words中的词放入一个哈希表中, 这样可以在常数时间内找到它. 然后用一个双重循环来遍历字符串s.

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int wordsLen = words.size();
        if(wordsLen == 0)
            return ret;
        int wordLen = words[0].length(), sLen = s.length(), totalLen = wordsLen * wordLen;
        
        unordered_map<string, int> wordExistOrig;
        
        for(int i = 0; i < wordsLen; i++){
            if(wordExistOrig.count(words[i])){
                wordExistOrig[words[i]]++;
            }
            else{
                wordExistOrig[words[i]] = 1;
            }
        }
        
        for(int i = 0; i <= sLen - totalLen; i++){
            unordered_map<string, int> wordExist = wordExistOrig;
            bool valid = true;
            for(int j = i; j < totalLen + i; j += wordLen){
                string str = s.substr(j, wordLen);
                if(wordExist.count(str) == 0) {
                    valid = false;
                    break;
                }
                else{
                    wordExist[str]--;
                    if(wordExist[str] < 0){
                        valid = false;
                        break;
                    }
                }
            }
            if(valid) ret.push_back(i);
        }
        
        return ret;
    }
};

还可以使用一种"滑动窗口"方法, 或者是双指针方法, 思路参考这里: http://www.2cto.com/kf/201406/311648.html. 举例来说比如题目中的例子: "barfoothefoobarman"和数组["foo", "bar"], 首先窗口长度为0, 起始位置为0, 窗口长度和起始位置都是以单词长度的整数倍变化的, 这里是3, 首先把第一个单词放进窗口(用{}来表示窗口): {bar}foothefoobarman, 由于foobar每个都只出现一次, 所以把bar的剩余次数(这个次数保存在hash表中)减1变为0, 接下来把下一个单词放入窗口: {barfoo}thefoobarman, 同样把foo的次数减1变为0, 这时窗口中已经有两个单词, 与words数组的大小相同, 就可以把当前的窗口起始位置放入结果集中. 接下来是单词the, 这个单词在words数组中没有, 所以窗口可以直接跳过它, 将窗口起始位置越过的barfoo的允许出现次数加1, 此时窗口位置位于barfoothe{}foobarman, 然后重复这个步骤. 为了不忽略类似abarfoo这种字符串中的结果, 所以要将窗口起始位置从0到单词长度3遍历一次.

代码如下, 运行时间36ms:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int wordsLen = words.size();
        if (wordsLen == 0)
            return ret;
        int wordLen = words[0].length(), sLen = s.length(), totalLen = wordsLen * wordLen;

        unordered_map<string, int> wordExist;

        for (int i = 0; i < wordsLen; i++) {
            if (wordExist.count(words[i])) {
                wordExist[words[i]]++;
            }
            else {
                wordExist[words[i]] = 1;
            }
        }
        for (int i = 0; i < wordLen; i++) {
            int slideLeft = i, j = i, wordFound = 0;

            while (slideLeft <= sLen - totalLen && j < sLen) {
                string str = s.substr(j, wordLen);
                if (wordExist.count(str) == 0) {
                    //下一个单词不再words中时将窗口初始位置移到当前之后的位置
                    j += wordLen;
                    for (; slideLeft < j; slideLeft += wordLen) {
                        string toDropStr = s.substr(slideLeft, wordLen);
                        if(wordExist.count(toDropStr))wordExist[toDropStr]++;
                    }
                    //slideLeft = j;
                    wordFound = 0;
                    continue;
                }
                if (wordFound == wordsLen) {
                    //当窗口满的时候丢弃最前端的字符串
                    string toDropStr = s.substr(slideLeft, wordLen);
                    wordExist[toDropStr]++;
                    slideLeft += wordLen;
                    wordFound--;
                }
                wordExist[str]--;
                if (wordExist[str] < 0) {
                    //当前字符串出现次数已满, 要不停的丢弃窗口最前端的字符串直到出现次数为0为止
                    while (wordExist[str] < 0) {
                        string toDropStr = s.substr(slideLeft, wordLen);
                        wordExist[toDropStr]++;
                        slideLeft += wordLen;
                        wordFound--;
                    }
                }
                wordFound++;
                if (wordFound == wordsLen) {//找到一个要求的位置
                    ret.push_back(slideLeft);
                }
                j += wordLen;
            }
            for (; slideLeft < j; slideLeft += wordLen) {
                //恢复每个单词出现的次数
                string toDropStr = s.substr(slideLeft, wordLen);
                if (wordExist.count(toDropStr)) wordExist[toDropStr]++;
            }
        }

        return ret;
    }
};

LeetCode 29. Divide Two Integers

题目描述:

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

不使用乘除和取模运算实现整数除法. 我的实现方法是使用位运算来实现二进制除法, 首先确定结果的符号位后取得被除数与除数的绝对值, 这样就可以只考虑原码不用考虑补码除法. 需要注意的是对于INT_MIN这个值(也就是-2147483648)要特殊处理, 因为它的值是这样的: 0x80000000, 也就是只有最高位是1, abs函数无法对这个值取绝对值, 而且可能造成溢出问题.

关于二进制除法可以参考这里: http://www.tyut.edu.cn/kecheng1/2008/site08/courseware/chapter1/1.2.htm

二进制数除法与十进制数除法很类似。可先从被除数的最高位开始,将被除数(或中间余数)与除数相比较,若被除数(或中间余数)大于除数,则用被除数(或中间余数)减去除数,商为1,并得相减之后的中间余数,否则商为0。再将被除数的下一位移下补充到中间余数的末位,重复以上过程,就可得到所要求的各位商数和最终的余数。

代码:

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor == 0) return INT_MAX;
        int sign = (dividend ^ divisor) & 0x80000000 ? -1 : 1;
        int absDividend = abs(dividend), absDivisor = abs(divisor);
        if(dividend == INT_MIN){
            if(divisor == -1) return INT_MAX;
            else absDividend = INT_MIN;
        }
        else{
            if(absDividend < absDivisor) return 0;
        }
        
        return sign * absDivid(absDividend, absDivisor);
    }
    
    int absDivid(unsigned int dividend, unsigned int divisor){
        int mDividend = getBit(dividend, 31), ret = 0;
        for(int i = 31; i >= 0; i--){
            if(mDividend >= divisor){
                ret |= (1 << i);A
                mDividend = mDividend - divisor;
            }
            if(i != 0){
                mDividend = (mDividend << 1) + getBit(dividend, i - 1);
            }
        }
        return ret;
    }
    
    int getBit(unsigned int n, int p){
        return n & (1 << p) ? 1 : 0;
    }
};

这段代码是默认int类型长度是4个字节.

LeetCode 28. Implement strStr()

题目描述:

Implement strStr().

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

实现查找子串函数. 使用双重循环.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int haylength = haystack.length(), needlelength = needle.length();
        if(haylength < needlelength) return -1;
        for(int i = 0; i <= haylength - needlelength; i++){
            int j;
            for(j = 0; j < needlelength; j++){
                if(haystack[i + j] != needle[j]) break;
            }
            if(j == needlelength)
                return i;
        }
        
        return -1;
    }
};

LeetCode 376. Wiggle Subsequence

题目描述:

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up: Can you do it in O(n) time?

使用动态规划, 只需要保存当前节点与之前一个节点的信息.

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int len = nums.size();
        if(len <= 2) return len;
        int maxLen = 2, diff = nums[1] - nums[0];
        for(int i = 2; i < len; i++){
            int d = nums[i] - nums[i - 1];
            if(d && diff && ((d ^ diff) & 0x80000000)){
                maxLen++;
            }
            if(d != 0){
                diff = d;
            }
        }
        return maxLen;
    }
};

关于给父母分享照片

关于照片存储备份的问题, 我现在用的Google相册, 虽然按照Google的尿性说不定哪天就给关了, 但是现在用起来还是挺方便的. 但是本来应该是主要功能的照片分享功能却由于那说是不存在但是却是确确实实无处不在的GFW的原因而变得几乎不可用. 尤其是对于我父母这样别说搭梯子, 百度云都不会用(我也不敢给他们用百度)的, 分享照片更是非常麻烦.

我先来总结一下给我父母这样的用户分享照片所需要的服务应该有什么样的特性:

  • 访问方便, 便于查找; 也就是说可生成分享链接或者与社交网络绑定
  • 国内访问速度快; 这就没有了用Google相册或者Flickr之类服务的可能
  • 稳定; 谁都不想过一段时间服务就关闭了
  • 要有相册管理功能, 至少缩略图之类应该具备
  • 免费
  • 最好有权限访问控制, 因为与父母分享的照片不少是不想公开的
  • 手机访问支持比较好

出于以上的几点, 我首先排除了国内的所有网盘, 因为它们基本都没有相册管理功能; 然后把目标划定在国内大型的互联网企业上. 至于iCloud, 小米, 华为等公司推出的云相册服务因为与要与设备绑定所以也排除. 百度家的东西排除, 网易相册的iOS客户端快三年没有更新了也不知道还能挺多久, 而且初始容量只有1G, 超出后只有每月300M, 有点不太够用. 至于阿里似乎没有推出过这种服务.

剩下的考虑企鹅, 不得不说企鹅的占有率真是厉害, 我父母手机上使用频率最高的应用就是微信了. 所以我一直用朋友圈来给父母分享一些照片. 但是这问题仍然很大, 首先是一次只能选择9张, 我一次上传一千多张根本就是不可能; 其次是微信对于图片压缩地太厉害, 基本上属于放大就不能看; 然后是没有PC端, 电脑上的许多照片不可能都传到手机上. 所以我每次都是选几张照片传上去.

直到昨天, 我突然心血来潮打开了尘封已久的QQ空间, 突然发现QQ空间相册竟然支持原图上传(其实我忘记了它以前支不支持), 并且有了只允许部分好友查看的功能. 突然觉得这就是我想要的与父母分享照片的工具. 父母都有QQ号并且可以通过手机QQ客户端查看; 可以保存原图, 不压缩画质(实测分辨率不变但是体积减少100-200kB左右, 并且不提供批量下载功能, 加上下载后会丢失EXIF信息, 因此不太适合做照片备份); 有访问权限控制; 国内访问速度有保障; 可以在PC端上传图片; 服务免费, 我现在有30G容量, 虽然不大, 但也勉强够用(而且不知道它是怎么计算容量的, 我昨天上传了1000+张3M左右的照片原图, 但是现在只显示用了0.4G).

关于安全和隐私, 企鹅虽然不能说很安全, 但是也算是有底线. 而想要隐私的话, 东西还是根本不要放到网上为好.

对我来说, 目前用QQ空间的相册功能算是给父母分享照片的最佳方案了.

STL容器学习笔记三 - Forward_list

Forward list 前向链表[C++11]

前向链表是提供常数复杂度的插入删除操作的容器, 它被实现为一个单链接链表.

forward_listlist的区别在于前者保存指向每个节点的后一个节点的指针, 而后者保存前后两个节点的指针. forward_listlist稍微高效, 但是缺点在于只能向前遍历.

与其他顺序容器相比主要优点在于在容器任意位置插入, 提取和移动的表现更好. 不足在于不能根据元素在容器中的位置来访问元素.

forward_list被设计得非常高效, 它与一个简单的C语言手写单向链表的效率相当. 实际上, 它是唯一一个出于性能考虑而不提供size成员函数的标准容器.

部分函数

只列举一些我不太熟悉的函数.

构造函数

默认构造函数

1
explicit forward_list (const allocator_type& alloc = allocator_type());

创建一个空容器. ​

填充构造函数

1
2
3
explicit forward_list (size_type n);
explicit forward_list (size_type n, const value_type& val,
const allocator_type& alloc = allocator_type());

创建一个大小为n的容器, 如果提供了val, 则n个值都初始化为val. ​

范围构造函数

1
2
3
template <class InputIterator>
forward_list (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());

[first, last)中的数据初始化.

拷贝构造函数

1
2
forward_list (const forward_list& fwdlst);
forward_list (const forward_list& fwdlst, const allocator_type& alloc);

移动构造函数

1
2
forward_list (forward_list&& fwdlst);
forward_list (forward_list&& fwdlst, const allocator_type& alloc);

除非alloc的类型与fwdlst不一致, 否则不会构造任何一个元素, 它们的所有权被直接转移.

初始化列表

1
2
forward_list (initializer_list<value_type> il,
const allocator_type& alloc = allocator_type());

forward_list::before___begin

1
2
iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;

返回指向容器中首个元素之前的元素的迭代器. 该迭代器不能解引用, 主要作为成员函数emplace_after, insert_after, erase_aftersplice_after的参数.

forward_list::emplace_after

1
2
template <class... Args>
iterator emplace_after (const_iterator position, Args&&... args);

在position的位置之后插入元素, args为插入的新元素的初始化参数.

forward_list::emplace_front

1
2
template <class... Args>
void emplace_front (Args&&... args);

在容器头部插入新元素, args为插入的新元素的初始化参数.

forward_list::erase_after

1
2
iterator erase_after (const_iterator position);
iterator erase_after (const_iterator position, const_iterator last);

删除容器中position之后的一个元素或者(position, last)范围内的元素.

forward_list::merge

1
2
3
4
5
6
void merge (forward_list& fwdlst);
void merge (forward_list&& fwdlst);
template <class Compare>
void merge (forward_list& fwdlst, Compare comp);
template <class Compare>
void merge (forward_list&& fwdlst, Compare comp);

根据指定顺序将fwdlst与当前容器合并.

forward_list::remove_if

1
2
template <class Predicate>
void remove_if (Predicate pred);

对容器中的每个元素, 执行pred(以pred(*i)的形式), 如果为true则删除该元素.

pred可以为函数指针或者函数对象.

forward_list::sort

1
2
3
void sort();
template <class Compare>
void sort (Compare comp);

排序函数, 该函数是稳定排序. 整个操作不包括任何的元素构造, 析构和复制. 元素只是在容器内移动.

时间复杂度: NlogN.

forward_list::unique

1
2
3
void unique();
template <class BinaryPredicate>
void unique (BinaryPredicate binary_pred);

删除重复元素. 这个操作只会删除与前一个元素相同的元素, 也就是说只能用于已经排序的容器.

第二种形式中的参数binary_pred以binary_pred(*i, *(i - 1))的形式调用, 此函数返回true则认为两个元素相等.

binary_pred可以为函数指针或者函数对象.