在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重
复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
思路：
数组大小为n，数字范围为0~n-1,也就是说如果数组不重复，则排序后每个数组i上的元素就应该是i
为此，我们可以模拟这个排序的过程，如果i位置上的元素不为i，则把它与nums[i]位置的元素进行交换，这相当于把nums[i]放到他该去的地方。如果nums[i]位置的元素已经是i了，则这刚好就是重复的数字；否则将交换到i位置上的数字继续这个过程，如果交换过来的数等于i，则说明这个数放在了他应该放的地方，继续处理i+1上的数，如果仍然不等，则将这个换来的数放到他应该放的地方....最后，对于i位置来说，要么找到了值为i的元素，要么找到了重复的元素，是不可能出现无限循环的，因为无限循环要求换来的数字与i位置的数字相等，但这时候已经判定重复并跳出返回了。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(length<=1)
return false;
int p1=0;
while(p1<length)
{
if(numbers[p1]!=p1)
{
while(numbers[p1]!=p1)
{
int right=numbers[numbers[p1]];
if(numbers[p1]==right)
{
*duplication=right;
return true;
}
swap(numbers[numbers[p1]],numbers[p1]);
}
}
p1++;
}
return false;
}
void swap(int& a,int& b)
{
int tmp=a;
a=b;
b=tmp;
}
};
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
auto& nums=array;
if(nums.empty()||nums[0].empty())
return false;
int row=nums.size()-1;
int col=0;
while(row>=0&&col<nums[row].size())
{
if(nums[row][col]==target)
return true;
else if(nums[row][col]<target)
col++;
else
row--;
}
return false;
}
};
int pLast=len+count*2;
int pCur=len;
而不是
int pLast=len+count*2-1;
int pCur=len-1;
虽然这一种也能实现，但少了个‘\0‘,需要自己在补一个。
class Solution {
public:
void replaceSpace(char *str,int length) {
int len=length;
int count=0;
for(int i=0;i<len;i++)
{
if(str[i]==‘ ‘)
count++;
}
int pLast=len+count*2;
int pCur=len;
while(pCur>=0&&pLast>pCur)
{
if(str[pCur]!=‘ ‘)
{
str[pLast]=str[pCur];
pLast--;
}
else
{
str[pLast--]=‘0‘;
str[pLast--]=‘2‘;
str[pLast--]=‘%‘;
}
pCur--;
}
return ;
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ans;
if(!head)
return ans;
Core(ans,head);
return ans;
}
void Core(vector<int>& in,ListNode* head)
{
if(!head)
return;
Core(in,head->next);
in.push_back(head->val);
}
};
思路很清晰的题，但容易出错，多写几次注意下细节，特别是传参长度的处理。
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty()||pre.size()!=vin.size())
return NULL;
return reConstructCore(pre,vin,0,0,pre.size());
}
TreeNode* reConstructCore(vector<int>& pre,vector<int>& vin,int pstart,int vstart,int len)
{
if(len<=0)
return NULL;
int tmp=pre[pstart];
int pos=0;
for(;pos<len&&vin[pos+vstart]!=tmp;pos++);
pos+=vstart;
int left=pos-vstart;
int right=len-left-1;
TreeNode* root=new TreeNode(tmp);
root->left=reConstructCore(pre,vin,pstart+1,vstart,left);
root->right=reConstructCore(pre,vin,pstart+left+1,pos+1,right);
return root;
}
};
要考虑的情况很多，值得好好看看，体味下二叉树的结构
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(!pNode)
return NULL;
return GetNextCore(pNode);
}
TreeLinkNode* GetNextCore(TreeLinkNode* node)
{
if(!node->next)
{
auto it=node->right;
if(!it)
return NULL;
while(it->left)
it=it->left;
return it;
}
auto pLast=node->next;
if(pLast->left==node)
{
if(node->right)
{
auto right=node->right;
while(right->left)
right=right->left;
return right;
}
else
return pLast;
}
else if(pLast->right==node)
{
if(node->right)
{
auto right=node->right;
while(right->left)
right=right->left;
return right;
}
else
{
while(pLast->next&&pLast->next->right==pLast)
pLast=pLast->next;
if(pLast->next==NULL)
return NULL;
else
return pLast->next;
}
}
else
return NULL;
}
};
这个分类讨论太多了，其实完全可以简化：
1).如果该节点存在右子树，则应该遍历右子树中的最左节点
2).如果不存在，则要找到某个节点，该节点是其父的左子节点（包括目前的这个节点）
这样就简化很多了
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(!pNode)
return NULL;
auto right=pNode->right;
if(right)
{
while(right->left)
right=right->left;
return right;
}
else
{
while(pNode->next&&pNode->next->right==pNode)
pNode=pNode->next;
if(pNode->next)
return pNode->next;
else
return NULL;
}
}
};
思路：
栈的特点是先入后出，队列的特点是先入先出
现在给了两个栈，其实可以想象成这样一个情景：
Tail和Head相当于两个水管，水从tail中流入，从Head中流出，这样实际上就相当于实现了队列
我们在Tail中灌水，就相当于push进数，然后pop提出最先灌进去的数，则从Head中读出。
如果Head现在是空，也就是说没有元素，则把Tail里的数全部转到Head中，当然顺序要变化，这也就相当于上图里用个管子把两个容器相连，然后把Tail底部的水抽到Head中
每次push都push到Tail中。
class Solution
{
public:
void push(int node) {
stack2.push(node);
}
int pop() {
if(!stack1.empty())
{
auto ans=stack1.top();
stack1.pop();
return ans;
}
else
{
if(stack2.empty())
return INT_MIN;
while(!stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
auto ans=stack1.top();
stack1.pop();
return ans;
}
}
private:
stack<int> stack1;//head
stack<int> stack2;//tail
};
原文：https://www.cnblogs.com/lxy-xf/p/11516404.html