剑指offer刷题记录(C++版本)（之二）
2019-08-27 本文已影响0人
傑jay
11.二进制中1的个数
-
题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
-
思路：如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
};
12.数值的整数次方
- 题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0
-
思路：
主要弄清楚不同情况下的整数次方的分类问题，符号变换情况，另外是0值情况。
将幂拆分成一半计算，主要使用快速幂方法，降幂计算从而降低时间复杂度
class Solution {
double power(double base, int exp) {
if (exp == 1) return base;
if ((exp & 1) == 0) { //判断exp奇偶只需要看最后一位是否为1
int tmp = power(base, exp >> 1);//右移一位求半幂，采用快速幂算法
return tmp * tmp;
} else {
int tmp = power(base, (exp - 1) >> 1);
return tmp * tmp * base;
}
}
public:
double Power(double base, int exp) {
if (base == 0)
{
if (exp > 0) return 0;
else if (exp == 0) return 0;
else throw invalid_argument("Invalid input!");//0的负数幂无意义
}
else {
if (exp > 0) return power(base, exp);
else if (exp == 0) return 1;
else return 1 / power(base, -exp);
}
}
};
13.调整数组顺序使奇数位于偶数前面
- 题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
-
思路：本体是思路可以说非常多，冒泡法排序，遍历重组等等。。
冒泡法，从后往前移动，每次循环都把所有奇数前移一次，偶数后移一次
void reOrderArray(vector<int> &array) {
for (int i = 0; i < array.size();i++)
{
for (int j = array.size() - 1; j>i;j--)
{
if (array[j] % 2 == 1 && array[j - 1]%2 == 0) //前偶后奇交换
{
swap(array[j], array[j-1]);
}
}
}
}
另有一种方法，遍历数组，奇数存一边，偶数存一边。因此时间复杂度更低，但需要占用更多空间
void reOrderArray(vector<int> &array) {
vector<int> array_temp;
vector<int>::iterator ib1, ie1;
ib1 = array.begin();
for (; ib1 != array.end();){ //遇见偶数，就保存到新数组，同时从原数组中删除
if (*ib1 % 2 == 0) {
array_temp.push_back(*ib1);
ib1 = array.erase(ib1);
}
else{
ib1++;
}
}
vector<int>::iterator ib2, ie2;
ib2 = array_temp.begin();
ie2 = array_temp.end();
for (; ib2 != ie2; ib2++) //将新数组的数添加到老数组
{
array.push_back(*ib2);
}
}
14.链表倒数第k个节点
- 题目：输入一个链表，输出该链表中倒数第k个结点。
- 思路：该题的考点在于，链表的长度如果不从头到尾读取一遍是未知的，因此关键在于哪一个是倒数第K个节点。因此采用双指针的方式，一个指向第1个节点，一个指向第k-1个节点，同时后移，后一个指针的地址取到NULL时，即链表结束，前一个指针指向的即倒数第K个节点。
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode *p, *q;
p = q = pListHead;
int i = 0;
for (; p != NULL; i++) {
if (i >= k)
q = q->next;
p = p->next;
}
if (i < k)
return NULL;
else
return q;
}
};
15.翻转链表
- 题目：输入一个链表，反转链表后，输出新链表的表头。
-
思路：主要的思想是用两个指针，其中newHead指向的是反转成功的链表的头部，currentHead指向的是还没有反转的链表的头部：
初始状态是newHead指向null，currentHead指向的是第一个元素，一直往后遍历直到newHead指向最后一个元素为止：
下面展示的是其中某个时间点的指向细节：
核心在于理解，反转链表反转的只是地址的指向改变
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *newHead = NULL;
ListNode *currentHead = pHead;
if(pHead == NULL || pHead->next == NULL){
return pHead;
}
while(currentHead != NULL){
ListNode *next = currentHead->next;
currentHead->next = newHead;
newHead = currentHead;
currentHead = next;
}
return newHead;
}
16.合并两个排序链表
- 题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
- 思路：1. 递归实现：两个当前数值比较，小的输出，然后后移一位继续更另一个数值比较，小的数值输出，如此循环
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL){
return pHead2;
}
if(pHead2 == NULL){
return pHead1;
}
if(pHead1->val <= pHead2->val){
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}else{
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
- 非递归原理一样，只不过看起来更复杂
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(!pHead1)
return pHead2;
if(!pHead2)
return pHead1;
ListNode* Head;
ListNode* p;
//取较小值作头结点
if(pHead1->val<=pHead2->val){
Head=pHead1;
pHead1=pHead1->next;
}
else{
Head=pHead2;
pHead2=pHead2->next;
}
//开始遍历合并
p=Head; //p为合并后的链表的工作指针
while(pHead1&&pHead2){ //当有一个链表到结尾时，循环结束
if(pHead1->val<=pHead2->val){ //如果链表1的结点小于链表2的结点
p->next=pHead1; //取这个结点加入合并链表
pHead1=pHead1->next; //链表1后移一位
p=p->next; //工作指针后移一位
}
else{ //否则取链表2的结点
p->next=pHead2;
pHead2=pHead2->next;
p=p->next;
}
}
if(pHead1 == NULL) //链表1遍历完了
p->next = pHead2; //如果链表2也遍历完了，则pHead2=NULL
if(pHead2 == NULL) //链表2遍历完了
p->next = pHead1; ///如果链表1也遍历完了，则pHead1=NULL
return Head;
}
17.树的子结构
- 题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。
- 思路：主要还是使用递归，用子函数判断两棵树是否相等，然后主函数递归判断
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool result=false;
if(pRoot1!=NULL&&pRoot2!=NULL)
{
if(pRoot1->val==pRoot2->val) //如果两个相等，则进行匹配
result=DoseTree1HaveTree2(pRoot1,pRoot2);
if(!result)
result=HasSubtree(pRoot1->left,pRoot2);
if(!result)
result=HasSubtree(pRoot1->right,pRoot2);
//如果不等的话则分别递归查找其左边和右边
}
return result; //如果没找到这里还是false
}
bool DoseTree1HaveTree2(TreeNode* pRoot1,TreeNode* pRoot2)
{
if(pRoot2==NULL) //如果已经比遍历到pRoot2位空，那么说明是子树
return true;
if(pRoot1==NULL) //如果pRoot1为空pRoot2不为空(如果为空已经返回)，则说明不是子树
return false;
if(pRoot1->val!=pRoot2->val) //如果存在两个值不相等，那么肯定也不是子树
return false;
return DoseTree1HaveTree2(pRoot1->left,pRoot2->left)&&
DoseTree1HaveTree2(pRoot1->right,pRoot2->right);
//剩下的就是递归得判断左右是否相等了。
}
};
18.二叉树的镜像
- 题目：操作给定的二叉树，将其变换为源二叉树的镜像
- 思路：递归分别交换左右子树
class Solution {
public:
void Mirror(TreeNode *pRoot) {
//终止条件就是当前的节点为空
if(pRoot==NULL) return;
//交换节点
TreeNode *tmp=new TreeNode(0);
tmp->left=pRoot->left;
tmp->right=pRoot->right;
pRoot->left=tmp->right;
pRoot->right=tmp->left;
delete tmp;
//判断左右分别是为空，不为空的话递归的来求镜像
if(pRoot->left)
Mirror(pRoot->left);
if(pRoot->right)
Mirror(pRoot->right);
}
};
19.顺时针打印矩阵
- 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
- 思路：通过循环一圈一圈拨开矩阵，条件的设置是重中之重，本体的要运行正确需要花很大气力
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector<int> res;
// 输入的二维数组非法，返回空的数组
if (row == 0 || col == 0) return res;
// 定义四个关键变量，表示左上和右下的打印范围
int left = 0, top = 0, right = col - 1, bottom = row - 1;
while (left <= right && top <= bottom)
{
// left to right
for (int i = left; i <= right; ++i) res.push_back(matrix[top][i]);
// top to bottom
for (int i = top + 1; i <= bottom; ++i) res.push_back(matrix[i][right]);
// right to left
if (top != bottom)
for (int i = right - 1; i >= left; --i) res.push_back(matrix[bottom][i]);
// bottom to top
if (left != right)
for (int i = bottom - 1; i > top; --i) res.push_back(matrix[i][left]);
left++,top++,right--,bottom--;
}
return res;
}
};
20.包含min函数的栈
- 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
-
思路：
看到这个问题, 我们最开始可能会想, 添加一个成员变量用于保存最小元素, 每次压栈时如果压栈元素比当前最小元素更小, 就更新最小元素.
但是这样会有一个问题, 如果最小元素被弹出了呢, 如何获得下一个最小元素呢? 分析到这里可以发现, 仅仅添加一个成员变量存放最小元素是不够的, 我们需要在最小元素弹出后还能得到次小元素, 次小的弹出后, 还要能得到次次小的.
因此, 用另一个栈来保存这些元素是再合适不过的了. 我们叫它最小元素栈.
每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出的元素和最小元素栈的栈顶元素相等, 就把最小元素的栈顶弹出.
class Solution {
public:
void push(int value) {
s.push(value);
if(sMin.empty())
sMin.push(value);
else if(value <= sMin.top())//进栈时比之前最小元素还小，则同时进最小值栈
sMin.push(value);
}
void pop() {
if(s.top() == sMin.top())//出栈时位当前最小元素，则最小值栈同时出
sMin.pop();
s.pop();
}
int top() {
return s.top();
}
int min() {
return sMin.top();
}
private://定义两个栈，一个实现正常栈的功能，一个用了存最小值栈
stack<int> s;
stack<int> sMin;
};
