剑指offer11-15笔试题

文章目录

- 11.数值的整数次方
- ==12.打印1到最大的n位数(不太熟)==
- ==13.在O(1)时间内删除链表结点==
- 14.调整数组顺序使奇数位于偶数前面
- 15.链表中倒数第k个结点

11.数值的整数次方

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

完善的思路1:

(1) 判断非法输入:底数为0,指数为负数

(2) 指数为正,直接循环计算

(3) 指数为负,先按照其绝对值计算结果,再取反

(4) 判断一个浮点数等于零由于计算机精度问题不能直接用 double = = 0 ,

可通过一个极小的范围来判断是否为零.

class Solution {
public:
    bool g_InvalidInput = false;
    double Power(double base, int exponent) 
    {
        if(euqalToZero(base) && exponent<0)
        {
            g_InvalidInput = true;
            return 0.0;
        }
        
        unsigned int absExponent = (exponent < 0)?
                        (unsigned int)(-exponent):
                         (unsigned int)(exponent);
        
        double result = PowerWithUnignedExponent(base,absExponent);
        if(exponent < 0)
            return 1.0/result;
        else
            return result;
    }
    bool euqalToZero(double base)
    {
        if((base - 0.0 > -0.000001) && (base - 0.0 < 0.000001))
            return true;
        else
            return false;
    }
    double PowerWithUnignedExponent(double base,int exponent)
    {
        double result = 1.0;
        for(int i=0; i<exponent; ++i)
            result *= base;
        return result;
    }
};

** 惊艳的思路2:**

(1) 指数为偶:

a^8 = a^4 * a^4

a^4 = a^2 * a^2

a^2 = a^1 * a^1

(2) 指数为奇:

a^9 = a^4 * a^4 *a

a^4 = a^2 * a^2

a^2 = a^1 * a^1

使用位移运算代替除法,用为与运算判断是否为奇

class Solution {
public:
    bool g_InvalidInput = false;
    double Power(double base, int exponent) 
    {
        if(euqalToZero(base) && exponent<0)
        {
            g_InvalidInput = true;
            return 0.0;
        }
        
        unsigned int absExponent = (exponent < 0)?
                        (unsigned int)(-exponent):
                         (unsigned int)(exponent);
        
        double result = PowerWithUnignedExponent(base,absExponent);
        if(exponent < 0)
            return 1.0/result;
        else
            return result;
    }
    bool euqalToZero(double base)
    {
        if((base - 0.0 > -0.000001) && (base - 0.0 < 0.000001))
            return true;
        else
            return false;
    }
    double PowerWithUnignedExponent(double base,int exponent)
    {
        if(exponent == 0)
            return 1.0;
        if(exponent == 1)
            return base;
        
        double result = PowerWithUnignedExponent(base,exponent>>1);
        result *= result;
        if(exponent & 0x1)
            result *= base;
        return result;
    }
};

12.打印1到最大的n位数(不太熟)

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

思路1:

#include<iostream>
#include<cstring>
using namespace std;
//打印出每个大数
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)
			cout<<number[i];
	}
	cout<<"\t";
}
//从[0]-->[n-1] 逐个填入数字
void print1ToMaxDigitsRecursively(char * number,int length,int index)
{
	if(index == length-1)
	{
		printNumber(number);
		return;
	}
	for(int i=0; i<10; ++i)
	{
		number [index+1] = i + '0';
		print1ToMaxDigitsRecursively(number,length,index+1);
	}
}
void print1ToMaxDigits(int n)
{
	if(n<0)
		return;
	char* number = new char[n+1];
	number[n] = '\0';

	for(int i=0; i<10; ++i)
	{
		number[0] = i + '0';
		print1ToMaxDigitsRecursively(number,n,0);
	}
	delete[] number;
}
int main(int argc,char** argv)
{
	int n;
	cin>>n;
	print1ToMaxDigits(n);
	return 0;
}

13.在O(1)时间内删除链表结点

题目描述: 给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间内删除该结点.

思路:

(1) 首先考虑输入的参数是否为空,为空直接返回

(2) 假设删除的是链表中间的节点a,只需将后一个节点b的值拿过来,并将pNext指向b的下一个节点c,然后iu再释放b

(3) 假设只有一个节点,那直接销毁头节点,并将输入(指向头节点指针的指针)置为NULL

(4) 假设删除的是最后一个节点,为了找到尾节点的前一个结点,那么只能从头到尾遍历所有节点,

struct ListNode
{
	int			value;
	ListNode*	pNext;
};
void deleteNodeInList(ListNode** pHead,ListNode * pToBeDeleted)
{
	if(pHead==NULL || pToBeDeleted==NULL)
		return;
	// pToBeDeleted is not the tailNode
	if(pToBeDeleted->pNext != NULL)
	{
		ListNode* pTmp = pToBeDeleted->pNext;
		pToBeDeleted->value = pTmp->value;
		pToBeDeleted->pNext = pTmp->pNext;

		delete pTmp;
		pTmp = NULL;
	}
	//just one node
	else if(*pHead == pToBeDeleted)
	{
		delete pToBeDeleted;
		pToBeDeleted = NULL;
		*pHead = NULL;
	}
	else	//pToBeDeleted is the last node
	{
		ListNode* pNode = *pHead;
		while(pNode->pNext != pToBeDeleted)
			pNode = pNode->pNext;
		pNode->pNext = NULL;
		delete pToBeDeleted;
		pToBeDeleted = NULL;
	}
}

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

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

思路1: 从前向后遍历,将遇到的偶数都存入新开辟的辅助空间内,并将其从原数组删除,然后将辅助空间的数据插在原数组的后面.

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {
        vector<int>::iterator p1 = array.begin();
        vector<int> array_tmp;	//辅助空间
        while(p1 != array.end())
        {
            if(*p1%2 == 0)
            {
                array_tmp.push_back(*p1);	//偶数插入到辅助空间,
                p1 = array.erase(p1);			//从原数组删除
            }
            else
            {
                p1++;
            }
        }
        vector<int>::iterator p2 = array_tmp.begin();
        while(p2 != array_tmp.end())
        {
            array.push_back(*p2);		//偶数插入到原数组后面
            p2++;
        }
    }
};

思路2: 不用辅助空间,从后往前,遇到前偶后奇就交换两个元素.

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {
        if(!array.empty())
            return;
        for(int i=0; i<array.size(); ++i)
        {
            //每次都从后面开始遍历
            for(int j=array.size()-1; j>i; j--)
            {
            //前偶后奇就交换
                if((array[j-1] & 0x1)==0 && (array[j] & 0x1) ==1)
                    swap(array[j-1],array[j]);
            }
        }
    }
};

15.链表中倒数第k个结点

题目描述: 输入一个链表，输出该链表中倒数第k个结点。

正常的思路1: 因为是单向链表，通过从头到尾两次遍历所有节点来计算倒数第k个节点会非常浪费时间。假设共n个节点，那么倒数第k个节点，正数就是第n-k+1个节点。只需通过两个指针(相差k个结点)遍历一次链表就可以了。

(1) 判断输入空链的情况

(2) 判断输入k=0情况

(3) 判断k>n的情况

(4) 传入的参数尽量不要改动，特别是指针，引用。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) 
    {
        //传入的参数尽量不要改动
        if(pListHead == NULL ||k == 0)
            return NULL;
        
        ListNode* pLeft  = pListHead;
        ListNode* pRight = pListHead;
        
        while(--k && pRight!=NULL)
            pRight = pRight->next;
        //如果pRight为空说明k大于链表节点的个数，应该返回空
        if(pRight == NULL)
            return NULL;
        //左右两个节点一同向后移动
        while(pRight->next != NULL)
        {
            pLeft = pLeft->next;
            pRight = pRight->next;
        }
        return pLeft;
    }
};

精简的思路2: 同样是通过两个指针(相差k个结点)遍历一次链表。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) 
    {
        if(k==0)
            return NULL;
        ListNode* pA = pListHead;
        ListNode* pB = pListHead;
        //让pA先走k步
        int i=0;
        for( ; pA!=NULL; ++i)
        {
            if(i>=k)
                pB = pB->next;
            pA = pA->next;
        }
        return i<k? NULL : pB;
    }
};

剑指offer11-15笔试题

文章目录

11.数值的整数次方

12.打印1到最大的n位数(不太熟)

13.在O(1)时间内删除链表结点

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

15.链表中倒数第k个结点

继续阅读

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

【数据结构】医院选址

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希