Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

数组和字符串-06

数组相关技术

1.这里有一些类似于数组的数据结构,但具有一些不同的属性:
字符串、哈希表(散列表)、链表、队列

2.我们其实可以调用内置函数来对数组进行排序。但是,理解一些广泛使用的排序算法的原理及其复杂度是很有用的。

3.二分查找也是一种很重要的技术,用于在排序数组中搜索特定的元素。

4.我们也了解到了双指针技巧,这一技巧也可以被用来解决:

  • 链表中的慢指针和快指针问题

  • 滑动窗口问题

    5.双指针技巧有时候与贪心算法有关,它可以帮助我们设计指针的移动策略。

接下来做一些题目,对数组和字符串进行总结:

题目:杨辉三角

给定一个非负数 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); // 全置 0
ans[i][0] = ans[i][i] = 1; // 边置 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 行。

示例:

1
2
输入: 3
输出: [1,3,3,1]

个人理解
示例可以看出,第 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); //根据题目,第k行,大小为 k + 1
for(int i = 0; i <= rowIndex; i++){
rows[i] = 1; // 最后一位置 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]; // 注意这里是char
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; // slow fast 双指针即可
for(int fast = 0; fast < nums.size(); fast++){
if(nums[slow] != nums[fast]){ // 不相等,slow 直接移动,然后赋值。
slow++;
nums[slow] = nums[fast];
} // 否则 fast 移动跳过重复项
}
return slow + 1; // 注意这里是是最后长度 需要 +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; // slow fast 双指针
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; // 结尾补零
}
};

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~