分享按钮对于博客来说是一个很有用的小工具, Wordpress也有很多分享插件, 但是可惜都是支持国外的社交网络, 支持国内的都许久未更新了. 现在国内比较好用的分享工具就是百度家的了, 鉴于百度劣迹斑斑, 今天我决定不用百度的分享工具而转而使用Wordpress官方出品的Jetpack工具包中的分享功能. 和绝大多数国外开发的插件一样, 这个工具默认没有国内的社交网络, 但是它有自定义分享连接的功能, 我就用这个工具来添加自己的分享按钮. 本文只介绍微信和微博的分享按钮设置方法, 其他网站都很类似, 就不在赘述了.

Wordpress版本: 4.5.3

JetPack版本: 4.1.1

本文中所有图片都使用Google服务, 如无法显示请自备梯子.

开启分享功能

在Jetpack后台中启用分享功能

设置

在设置=>共享菜单中可以设置分享按钮的外观等属性, 设置好后就可以使用它本身自带的FB, Twitter等分享功能了. 但是我想分享到微博怎么办呢? 在这里有一个"添加一个新的服务"功能, 就是自定义分享链接啦.

点击连接后弹出该窗口:

服务名称我们可以自己选择, 接下来的参数就是分享链接和图标了, 我们先来搞定分享链接.

微博分享链接

一般的分享链接都是通过URL参数传递的要分享的数据, 我们先来看看一个正常的微博分享链接长什么样. 首先随便打开一篇门户网站的文章, 比如这篇http://cul.qq.com/a/20160711/007865.htm, 找到分享按钮然后点击, 打开的URL是这样的:

http://service.weibo.com/share/share.php?url=http%3A%2F%2Fcul.qq.com%2Fa%2F20160711%2F007865.htm&appkey=&title=%A1%B6%B4%F3%D3%E3%BA%A3%CC%C4%A1%B7%B3%F6%C1%CB%CE%CA%CC%E2%A3%AC%BB%B9%CA%C7%B9%DB%D6%DA%B3%F6%C1%CB%CE%CA%CC%E2&pic=http://img1.gtimg.com/cul/pics/hv1/7/145/2096/136329382.jpg||http://img1.gtimg.com/cul/pics/hv1/56/145/2096/136329431.jpg||http://img1.gtimg.com/cul/pics/hv1/83/145/2096/136329458.jpg&ralateUid=&language=&searchPic=false

它有这样几个参数:

• url: 要分享的URL
• appkey
• title: 标题
• pic: 应该是文章图片了
• relateUid
• language
• searchPic

其中我们只要关心url和title两个参数就可以了, 尝试删除其他参数, 只保留url和title

http://service.weibo.com/share/share.php?url=http%3A%2F%2Fcul.qq.com%2Fa%2F20160711%2F007865.htm&title=%A1%B6%B4%F3%D3%E3%BA%A3%CC%C4%A1%B7%B3%F6%C1%CB%CE%CA%CC%E2%A3%AC%BB%B9%CA%C7%B9%DB%D6%DA%B3%F6%C1%CB%CE%CA%CC%E2

OK, 工作地很好. 这样我们就可以进行设置了, 把分享链接设置如下:

http://service.weibo.com/share/share.php?url=%post_full_url%&title=%post_title%

微博分享图标

直接使用Google图片搜索, 设置图片大小为16*16, 可以找到微博官方提供的图标:

http://www.sinaimg.cn/blog/developer/wiki/LOGO_16x16.png

微信分享

微信分享网页一般都是通过二维码扫描后在微信内置浏览器内打开后再分享, 因此分享到微信我们只要生成URL对应的二维码即可. 有许多在线二维码生成的网站, 我使用http://cli.im/api这个网站提供的API.

分享链接设置为http://cli.im/api/qrcode/code?text=%post_full_url%&mhid=sELPDFnok80gPHovKdI, 图标设置为https://res.wx.qq.com/zh_CN/htmledition/v2/images/favicon2e4e03.ico

最终效果

正则表达式匹配, 题目描述:

Implement regular expression matching with support for ‘.’ and ‘*’.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

这个题目我是用动态规划AC的, 主要思路是这样的: 数组dp[i][j]表示s的前i个字符(下标从0到i - 1)和p的前j个字符(下标从0到j - 1)是否匹配(p经过处理, 表示重复任意次的*单独保存在另一个数组里). 因此我们的随后结果就是要得到dp[s.size()][p.size()]. 而dp[i][j]的值为真有以下三种可能:

1. dp[i - 1][j]为真且s[i - 1]这个字符加与不加不影响匹配成立与否. 这要求p[j - 1]这个字符是被*标记的, 并且字符s[i - 1]与p[j - 1]可以匹配, 即s[i - 1] == p[j- 1]或p[j - 1] == ‘.’.
2. dp[i][j - 1]为真且p[j - 1]这个字符加与不加不影响匹配成立与否. 这要求p[j - 1]这个字符是被*标记的.
3. dp[i - 1][j - 1]为真并且s[i - 1]与p[j - 1]可以匹配, 即s[i - 1] == p[j- 1]或p[j - 1] == ‘.’.

可以得到dp[i][j] = (dp[i - 1][j] && (s[i - 1] == p[j - 1] || p[j - 1] == '.') && star[j - 1]) || (dp[i][j - 1] && (star[j - 1])) || (dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.')), 其中star[i]表示p[i]是否被*标记.

class Solution {
public:
    bool isMatch(string s, string p) {
        string e;
        vector<bool> star;
        for(int i = 0; i < p.size(); i++){
            if(p[i] == '*') star.back() = true;
            else{
                e.push_back(p[i]);
                star.push_back(false);
            }
        }
        p = e;
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        dp[0][0] = true;
        for(int i = 1; i <= p.size(); i++){
            dp[0][i] = dp[0][i - 1] && star[i - 1];
        }
        for(int i = 1; i <= s.size(); i++)
            for(int j = 1; j <= p.size(); j++){
                dp[i][j] = (dp[i - 1][j] && (s[i - 1] == p[j - 1] || p[j - 1] == '.') && star[j - 1]) || (dp[i][j - 1] && (star[j - 1])) || (dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'));
            }
        return dp[s.size()][p.size()];
    }
};

题目描述

Determine whether an integer is a palindrome. Do this without extra space.

我没有太明白这个without extra space的具体含义, 传入数据只有一个int型, 难道是要完全不使用局部变量吗? 这个要求总觉得有点匪夷所思. 忽略这一点, 这个题目还是很简单的.

代码:

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        
        long long r = 0, t = x;
        while(t > 0){
            r = r * 10 + t % 10;
            t /= 10;
        }
        
        if(x == r)
            return true;
        else
            return false;
    }
};

题目描述:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

比较简单的题目, 因为要转换的是整数, 因此只需要考虑前导空格和符号.

代码:

class Solution {
public:
    bool isNumber(char a){
        return a >= '0' && a <= '9';
    }

    int myAtoi(string str) {
        int len = str.length(), p = 0;
        if(str[0] == ' '){
            for(int i = 0; str[i] == ' '; i++) p++;
        }
        if(!(isNumber(str[p]) || str[p] == '-' || str[p] == '+'))
            return 0;
            
        int sign = 1;
        if(str[p] == '-'){
            sign = -1;
        }
        
        if(str[p] == '-' || str[p] == '+')
            p++;
            
        long long re = 0;
        len = str.length();
        for(int i = p; i < len && isNumber(str[i]); i++){
            re *= 10;
            re += str[i] - '0';
            
            if(sign > 0 && re > INT_MAX)
                return INT_MAX;
            if(sign < 0 && -re < INT_MIN)
                return INT_MIN;
        }
        
        return sign * re;
    }
};

题目描述:

Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

问题比较简单, 关键问题在于对于int类型数据表示范围的了解和对溢出的处理.

代码:

class Solution {
public:
    int reverse(int x) {
        long long re = 0;
        int sign = 1;
        if(x < 0){
            sign = -1;
            x = -x;
        }
        while(x > 0){
            re = re * 10 + ( x % 10 );
            x /= 10;
        }
        
        if(re > 0x7fffffff)
            return 0;
        
        return sign * re;
    }
};

题目描述:

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

比较简单的字符串处理, 根据给定的要求模拟即可.

class Solution {
public:
    string convert(string s, int numRows) {
        int n = numRows * 2 - 2, len = s.length(), column;
        if(len == 0)
            return string("");
        if(numRows == 1)
            return s;
        else
            column = (len / n) * 2 + 2;
        char arr[numRows][column];

        memset(arr, 0, sizeof(arr));
        for(int i = 0; i < len; i++){
            if((i % n) < numRows)
                arr[i % n][i / n * 2] = s[i];
            else
                arr[numRows - (i % n - numRows) - 2][i / n * 2+ 1] = s[i];
        }

        string re;
        for(int i = 0; i < numRows; i++){
            for(int j = 0; j < column; j++)
                if(arr[i][j] != 0)
                    re.push_back(arr[i][j]);
        }

        return re;
    }
};

题目描述:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

要求找出一个字符串中出现的最长的回文子串. 我自己没有想出什么特别好的办法, 只能用比较暴力的手段来通过. 主要思想就是遍历每一个字符, 对这个字符向两边延伸, 直到不符合回文的定义, 记录下最大值.

代码:

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length(), longestLen = 0, longestBegin;
        for(int i = 0; i < len; i++){
            bool oddInvalidFlag = false, evenInvalidFlag = false;
            for(int j = 0; i - j >= 0 && i + j + 1 < len; j++){
                if(s[i - j] != s[i + j]) oddInvalidFlag = true;
                if(s[i - j] != s[i + j + 1]) evenInvalidFlag = true;
                if(oddInvalidFlag && evenInvalidFlag)
                    break;
                if(!oddInvalidFlag && s[i - j] == s[i + j] && (j << 1) + 1 > longestLen){
                    longestLen = (j << 1) + 1;
                    longestBegin = i - j;
                }
                if(!evenInvalidFlag && s[i - j] == s[i + j + 1] && (j << 1) + 2 > longestLen){
                    longestLen = (j << 1) + 2;
                    longestBegin = i - j;
                }
            }
            int j = len - i - 1;
            if(!oddInvalidFlag && i >= j && s[i - j] == s[i + j] && (j << 1) + 1 > longestLen){
                longestLen = (j << 1) + 1;
                longestBegin = i - j;
            }
            
        }
        
        return s.substr(longestBegin, longestLen);
    }
};

以上代码对每一个字符使用了一个循环, 运行时间120ms左右. 但是如果把子串长度为奇数和偶数分开来的话, 速度反而会变快, 我想应该是特定测试数据使总得指令数变少了.

另一个版本:

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length(), longestLen = 0, longestBegin;
        for(int i = 0; i < len; i++){
            for(int j = 0; i - j >= 0 && i + j < len; j++){
                if(s[i - j] != s[i + j])
                    break;
                if((j << 1) + 1 > longestLen){
                    longestLen = (j << 1) + 1;
                    longestBegin = i - j;
                }
            }
            
            for(int j = 0; i - j >= 0 && i + j + 1 < len; j++){
                if(s[i - j] != s[i + j + 1])
                    break;
                if((j << 1) + 2 > longestLen){
                    longestLen = (j << 1) + 2;
                    longestBegin = i - j;
                }
            }
        }
        
        return s.substr(longestBegin, longestLen);
    }
};

一个优化小Trick

在最外层循环中将循环条件i < len变为i < len - longestLen / 2, Runtime可缩短近半.

更优解

根据这个帖子的方法https://discuss.leetcode.com/topic/49578/directly-reaching-the-best-solution-4ms-in-c-quite-simple, 运行时间成功缩短到4ms.

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length(), longestLen = 0, longestBegin = 0;
        int i = 0;
        while(i < len - longestLen / 2){
            int r = i, l = i;
            for(; r < len - 1 && s[r] == s[r + 1]; r++);
            i = r + 1;
            for(; l >= 0 && r < len && s[l] == s[r]; l--, r++);
            int curLen = r - l - 1;
            if(curLen > longestLen) longestLen = curLen, longestBegin = l + 1;
        }
        
        return s.substr(longestBegin, longestLen);
    }
};

说明: 判断回文子串的方法不变, 都是向两边延伸, 关键在于回文串中心的选择, for(; r < len - 1 && s[r] == s[r + 1]; r++);跳过了连续相同的字符, 这是因为连续的相同字符必然是回文串, 可以直接从这样的回文串开始向两边延伸.

题目:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

最直接方法, 合并为一个数组后进行排序, 运行时间56ms:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int i = 0 ; i < nums2.size(); i++)
            nums1.push_back(nums2[i]);
        
        int n = nums1.size();
        partial_sort(nums1.begin(), nums1.end(), nums1.end());
        if(n % 2 == 0)
            return ((double)nums1[n / 2] + (double)nums1[n / 2 - 1]) / 2;
        else
            return (double)nums1[n / 2];
        
    }
};

另一种方法是利用两个数组都是排好序的这一属性, 将两个数组看作堆, 每次pop出两个数组顶端较小的值, 直到有一半的数被pop出去, 剩下的两个顶端值就可以求得中间值.

运行速度稍有提升:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int numTotal = nums1.size() + nums2.size();
        int n = numTotal / 2;
        int p1 = 0, p2 = 0;
        if(numTotal % 2){
            while(p1 < nums1.size() && p2 < nums2.size() && p1 + p2 < n){
                if(nums1[p1] < nums2[p2]) p1++;
                else p2++;
            }
            if(p1 + p2 < n){
                if(p1 == nums1.size()){
                    while(p1 + p2 < n) p2++;
                }
                if(p2 == nums2.size()){
                    while(p1 + p2 < n) p1++;
                }
            }
            if(p1 == nums1.size()) return (double)nums2[p2];
            else if(p2 == nums2.size()) return (double)nums1[p1];
            else return (double)min(nums1[p1], nums2[p2]);
        }
        else{
            while(p1 < nums1.size() && p2 < nums2.size() && p1 + p2 < n - 1){
                if(nums1[p1] < nums2[p2]) p1++;
                else p2++;
            }
            if(p1 + p2 < n - 1){
                if(p1 == nums1.size()){
                    while(p1 + p2 < n - 1) p2++;
                }
                if(p2 == nums2.size()){
                    while(p1 + p2 < n - 1) p1++;
                }
            }
            if(p1 == nums1.size()) return (double)((nums2[p2] + nums2[p2 + 1]) / 2.0);
            else if(p2 == nums2.size()) return (double)((nums1[p1] + nums1[p1 + 1]) / 2.0);
            else{
                int t1, t2;
                if(nums1[p1] < nums2[p2]) t1 = nums1[p1++];
                else t1 = nums2[p2++];
                if(p1 == nums1.size()){
                    t2 = nums2[p2++];
                }
                else if(p2 == nums2.size()){
                    t2 = nums1[p1++];
                }
                else{
                    if(nums1[p1] < nums2[p2]) t2 = nums1[p1++];
                    else t2 = nums2[p2++];
                }
                return (double)((t1 + t2) / 2.0);
            }
        }
    }
};

题目:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

基本思路是遍历一遍字符串, 每访问到一个新字符时, 先检查有没有出现过(而一个字符有没有出现过用一个用字符的ASCII码作为索引的数组保存). 如果没有出现过(用-1表示)就记录下这个第一次出现的下标; 如果出现过, 就把子串的起始位置变为上次出现位置+1, 并把上次出现位置之前的字符设置为-1. 每次循环记录找到的最长长度.

代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int charHash[128];
        for(int i = 0; i < 128; i++)
            charHash[i] = -1;
            
        int p1 = 0, p2 = 0, maxLength = 0;
        for(; p2 < s.length(); p2++){
            if(charHash[s[p2]] == -1)
                charHash[s[p2]] = p2;
            else{
                int t = charHash[s[p2]] + 1;
                for(; p1 < t; p1++)
                    charHash[s[p2]] = -1;
                charHash[s[p2]] = p2;
            }
            
            if(p2 - p1 + 1> maxLength)
                maxLength = p2 - p1 + 1;
        }
        
        return maxLength;
    }
};

题目描述:

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

计算a的b次幂的值, 其中b很大并且用数组表示. 关键在于结果要对于1337取余, 这就意味着在计算过程中不会发生溢出问题. 根据公式:

(a * b) % n = ((a % n) * (b % n)) % n

以及

a ^ (n + m) = (a ^ n) * (a ^ m)

用b{i}表示数组b中到下标i为止的数, a ^ b{i} = ((a ^ b{i - 1}) ^ 10) * (a ^ b[i]), 把幂运算替换为乘法运算和循环, 在每一个循环体中都对结果取余. 就可以得到结果. 其中b[i]为0和第一次循环要特别处理.

代码如下, 耗时24ms:

class Solution {
    int MOD = 1337;
public:
    int superPow(int a, vector<int>& b) {
        int ret = 0;
        for(int i = 0; i < b.size(); i++){
            int t = b[i], retPowTen = 1;
            long long powT = 1;
            for(int j = 0; j < 10; j++){
                retPowTen = (retPowTen * ret) % MOD;
            }
            ret = retPowTen;
            if(t == 0){
                powT = 0;
            }
            else{
                for(int j = 0; j < t; j++){
                    powT = (powT * a) % MOD;
                }
            }
            if(powT && ret)
                ret = (ret * (powT % MOD)) % MOD;
            else if(!ret)
                ret = powT % MOD;
            else
                ret = ret % MOD;
        }
        return ret;
    }
};