11 二进制中1的个数
题目描述
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
示例1
输入：
返回值：
思路：
判断二进制末尾是否为1，将整数整体右移一位，循环32次
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int NumberOf1(int n) {
int num=0;
for(int i=0;i<32;i++){
if(n&1==1)num++;
n=n>>1;
}
return num;
}
};
|
12 数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
思路：
指数为0时结果为1
指数为负数时结果为指数为正数时的倒数
指数为偶数时，式子等价于基数平方然后指数除以2，这样计算可以减少时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
double Power(double base, int exponent) {
if(exponent==0)return 1;
int cur=1;
bool sym=exponent>0?true:false;
exponent=exponent>0?exponent:-exponent;
if(exponent%2==1){
cur=base;
exponent-=1;
}
while(exponent>1){
base*=base;
exponent/=2;
}
base*=cur;
return sym?base:1/base;
}
};
|
13 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：
用空间换时间，创建2个容器分别存放奇数和偶数，最后copy到原数组的地址空间下
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> left,right;
for(auto a:array){
if(a&1==1)left.push_back(a);
else right.push_back(a);
}
copy(left.begin(),left.end(),array.begin());
copy(right.begin(),right.end(),array.begin()+left.size());
}
};
|
14 链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
输入：
返回值：
思路：
双指针，第一个指针先开始移动，移到正数第k个时第二个指针开始移动
第一个指针移到链表末尾时，第二个指针刚好少移动k位，此时第二个指针的位置就是倒数第k位
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
int n=k;
if(pListHead==nullptr)return nullptr;
ListNode *p=pListHead,*q=pListHead;
for(p=pListHead,q=pListHead;p!=nullptr;p=p->next,n--){
if(n<=0)q=q->next;
}
return n>0?nullptr:q;
}
};
|
15 反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
输入：
返回值：
思路：
从前向后遍历链表，将当前结点和后面的借点切断，然后这个节点作为头节点添加到新链表中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *cur=nullptr;
while(pHead){
ListNode *temp;
temp=pHead->next;
pHead->next=cur;
cur=pHead;
pHead=temp;
}
return cur;
}
};
|
