剑指 Offer 15. 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
方法1：逐位判断
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans=0;
while(n>0){
if(n&1)ans++;
n>>=1;
}
return ans;
}
};
方法二：巧用 n&(n?1)
(n?1) 解析： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
n&(n?1) 解析： 二进制数字 n最右边的 1 变成 0，其余不变。
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += 1
n &= n - 1
return res
作者：jyd
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析：
时间复杂度 O(M)： n&(n?1) 操作仅有减法和与运算，占用 O(1) ；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ），占用 O(M)。
空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。
剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
提示：``
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
class Solution {
public:
double myPow(double x, int n) {
double res=1.0;
if(n==-1)return 1/x;
if(n==0)return 1.0;
if(n==1)return x;
res=myPow(x,n/2);
res=res*res;
res*=myPow(x,n%2);
return res;
}
};
- 快速幂，写习惯了递归，迭代也可
- 本题注意n为负数的情况
- 迭代首先将 n=-n, x=1/x, 注意x为0的情况
剑指 Offer 17. 打印从1到最大的n位数(大数问题)
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
方法一：绝对不可以的解法！
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> nums;
int maxNum=pow(10,n);
for(int i=1;i<maxNum;i++){
nums.push_back(i);
}
return nums;
}
};
- 虽然这么写能通过，但是当n很大时，数值无法用int/long等表示，所以得用字符串表示避免溢出。
- 可以写大数加法，也就是高精度加法
- 观察可知，输出实际上是全排列，所以也可通过递归来写
stoi函数
全排列：
class Solution {
public:
vector<int> nums;
void addNums(string &s){
if(stoi(s)==0)return;
nums.push_back(stoi(s));
}
void dfs(string &s,int dep,int n){
if(dep==n){
addNums(s);
return;
}
for(int i=0;i<=9;i++){
s[dep]='0'+i;
dfs(s,dep+1,n);
}
}
vector<int> printNumbers(int n) {
string s(n,'0');
dfs(s,0,n);
return nums;
}
};
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode *q=head,*p;
if(head->val==val)return head->next;
while(q!=NULL){
if(q->val==val){
p->next=q->next;
break;
}
p=q;
q=q->next;
}
return head;
}
};
- 链表基础操作，虽然我平常不咋用链表
- 可能变量命名我得注意点，也没考虑head为NULL的情况
单指针的写法：
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
if (head.val == val) return head.next;
ListNode cur = head;
while (cur.next != null && cur.next.val != val)
cur = cur.next;
if (cur.next != null)
cur.next = cur.next.next;
return head;
}
}
递归写法：
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return NULL;
if(head->val == val) return head->next;
head->next = deleteNode(head->next,val);
return head;
}
};
面试题 02.03. 删除中间节点 （18原题）
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
要求在O(1)时间解决
class Solution {
public:
void deleteNode(ListNode* node) {
node->val=node->next->val;
node->next=node->next->next;
}
};
- 不能自杀，就杀别人，并且取代别人，时间复杂度O(1)
|