集合：
定義：
由一個或多個確定的元素所構成的整體，
特性：
1.集合里的元素型別不一定相同，
2.集合里的元素沒有順序，
事實上，這樣的集合并不直接存在于編程語言中，然而，實際編程語言中的很多資料結構，就是在集合的基礎上添加了一些規則形成的，
串列（線性串列）
定義：
一種資料項構成的有限序列，即按照一定的線性順序，排列而成的資料項的集合，
串列的概念是在集合的特征上形成的，它具有順序，且長度是可變的，
串列最常見的表現形式有陣列和鏈表，而我們熟悉的堆疊和佇列則是兩種特殊型別的串列，
陣列
如何從宏觀上區分串列和陣列呢？這里有一個重要的概念：索引，
1.陣列會用一些名為索引的數字來標識每項資料在陣列中的位置，且在大多數編程語言中，索引是從 0 算起的，我們可以根據陣列中的索引，快速訪問陣列中的元素，串列中沒有索引，這是陣列與串列最大的不同點，
2.陣列中的元素在記憶體中是連續存盤的，且每個元素占用相同大小的記憶體，串列中的元素在記憶體中可能彼此相鄰，也可能不相鄰，比如串列的另一種實作方式——鏈表，它的元素在記憶體中則不一定是連續的
1.Leetcode724.尋找陣列的中心下標
前綴和
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;
}
};
2.Leetcode35.搜索插入位置
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;
}
};
3.Leetcode56.合并區間
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 開始，我們可以將它看作一個矩陣，并處理矩陣的相關問題，
4.面試題 01.07. 旋轉矩陣
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]);
}
}
}
};
5.面試題 01.08. 零矩陣
法一：標記陣列
最容易想到了就不寫了
法二：使用兩個標記變數
我們可以用矩陣的第一行和第一列代替方法一中的兩個標記陣列，以達到 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;
}
}
}
};
6.Leetcode498. 對角線遍歷
直接模擬
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;
}
};
7.Leetcode14. 最長公共前綴
法一：橫向掃描暴力解
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;
}
};
8.Leetcode5. 最長回文子串
法一：暴力法，直接超時
class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len<2)return s;
int begin=0;
int maxlen=1;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(j-i+1>maxlen&&check(i,j,s)){
maxlen=j-i+1;
begin=i;
}
}
}
printf("%d",maxlen);
return s.substr(begin,maxlen);
}
bool check(int i,int j,string s){
int len=(j-i)/2;
for(int k=0;k<=len;k++){
if(s[i+k]!=s[j-k]){
return false;
}
}
return true;
}
};
法二：動態規劃
const int N=1010;
class Solution {
public:
bool dp[N][N];
string longestPalindrome(string s) {
int len=s.size();
if(len<2||len==2&&(s[0]==s[1]))return s;
int begin=0,end=0;
memset(dp,0,sizeof dp);
for(int i=0;i<len;i++){
dp[i][i]=true;
if(i+1<len&&s[i]==s[i+1]){
dp[i][i+1]=true;
begin=i;
end=i+1;
}
}
for(int k=2;k<len;k++){
for(int i=0;i<len;i++){
if(i+k==len)break;
if(s[i]==s[i+k]&&dp[i+1][i+k-1]){
dp[i][i+k]=true;
if(k>end-begin){
begin=i;
end=i+k;
}
}
}
}
return s.substr(begin,end-begin+1);
}
};
法三：中心擴展法
const int N=1010;
typedef pair<int,int>PII;
class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len==0||len==1)return s;
PII ans={0,0};
for(int i=0;i<len;i++){
auto t=check(i,i,s);
if(t.second-t.first>ans.second-ans.first){
ans=t;
}
t=check(i,i+1,s);
if(t.second-t.first>ans.second-ans.first){
ans=t;
}
}
return s.substr(ans.first,ans.second-ans.first+1);
}
PII check(int i,int j,string s){
PII ans;
int len=s.size();
int l=i,r=j;
while(s[l]==s[r]){
ans={l,r};
l--;
r++;
if(l<0||l>=len||r<0||r>=len)break;
}
return ans;
}
};
9.Leetcode151. 翻轉字串里的單詞
注意要去掉多余的空格
class Solution {
public:
string reverseWords(string s) {
int i=0,j=s.size()-1;
while(s[i]==' ')i++;
while(s[j]==' ')j--;
s=s.substr(i,j+1-i);
for(int i=0;i<s.size();i++){
int j=i;
while(j<s.size()&&s[j]!=' ')j++;
reverse(s.begin()+i,s.begin()+j);
if(j==s.size())break;
int p=j;
while(s[p+1]==' ')p++;
if(p!=j)s=s.substr(0,j+1)+s.substr(p+1,s.size()-p-1);
i=j;
}
reverse(s.begin(),s.end());
return s;
}
};
10.Leetcode28. 實作 strStr()
KMP
class Solution {
public:
int strStr(string haystack, string needle) {
int n=haystack.size();
int m=needle.size();
if(n==0&&m>0)return -1;
if((n==0||m==0)||haystack==needle)return 0;
int ans=0;
const int N=5e4+10;
int ne[N];
memset(ne,0,sizeof ne);
bool flag=false;
haystack=" "+haystack;
needle=" "+needle;
for(int i=2,j=0;i<=m;i++){
while(j&&needle[i]!=needle[j+1])j=ne[j];
if(needle[i]==needle[j+1])j++;
ne[i]=j;
}
for(int i=1,j=0;i<=n;i++){
while(j&&haystack[i]!=needle[j+1])j=ne[j];
if(haystack[i]==needle[j+1])j++;
if(j==m){
ans=i-m;
flag=true;
break;
}
}
if(!flag)return -1;
return ans;
}
};
11.Leetcode344. 反轉字串
class Solution {
public:
void reverseString(vector<char>& s) {
int len=s.size();
for(int i=0;i<len/2;i++){
swap(s[i],s[len-i-1]);
}
}
};
12.Leetcode561. 陣列拆分 I
直接排序，兩個一組
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
int len=nums.size();
quicksort(0,len-1,nums);
int ans=0;
for(int i=0;i<len;i+=2){
ans+=nums[i];
}
return ans;
}
void quicksort(int l,int r,vector<int>&nums){
if(l==r)return;
int x=nums[l],i=l-1,j=r+1;
while(i<j){
do{i++;}while(nums[i]<x);
do{j--;}while(nums[j]>x);
if(i<j)swap(nums[i],nums[j]);
}
quicksort(l,j,nums);
quicksort(j+1,r,nums);
}
};
13.Leetcode167. 兩數之和 II - 輸入有序陣列
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int>ans;
int len=numbers.size();
int i=0,j=len-1;
int prei=0,prej=len-1;
while(i<=j){
if(numbers[i]+numbers[j]==target){
ans.push_back(i+1);
ans.push_back(j+1);
break;
}else if(numbers[i]+numbers[j]<target){
i++;
if(i==prei)break;
prei=i;
}else{
j--;
if(j==prej)break;
prej=j;
}
}
return ans;
}
};
14.Leetcode27. 移除元素
快慢指標
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len=nums.size();
int j=0;
for(int i=0;i<len;i++){
if(nums[i]!=val)nums[j++]=nums[i];
}
return j;
}
};
15.Leetcode485. 最大連續 1 的個數
class Solution {
public:
int ans=0;
int findMaxConsecutiveOnes(vector<int>& nums) {
int len=nums.size();
for(int i=0;i<len;i++){
int j=i;
while(j<len&&nums[j]==1)j++;
ans=max(ans,j-i);
if(i!=j)i=j-1;
}
return ans;
}
};
16.Leetcode209. 長度最小的子陣列
class Solution {
public:
const int MAX=0x3f3f3f3f;
int ans=MAX;
int minSubArrayLen(int target, vector<int>& nums) {
int len=nums.size();
for(int i=0;i<len;i++){
int j=i,sum=0;
while(j<len&&sum<target){
sum+=nums[j++];
}
if(j==len&&sum<target)break;
if(sum>=target&&j-i!=0)ans=min(ans,j-i);
}
if(ans==MAX)return 0;
return ans;
}
};
17.Leetcode118. 楊輝三角
class Solution {
public:
vector<vector<int>>ans;
vector<int>line;
vector<vector<int>> generate(int numRows) {
vector<vector<int>>ans=dfs(1,numRows);
return ans;
}
vector<vector<int>>dfs(int row,int end){
vector<int>preline=line;
line.clear();
if(row==1){
line.push_back(1);
}else if(row==2){
line.push_back(1);
line.push_back(1);
}else{
int len=preline.size();
line.push_back(1);
for(int i=0;i<len-1;i++){
line.push_back(preline[i]+preline[i+1]);
}
line.push_back(1);
}
ans.push_back(line);
if(row<end)dfs(row+1,end);
return ans;
}
};
18.Leetcode119. 楊輝三角 II
class Solution {
public:
vector<int>line;
vector<int> getRow(int numRows) {
vector<int>ans=dfs(1,numRows+1);
return ans;
}
vector<int>dfs(int row,int end){
vector<int>preline=line;
line.clear();
if(row==1){
line.push_back(1);
}else if(row==2){
line.push_back(1);
line.push_back(1);
}else{
int len=preline.size();
line.push_back(1);
for(int i=0;i<len-1;i++){
line.push_back(preline[i]+preline[i+1]);
}
line.push_back(1);
}
if(row<end)dfs(row+1,end);
return line;
}
};
19. Leetcode557. 反轉字串中的單詞 III
class Solution {
public:
string reverseWords(string s) {
int len=s.size();
for(int i=0;i<len;i++){
int j=i;
while(j<len&&s[j]!=' ')j++;
reverse(s.begin()+i,s.begin()+j);
i=j;
}
return s;
}
};
20.Leetcode153. 尋找旋轉排序陣列中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int len=nums.size();
int l=0,r=len-1;
int high=nums[len-1];
while(l<r){
int mid=(l+r)/2;
if(nums[mid]<=high){
r=mid;
}else{
l=mid+1;
}
}
return nums[l];
}
};
21.Leetcode26. 洗掉有序陣列中的重復項
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len=nums.size(),j=0;
for(int i=0;i<len;i++){
if(j==0||nums[i]!=nums[j-1]){
nums[j++]=nums[i];
}
}
return j;
}
};
22.Leetcode283. 移動零
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int len=nums.size(),j=0;
for(int i=0;i<len;i++){
if(nums[i]!=0){
nums[j++]=nums[i];
}
}
for(int i=j;i<len;i++){
nums[i]=0;
}
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357253.html
標籤：其他
上一篇：用scala實作spark讀取并處理資料然后提交到mongodb案例，包含遠程除錯spark總結分享
下一篇：最大最小歸一化和反歸一化