# 《剑指Offer》第三章

xiaoxiao2021-02-28  9

//注意，判断浮点数是否相等，不能用==，而是差值在某个范围内 bool equal(double num1, double num2) { if (num1 - num2 > -0.0000001 && num1 - num2 < 0.0000001) return true; else return false; } double PowerWithUnsignedExponent(double base, unsigned int exponent) { double result = 1.0; for (int i = 1; i <= exponent; ++i) result *= base; return result; } double Power(double base, int exponent) { if (equal(base, 0.0) && exponent < 0) throw new exception("输入不合法"); unsigned int absExponent = (unsigned int)(exponent); if (exponent < 0) absExponent = (unsigned int)(-exponent); double result = PowerWithUnsignedExponent(base, absExponent); if (exponent < 0) result = 1 / result; return result; }书中给出了高效的解法：a^n=a^(n/2)*a^(n/2) 或者 a^n=a^((n-1)/2)*a^((n-1)/2)*a，利用这个式子，求解：

double PowerWithUnsignedExponent(double base, unsigned int exponent) { if (exponent == 0) return 1; if (exponent == 1) return base; double result = PowerWithUnsignedExponent(base, exponent >> 1); result *= result; if (exponent & 0x1 == 1) result *= base; return result; } 第二题：打印1到最大的n位数

bool Increment(vector<int> &number) { bool isOverflow = false; int nTakeOver = 0; int length = number.size(); for (int i = length -1; i >= 0; --i) { int nSum = number[i] + nTakeOver; if (i == length - 1) ++nSum; if (nSum >= 10) { if (i == 0) isOverflow = true; else { nSum -= 10; nTakeOver = 1; number[i] = nSum; } } else { number[i] = nSum; break; } } return isOverflow; } void PrintNumber(vector<int> &number) { int i = 0; while (i < number.size() && number[i] == 0) { ++i; } for (; i < number.size(); ++i) { cout << number[i]; } cout << "\n"; } void print1ToMaxNDigits(int n) { if (n <= 0) return; vector<int> number(n,0); while (!Increment(number)) PrintNumber(number); } 第三题：在O(1)时间内删除链表节点

void RerderOddEven(vector<int> &nums) { int left = 0; int right = nums.size() - 1; while (left < right) { while (left < right && (nums[left] & 0x01) == 1) ++left; while (left < right && (nums[right] & 0x01) == 0) --right; if (left < right) swap(nums[left], nums[right]); } } 第五题：反转链表

ListNode* ReverseList(ListNode *pHead) { ListNode *pReversedHead = NULL; ListNode *pNode = pHead; ListNode *pPrev = NULL; while (pNode != NULL) { ListNode *pNext = pNode->next; if (pNext == NULL) pReversedHead = pNext; pNode->next = pPrev; pPrev = pNode; pNode = pNext; } return pReversedHead; } 第六题：合并两个排序的链表