1

找出数组中重复的数字

class Solution{
public:
	int duplicateArray(vector<int&>nums){
		int n = nums.size();
		for(auto x: nums)
			if (x<0 ||x>=n)
				return-1;
		for(int i = 0; i < n; i++){			while(i!=nums[i]&&nums[nums[i]]!=nums[i]) swap(nums[i],nums[nums[i]]);
			if(nums[i]!=i && nums[nums[i]]==nums[i]) return nums[i];
		}
		return -1;
	}
}

• 第一层循环，如果某个数不在范围内，直接返回-1；做完循环之后，剩下的所有数都在范围内(0-n-1) 利用这个特点，每个数 最终放到正确的位置上面 00 11 ;
• 从第一个数开始遍历，把该位置上面的数字放到正确位置上，直到换到不能换为止，要么是该位置数同了，要么是找到重复的了
• 每次交换完后都会有一个数放到正确的位置上面，一共只有n个数，交换操作只会进行n次 ，整个时间复杂度 O(n) 额外空间复杂度O(1)
• 主要的思想 交换，如果当前数nums[i]没有在正确位置上面，并且正确位置上的数也不是匹配的 两者交换，直到换到不能换为止。
• 不懂 为什么要一直交换？

不修改数组找出重复的数字

长度n+1的数组。数组中所有数均在1-n范围内。抽屉原理。至少有两个苹果放到一个抽屉里。

• 思想，递归，分治

class Solution{
public:
	int duplicaeInArray(vector<int>& nums){
		int l=1,r=numsize()-1;
		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 r;
	}
}；

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成这样一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Example

{ [1,2,8,9], [2,4,9,12], [4,7,10,12], [6,8,11,15] } 如果查找的数为7 ，返回true; 如果查找的数为8,返回false

• 思路：右上角点的特殊性。 类似二分的思想，每次判断一下 当前的数和右上角的数大小关系，小的话，下边这一列就不用判断了；大的话，右上角左边的数就不用管了，整个一行；这样的话每次操作省掉一列或者一行，即行号减1或列号减1。最坏 n+m 线性的

class Solution{
public:
	bool searchArray(vector<vector<int>> array,int target){
		if(array.empty() || array[0].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;
	}
}
 

• 首先检查边界 如果它是空的，直接返回false
• 否则从右上角开始往下找 往左下角走

替换空格

把字符串中的每个空格替换成 “%20”

• 语法题
• 思路：开辟一个新的数组，从前往后遍历，遇到空格补上%20

class Solution{
public:
	string replaceSpaces(string &str){
		string res;
		for(auto x: str)
			if(x=='')
				res+="%20";
			else
				res+=x;
		return res;
	}
}

从尾到头打印链表

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());
	}
}

重建二叉树 classique

• 题目描述：输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

• 注意：二叉树中每个节点的值都互不相同；输入的前序遍历和中序遍历一定合法

• 前序遍历：根左右

• 中序遍历：左根右

• 递归的思想

• 优化：快速找出某一个数在中序遍历中的位置，哈希表的利用

BinaryTreeNode* Construct(int* preorder, int* inorder,int length)
{
	if(preorder == nullptr || inorder == nullptr || length <= 0)
		return nullptr;
 
	return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
 
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder)
{
	//前序遍历序列的第一个数字是根节点的值
	int rootValue=startPreorder[0];
	BinaryTreeNode* root = new BinaryTreeNode();
	root->m_nValue=rootValue;
	root->m_pLeft=root->m_pRight=nullptr;
 
	if(startPreorder == endPreorder)
	{
		if(startInorder==endInorder && *startPreorder == *startInorder)
			return root;
		else
			throw std::exception("Invalid input.");
	}
 
	//在中序遍历序列中找到根节点的值
	int* rootInorder=startInorder
	while(rootInorder<=endInorder && *rootInorder !=rootValue)
		++rootInorder;
 
	if(rootInorder == endInorder && *rootInorder != rootValue)
		throw std::exceptioon("Invalid input");
 
	int leftLength = rootInorder-startInorder;
	int* leftPreorderEnd = startPreorder+leftLength;
	if(leftLength>0)
	{
		//构建左子树
		root->m_pLeft = ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
	}
	if(leftLength < endPreorder-startPreorder)
	{
		//构建右子树
		root->m_pRight=ConstrucCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder)
	}
}

• 在constructcore函数中，先根据前序遍历序列的第一个数字创建根节点，接下来在中序遍历序列中找到根节点的位置，这样来确定左右子树节点的数量。前序遍历和中序遍历序列中划分了左右子树节点的值后，我们就可以递归地调用函数constructcore去分别构建它的左右子树。

二叉树的后继节点

• 题目描述：给定一棵二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
• 分情况
  1. 如果一个节点有右子树，那么它的下一个节点就是它的右子树的最左子节点。从右节点出发一直沿着指向左子节点的指针，我们就能找到它的下一个节点。
  2. 若一个节点没有右子树。并且该节点是它父节点的左子节点，那么它的下一个节点就是它的父节点
  3. 若一个节点没有右子树。并且该节点是它父亲的右子节点，那么 我们可以沿着父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。若这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。

BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
	if(pNode == nullptr)
		return nullptr;
	BinaryTreeNode* pNext = nullptr;
	if(pNode->m_pRight != nullptr)
	{
		BinaryTreeNode* pRight = pNode->m_pRight;
		while(pRight->m_pLeft != nullptr)
			pRight=pRight->m_pLeft;
 
		pNext=pRight;
	}
	else if(pNode->m_pParent != nullptr)
	{
		BinaryTreeNode* pCurrent = pNode;
		BinaryTreeNode* pParent = pNode->m_pParent;
		while(pParent != nullptr && pCurrent == pParent->m_pRight)
		{
			pCurrent=pParent;
			pParent=pParent->m_pParent;
		}
		pNext = pParent;
	}
	return pNext;
}

用两个栈实现队列

• 题目：实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。

template <typename T>class CQueue
{
public:
	CQueue(void);
	~CQueue(void);
 
	void appendTail(const T& node);
	T deleteHead();
private:
	stack<T> stack1;
	stack<T stack2;
};
 

• 操作两个先进后出的栈实现一个先进先出的队列CQueue
• 删除：当stack2不为空时，stack2中的栈顶元素是最先进入队列的元素，可以弹出；当stack2为空时，我们把stack1中的元素逐个弹出并压入stack2. 先进入队列的元素被压到stack1的底端，经过弹出和压入操作之后就处于stack2的顶端，又可以直接弹出。
• 插入： 压入stack1.

template<typename T> void CQueue<T>::appendTail(const T& element)
{
	stack1.push(element);
}
 
template<typename T> T CQueue<T>::deleteHead()
{
	if(stack2.size()<=0){
		while(stack1.size()>0)
		{
			 T& data = stack1.top();
			 stack1.pop();
			 stack2.push(data);
		}
	}
 
	if(stack2.size()==0)
		throw new exception("queue is empty");
 
	T head = stack2.top();
	stack2.pop();
}

快速排序

• 思想： 先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。

int Partition(int data[],int length,int start,int end){
	if(data == nullptr) || length <= 0 ||start < 0||end >=length)
	throw new std::exception("Invalid Parameters");
 
	int index = RandomInRange(start,end);
	Swap(&data[index],&data[end]);
 
	int small = start-1;
	for(index = start; index <end;++index)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				Swap(&data[index],&data[small]);
		}
	}
 
	++small;
	Swap(&data[small],&data[end]);
 
	return small;
 
 }
 void QuickSort(int data[],int length,int start,int end)
 {
	 if(start == end)
		 return;
	 int index = Partition(data,length,start,end);
	 if(index > start)
		 QuickSort(data,length,start,index-1);
	 if(index < end)
		 QuickSort(data,length,index+1,end)
 
 }
 

• 从左到右检查数组，每发现一个比pivot小的 就把它放到小区的末尾，pivot最后插入中间。
• 每一次partition 固定一个元素

旋转数组

• 题目：输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如：{3,4,5,1,2}为{1,2,3,4,5}的一个旋转。最小为1.
• 旋转后的数组→两个排序的子数组。前面子数组的元素大于等于后面子数组的元素
• 有序 想到二分查找，两个指针，一前一后。移动。每次查找范围缩小一半。再用更新之后的两个指针重复做新一轮的查找。
• 循环结束的条件：第一个指针前面子数组的最后一个元素，第二个指针后面子数组的第一个元素。两个指针指向相邻的两个元素，第二个指针指向的刚好是最小的元素。
• while的理解：问题是否仍然存在？

int Min(int* numbers,int length)
{
	if(numbers == nullptr || length <= 0)
		throw new std::exception("Invalid parameters");
 
	int index1 = 0;
	int index2 = length-1;
	int indexMid = index1;
	while(numbers[index1]>=numbers[index2]){
	//旋转数组的特征
 
		if(index2-index1==1)
		{
			indexMid = index2;
			break;
		}
 
		indexMid=(index1+index2)/2;
 
		//如果下标为Index1,index2,indexMid指向的三个数字相等
		//则只能顺序查找
		if(numbers[index1]==numbers[index2]&&numbers[indexMid]==numbers[index1])
			return MinInOrder(numbers,index1,index2);
 
		if(numbers[indexMid]>=numbers[index1])
			index1=indexMid;
		if(numbers[indexMid]<=numbers[index2])
			index2=indexMid;
	}
	return numbers[indexMid];
}
int MinInorder(int* numbers,int index1,int index2)
{
	int result=numbers[index1];
	for(int i=index1+1;i<=index2;++i)
	{
		if(result>numbers[i])
		result=numbers[i];
	}
}

矩阵中的路径

bool hasPath(char* matrix,int rows,int cols,char* str)
{
	if(matrix == nullptr || rows<1 || cols <1 || str == nullptr)
		return false;
 
	bool* visited = new bool[rows*cols];
	memset(visited,0,rows*cols);
 
	int pathLength = 0;
	for(int row = 0;row<rows;++row)
	{
		for(int col = 0;col<cols;++col)
		{
			if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited))
				return true;
		}
	}
	delete[] visited;
 
	return false;
}
 
bool hasPathCore(const char* matrix,int rows,int cols,int row,int col,const char*str,int& pathLength,bool* visited){
 
	if(str[pathLength] == '\0')
		return true;
 
	bool hasPath = false;
	if(row>=0&&row<rows&&col>=0&&col<cols&&matrix[row*cols+col]==str[pathLength]&&!visited[row*cols+col])
	{
		++pathLength;
		visited[row*cols+col]=true;
 
		hasPath = hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited)||hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)||hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited)||hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited);
 
		if(!hasPath)
		{
			--pathLength;
			visited[row*cols+col] = false;
		}
	}
	return hasPath;
}

机器人的运动范围

• 题目：从（0,0）开始移动，不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够达到多少个格子？

int movingCount(int threshold,int rows,int cols)
{
	if(threshold<0||rows<=0||cols<=0)
		return 0;
 
	bool* visited=new bool[rows*cols];
	for(int i=0;i<rows*cols;i++)
		visited[i]=false;
 
	int count = movingCountCore(threshold,rows,cols,0,0,visited);
 
	delete[] visited;
 
	return count;
}
 
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool* visited){
	int count=0;
	if(check(threshold,rows,cols,col,visited))
	{
		visited[row*cols+col] = true;
 
		count=1+movingCountCore(threshold,rows,cols,row-1,col,visited)+movingCountCore(threshold,rows,cols,row,col-1,visited)+movingCountCore(threshold,rows,cols,row+1,col,visited)+movingCountCore(threshold,rows,cols,row,col+1,visited);
	}
 
	return count;
}
 
bool check(int threshold,int rows,int cols,int row,int col, bool* visited)
{
 
	if(row >= 0 && row<rows && col>=0 &&col<cols && getDigitSum(row)+getDigitSum(col)<=threshold&& !visited[row*cols+col])
		return true;
 
	return false;
}
int getDigitSum(int number)
{
	int sum = 0;
	while(number>0){
		sum+=number%10;
		number/=10;
	}
	return sum;
}

二进制中1的个数

• 位运算。
• 基本思路1：先判断整数二进制表示中最右边一位是不是1；接着把输入的整数右移一位，再判断是不是1 最右位；这样每次移动一位，直到整个整数变为0为止。 如何判断一个整数的最右边是否为1？把整数和1做位与运算看结果是不是0.

int NumberOf1(int n)
{
	int count=0;
	while(n)
	{
		if(n&1)
			count++;
		n=n>>1;
	}
	return count;
}

• 这样的问题是，对于负数 右移。可能会引起死循环。负数右移，最高位要设置为1.
• 解决：不右移输入的数字n。取flag为1 （0…01），将flag不断左移，与n做与运算判断。unsigned int类型，32位 有限，当 flag 左移到所有位都被移出，变成 0 时，while 结束。‘
• 如果flag定义为int? int的最高位为符号位，左移把1移进符号位，对有符号int左移溢出，在c里是未定义行为。

int NumberOf1(int n){
	unsigned int flag=1;
	while(flag){
		if(n&flag)
			count++;
		flag=flag<<1;
	}
	return count;
}