秋招复习计划-算法题3

  |  

前言
二进制中1的个数、数值的整数次方、调整数组顺序使奇数位于偶数前、链表中倒数第K个节点、反转链表


29



二进制中1的个数

题目描述

输入一个整数,输出改数二进制表示中的1的个数。如果为负数,则用补码表示

题目分析

这道题我的思路是,十进制转二进制,拆分成数组,遍历,计数,试了一下,麻烦,而且由于JS对于十进制转二进制的方式不过简便,而最简便的方式num.toString(2),只有正数转换是正确的。所以这个方法并不推荐。对于二进制,位运算才是王道。

方法1:

如果一个数,他与1与的结果是1,那么证明,它的最右一位为1,否则为0,那么我们不断右移这个数,就可以判断这个数中1的个数。但是这个方法有个问题,就是对于负数,右移需要需要补符号为,正数补0,并没有问题,但是负数补1,这样1的个数就会出错。解决这个问题的方法也很简单,既然数不能右移,那么我们左移1,同样可以做到按位比较。

方法二:

如果一个数不为0,那么它至少有一个1。如果我们把这个数减1,那么它最右一位的1就会变成0,而在这个1右边的所有位都会取反,这时候我们将减1的数与原数与,则能将最右一位的1及其后面的所有位取0。这样我们就消掉了一个1,重复这个过程,当所有1被消除后,计数就是1的个数,而且这个方法最精妙的地方在于循环的次数就是1的个数。

算法代码

1
2
3
4
5
6
7
8
function numberOf1(n) {
let arr = n.toString(2).split(""),
count = 0;
for(i in arr) {
if(arr[i] == '1') count++;
}
return count;
}

我把我的方法贴出来,至少它在n为正数的时候还是有用的

1
2
3
4
5
6
7
8
9
function numberOf1(n) {
let count = 0,
flag = 1;
while(flag) {
if (flag & n) count++;
flag = flag << 1;
}
return count;
}

方法1的代码

1
2
3
4
5
6
7
8
function numberOf1(n) {
let count = 0;
while(n) {
n = n & n-1;
count++;
}
return count;
}

方法2的代码

1
2
3
4
5
6
7
8
function numberOf1(n) {
let arr = n.toString(2).split(""),
count = 0;
for(i in arr) {
if(arr[i] == '1') count++;
}
return count;
}

数值的整数次方

写到一半,没保存,心态崩了,不想多写了

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题目分析

这道题用传统的方法也可以做,只不过效率太低,这里我们用到快速幂的方法。不懂可以百度搜快速幂,原理如下:

数值的整数次方1

也就是说我们要算a的11次方,我们只需要算a的1次方,a的2次方,a的8次方,也就是说我们结果需要算的是这个指数对应的二进制数上有1的位,

比如1011,所以img

数值的整数次方2

数值的整数次方3

好了,此外再说一句,对1进行按位与,可以判断二进制数最右边的位数是否为1,因此也可以判断奇偶数,因为奇数最后一位一定为1。

让我们来看看这道题的代码吧。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function Power(base, exponent) {
// write code here
let res = 1,
n;
if (exponent > 0) {
// 指数大于0的情况下
n = exponent;
} else if (exponent < 0) {
// 指数小于0的情况下
if (!base) throw new Error('分母不能为0');
n = -exponent;
} else {
// 指数等于0的情况下
return 1;
}
while (n) {
// 也可以用递归做,这里采用了循环
if (n & 1)
// 当指数为奇数时,包括了1
res *= base;
base *= base;
n >>= 1;
}
return exponent > 0 ? res : 1 / res;
}

调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

题目分析

判断是否为奇数,统计奇数个数,然后新建数组,把所有奇数存进去数组前面,剩下的存进去数组后面。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function reOrderArray(array) {
// oddBegin主要是用作奇数的索引,oddCount是用作偶数的索引,newArray用来存储,用空间来换运行时间,复杂度为O(n)
let oddBegin = 0,
oddCount = 0;
const newArray = [];
for(let i = 0; i < array.length; i++) {
if (array[i] & 1) {
oddCount++;
}
}
for(let i = 0; i < array.length; i++) {
if(array[i] & 1) {
newArray[oddBegin++] = array[i];
} else {
newArray[oddCount++] = array[i];
}
}
return newArray;
}

链表中倒数第K个节点

题目描述

输入一个链表,输出该链表中倒数第k个节点

题目分析

由于链表是单向的,只有到达最后一个几点才会停止,所以我们可以考虑用两个指针来跑。先让一个指针跑到第k个节点,这就需要想下跳k-1次。然后两个指针一起跑,先跑的指针到达链表末尾时,另一个指针就是倒数第K个

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function FindKthToTail(head, k) {
if(head == null || k < 0) return null;
let pNode1 = head,
pNode2 = head;
while(--k) {
if(pNode.next !== null) {
pNode2 = pNode2.next;
} else {
return null;
}
}
while(pNode2.next !== null) {
pNode1 = pNode1.next;
pNode2 = pNode2.next;
}
return pNode1;
}

反转链表

题目描述

输入一个链表,反转俩表后,输出链表的所有元素

题目分析

反转链表的话,就是把原先的链打断,然后让后一个的节点的next等于前一个节点。那么就需要三个指针,pPre指向前一个节点,pCurrent指向当前节点,pNext保存下一个节点

算法代码

1
2
3
4
5
6
7
8
9
10
11
function ReverseList(pHead) {
let pPre = null,
pNext = null;
while(pHead !== null) {
pNext = pHead.next;
pHead.next = pPre;
pPre = pHead;
pHead = pNext;
}
return pPre;
}
文章目录
  1. 1. 二进制中1的个数
  2. 2. 数值的整数次方
  3. 3. 调整数组顺序使奇数位于偶数前面
  4. 4. 链表中倒数第K个节点
  5. 5. 反转链表
|