发表于 分类于
本文字数： 373 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

只有一个元素出现奇数次，其它元素出现偶数次，异或后结果就是答案。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x=nums[0];
        for(int i=1;i<nums.size();++i)
            x ^= nums[i];
        return x;
    }
};

发表于 更新于 分类于
本文字数： 313 阅读时长 ≈ 1 分钟

今天晚上第一次看了话剧，本以为应该是一个挺无聊的一个东西。再次印证-不要轻易评价一个事物。

场景

主要由旋转舞台、强弱灯光和音效组成。两个同心圆旋转舞台，通过旋转道具和任务位置配合强弱灯光突出、切换场景及旋转视角。场景过渡自然流畅，值得称赞。

对于音效，首先给我的印象是相比普通晚会舞台音响干净、没有杂音。我还注意到一点，这种演出话筒较多，但是并没有出现除讲话人外的声音。对于这种杂音，软件算法可以很好滤除，而没有后台说话声可能是因为演员有注意或者有人控制麦克风。

表演

人物比较多。主演台词很多，但是没有任何卡顿，表情动作也很到位。整个话剧下来，非常自然流畅。

剧情

基于历史，用几个人经历展现了一段历史。不矫揉造作，内容饱满。

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟 
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
请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42
示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

以为数据比较水，结果改了好几遍，有点冗长。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    int myAtoi(string str) {
        string s;
        int flag=1;
        for(int i=0;i<str.size();++i)
        {
            while(str[i]==' ')
            {
                ++i;
                if(i>=str.size())
                    return 0;
            }
            if(str[i]!='-'&&str[i]!='+'&&!(str[i]>='0'&&str[i]<='9'))
                return 0;
            if(str[i]=='-')
            {
                flag = -1;
                ++i;
            }
            else if(str[i]=='+')
            {
                flag = 1;
                ++i;
            }
            while(str[i]=='0')
            {
                ++i;
                if(i>=str.size())
                    return 0;
            }
            while(str[i]>='0'&&str[i]<='9'&&i<str.size())
            {
                s += str[i];
                ++i;
            }
            break;
        }
        if(s.size()>10)
            return flag>0?2147483647:-2147483648;
        else if(s.size()==10)
        {
            if(flag>0)
            {
                string t = "2147483647";
                if(s>t)
                    return 2147483647;
            }
            else
            {
                string t = "2147483648";
                if(s>t)
                    return -2147483648;
            }
        }
        int sum = 0;
        int pow = 1;
        for(int i=s.size()-1;i>=0;--i)
        {
            sum += (s[i]-'0')*pow;
            pow *= 10;
        }
        return flag>0?sum:-sum;    
    }
};

发表于 分类于
本文字数： 936 阅读时长 ≈ 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
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

从左到右计算当前字符应该放在第几行，最后所有行连起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string convert(string s, int numRows) {
        string row[numRows];
        if(numRows==1)
            return s;
        for(int i=0;i<s.size();++i)
        {
            int t = i%(numRows*2-2);
            if(t<numRows)
                row[t] += s[i];
            else
                row[numRows*2-t-2] += s[i];
        }
        string res = "";
        for(int i=0;i<numRows;++i)
            res += row[i];
        return res;
    }
};

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟 
1
2
3
4
5
6
7
8
9
10
11
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

第一种普通的算法，O(n^2)

第二种manacher算法，O(n)

第一种

从中间位置向两边扩展，对于一个中间位置的扩展操作为O(n)

遍历中间位置，中间位置可能是某个字符，也可能在某两个字符之间，遍历操作复杂度O(2n)
总的时间复杂度O(n^2), 空间复杂度O(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
28
29
30
31
32
33
34
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<1)
            return "";
        int start, end, len;
        start = end = len = 0;
        for(int i=1;i<2*s.size();++i)
        {
            int l,r;
            if(i&1)
                l = r = i>>1;
            else
            {
                l = (i-1)>>1;
                r = (i+1)>>1;
            }
            while(s[l]==s[r]&&l>=0&&r<s.size())
            {
                --l;
                ++r;
            }
            --r;
            ++l;
            if(r-l+1>len)
            {
                len = r-l+1;
                start = l;
                end = r;
            }
        }
        return s.substr(start, len);
    }
};

manacher算法

解析

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
char str[3000];
int len[3000];
char res[3000];
int min(int x, int y){ return x<y?x:y;}
char* longestPalindrome(char* s) {
    int id,mx,max_len;
    id = mx = max_len = 0;
    str[0] = '$';
    int k=1;
    for(int i=0;s[i]!='\0';++i)
    {
        str[k++] = '#';
        str[k++] = s[i];
    }
    str[k++] = '#';
    str[k] = '\0';
    int start,end;
    for(int i=1;i<k;++i)
    {
        if(i<mx)
            len[i] = min(len[2*id-i], mx-i);
        else
            len[i] = 1;
        while(str[i+len[i]]==str[i-len[i]])
            ++len[i];
        if(len[i]+i>mx)
        {
            mx = len[i]+i;
            id = i;
        }
        if(len[i]-1>max_len)
        {
            max_len = len[i]-1;
            start = i-max_len;
            end = i+max_len;
        }
    }
    k = 0;
    for(int i=start;i<=end;++i)
        if(i%2==0)
            res[k++] = str[i];
    res[k] = '\0';
    return res;
}