算法题目(二)

一些算法题的解法

Posted by Ted on March 16, 2015

11、旋转数组的最小数字

12、斐波那契数列

13、二进制中1的个数

14、求数值的整数次方

15、打印1到最大的N位数

16、在O(1)时间删除节点

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

18、获取链表中倒数第k个结点

19、反转链表

20、合并两个排序的链表

11、旋转数组的最小数字

题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为旋转。 输入一个递增的排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小元素为1.

解法一

直接遍历,找到比第0位小的数,就是最小数,时间复杂度为O(n);

int find_min(int arr[],int len)
{
    int i = 0;
    for (i = 1; i < len; i++)
    {
        if (arr[i] < arr[0])
            return arr[i];
    }
    return arr[0];
}

解法二

解法一没有利用旋转数组的特性,旋转之后的数组实际上可以划分为两个排序的子数组,而且前面的子数组的元素都是大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。利用二分法来实现O(logn)的查找。

首先每次找到数组中中间的数字mid,如果mid大于最左端left,说明最小数在mid的右侧区间,则改变left,置left为mid;如果mid小于数组右侧right,说明最小数在mid的左侧区间,则改变right为mid….当left的数字小于等于right的数字时,说明已经找到最小数,这个也是循环结束的条件

img

int find_min(int arr[],int len)
{
    if(arr == 0 || len <= 0){
        return 0;
    }
    int begin = 0;
    int end = len - 1;
    int middle;
    while(arr[begin] >= arr[end]){
        if((end - begin) == 1){
            middle = end;
            break;
        }
        middle = (begin + end)/2;
        if(arr[middle] >= arr[begin]){
            begin = middle;
        }else if(arr[middle] <= arr[end]){
            end = middle;
        }
    }
    return arr[middle];
}

12、斐波那契数列

题目:写一个函数,输入n,求斐波那契数列的第n项。斐波那契数列的定义:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

解法一

矩阵法,时间复杂度O(log2^n), 斐波那契的递推公式可以表示成如下矩阵形式,利用矩阵的分治法

img

typedef struct MTX{
    int m00;
    int m01;
    int m10;
    int m11;
}mtx;
mtx mtx0;


mtx m_multiply(mtx a, mtx b)
{
    mtx c;
    c.m00=a.m00*b.m00+a.m01*b.m10;
    c.m01=a.m00*b.m01+a.m01*b.m11;
    c.m10=a.m10*b.m00+a.m11*b.m10;
    c.m11=a.m10*b.m01+a.m11*b.m11;
    return c;
}

mtx m_power(int k)
{
    mtx m;

    if(1==k)
    {
        m=mtx0;
        return m;
    }
    else if(0==k%2)
    {
        m=m_multiply(m_power(k/2),m_power(k/2));
        return m;
    }
    else
    {
        m=m_multiply(m_power((k-1)/2),m_power((k-1)/2));
        m=m_multiply(m,mtx0);
        return m;
    }
}
int fibonacci(int n)
{
    int m;
    mtx mtx1;

    int t[2]={0, 1};
    if(n<3)
        return t[n];
    else
        mtx1=m_power(n-2);
    return mtx1.m00;
}

int main(void) {
    mtx0.m00 = 1;
    mtx0.m01 = 1;
    mtx0.m10 = 1;
    mtx0.m11 = 0;
    int n = 8;
    int m = fibonacci(n);
    printf("Fibonacci(%d)=%d", n, m);
    return 0;
}

解法二

递归,时间复杂度O(2^N)

long fibonacci(int n){
    if (n==1||n==2){
        return 1;
    }
    return fibonacci(n-2) + fibonacci(n-1);
}

解法三

循环,时间复杂度O(N)

long fibonacci(int n){
    if (n==1||n==2){
        return 1;
    }

    long prePre = 1;
    long pre = 1;
    long current = 2;
    for (int i = 3; i <= n ; i++) {
        current = prePre + pre;
        prePre = pre;
        pre = current;
    }
    return current;
}

13、二进制中1的个数

题目:请实现一个函数,输入一个整数,输出该数二进制表示中1的个数,例如把9表示成二进制是1001,有2个1,因此如果输入9,则输出2。

解法一

int bit_count(int value){
    if (value < 0){
        return 0;
    }

    int count = 0;
    while (value){
        if (value % 2 == 1){
            count ++;
        }
        value = value/2;
    }
    return count;
}

解法二

用位操作

int bit_count(int value){
    if (value < 0){
        return 0;
    }

    int count = 0;
    while (value) {
        count += value & 0x01;
        value >>= 1;
    }
    return count;
}

还有更多的位运算,求1.

14、求数值的整数次方

题目:给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

img

#include<stdio.h>
#include<math.h>
#include<stdbool.h>

bool flag = true;

//求base的正数absExp次幂
double PowerAbs(double base,unsigned int absExp)
{
	//递归退出的条件
	if(absExp == 0)
		return 1.0;
	if(absExp == 1)
		return base;
	
	//递归求次方
	double result = PowerAbs(base,absExp>>1);
		result *= result;
	//判断奇偶性
	if(absExp&1 == 1)
		result *= base;

	return result; 
}

//求base的exp次方
double Power(double base,int exp)
{
	//底数为0,指数为负数的情况
	if(fabs(base-0.0)<0.0000001 && exp<=0)
	{
		flag = false;
		return 0.0;
	}

	unsigned int absExp = (unsigned int)abs(exp);
	double result = PowerAbs(base,absExp);
	if(exp<0)
		result = 1.0/result;

	return result;
}

int main()
{
	int n,exp;
	double base;
	while(scanf("%d",&n) != EOF)
	{
		int i;
		for(i=0;i<n;i++)
		{
			//每次都要先将flag置为true
			flag = true;
			scanf("%lf %d",&base,&exp);
			double result = Power(base,exp);
			if(flag)
				printf("%.2ef\n",result);
			else
				printf("INF\n");
		}
	}
	return 0;
}

15、打印1到最大的N位数

题目:输入数字n,按顺序打印出从最1到最大的n位十进制数,比如输入3,则打印出1、2、3直到最大的三位数999.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>


// 字符串number表示一个数字,在 number上增加1
// 如果做加法溢出,则返回true;否则为false
bool Increment(char* number)
{
    bool isOverflow = false;
    int nTakeOver = 0;
    int nLength = strlen(number);

    for(int i = nLength - 1; i >= 0; i --)
    {
        int nSum = number[i] - '0' + nTakeOver;
        if(i == nLength - 1)
            nSum ++;

        if(nSum >= 10)
        {
            if(i == 0)
                isOverflow = true;
            else
            {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = '0' + nSum;
            }
        }
        else
        {
            number[i] = '0' + nSum;
            break;
        }
    }

    return isOverflow;
}


void PrintNumber(char* number)
{

    bool isBeginning0 = true;
    int nLength = strlen(number);

    for(int i = 0; i < nLength; ++ i)
    {
        if(isBeginning0 && number[i] != '0')
            isBeginning0 = false;

        if(!isBeginning0)
        {
            printf("%c", number[i]);
        }
    }

    printf("\n");
}

void Print1ToMaxOfNDigits(int n)
{
    if(n <= 0)
        return;

    char *number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';

    while(!Increment(number))
    {
        PrintNumber(number);
    }

    delete []number;
}


int main(){
    Print1ToMaxOfNDigits(2);
    return 0;
}

16、在O(1)时间删除节点

题目:给定单项链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该节点。

O(n)解法就是常规的删除链表结点的做法。从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。这种思路由于要顺序查找,时间复杂度自然就是O(n)了。

O(1)我们可以很方便的得到待删除节点的下一个节点。如果我们把下一个节点的内容复制到待删除的节点上,再把下一个节点删除掉,那是不是相当于删除了当前需要删除的节点?

#include <iostream>
using namespace std;

typedef struct LNode{
    int value;
    LNode *next;
}LNode, *List;

void InsertList(List &l, int value)//头插入节点
{
    List head;
    LNode *p=new LNode;
    p->value=value;
    if(NULL==l)
        p->next=NULL;
    else
        p->next=l;
    l=p;
}

void PrintList(List l)//打印链表
{
    LNode *p=l;
    while(p)
    {
        cout<<p->value<<" ";
        p=p->next;
    }
    cout<<endl;
}

void DeleteNode(List &l, LNode *toBeDeleted)//删除链表l中的toBeDeleted节点
{
    LNode *p;
    if(!l || !toBeDeleted)
        return;

    if(l==toBeDeleted)//若删除的节点是表头
    {
        p=l->next;
        delete toBeDeleted ;
        l=p;
    }
    else
    {
        if(toBeDeleted->next==NULL)//若删除的节点是最后一个节点
        {
            p=l;
            while(p->next!=toBeDeleted)
                p=p->next;
            p->next=NULL;
            delete toBeDeleted;
        }
        else//删除节点是中间节点
        {
            p=toBeDeleted->next;
            toBeDeleted->value=p->value;
            toBeDeleted->next=p->next;
            delete p;

        }

    }

}

int main()
{
    List l=NULL;
    LNode *p;
    int n;
    InsertList(l, 3);
    InsertList(l, 7);
    InsertList(l, 12);
    InsertList(l, 56);
    InsertList(l, 33);
    InsertList(l, 78);
    InsertList(l, 20);
    InsertList(l, 89);

    PrintList(l);
    cout<<"请输入要删除的节点:";
    cin>>n;

    p=l;
    while(p->value!=n && p)
        p=p->next;

    if(!p)
    {
        cout<<"不存在这样的节点!"<<endl;
        return 0;
    }
    else
        DeleteNode(l, p);
    cout<<"删除后的链表:";
    PrintList(l);

    return 0;

}

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

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

思路:遍历,发现偶数,与后面的奇数对调位置。

#include <stdio.h>
void Adjust(int arr[],int len)
{
    int i, j;
    for (i = 0; i < len; i++)
    {
        if ((arr[i]%2)==0)
            for (j = i + 1; j < len; j++)
            {
                int temp;
                if ((arr[j] % 2) == 1)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    break;
                }
            }
    }
}

int main()
{
    int i;
    int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 11 };
    int len = sizeof(arr) / sizeof(arr[0]);
    Adjust(arr, len);
    for (i = 0; i < len; i++)
    {
        printf("%3d", arr[i]);
    }
    printf("\n");
    return 0;
}

18、获取链表中倒数第k个结点

题目:输入一个链表,输出该链表中的倒数第k个结点。比如链表中的值为1,2,3,4,5,6。倒数第三个结点为值为4的结点。

思路:可以通过定义两个指针,第一个指针p1先走k-1步后第二个指针p2再开始走,到k步时两个指针同步走,那么当p1到底链表的结尾时,p2正好走到了第k个结点。

struct ListNode
{
  int value;
  ListNode *next;
};

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    if(pListHead == NULL || k == 0)
        return NULL;

    ListNode *pAhead = pListHead;
    ListNode *pBehind = NULL;
    for(unsigned int i = 0; i < k - 1; ++ i)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return NULL;
        }
    }
    pBehind = pListHead;
    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    return pBehind;
}

19、反转链表

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

思路:为了反转这个单链表,我们先让头结点的next域指向结点2,再让结点1的next域指向结点3,最后将结点2的next域指向结点1,就完成了第一次交换,顺序就变成了Header-结点2-结点1-结点3-结点4-NULL,然后进行相同的交换将结点3移动到结点2的前面,然后再将结点4移动到结点3的前面就完成了反转

void reverse(ListNode *head){
    ListNode* cur;
    ListNode* temp;
    cur = head->next;
    while(cur->next != NULL){
        temp = cur->next;
        cur->next = temp->next;
        temp->next = head->next;
        head->next = temp;
    }
    
    cur->next = head;//相当于成环
    head = cur->next->next;//新head变为原head的next
    cur->next->next=NULL;//断掉环
}

20、合并两个排序的链表

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1==NULL||pHead2==NULL)
        return pHead1==NULL?pHead2:pHead1;
    
    ListNode *pHead=NULL; // 新链表
    ListNode *p1=pHead1;  // 定位链表1的结点
    ListNode *p2=pHead2;  // 定位链表2的结点
    ListNode *p=pHead;    // 
    
    while(p1!=NULL&&p2!=NULL)
    {
        ListNode *q= NULL;  // 
        if(p1->value <=p2->value) // 看看插哪个点
            q=p1;
        else
            q=p2;
        if(pHead ==NULL)//初次插入结点
        {
            p=q;
            (q==p1)?(p1=p1->next):(p2=p2->next);
            p->next = NULL;
            pHead=p;//这里很重要啊!!!
        }
        else
        {
            p->next=q;
            (q==p1)?(p1=p1->next):(p2=p2->next);
            p=p->next;
            p->next=NULL;
        }
    } // 有一边已经被选完了
    
    p->next= (p1==NULL)?p2:p1;
    return pHead;
}