数组相关技术
1.这里有一些类似于数组的数据结构，但具有一些不同的属性：
字符串、哈希表(散列表)、链表、队列、栈
2.我们其实可以调用内置函数来对数组进行排序。但是，理解一些广泛使用的排序算法的原理及其复杂度是很有用的。
3.二分查找也是一种很重要的技术，用于在排序数组中搜索特定的元素。
4.我们也了解到了双指针技巧，这一技巧也可以被用来解决：
接下来做一些题目，对数组和字符串进行总结：
题目：杨辉三角
给定一个非负数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例：
1
2
3
4
5
6
7
| 输入: 5
输出:
[ [1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]
|
个人理解：
我们找规律发现，下一行是由上一行复制下来然后整体错位一个再相加。
啥意思呢，就是说，121 = 110 + 011，也就是当前值，由它上面和左上值相加。
利用动态规划就可以搞定：首先定义一个矩阵，然后全部置 0 边置 1。
然后动态方程 ans[i][j] = ans[i-1][j-1] + ans[i-1][j]。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans(numRows);
for(int i = 0; i < numRows; i++){
ans[i] = vector<int>(i+1,0);
ans[i][0] = ans[i][i] = 1;
}
if(numRows <= 2) return ans;
for(int i = 0; i < numRows; i++)
for(int j = 1; j < ans[i].size()-1; j++)
ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
return ans;
}
};
|
题目：杨辉三角 II
给定一个非负索引 k 其中 k ≤ 33，返回杨辉三角的第 k 行。
示例：
个人理解：
示例可以看出，第 k 行，是索引为 k 的行数，即 k+1 行。
还是动态规划，利用前一行和后一行的和的关系。就是开始理解复杂点。
第 k 行的最后一位肯定为 0。
第 i 位 k[i] 是将上一行的第 i 位 k-1[i] 加上一行第 i-1 位 k-1[i-1]。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> rows(rowIndex + 1);
for(int i = 0; i <= rowIndex; i++){
rows[i] = 1;
for(int j = i; j > 1; j--)
rows[j-1] = rows[j-2] + rows[j-1];
}
return rows;
}
};
|
题目：反转字符串中的单词 III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
1
2
3
| 输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
|
个人理解：
这个题一看就很眼熟，就是之前 反转字符串 和 翻转字符串中的单词 的结合体，没啥说的。
一个翻转、一个栈。
代码如下(C++):
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
| class Solution {
public:
string reverseWords(string s) {
int left = 0, right = s.size() - 1;
char tmp;
while(left <= right){
tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
left = 0, right = s.size() - 1;
stack<string> st;
string word;
while(left <= right){
char c = s[left];
if(!word.empty() && c == ' '){
st.push(word);
word = "";
}else if(c != ' ') word += c;
left++;
}
st.push(word);
string ans;
while(!st.empty()){
ans += st.top();
st.pop();
if(!st.empty()) ans += ' ';
}
return ans;
}
};
|
题目：寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
例如：数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。
请找出其中最小的元素。你可以假设数组中不存在重复元素。
示例：
1
2
3
4
5
| 输入: [3,4,5,1,2]
输出: 1
输入: [4,5,6,7,0,1,2]
输出: 0
|
个人理解：
不太明白这个题目的目的，双指针获取最小值很简单啊。看答案很多用的二分法，暂时还没学到，先用双指针做了再说。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while(left < right){
if(nums[left] > nums[right]) left++;
else right--;
}
return nums[left];
}
};
|
题目：删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1)额外空间的条件下完成。
示例：
1
2
3
4
5
| 给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
|
你不需要考虑数组中超出新长度后面的元素。
个人理解：
一看到原地，那基本就是双指针做，一个 solw 一个 fast，就可以解决，最后长度就是 slow 的坐标 +1。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(!nums.size()) return 0;
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++){
if(nums[slow] != nums[fast]){
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
};
|
题目：移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。
示例：
1
2
| 输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
|
个人理解：
看到原数组，那就是双指针了。只要不是零，就复制，然后移动，最后在末尾补零即可。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++){
if(nums[fast] != 0){
nums[slow] = nums[fast];
slow++;
}
}
for(int i = slow; i < nums.size(); i++) nums[i] = 0;
}
};
|
声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。
