摘要：数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从算起的。列表中没有索引，这是数组与列表最大的不同点。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含。
定义：
由一个或多个确定的元素所构成的整体。
特性：
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
...值必须小于（或等于）存储在其右子树中的任何值。 1.Leetcode98. 验证二叉搜索树 法一：利用二叉树的性质，根结点的值大于左子树上的点，小于右子树上的点 const long long MAX=2e31;const long long MIN=-MAX;class Solution {public: bool isValid...
...」、「 白银 」、「 青铜 」。记录下每个人的 CSDN博客、LeetCode 主页，排名靠前的人可以得到更多的曝光。 ?【万人千题】结对编程排位赛? 如果想参加的「 第二期 」的同学，可以先联系作者加群，看看第一期的同袍...
...入门100例》(第10例) 平均数 《算法零基础100讲》(第22讲) 字符串 前言 给自己树立一个「 目标 」是非常重要的，有「 目标 」才会有「 方向 」，有「 目标 」才会有「 动力 」，有「 目标 」才会有「 人生的意义 」。有了...
...法写的全面还是需要考虑到很多方面的。1）数组中的是字符串类型，要进行数据类型转换 parseInt() 。 2）两个操作数进行运算时，第二个出栈的操作数在前，第一个出栈的操作数在后（注意除法）。 3）对于浮点型数据，只取小...
阅读 2383·2021-11-25 09:43
阅读 1786·2021-11-18 13:25
阅读 1794·2021-11-15 11:38
阅读 3184·2021-10-14 09:43
阅读 1801·2021-10-14 09:42
阅读 3256·2021-09-22 15:52
阅读 1342·2021-09-22 15:49
阅读 1916·2019-08-30 15:54
