- 数组是数据结构中的基本模块之一。因为字符串是由字符数组形成的，所以二者是相似的。大多数面试问题都属于这个范畴。下面为学习数组与字符串的相关心得。
一. 数组相关
-
集合：一般被定义为：由一个或多个确定的元素所构成的整体。
- 集合里的元素类型不一定相同。
- 集合里的元素没有顺序。
列表：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。
数组：读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。在计算机中，内存可以看成一些已经排列好的格子，每个格子对应一个内存地址。
Leetcode题解
<!--
寻找数组中心索引
给你一个整数数组 nums，请编写一个能够返回数组 “中心下标” 的方法。
数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心下标，返回 -1 。如果数组有多个中心下标，应该返回最靠近左边的那一个。
注意：中心下标可能出现在数组的两端。
-->
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int suml=0,sum=0;
for(int x:nums) sum+=x; #计算数组全部元素总和
for(int i=0;i<nums.size();i++)
{
#从数组最左侧开始依次减去该元素，直至左右总和相等或全部元素已遍历。
if(sum-suml-nums[i]==suml) return i;
suml+=nums[i];
}
return -1;
}
};
二维数组相关
- 二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。所以二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。
Leetcode题解
旋转矩阵
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
示例:
给定 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]
]
不占用额外内存空间能否做到？
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int temp;
int n=matrix.size();
#寻找到旋转数组的规律，很明显，每次旋转（除去中间的元素）都是4个元素轮换。
for(int i=0;i<n/2;i++){
for(int j=i;j<n-i-1;j++){
temp=matrix[i][j];
matrix[i][j]=matrix[n-j-1][i];
matrix[n-j-1][i]=matrix[n-1-i][n-j-1];
matrix[n-1-i][n-j-1]=matrix[j][n-1-i];
matrix[j][n-1-i]=temp;
}
}
}
};
字符串相关
- 字符串与数组有很多相似之处，比如使用 名称[下标] 来得到一个字符。
- 我们可能无法使用 == 来比较两个字符串。当我们使用 == 时，它实际上会比较这两个对象是否是同一个对象。
/*
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/array-and-string/ceda1/
来源：力扣（LeetCode）
*/
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string s="";
if(strs.size()==0) return s; //为空字符串则不需要求解，返回0
else if(strs.size()==1) return strs[0]; //只有一个字符串则返回该字符串
int size=strs[0].length(),i=0;
for(int i=1;i<strs.size();i++)
if(strs[i].length()<size) size=strs[i].length(); //获取最短字符串长度，防止越界
for(int j=0;j<size;j++){
for(i=0;i<strs.size()-1;i++)
if(strs[i][j]!=strs[i+1][j]) return s; //一个一个比对每一个字符串
if(i==strs.size()-1) s+=strs[0][j];
}
return s;
}
};
