数组和字符串
@[toc]
本文主要为LeetCode刷题学习笔记。
核心要点
集合
集合里的元素类型不一定相同。
集合里的元素没有顺序。
列表
是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。
列表最常见的表现形式有数组和链表，而栈和队列则是两种特殊类型的列表。
数组
数组与列表的区别在于索引。索引是数组中的一个重要概念，列表中没有索引这个概念。在大多数编程语言中，索引是从0算起的。
数组中元素在内存中也是连续存储的。
数组中有基本的四种操作：
- 读取元素
nums[i] // 读取第数组中的第i个元素。
- 查找元素
s1.find(s2,position) //在S1中查找子串S2, position示从从这个位置开始的字符串中找指定元素，默认为0。
//返回值为目标字符的位置，当没有找到目标字符时返回npos。
- 插入元素
s1.insert(2,"123") // 下标为2处插入“123”。
- 删除元素
s1.erase(1,3) // 删除从1开始，长度为3的子串
除此之外还有：
s1.append(s2,1,3) // 添加s2下标从1开始，长度为3的字符串到s1。
s1.swap(s2) // 交换s1，s2.
s1.assign(4,"K") // s1赋值为“KKKK"
编程实例
一维数组
合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
- 实现思想
思想也就很简单，首先按照二维数组里面的一维数组的第一个元素排序，这个时候比较上一个一维数组的末尾元素(比如[1,3]中的3)与下一个一维数组的第一个元素(比如[2,6]中的2)大小，然后判断是否要合并。
- C++实现
class Solution {
public:
static bool cmp(vector<int> num1, vector<int> num2){
return num1[0]<num2[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<2) return intervals;
sort(intervals.begin(), intervals.end(),cmp);
int n = intervals.size();
vector<vector<int>> ans;
ans.push_back(intervals[0]);
for(int i=1; i<n; ++i){
if(ans.back()[1] >= intervals[i][0]){
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
} else {
ans.push_back(intervals[i]);
}
}
return ans;
}
};
这里要注意：
static bool cmp(vector<int> num1, vector<int> num2){
return num1[0]<num2[0];
之所以要加static的原因是：使用了函数指针，而函数指针所指函数须得是静态才行。如果不加的话，报错如下：
fatal error: reference to non-static member function must be called
二维数组
旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 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]
]
- 思路
我们首先需要对其最外层循环，将每个数字旋转90度，然后进入内层循环，所以我们要循环的外层数就是N/2(for(int r=0; r<n/2;++r))；当确定了循环的层数之后，我们需要进入内层循环，内层循环的起始位置s=r，内层循环的终止位置从右边往左边看就是N-1-r。
接下来就是需要确定各个元素的位置了，刚开始起始位置的元素坐标是(r,i)。因为是按照顺时针旋转90度，所以逆时针旋转的坐标为(end-(i-s), r)，(end, end-(i-s)), (i, end)。
- C++实现
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int r=0; r<n/2;++r){
int s = r;
int end = n-1-r;
for(int i=s; i<end; i++){
int temp = matrix[r][i];
matrix[r][i] = matrix[end-(i-s)][r];
matrix[end-(i-s)][r] = matrix[end][end-(i-s)];
matrix[end][end-(i-s)] = matrix[i][end];
matrix[i][end] = temp;
}
}
}
};
对角线遍历
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
解释：
image
说明:
给定矩阵中的元素总数不会超过 100000 。
- 思路解析
我们可以知道每一条斜线上的坐标之和为一个固定的值，从0到m+n。如果我们以这个和作为大循环遍历的话(for(int s=0; s<=m+n;s++))，我们只需要去确定行或者列中的一个，我们就可以通过总和s减去行或者列得到另一个。以行为例，如果我们知道行坐标r的范围，那么s-r就是纵坐标的值。
那现在的问题就是如何确定行坐标的值。
当s小于行坐标的总数时，行坐标的最大值为s，否者为m = matrix.size()-1。程序里面表示为int max_r = min(s, m);，(对应第0列边界)。
当s很大时，大到被最后一列限制的时候，此时行坐标的最小值为s-n，否者为0。程序里面表示为int min_r = max(0, s-n)，(对应第最后一列边界)。
- C++实现
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if (matrix.empty()) return ans;
int m = matrix.size()-1;
int n = matrix[0].size()-1;
for(int s=0; s<=m+n;s++){
int min_r = max(0, s-n);
int max_r = min(s, m);
if(s%2==1){
for(int r=min_r; r<=max_r; ++r){
ans.push_back(matrix[r][s-r]);
}
} else {
for(int r=max_r; r>=min_r; --r){
ans.push_back(matrix[r][s-r]);
}
}
}
return ans;
}
};
字符串简介
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
- 解题思路
先从字符串数组中取出第一个字符strs[0]，之后从前往后取出子字符，for(int i=0;i<=strs[0].length();++i)，sub_tem = strs[0].substr(0, i);，拿到的子字符与剩余字符一一对比，如果能找到且返回的坐标是0，也就是从头开始就匹配到了，那就说明这个字符满足要求，否者循环就没必要进行下去，已经不满足要求了。
如果到最后一个都能找到的话，就说明当前这个子字串是最长公共前缀。
- C++实现
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
string ans = "";
if(n==0) return ans;
if(n==1) return strs[0];
string sub_tem;
for(int i=0;i<=strs[0].length();++i){
sub_tem = strs[0].substr(0, i);
for(int j=1;j< strs.size();++j){
if(strs[j].find(sub_tem)!=0) break;
if(j==strs.size()-1) ans.swap(sub_tem);
}
}
return ans;
}
};
翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶：
请选用 语言的用户尝试使用
额外空间复杂度的原地解法。
双指针
移除元素
给你一个数组nums 和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
- 解题思路
设定两个快慢指针slow和fast，slow指针从0开始，fast指针随着循环从0到n(数组长度)。当遇到非val值时，fast元素赋值到slow，并且++slow，为下一个赋值做准备。当循环结束，slow的值就是非val值的个数。
- C++实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int slow=0;
for(int fast=0;fast<n;++fast){
if(nums[fast]!=val){
nums[slow]=nums[fast];
++slow;
}
}
return slow;
}
};
