the-method-of-programming-1

1.1的举一反三

单词翻转

1
2
Input："I am a student."
Output: "student. a am I"

尝试使用三步反转，按空格分词，先对每个词反转再整体反转

1
2
3
I am a student.
I ma a .tneduts
student. a am I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string reverseWord(string str)
{
    stringstream ss(str);
    string tmp;
    string result;
    ss >> tmp;
    reverse(tmp.begin(), tmp.end());
    result += tmp;

    while (ss >> tmp)
    {
        reverse(tmp.begin(), tmp.end());
        result += " ";
        result += tmp;
    }
    reverse(result.begin(), result.end());
    return result;
}

1.4

in a word, 临时变量溢出

计算机对int溢出的处理

比如一个4字节的int类型1052254545

1
2
int n = 1052254545;
int m = n * 10; //1932610858

正常情况下m应该为10522545450,但这个数的二进制位有34位，int在这里只能保存32位，所以只会保留后32位

1
2
3
4
5
//10522545450
‭10 0111 0011 0011 0001 0100 1101 0010 1010‬

//1932610858
   0111 0011 0011 0001 0100 1101 0010 1010‬

1.6 Manacher算法

12212321

$#1#2#2#1#2#3#2#1#

S[i] # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P[i] 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1

max(P[i] - 1)是原字符串中最长回文子串的长度