0%

发表于 更新于

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

哈希

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
class Solution
{
public:
    //Insert one char from stringstream
    int pos[256]{0};
    int len = 0;
    void Insert(char ch)
    {
        if (pos[ch] == 0)
        {
            pos[ch] = len + 1;
        }
        else
        {
            pos[ch] = -1;
        }
        len++;
    }
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        char t = '#';
        int min_pos = 0;
        for (int i = 0; i < 256; i++)
        {
            int current_pos = pos[i];
            if (current_pos > 0)
            {
                if (min_pos == 0 || min_pos > current_pos)
                {
                    min_pos = current_pos;
                    t = i;
                }
            }
        }
        return t;
    }
};

发表于 更新于

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

词法、状态机

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
class Solution {
public:
    bool isNumeric(char* string)
    {
        if (string == nullptr)
        {
            return false;
        }
        else
        {
            char *w = string;
            int state = 0;
            switch (state)
            {
                case 0:
                    switch (*w)
                    {
                        case '-':
                        case '+':
                            state = 1;
                            w++;
                            break;
                        case '0':
                    }
            }
        }
    }
};

发表于 更新于

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

  1. 词法：状态机
  2. dp[m, n]指模式p[0,m]与字符串s[0,n]匹配

dp[m,n]={trueif m=0 and n=0falseif m=0 and n≠0dp[m−2,n] or dp[m−1,n] ordp[m−1,n−1] and(p[m−1]=s[n] or p[m−1]=′.′)if m≥1 and p[m]=′∗′dp[m−1,n−1] and (p[m]=s[n] or p[m]=‘‘.")otherwisedp[m, n] = \begin{cases} true & if\ m=0 \ and\ n=0 \\ false & if\ m=0 \ and\ n \neq 0 \\ dp[m - 2, n]\ or\ dp[m - 1, n]\ or\\ \quad dp[m - 1, n - 1]\ and\\ \qquad (p[m - 1] = s[n]\ or\ p[m - 1] = '.') & if\ m \ge 1\ and\ p[m]='*' \\ dp[m - 1, n - 1]\ and\ (p[m] = s[n]\ or\ p[m]=``.") & otherwise \end{cases}

dp[m, n]仅仅与dp[m - 2, n], dp[m - 1, n], dp[m - 1, n - 1]有关

或，倒推，dp[m, n]指模式p[m:]与字符串s[n:]匹配

dp[m,n]={trueif m=len(p) and n=len(s)falseif m=len(p) and n≠len(s)dp[m+2,n] or (p[m]=s[n] or p[m]=′.′) and (dp[m+2,n+1] or dp[m,n+1])if m<len(p) and p[m+1]=′∗′dp[m+1,n+1] and (p[m]=s[n] or p[m]=′.′)otherwisedp[m, n] = \begin{cases} true & if\ m = len(p) \ and\ n = len(s) \\ false & if\ m = len(p) \ and\ n \neq len(s) \\ dp[m + 2, n]\ or\ (p[m] = s[n]\ or\ p[m] = '.') \\ \quad \ and\ (dp[m + 2, n + 1]\ or\ dp[m, n + 1]) & if\ m \lt len(p)\ and\ p[m + 1] = '*' \\ dp[m + 1, n + 1]\ and\ (p[m] = s[n]\ or\ p[m]='.') & otherwise \end{cases} 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 注：以下程序在GCC及Clang++ 3.x下，用例"a","a."中行为异常，在Clang++更高版本中没有问题
class Solution {
public:
    bool match(const char* str, const char* pattern)
    {
        if (str == nullptr || pattern == nullptr)
        {
            return false;
        }
        else
        {
            const int sl = strlen(str);
            const int pl = strlen(pattern);
            if (sl != 0 && pl == 0)
            {
                return false;
            }
            else
            {
                bool dp[sl + 1][pl + 1];
                memset(dp, false, sizeof(dp));
                dp[sl][pl] = true;
                for (int i = sl; i >= 0; i--)
                {
                    for (int j = pl - 1; j >= 0; j--)
                    {
                        if (j == pl - 1)
                        {
                            if (pattern[j] == str[i] || pattern[j] == '.')
                            {
                                dp[i][j] = dp[i + 1][j + 1];
                            }
                            else
                            {
                                dp[i][j] = false;
                            }
                        }
                        else
                        {
                            if (pattern[j + 1] == '*')
                            {
                                if (dp[i][j + 2])
                                {
                                    dp[i][j] = true;
                                }
                                else
                                {
                                    if (pattern[j] == str[i] || pattern[j] == '.')
                                    {
                                        if (i == sl)
                                        {
                                            dp[i][j] = dp[i][j + 2];
                                        }
                                        else
                                        {
                                            dp[i][j] =  (dp[i + 1][j + 2] || dp[i + 1][j]);
                                        }
                                    }
                                    else
                                    {
                                        dp[i][j] = false;
                                    }
                                }
                            }
                            else
                            {
                                if (pattern[j] == str[i] || (pattern[j] == '.' && str[i] != '\0'))
                                {
                                    dp[i][j] = dp[i + 1][j + 1];
                                }
                                else
                                {
                                    dp[i][j] = false;
                                }
                            }
                        }
                    }
                }
                return dp[0][0];
            }
        }
    }
};

发表于 更新于

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。

先算A[0]*A[1]*...*A[i-1]，再乘A[i+1]*...*A[n-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
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        const int size = A.size();
        if (size < 1)
        {
            return {};
        }
        else
        {
            vector<int> B(size);
            int t = 1;
            B[0] = 1;
            for (int i = 1; i < size; i++)
            {
                B[i] = B[i - 1] * A[i - 1];
            }
            for (int i = size - 2; i >= 0; i--)
            {
                t *= A[i + 1];
                B[i] *= t;
            }
            return B;
        }
    }
};

发表于 更新于

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

数字i交换至第i位

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
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    void swap(int numbers[], const int a, const int b)
    {
        int t = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = t;
    }
    bool duplicate(int numbers[], int length, int* duplication) {
        if (numbers == nullptr || length == 0)
        {
            return false;
        }
        else
        {
            for (int i = 0; i < length; i++)
            {
                while (numbers[i] != i)
                {
                    if (numbers[i] < 0 || numbers[i] >= length)
                    {
                        return false;
                    }
                    else
                    {
                        if (numbers[numbers[i]] == numbers[i])
                        {
                            *duplication = numbers[i];
                            return true;
                        }
                        else
                        {
                            swap(numbers, i, numbers[i]);
                        }
                    }
                }
            }
            return false;
        }
    }
};

发表于 更新于

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

文法、状态机

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
class Solution {
public:
    int StrToInt(string str) {
        if (str.size() == 0)
        {
            return 0;
        }
        else
        {
            auto it = str.begin();
            int result = 0, symbol;
            switch (*it)
            {
                case '-':
                    symbol = -1;
                    it++;
                    break;
                case '+':
                    symbol = 1;
                    it++;
                    break;
                default:
                    if (*it >= '0' && *it <= '9')
                    {
                        symbol = 1;
                    }
                    else
                    {
                        return 0;
                    }
            }
            for (; it != str.end(); it++)
            {
                if (*it >= '0' && *it <= '9')
                {
                    result *= 10;
                    result += (*it - '0');
                }
                else
                {
                    return 0;
                }
            }
            return symbol * result;
        }
    }
};

发表于 更新于

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

按位加，相异为1，相同且为1则进位，直至无进位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int Add(int num1, int num2)
    {
        while (num2 != 0)
        {
            const int base = num1 ^ num2;
            const int next = (num1 & num2) << 1;
            num2 = next;
            num1 = base;
        }
        return num1;
    }
};

发表于 更新于

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

移位、sizeof数组

1
2
3
4
5
6
class Solution {
public:
    int Sum_Solution(int n) {
        return sizeof(bool[n][n + 1]) >> 1;
    }
};

发表于 更新于

让小朋友们围成一个大圈。然后,随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友。哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

记初始编号为n0n_0，共NN个小朋友，第一个出列小朋友的初始编号为n0=(m−1)%Nn_0=(m-1)\%N，从其下一个初始编号为n0=m%Nn_0=m\%N的小朋友开始重新编号为新编号n1=0n_1=0，则再下一个出列小朋友为新编号n1=(m−1)%(N−1)n_1=(m-1)\%(N-1)。

对于任意小朋友，新旧编号的关系为

n1≡f0(n0)≡[n0−(m%N)]%(N−1)n_1 \equiv f_{0}(n_0) \equiv [n_0-(m\%N)]\%(N-1)

推广之

ni≡fi−1(ni−1)≡{ni−1−[m%(N−i+1)]}%(N−i)n_i \equiv f_{i-1}(n_{i-1}) \equiv \{n_{i-1}-[m\%(N-i+1)]\}\%(N-i)

反之

ni−1≡fi−1−1(ni)≡{ni+[m%(N−i+1)]}%(N−i+1)≡(ni+m)%(N−i+1)n_{i-1} \equiv f_{i-1}^{-1}(n_{i}) \equiv \{ n_i + [m\%(N-i+1)] \} \% (N - i + 1) \\ \equiv ( n_i + m ) \% (N - i + 1)

显然，最后一个小朋友即为

nN−1=0n_{N-1} = 0

即对该小朋友

0=nN−1={nN−2−[m%2]}%(N−i)=fN−1(n0)0 = n_{N-1} = \{n_{N-2}-[m\%2]\}\%(N-i)=f_{N-1}(n_0)

而最后一个小朋友初始时的编号

n0=f0−1(n1)=f0−1[f1−1(n2)]=f0−1⋯fN−2−1(nN−1)n_0 = f_0^{-1}(n_1) = f_0^{-1}[f_1^{-1}(n_2)] = f_0^{-1} \cdots f_{N-2}^{-1} (n_{N-1})

代入即

n0=f0−1⋯fN−2−1(0)n_0 = f_0^{-1} \cdots f_{N-2}^{-1}(0) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
        {
            return -1;
        }
        else
        {
            int r = 0;
            for (int i = 2; i <= n; i++)
            {
                r = (r + m) % i;
            }
            return r;
        }
    }
};

发表于 更新于

大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

不重复，且最大最小之差小于5

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
class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.size() < 5)
        {
            return false;
        }
        else
        {
            array<int, 14> c = {0};
            int min = 14, max = 0;
            for (const int n: numbers)
            {
                if (n > 0)
                {
                    c[n]++;
                    if (c[n] > 1)
                    {
                        return false;
                    }
                    else
                    {
                        if (n > max)
                        {
                            max = n;
                        }
                        if (n < min)
                        {
                            min = n;
                        }
                    }
                }
            }
            if (max - min < 5)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
};