初级算法
旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
| 给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
|
示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
|
本题相当于将矩阵转置后，再将每一行逆序。所以，先行列互换，然后将每一行逆序。
可以得到代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix[0].size();
for(int i = 0; i < n; ++i)
{
for(int j = i + 1; j < n; ++j)
{
swap(matrix[i][j], matrix[j][i]);
}
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
|
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
1
2
| 输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
|
示例 2：
1
2
| 输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
|
这题也很简单。。。只要进行逆序。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
void reverseString(vector<char>& s) {
int tempCh;
for(int i = 0; i < s.size() / 2; ++i)
{
tempCh = s[s.size() - 1 - i];
s[s.size() - 1 - i] = s[i];
s[i] = tempCh;
}
}
};
|
整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
示例 2:
示例 3:
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
这题要注意的点是，要把要返回的结果设置为long型，并且用一个long型变量接收x的值，这样可以对溢出的情况进行判断。
核心步骤：
i = 10 * i + (t % 10) i是用来存放结果t = t / 10 t是接收x的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int reverse(int x) {
long i = 0;
long t = x;
while(t)
{
i = 10*i + (t%10);
t = t/10;
}
if(i < INT_MIN || i > INT_MAX)
{
return 0;
}
return i;
}
};
|
字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
1
2
3
4
5
| s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
|
注意事项：您可以假定该字符串只包含小写字母。
建立一个unordered_map<char, int> 建立字符和其出现的次数的映射。最后找出只出现一次字符的下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> mci;
for(auto c : s)
mci[c]++;
for(int i = 0; i < s.size(); ++i)
{
if(mci[s[i]] == 1)
return i;
}
return -1;
}
};
|
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
1
2
| 输入: s = "anagram", t = "nagaram"
输出: true
|
示例 2:
1
2
| 输入: s = "rat", t = "car"
输出: false
|
说明:
你可以假设字符串只包含小写字母。
只要统计s中每个字符的出现次数，t中每个字符的出现次数，再进行比较，注意先判断两个字符串是不是一样长，如果不一样长直接返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> ms, mt;
for(auto c : s)
ms[c]++;
for(auto c : t)
mt[c]++;
if(ms.size() != mt.size())
return false;
for(auto e : ms)
{
if(e.second != mt[e.first])
return false;
}
return true;
}
};
|
验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
1
2
| 输入: "A man, a plan, a canal: Panama"
输出: true
|
示例 2:
1
2
| 输入: "race a car"
输出: false
|
先对字符串进行处理，忽略掉空格，最后在进行头尾一个一个比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isPalindrome(string s) {
if(s == "")
return true;
vector<char> cv;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] >= 'A' && s[i] <= 'Z')
cv.push_back(s[i]+32);
else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9'))
cv.push_back(s[i]);
}
for(int i = 0; i < cv.size() / 2; ++i)
{
if(cv[i] != cv[cv.size() - 1 - i])
return false;
}
return true;
}
};
|
