-
调整数组顺序使奇数位于偶数前面
-
复杂链表的复制
-
二叉搜索树与双向链表
调整数组顺序使奇数位于偶数前面【数组】
题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
我的想法：创建一个新的数组，将array的奇数放进去，再遍历一次将array中的偶数放进去。
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> res;
for(int i=0;i<array.size();i++)
{
if(array[i]%2!=0) //是奇数
{
res.push_back(array[i]);
}
}
for(int i=0;i<array.size();i++)
{
if(array[i]%2==0) //是偶数
{
res.push_back(array[i]);
}
}
array=res;
}
};
smart方法：快速排序的思想
- i++往前走碰到偶数停下来，j = i+1
- 若 a[j]为偶数，j++前进，直到碰到奇数
a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移 - 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动
class Solution {
public:
void reOrderArray(vector<int> &array) {
int len = array.size();
if(len <= 1){ // 数组空或长度为1
return;
}
int i = 0;
while(i < len){
int j = i + 1;
if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
while(array[j]%2 == 0){ // j为偶数，前进
if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
return;
j++;
}
// 此时j为奇数
int count = j-i;
int temp = array[i];
array[i] = array[j];
while(count>1){
array[i+count] = array[i+count-1];//数组后移
count--;
}
array[i+1] = temp;
}
i++;
}
}
};
或者插入排序的思想：当前数是奇数，就往前找，遇到偶数就往它前面插
或者直接在vector中删除
void reOrderArray(vector<int> &array) {
int len = array.size();
vector<int> :: iterator it = array.begin();
for(int i=0;i<len;i++)
{
if(*it%2==0){
int tmp = *it;
array.erase(it);
array.push_back(tmp);
}
else
it++;
}
}
复杂链表的复制
题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
我的想法：巨恶心！！！
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
RandomListNode* p=pHead;
RandomListNode* result=new RandomListNode{0};
RandomListNode* presult=result;
int length=0;
//先把next指向配置好
while(p!=NULL)
{
length+=1; //计算链表的长度
RandomListNode* temp1=new RandomListNode{p->label};
presult->next=temp1;
presult=presult->next;
p=p->next;
}
presult=result->next; //指向要返回的链表表头
p=pHead; //指向表头
//配置random指向
int help[length]; //建立了一个数组存储的是当前节点距离random节点的距离
for(int i=0;i<length;i++)
{
if(p->random==NULL) //random指向空的时候设定为-1
{
help[i]=-1;
p=p->next;
}
else //否则就找到当前距离random的那个节点的距离长度并存储这个长度dist
{
int dist=0;
RandomListNode *q=pHead;
RandomListNode *temp2=p->random;
while(q!=temp2)
{
dist++;
q=q->next;
}
help[i]=dist;
p=p->next;
}
}
for(int i=0;i<length;i++)
{
if(help[i]==-1) //是空值就返回空
{
presult->random=NULL;
presult=presult->next;
}
else{
RandomListNode *p4=result->next;
for(int j=0;j<help[i];j++)
{
p4=p4->next;
}
presult->random=p4;
presult=presult->next;
}
}
return result->next;
}
};
smart方法：
/*
*解题思路：
*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null;
}
RandomListNode currentNode = pHead;
//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
while(currentNode != null){
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode = currentNode.next;
currentNode.next = cloneNode;
cloneNode.next = nextNode;
currentNode = nextNode;
}
currentNode = pHead;
//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
while(currentNode != null) {
currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
currentNode = currentNode.next.next;
}
//3、拆分链表，将链表拆分为原链表和复制后的链表
currentNode = pHead;
RandomListNode pCloneHead = pHead.next;
while(currentNode != null) {
RandomListNode cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
currentNode = currentNode.next;
}
return pCloneHead;
}
}
C++版本
class Solution {
public:
/*
1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
2、遍历链表，A1->random = A->random->next;
3、将链表拆分成原链表和复制后的链表
*/
RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead) return NULL;
RandomListNode *currNode = pHead;
while(currNode){
RandomListNode *node = new RandomListNode(currNode->label);
node->next = currNode->next;
currNode->next = node;
currNode = node->next;
}
currNode = pHead;
while(currNode){
RandomListNode *node = currNode->next;
if(currNode->random){
node->random = currNode->random->next;
}
currNode = node->next;
}
//拆分
RandomListNode *pCloneHead = pHead->next;
RandomListNode *tmp;
currNode = pHead;
while(currNode->next){
tmp = currNode->next;
currNode->next =tmp->next;
currNode = tmp;
}
return pCloneHead;
}
};
二叉搜索树与双向链表
题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
我的理解：二叉搜索树的性质是左孩子<根<右孩子，可以根据二叉树的性质直接利用中序遍历。（但是，没写出来...orz）
投机取巧办法！
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL;
vector<TreeNode*> list; //建立一个TreeNode类型的数组
Convert(pRootOfTree,list); //用来实现中序遍历的函数
return Convert(list); //用一个数组遍历结果
}
//中序遍历
void Convert(TreeNode* pRootOfTree,vector<TreeNode*> &list)
{
if(pRootOfTree->left!=NULL)
Convert(pRootOfTree->left,list);
list.push_back(pRootOfTree);
if(pRootOfTree->right!=NULL)
Convert(pRootOfTree->right,list);
}
//实现数组的left和right连接
TreeNode* Convert(vector<TreeNode*> list)
{
for(int i=0;i<list.size()-1;i++)
{
list[i]->right=list[i+1];
list[i+1]->left=list[i];
}
return list[0];
}
};
实际上考察的递归
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL; //找到左子树的最左边的节点（若最左节点左右子树为空，则返回这个节点）
if(pRootOfTree->left==NULL&&pRootOfTree->right==NULL)
return pRootOfTree; //否则，找到此节点的右子树的最左节点（若无左子树，则返回根节点）
//将左子树构造成双链表，并返回链表头节点
TreeNode* left=Convert(pRootOfTree->left);
TreeNode* p=left;
//定位至左子树双链表最后一个节点
//若上面定位到的节点left不为空，则说明此节点左右子树为空，则此节点是整个链表的头结点
//若定位到的节点left为空，则说明此节点的父节点存在右子树，此时应返回的值是此时根节点（此时根节点最小）
while(p!=NULL&&p->right!=NULL)
p=p->right; //想象成链表的节点一直往下在走
//如果左子树链表不为空的话，将当前root追加到左子树链表
if(left!=NULL)
{
p->right=pRootOfTree;
pRootOfTree->left=p;
}
//将右子树构造成双链表，并返回链表头节点
TreeNode* right=Convert(pRootOfTree->right);
//如果右子树链表不为空的话，将该链表追加到pRootOfTree节点之后
if(right!=NULL)
{
right->left=pRootOfTree;
pRootOfTree->right=right;
}
return left!=NULL?left:pRootOfTree;
}
};
网友评论