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 n0dp[m2,n] or dp[m1,n] ordp[m1,n1] and(p[m1]=s[n] or p[m1]=.)if m1 and p[m]=dp[m1,n1] 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 nlen(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=(m1)%Nn_0=(m-1)\%N,从其下一个初始编号为n0=m%Nn_0=m\%N的小朋友开始重新编号为新编号n1=0n_1=0,则再下一个出列小朋友为新编号n1=(m1)%(N1)n_1=(m-1)\%(N-1)

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

n1f0(n0)[n0(m%N)]%(N1)n_1 \equiv f_{0}(n_0) \equiv [n_0-(m\%N)]\%(N-1)

推广之

nifi1(ni1){ni1[m%(Ni+1)]}%(Ni)n_i \equiv f_{i-1}(n_{i-1}) \equiv \{n_{i-1}-[m\%(N-i+1)]\}\%(N-i)

反之

ni1fi11(ni){ni+[m%(Ni+1)]}%(Ni+1)(ni+m)%(Ni+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)

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

nN1=0n_{N-1} = 0

即对该小朋友

0=nN1={nN2[m%2]}%(Ni)=fN1(n0)0 = n_{N-1} = \{n_{N-2}-[m\%2]\}\%(N-i)=f_{N-1}(n_0)

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

n0=f01(n1)=f01[f11(n2)]=f01fN21(nN1)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=f01fN21(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;
}
}
}
};