劍指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哈希