摘要：数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从算起的。列表中没有索引，这是数组与列表最大的不同点。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含。
定义：
由一个或多个确定的元素所构成的整体。
特性：
1.集合里的元素类型不一定相同。
2.集合里的元素没有顺序。
事实上，这样的集合并不直接存在于编程语言中。然而，实际编程语言中的很多数据结构，就是在集合的基础上添加了一些规则形成的。
定义：
一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。
列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。
列表最常见的表现形式有数组和链表，而我们熟悉的栈和队列则是两种特殊类型的列表。
如何从宏观上区分列表和数组呢？这里有一个重要的概念：索引。
1.数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素。列表中没有索引，这是数组与列表最大的不同点。
2.数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。列表中的元素在内存中可能彼此相邻，也可能不相邻。比如列表的另一种实现方式——链表，它的元素在内存中则不一定是连续的
前缀和
class Solution {public: int pivotIndex(vector<int>& nums) { int a[10100]; memset(a,0,sizeof a); int len=nums.size(); for(int i=1;i<=len;i++){ a[i]=a[i-1]+nums[i-1]; } for(int i=1;i<=len;i++){ if(a[i-1]==a[len]-a[i]){ return i-1; } } return -1; }};class Solution {public: int searchInsert(vector<int>& nums, int target) { int len=nums.size(); int l=0,r=len-1; while(l<r){ int mid=(l+r)/2; if(nums[mid]>=target){ r=mid; }else{ l=mid+1; } } if(l==len-1&&target>nums[l])return l+1; return l; }};const int INF=-0x3f3f3f3f;class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>>ans; sort(intervals.begin(),intervals.end()); int len=intervals.size(); int begin,end; for(int i=0;i<len;i++){ vector<int>line; int a=intervals[i][0],b=intervals[i][1]; if(!i){ begin=a; end=b; } if(i&&a>end){ line.push_back(begin); line.push_back(end); ans.push_back(line); begin=a; end=b; }else if(i&&a<=end){ end=max(end,b); } if(i==len-1){ vector<int>tail; tail.push_back(begin); tail.push_back(end); ans.push_back(tail); } } return ans; }};只是将数组中的每个元素变成了一维数组
二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。
class Solution {public: void rotate(vector<vector<int>>& matrix) { int len=matrix.size(); for(int i=0;i<len;i++){ for(int j=0;j<i;j++){ swap(matrix[i][j],matrix[j][i]); } } for(int i=0;i<len;i++){ for(int j=0;j<len/2;j++){ swap(matrix[i][j],matrix[i][len-j-1]); } } }};法一：标记数组
最容易想到了就不写了
法二：使用两个标记变量
我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 00。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 00。
在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。
class Solution {public: void setZeroes(vector<vector<int>>& matrix) { int n=matrix.size(); int m=matrix[0].size(); bool row=false,col=false; for(int i=0;i<m;i++){ if(!matrix[0][i]){ row=true; break; } } for(int i=0;i<n;i++){ if(!matrix[i][0]){ col=true; break; } } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if(!matrix[i][j])matrix[0][j]=matrix[i][0]=0; } } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if(!matrix[0][j]||!matrix[i][0])matrix[i][j]=0; } } if(row){ for(int i=0;i<m;i++){ matrix[0][i]=0; } } if(col){ for(int i=0;i<n;i++){ matrix[i][0]=0; } } }};法三：使用一个标记变量
我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 00。这样，第一列的第一个元素即可以标记第一行是否出现 00。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
class Solution {public: void setZeroes(vector<vector<int>>& matrix) { int n=matrix.size(); int m=matrix[0].size(); bool col=false; //注意先列再行不然行matrix[0][0]的改变会影响到列 for(int i=0;i<n;i++){ if(!matrix[i][0]){ col=true; break; } } for(int i=0;i<m;i++){ if(!matrix[0][i]){ matrix[0][0]=0; break; } } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if(!matrix[i][j])matrix[0][j]=matrix[i][0]=0; } } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if(!matrix[0][j]||!matrix[i][0])matrix[i][j]=0; } } if(matrix[0][0]==0){ for(int i=0;i<m;i++){ matrix[0][i]=0; } } if(col){ for(int i=0;i<n;i++){ matrix[i][0]=0; } } }};直接模拟
class Solution {public: vector<int> findDiagonalOrder(vector<vector<int>>& mat) { vector<int>ans; int n=mat.size(),m=mat[0].size(); bool flag=true; int pre; pre=0; int len=m+n; for(int i=0;i<len*2-1;i++){ if(flag){ int row=pre; int col=i-pre; int b=2*len-i; while(!(row>=0&&row<n&&col>=0&&col<m)&&b--){ row--; col++; } while(row>=0&&row<n&&col>=0&&col<m){ ans.push_back(mat[row--][col++]); } pre=col; }else{ int row=i-pre; int col=pre; int b=2*len-1-i; while(!(row>=0&&row<n&&col>=0&&col<m)&&b--){ row++; col--; } while(row>=0&&row<n&&col>=0&&col<m){ ans.push_back(mat[row++][col--]); } pre=row; } flag=!flag; } return ans; }};
法一：横向扫描暴力解
class Solution {public: string longestCommonPrefix(vector<string>& strs) { string ans; int len=strs.size(); int n=strs[0].size(); for(int i=0;i<n;i++){ auto c=strs[0][i]; int j; for(j=1;j<len;j++){ if(c!=strs[j][i])break; } if(j==len){ ans+=c; }else{ return ans; } } return ans; }};法二：
看了大佬的解法，超级巧妙
字典排序后，第一个串与最后一个串差异最大，找他们两的公共前缀，就是所有子串的公共前缀
class Solution {public: string longestCommonPrefix(vector<string>& strs) { string ans; sort(strs.begin(),strs.end()); string st=strs[0],end=strs[strs.size()-1]; int len1=st.size(),len2=end.size(); int t=0; while(t<len1&&t<len2&&st[t]==end[t]){ ans+=st[t]; t++; } return ans; }};法一：暴力法，直接超时
class Solution {public: string longestPalindrome(string s) { int len=s.size(); if(len<2
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123292.html
摘要：也就是说，有个节点的平衡二叉搜索树，它的高度是。以搜索操作为例，如果二叉搜索树的高度为，则时间复杂度为。二叉搜索树的高度的确很重要。树集合，中的或者中的，是由高度平衡的二叉搜索树实现的。 ...
摘要：万人千题结对编程排位赛如果想参加的第二期的同学，可以先联系作者加群，看看第一期的同袍是如何奋斗的。 博主会带领大家进行 《C语言入门100例》 和 《算法零基础...
摘要：三结对编程排位赛四个人为一组，由队长带队刷题，每周根据这周四个人的刷题总数进行队伍间排名。万人千题结对编程排位赛如果想参加的第二期的同学，可以先联系作者加群，看看第一期的同袍是如何奋斗的。 ...
摘要：小鹿题目根据逆波兰表示法，求表达式的值。给定逆波兰表达式总是有效的。算法思路仔细观察上述的逆波兰表达式，可以发现一个规律就是每遇到一个操作符，就将操作符前的两个操作数进行运算，将结果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 题目：Evaluate ...
阅读 2514·2021-11-25 09:43
阅读 1902·2021-11-18 13:25
阅读 1898·2021-11-15 11:38
阅读 3311·2021-10-14 09:43
阅读 1927·2021-10-14 09:42
阅读 3715·2021-09-22 15:52
阅读 1520·2021-09-22 15:49
阅读 1996·2019-08-30 15:54
