LeetCode思路总结(C#)
题目来自LeetCode，以及《程序员面试金典》第九章1.1-1.9
例题1.1
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
1
2
| 输入：s = "leetcode"
输出：false
|
示例 2：
提示：
- 0 <= len(s) <=100
- 如果不适用额外数据结构更好
思路1：
使用额外数据结构，通常情况下题目里是使用ASCII码表示，如果编码不是ASCII这个思路将行不通。
ASCII码一共有128个，我们可以声明一个数组，将ASCII码的编号作为数组下标来检查字符是否重复，比如’a’可以用Array[97]表示，‘A’可以用Array[65]表示
1
2
3
4
5
6
7
8
9
10
| public bool IsUnique(string astr){
int[] char_num = new int[128];
for(int i=0;i<astr.Length;i++){
char_num[astr[i]]++;
if(char_num[astr[i]]>1){
return false;
}
}
return true;
}
|
思路2：
不适用额外的数据结构，遍历字符串，每到一个字符的时候，检查剩余字符是否和当前字符相同。
1
2
3
4
5
6
7
8
9
10
| public bool IsUnique(string astr){
for(int i = 0; i < astr.Length; i++){
for(int j = i+1; j<astr.Length; j++){
if(astr[i] == astr[j]){
return false;
}
}
}
return true;
}
|
例题1.3
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例1:
1
2
| 输入："Mr John Smith ", 13
输出："Mr%20John%20Smith"
|
示例2:
1
2
| 输入：" ", 5
输出："%20%20%20%20%20"
|
提示：
思路
先计算空格数量，再通过已知的字符串实际长度计算出URL化之后的字符串长度，设定一个计数器用于记录字符在新的字符串的实际位置
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
| public string ReplaceSpaces(string S, int length)
{
int index = 0;
int space_count = 0;
for(int i = 0; i < length; i++)
{
if(S[i] == ' ')
{
space_count++;
}
}
char[] temp = new char[length + space_count*2];
for(int i = 0; i < length; i++)
{
if(S[i] == ' ')
{
temp[index++] = '%';
temp[index++] = '2';
temp[index++] = '0';
}
else
{
temp[index++] = S[i];
}
}
return new string(temp);
}
|
例题1.8
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
|
示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
|
思路
最开始的时候，通过直接遍历找到0便置0，很快便把整个数组的所有数全部置0了，很明显这么做是错的，需要将得到的0分开记录，再根据记录将原有数组的行和列置0。
通过创建y(行)和x(列)的记录，根据这两个记录进行清零
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
| public void SetZeroes(int[][] matrix)
{
bool[] y = new bool[matrix.Length];
bool[] x = new bool[matrix[0].Length];
for(int i = 0; i < y.Length; i++)
{
for(int j = 0; j < x.Length; j++)
{
if(matrix[i][j] == 0)
{
y[i] = true;
x[j] = true;
}
}
}
for(int i = 0; i < y.Length; i++)
{
if (y[i])
{
for (int j = 0; j < x.Length; j++)
{
matrix[i][j] = 0;
}
}
}
for(int j=0; j< x.Length; j++)
{
if (x[j])
{
for (int i = 0; i < y.Length; i++)
{
matrix[i][j] = 0;
}
}
}
}
|
例题 1.9
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
示例1:
1
2
| 输入：s1 = "waterbottle", s2 = "erbottlewat"
输出：True
|
示例2:
1
2
| 输入：s1 = "aa", s2 = "aba"
输出：False
|
提示：
思路
有点脑筋急转弯的意思，通过观察可以得到不管是s1还是s2，如果将s1和它本身进行拼接，必定包含s2将示例1的输入进行分解，我们可以看到waterbottle可以分成wat和erbottle两部分，s1=wat + erbottle，s2 = erbottle + wat。如果我们将s1和它本身进行拼接那么 s1 + s1 = wat + erbottle + wat + erbottle，可以看到s1 + s1 = wat + （erbottle + wat） + erbottle 里面是包含s2的，通过拼接就可以得出结果。
1
2
3
4
5
6
7
8
9
10
11
| public bool IsFlipedString(string s1, string s2)
{
if (s1.Length != s2.Length)
return false;
if (string.IsNullOrEmpty(s1) && string.IsNullOrEmpty(s2))
return true;
string doubleS2 = s2 + s2;
if (doubleS2.Contains(s1))
return true;
return false;
}
|
