1.找出數(shù)組中重復(fù)的數(shù)字
注意點(diǎn)：
- 1.有一個(gè)出現(xiàn)在0~n-1之外的就要返回-1
- 2.空值返回-1
- 3.時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)的解法
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n=nums.size();
if(n==0) return -1;
for(int i=0;i<n;i++)
{
if(nums[i]<0||nums[i]>=n) return -1;
}
for(int i=0;i<n;i++)
{
while(nums[nums[i]]!=nums[i])swap(nums[i],nums[nums[i]]);
if(nums[i]!=i) return nums[i];
}
return -1;
}
};
2.不修改數(shù)組找出重復(fù)的數(shù)字
分治+抽屜原理呵恢，將每個(gè)數(shù)的取值的區(qū)間[1, n]劃分成[1, n/2]和[n/2+1, n]兩個(gè)子區(qū)間，然后分別統(tǒng)計(jì)兩個(gè)區(qū)間中數(shù)的個(gè)數(shù)。
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l=1,r=nums.size()-1;//n+1長度的數(shù)組
while(l<r)
{
int mid=l+r>>1;//[l,mid],[mid+1,r]
int s=0;
for(auto x:nums) s+=x>=l&&x<=mid;
if(s>mid-l+1) r=mid;
else
l=mid+1;
}
return l;
}
};
3.二維數(shù)組中的查找
每一步會(huì)排除一行或者一列猾普，矩陣一共有 n 行，m 列，所以最多會(huì)進(jìn)行 n+m 步纠俭。所以時(shí)間復(fù)雜度是 O(n+m)冰木。
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
if(array.empty())return false;
int i=0,j=array[0].size()-1;
while(i<array.size()&&j>=0)
{
if(array[i][j]==target) return true;
if(array[i][j]>target) j--;
else i++;
}
return false;
}
};
4.替換空格
class Solution {
public:
string replaceSpaces(string &str) {
string res;
for(auto x:str)
{
if(x==' ')
res+="%20";
else
res+=x;
}
return res;
}
};
5.從尾到頭打印鏈表
反向迭代器漲姿勢了驮樊，vector<int>(res.rbegin(),res.rend())
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int>res;
while(head)
{
res.push_back(head->val);
head=head->next;
}
return vector<int>(res.rbegin(),res.rend());
}
};
6.重建二叉樹
class Solution {
public:
unordered_map<int,int>mp;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size();
for(int i=0;i<n;i++)
mp[inorder[i]]=i;//記錄中序遍歷中數(shù)對應(yīng)的位置
return dfs(preorder,inorder,0,n-1,0,n-1);
}
TreeNode* dfs(vector<int>& pre,vector<int>& in,int pl,int pr,int il,int ir)
{
if(il>ir) return NULL;
int k=mp[pre[pl]]-il;//中序遍歷中左子樹的數(shù)量
//重構(gòu)根節(jié)點(diǎn)
TreeNode* root=new TreeNode(pre[pl]);
//遞歸左子樹
root->left=dfs(pre,in,pl+1,pl+k,il,il+k-1);
//遞歸右子樹
root->right=dfs(pre,in,pl+k+1,pr,il+k+1,ir);
return root;
}
};
7.二叉樹的下一個(gè)節(jié)點(diǎn)
俗稱樹的后繼,給定一棵二叉樹的其中一個(gè)節(jié)點(diǎn)，請找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)片酝。
- 如果有右子樹囚衔，那么右子樹最左側(cè)結(jié)點(diǎn)就是答案
- 如果沒有右子樹，那么就一直往上找雕沿，直到找到當(dāng)前這個(gè)點(diǎn)练湿，它是它father的左子樹，那么它的father就是后繼
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
if(p->right)
{
p=p->right;
while(p->left)
p=p->left;
return p;
}
while(p->father&&p==p->father->right) p=p->father;
return p->father;
}
};
8.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
兩個(gè)棧stk與cache审轮，一個(gè)用于存肥哎，另一個(gè)用于取或者查
class MyQueue {
public:
stack<int>stk,cache;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stk.push(x);
}
void copy(stack<int>&a,stack<int>&b)
{
while(a.size())
{
b.push(a.top());
a.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
copy(stk,cache);
int res=cache.top();
cache.pop();
copy(cache,stk);
return res;
}
/** Get the front element. */
int peek() {
copy(stk,cache);
int res=cache.top();
copy(cache,stk);
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk.empty();
}
};
9.斐波那契數(shù)列
- 面試的時(shí)候能不用遞歸就不用遞歸
class Solution {
public:
int res=0;
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
return res=Fibonacci(n-1)+Fibonacci(n-2);
}
};
- 首選dp
class Solution {
public:
int Fibonacci(int n) {
int dp[n+10];
dp[0]=0;
dp[1]=1;
dp[2]=1;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
10.矩陣中的路徑
dfs+回溯，注意邊界條件的順序
class Solution {
public:
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool hasPath(vector<vector<char>>& matrix, string &str) {
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[i].size();j++)
if(dfs(matrix,str,0,i,j))
return true;
return false;
}
bool dfs(vector<vector<char>>&matrix,string &str,int u,int x,int y)
{
if(matrix[x][y]!=str[u])
return false;
if(u==str.size()-1)
return true;
char t=matrix[x][y];
matrix[x][y]='*';
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<matrix.size()&&b>=0&&b<matrix[0].size())
if(dfs(matrix,str,u+1,a,b))
return true;
}
matrix[x][y]=t;
return false;
}
};
