练习题2

发表于   |   分类于   |  

二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路

n&(n-1)会每次都减少一个数字1
例如可以通过n&(n-1)判断这个数是不是2的幂次，如果是则这值为0

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         while(n!=0)
         {
         	count++;
            n=n&(n-1);
         }
         return count;
     }
};

O(1)的时间内删除链表的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void DeleteNode(ListNode* head,ListNode* toDeNode)
{
	if(head==NULL||toDeNode==NULL)
		return;
	//当只有一个节点时
	if(head->next==NULL)
	{
		delete head;
		head=NULL;
		toDeNode=NULL;
	}
	//当要删除中间节点时
	else if(toDeNode->next!=NULL)
	{
		pNext=toDeNode->next;
		toDeNode->val=pNext->val;
		toDeNode->next=pNext->next;
		delete pNext;
		pNext=NULL;
	}
	//当要删除尾节点时，必须一步步来
	else
	{
		ListNode* pNode=head;
		while(pNode->next!=toDeNode)
		{
			pNode=pNode->next;
		}
		pNode->next=NULL;
		delete toDeNode;
		toDeNode=NULL;
	}
}

调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int isEven(int x)
{
	return (x & 1) == 0;
}

void reOrderArray(vector<int> &array) {

	
    vector<int> odd;
    vector<int> even;
    int len=array.size();
    vector<int>::iterator it;
    for(it=array.begin();it!=array.end();it++)
    {
       	if (isEven(*it))
			even.push_back(*it);
		else
			odd.push_back(*it);
    }
    array.clear();
    array.resize(len);
    int oddLen=odd.size();
    copy(odd.begin(),odd.end(),array.begin());
    copy(even.begin(),even.end(),array.begin()+oddLen);
}
};

链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    	if(pListHead==NULL||k==0)
            return NULL;
        ListNode *p=pListHead;
        ListNode *q=pListHead;
  
        for(int i=0;i<k-1;i++)
        {
            if(p->next!=NULL)
                {
                p=p->next;
            }
            else
                return NULL;
        }
        while(p->next!=NULL)
            {
            p=p->next;
            q=q->next;
        }
        return q;
        
    }
};

判断链表是否有环

用快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isloop(ListNode*head)
{
	if(head==NULL||head->next==NULL)
		return false;
	ListNode *slow=head;
	ListNode *fast=head;
	while(fast!=NULL&&fast->next!=NULL)
	{
		slow=slow->next;
		fast=fast->next->next;
		if(slow==fast)
			return true;
	}
	return false;
}

那么如何找出入口地址呢？
1
如图，为了简单起便，我们假设快指针只转了一圈，就与慢指针相遇了。此时，
慢指针走了 AB+BC
快指针走了 AB+BC+CB+BC
则，2(AB+BC)=AB+BC+CB+BC
AB=CB
则可以在相遇的时候，从表头再设置一个指针，等他们相遇的时候，就是入口处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* isloop(ListNode*head)
{
	if(head==NULL||head->next==NULL)
		return false;
	ListNode *slow=head;
	ListNode *fast=head;
	while(fast!=NULL&&fast->next!=NULL)
	{
		slow=slow->next;
		fast=fast->next->next;
		if(slow==fast)
			break;
	}
	ListNode *p=head;
	while(p!=slow)
	{
		p=p->next;
		slow=slow->next;
	}
	return p;
}

判断两个单向链表是否相交

思路

若两个链表相交，则他们从交点开始，后面都是一样的。
这样，我们就可以通过判断最后一个节点是否相同就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isCross(ListNode* head1,ListNode* head2)
{
	ListNode* p1=head1;
	ListNode* p2=head2;
	while(p1->next!=NULL)
	{
		p1=p1->next;
	}
	while(p2->next!=NULL)
	{
		p2=p2->next;
	}
	if(p1==p2)
		return true;
	else
		return false;
}

假如我们还需要找出第一个公共交点，该怎么办呢？
这里，我们可以两个链表先遍历一遍得出链表的长度，然后计算长度差值L，先在长的链表上遍历L个节点，之后再同步遍历，第一个相同的节点就是第一个公共节点。