11. 二进制中1的个数
- 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
// Solution:位运算
// Tips:整数右移一位与整数除以二在数学上等价，但除法效率很低
// （1）如果整数右移一位，再与1做与运算判断最后一位是不是1，负数会造成死循环
// （2）因此，采用整数与1按位与，然后把1左移1位，再按位与...
// （3）把一个整数减去1，再和原整数按位与，会将最右边的1变成0；所以一个整数的二进制有多少1，就可进行多少次操作。
class Solution {
public:
int NumberOf1(int n) {
/*（2）
int count = 0;
unsigned int flag = 1;
while (flag) {
if (n & flag) {
count ++;
}
flag = flag << 1;
}
return count;*/
// （3）
int count = 0;
while(n) {
count ++;
n = n & (n-1);
}
return count;
}
};
12. 数值的整数次方
- 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
// Solution: 需要考虑多种边界条件，以及使用斐波那契乘方、位运算提高循环乘法效率
// Tips:(1)考虑指数<=0,小于0时需要先求|e|,再求倒数,此时要求base!=0;
// (2)e=0时，0^0没有意义，可考虑输出1或0；
// (3)double/float浮点数判断相等，不使用==，|做差|<sigma；
class Solution {
public:
bool gInvalidInput = false;
double Power(double base, int exponent) {
gInvalidInput = false;
// 判断指数e<0时，底数base是否等于0.0
if (exponent <= 0 && (equal(base, 0.0))) {
gInvalidInput = true;
return 0.0;
}
// 判断指数e<0时，需要求-e，并计算指数结果后求倒数
unsigned int absExponent = (unsigned int)exponent;
if (exponent < 0) {
absExponent = (unsigned int)(-exponent);
}
double result = PowerWithUnsignedExponent(base, absExponent);
if (exponent < 0)
result = 1.0 / result;
return result;
}
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 res = 1.0;
for (int i=1; i <= exponent; i ++) {
res *= base;
}*/
// 使用a^n公式及位运算：
// （1）n为偶数，a^n = a^(n/2) * a^(n/2)
// （2）n为奇数，a^n = a^(（n-1）/2) * a^((n-1)/2) * a
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
double res = PowerWithUnsignedExponent(base, exponent >> 1);
res *= res;
if (exponent & 0x1 == 1)
res *= base;
return res;
}
};
《剑指offer面试题12：打印1到最大的n位数》
（1）大数用字符串表示，最前补0；
（2）递归打印0~9的全排列。
（3）特殊输入如0，-1等需要考虑。
《剑指offer面试题13：在O(1)时间删除链表结点》给定单向链表头指针和一个结点指针，删除该结点
（1）O(n)顺序找到要删除结点的前一个结点， 更改pNext；
（2）O(1)复制下一个结点，删除下一个结点，尾结点费时（另需考虑仅一个结点），时间复杂度=[(n-1)*O(1)+O(n)]/n=O(1)。
13. 调整数组顺序使奇数位于偶数前面（注意erase时，iterator需要变化）
- 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
class Solution {
public:
void reOrderArray(vector<int> &array) {
if (array.size() == 0) {
return;
}
vector<int> right;
vector<int>::iterator itArray;
for (itArray = array.begin(); itArray != array.end(); itArray ++) {
if (isEven(*itArray)) {
right.push_back(*itArray);
array.erase(itArray);
itArray --; // 因为删除vector元素后，循环itArray++会导致跳过访问一个元素，以及后续访问溢出
}
}
vector<int>::iterator itRight;
for (itRight = right.begin(); itRight != right.end(); itRight++) {
array.push_back(*itRight);
}
}
// 解耦判断条件
bool isEven(int n) {
return !(n & 1);
}
};
14. 链表中的倒数第k个结点
- 输入一个链表，输出该链表中倒数第k个结点。
// Tips:(1)pListHead==NULL; (2)unsigned int k==0时， k-1是4294967295; (3)链表个数<k.
/*
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) {//k==0时，不返回，unsigned int会导致循环崩溃
return NULL;
}
ListNode* pAhead = pListHead;
ListNode* pBehind = pListHead;
for (unsigned int i=0; i < k-1; i ++) {
if (pAhead->next != NULL) {//链表个数小于k时
pAhead = pAhead->next;
} else {
return NULL;
}
}
while (pAhead->next != NULL) {
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
};
15. 反转链表
- 输入一个链表，反转链表后，输出链表的所有元素。
// Solution:使用三个指针pPrev，pNode，pNext完成反转
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode* pPrev = NULL;
ListNode* pNode = pHead;
// ListNode* pReverseHead = NULL;
while (pNode != NULL) {
ListNode* pNext = pNode->next;
// if (pNext == NULL) {
// pReverseHead = pNode;
// }
pNode->next = pPrev;
pPrev = pNode;
pNode = pNext;
}
// return pReverseHead;
return pPrev;
}
};
网友评论