LeetCode专题——《剑指offer》⽂章⽬录
下⾯只给出答案，具体题⽬请参考：
// 基于桶排序
class Solution {
public:
int findRepeatNumber(vector<int>& nums){
int length = nums.size();
if(length ==0)
return fal;
for(int i =0; i < length; i++){
if(i == nums[i])
continue;
while(i != nums[i]){
if(nums[i]== nums[nums[i]])
return nums[i];
el
swap(nums[i], nums[nums[i]]);
}
}
return-1;
}
};
/
/ 进阶题⽬是⽤⼆分法，见《剑指offer》
// 从右上⾓开始找，每次排除⼀⾏或者⼀列
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>> matrix,int target){ if(matrix.size()==0|| matrix[0].size()==0)
return fal;
int rows = matrix.size();
int cols = matrix[0].size();
int row =0;
int col = cols -1;
while(row < rows && col >=0){
if(matrix[row][col]== target)
return true;
el if(matrix[row][col]< target)
row++;
el
col--;
}
return fal;
}
};
// 或者逐⾏⼆分
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>> matrix,int target){ for(int i =0; i < matrix.size(); i++){
int low =0;
int high = matrix[i].size()-1;
while(low <= high){
int mid =(low + high)/2;
if(target > matrix[i][mid])
low = mid +1;
el if(target < matrix[i][mid])
high = mid -1;
el
return true;
}
}
return fal;
}
};
// 从后往前
class Solution {
public:
string replaceSpace(string str){
int length = str.size();
if(length <=0)
return"";
int numOfBlank =0;
for(int i =0; i < length; i++){
if(str[i]==' ')
numOfBlank++;
}
int newLength = length +2* numOfBlank;
string res(newLength,' ');
int indexOfOriginalStr = length -1;
int indexOfNewStr = newLength -1;
while(indexOfOriginalStr >=0&& indexOfNewStr >=0){
if(str[indexOfOriginalStr]==' '){
res[indexOfNewStr--]='0';
res[indexOfNewStr--]='2';
res[indexOfNewStr--]='%';
indexOfOriginalStr--;
}el{
res[indexOfNewStr--]= str[indexOfOriginalStr--];
}
}
return res;
}
};
// 递归
class Solution {
public:
vector<int>reverPrint(ListNode* head){
reverPrintRecursively(head);
return myVector;// 注意这⾥的写法
}
void reverPrintRecursively(ListNode* head){
if(head !=nullptr){
reverPrint(head->next);// 先递归打印完后⾯的节点元素 myVector.push_back(head->val);// 再打印当前元素}
}
private:
vector<int> myVector;
};
// ⽤栈也可以
// 经典分治算法
class Solution {
public:
TreeNode*buildTree(vector<int>& preorder, vector<int>& inorder){
if(preorder.size()<=0|| inorder.size()<=0|| preorder.size()!= inorder.size()){
return nullptr;
}
int length = preorder.size();
return reConstructRecursively(preorder,0, length -1, inorder,0, length -1);
}
TreeNode*reConstructRecursively(vector<int>&preorder,int preStart,int preEnd,
vector<int>&inorder,int inStart,int inEnd){
int rootVal = preorder[preStart];
TreeNode* root =new TreeNode(rootVal);
root->left = root->right =nullptr;
if(preStart == preEnd && inStart == inEnd && preorder[preStart]== inorder[inStart])//递归出⼝
return root;
int inRoot = inStart;
for(; inRoot <= inEnd; inRoot++){
if(inorder[inRoot]== rootVal)
break;
}
int leftLength = inRoot - inStart;
if(leftLength >0){
root->left =reConstructRecursively(preorder, preStart+1, preStart+leftLength, inorder, inStart, inRoot-1);
}
if(inEnd - inRoot >0){
root->right =reConstructRecursively(preorder, preStart+leftLength+1, preEnd, inorder, inRoot+1, inEnd);
}
return root;
}
};
// ⼒扣《剑指offer》专题中没有这个题
class Solution {
public:
TreeLinkNode*GetNext(TreeLinkNode* pNode)
{
if(pNode ==nullptr)
return nullptr;
TreeLinkNode* pNextNode =nullptr;
if(pNode->right !=nullptr){
TreeLinkNode* pRightNode = pNode->right;
while(pRightNode->left !=nullptr)
pRightNode = pRightNode->left;
pNextNode = pRightNode;
return pNextNode;// 之前这⾥没加return，导致错误。
}
TreeLinkNode* pParent = pNode->next;
while(pParent !=nullptr){
if(pParent->left == pNode){
pNextNode = pParent;
break;
}el if(pParent->right == pNode){
pNode = pParent;
pParent = pParent->next;
}
}
return pNextNode;
}
};
// ⽤全局变量处理异常
int g_invalidInput =fal;
class CQueue{
public:
CQueue(){
// nothing
}
void appendTail(int value){
stack1.push(value);
}
int deleteHead(){
pty()){
while(!pty()){
stack2.p());
stack1.pop();
}
}
if(!pty()){
int res = p();
stack2.pop();
return res;
}
g_invalidInput =true;// 区别是正常返回-1，还是异常返回-1 return-1;
}
private:
