大家好，又见面了，我是你们的朋友全栈君。
前言
很多人加我都是想询问如何学好算法。我的方法是我用了 十年 的时间，自己总结出来的，不可能适合所有人，但是我觉得挺有效的，如果你觉得可行，尽管一试！
首先，我们心中要有一团?火?，一团希望之?火?！只要你心中充满希望，即使是死去的意志也会在你内心复活。
你永远无法弥补你的过去，但是，你可以改变你的未来！就算暗淡无光的尘土，也会有爆发光芒的那一刻！抓住那尘埃中的刹那光辉，燃烧自己吧！
一、树立目标
给自己树立一个「 目标 」是非常重要的，有「 目标 」才会有「 方向 」，有「 目标 」才会有「 动力 」，有「 目标 」才会有「 人生的意义 」。有了「 目标 」，再做一定的「 规划 」，并且「 坚持 」做下去，我相信，「 成功的一天终会到来 」。
目标可以是：刷一万道题、学会一百个算法、拿到字节的 offer、年入百万 等等，因人而异，当然，不建议以 财务自由 作为目标，因为每个人对 财务自由 的定义不同。
二、如何开始
我不是很推崇从一开始就看 《算法导论》 这样的天书，没错，对于初学者而言，这就是天书。在对算法没有任何概念的情况，看书并不是一个明智的选择。
那么问题来了，不看书，我们看什么呢？
第一阶段我是这么规划的：
1）挑一门自己想学习的语言；
2）零基础情况下，把 50 个简单题先刷掉；
3）遇到不会的，先想10分钟，想不出来看「 解题报告 」；
4）看完后一定要自己敲一遍，并且放到重刷列表；
5）重新刷之前 50 个题里面你看了「 解题报告 」的题；
接下来才是本文的重点内容。
文章目录
- 前言
- 一、树立目标
- 二、如何开始
- 三、找到组织
- 四、零基础算法
-
- 1、求1+2+…+n
- 2、递归乘法
- 3、斐波那契数
- 4、n 的第 k 个因子
- 5、统计平方和三元组的数目
- 6、找出数组的最大公约数
- 7、最大三角形面积
- 8、数组异或操作
- 9、整数的各位积和之差
- 10、统计位数为偶数的数字
- 11、搜索旋转排序数组
- 12、差的绝对值为 K 的数对数目
- 13、宝石与石头
- 14、所有奇数长度子数组的和
- 15、缺失的第一个正数
- 16、排序数组
- 17、根据字符出现频率排序
- 18、二进制链表转整数
- 19、K 进制表示下的各位数字总和
- 20、各位相加
- 21、七进制数
- 22、数字转换为十六进制数
- 23、数组串联
- 24、重新排列数组
- 25、打印从1到最大的n位数
- 26、一维数组的动态和
- 27、有多少小于当前数字的数字
- 28、找出所有子集的异或总和再求和
- 29、解码异或后的数组
- 30、交换数字
- 31、位1的个数
- 32、数字范围按位与
- 33、颠倒二进制位
- 34、前 n 个数字二进制中 1 的个数
- 35、好数对的数目
- 36、判断句子是否为全字母句
- 37、执行操作后的变量值
- 38、IP 地址无效化
- 39、统计一致字符串的数目
- 40、反转字符串
- 41、左旋转字符串
- 42、检查两个字符串数组是否相等
- 43、复数乘法
- 44、开幕式焰火
- 45、将数字变成 0 的操作次数
- 46、层数最深叶子节点的和
- 47、二叉树的深度
- 48、数组元素积的符号
- 49、删除中间节点
- 50、删除链表的节点
- 五、粉丝福利
三、找到组织
说了这么多，只是想建立一个「 愿景 」。这个「 愿景 」就是 —— 「 群人皆佬，共赴大厂 」。
光有「 愿景 」是不够的，我们需要「 付诸实际行动 」，任何一项大工程都不是「 一朝一夕 」能够完成的，「 制定计划 」 是尤为重要的事情。例如，想要学好算法，至少需要掌握一门语言，可以是 C、C++、Python、Java。这里强烈推荐 C语言，因为俗话说得好：
「 学好C语言，走遍天下都不怕 」
为了
「 督促大家 」更好的学习，所以我建立了一些团队供各位
「 技术交流 」之用，因为团队大了不好带，所以初期就把团队分好组，这样每个团队都能有很好的照顾，比一下子吃成胖子要好得多，当然每个团队我都会挑选一些
「 精英人员 」作为领袖，以便更好的来达成我们共同的
「 愿景 」。
这主要是提供给各位志想同道合之士交流沟通的一个桥梁，起到
「 媒介 」的作用。让同样和我
「 志同道合 」的人积极投身到这个事业中来，将祖国的
「 算法 」发扬光大，背靠祖国，面向国际，强我国威，壮我河山！
用
「 算法 」改变世界，
「 让天下没有难学的算法 」。
我不希望你是以粉丝的身份加入我的团队，我更希望我们是
「 合伙人 」，只是没有任何利益上的输送，我也不会在里面做任何产品的推销，所以，
「 广告商勿扰 」。
大多都是正在上大学的学生，我不想赚学生的钱，毕竟能上学已属不易。而且，很多大学生的激情，
「 引燃 」了我自己的
「 青春 」，所以我很喜欢和大学生交流，有时候也会给他们一些面试以及职场上的建议，久而久之，就成了
「 无话不谈 」的好朋友。
正是这一点，让我激发了认识更多的人的欲望，毕竟，
「 活到老学到老 」，
「 靠近优秀的人，使自己变得更加优秀 」，始终保持一个学习的态度，多沟通交流，让自己
「 更加强大 」！
各位成员是有明确共同目标的，这样才能共同成长，大致特征如下：
如果你满足以上任意一点，那么，我们就是志同道合的人啦！请通过 「 博主的CSDN主页 」 找到联系方式，联系博主。
四、零基础算法
1、求1+2+…+n
1. 问题描述
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
2. 问题分析
首先，题目要求不用乘法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。那如果我用了会怎么样？答案是并不会怎么样，因为平台不会去对它做语法分析，只是调用了你的函数，提供一些输入数据，如果输出数据和它给定的相同，就算通过。
作为你接触算法的第一道题，其实这些条件都无所谓的，能过就行，他只检测输入输出，不检测你实际代码。
对于新人来说，把问题过掉比问题本身更重要，题数的增加，是信心的增加，信心比什么都重要，有了信心，你才能继续往下走，只要你能往下推进，你才能继续学习，继续学习你迟早会学到相应的算法。好了，过了这题以后，把这道题放入你的重刷列表，等你对算法有一定理解以后再来用题目要求的方法来过了它。
3. 源码详解
int sumNums(int n){
return n * (n+1) / 2; // (1)
}
( 1 ) (1) (1) 公差为 1 的等差数列求和公式，完事；
2、递归乘法
1. 问题描述
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
2. 问题分析
第一题做的时候，我说过什么来着？别想太多，记住，你还是小白的时候，千万不要想太多，绕过平台规则自由的飞翔，让你的进度往前推进，有信心以后再回来巩固和提高。
3. 源码详解
int multiply(int A, int B){
return A * B; // (1)
}
- ( 1 ) (1) (1) 管他什么递归乘法，直接上乘法运算符；
3、斐波那契数
1. 问题描述
斐波那契数，通常用 F ( n ) F(n) F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 0 0 和 1 1 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F ( 0 ) = 0 ， F ( 1 ) = 1 F ( n ) = F ( n − 1 ) + F ( n − 2 ) , ( 1 < n ≤ 30 ) F(0) = 0，F(1) = 1 \\ F(n) = F(n – 1) + F(n – 2), (1 \lt n \le 30) F(0)=0，F(1)=1F(n)=F(n−1)+F(n−2),(1<n≤30) 给你 n n n ，请计算 F ( n ) F(n) F(n)。
2. 问题分析
这个问题考察的是数组的递推，把 F ( i ) F(i) F(i) 理解成 C语言的数组，用 f [ i ] f[i] f[i] 来表示第 i i i 个斐波那契数，然后就是一个循环就可以解决了。
3. 源码详解
int f[31]; // (1)
int fib(int n) {
f[0] = 0; // (2)
f[1] = 1; // (3)
for(int i = 2; i <= n; ++i) {
f[i] = f[i-1] + f[i-2]; // (4)
}
return f[n]; // (5)
}
- ( 1 ) (1) (1) 定义一个全局的辅助数组；
- ( 2 ) − ( 3 ) (2)-(3) (2)−(3) 初始化 F ( 0 ) = 0 ， F ( 1 ) = 1 F(0) = 0，F(1) = 1 F(0)=0，F(1)=1，分别存储到数组的第 0 个和第 1 个位置；
- ( 4 ) (4) (4) 一层循环模拟递推公式；
- ( 5 ) (5) (5) 返回第 n n n 个值 f [ n ] f[n] f[n]，也就是斐波那契数列第 n n n 项；
4、n 的第 k 个因子
1. 问题描述
给你两个正整数 n n n 和 k k k，其中两者范围为 1 ≤ k ≤ n ≤ 1000 1 \le k \le n \le 1000 1≤k≤n≤1000。如果正整数 i i i 满足
n % i == 0，那么我们就说正整数 i i i 是整数 n n n 的因子。考虑整数 n n n 的所有因子，将它们 升序排列 。请你返回第 k k k 个因子。如果 n n n 的因子数少于 k k k ，请你返回 − 1 -1 −1。
2. 问题分析
首先，对于 n n n 这个范围，它的因子数撑死 1000 1000 1000 个，实际上会少很多很多，有兴趣可以自己证明下，当然 夜深人静写算法（三）- 初等数论入门 也有关于因子相关的详细内容，不再累述。所以我们可以从 1 1 1 到 n n n 枚举，看哪些是 n n n 的因子，然后再用一个计数器计数，直到数到第 k k k 个就是我们需要求的答案了。
如果全部枚举完，计数器都没有到 k k k，那么很显然，没有 k k k 个因子，直接返回 − 1 -1 −1 即可。
3. 源码详解
int kthFactor(int n, int k){
int i, cnt = 0; // (1)
for(i = 1; i <= n; ++i) {
// (2)
if(n % i == 0) {
// (3)
++cnt; // (4)
if(cnt == k)
return i; // (5)
}
}
return -1; // (6)
}
- ( 1 ) (1) (1) 定义 c n t cnt cnt 为因子计数器；
- ( 2 ) (2) (2) 从 1 1 1 到 n n n 枚举；
- ( 3 ) (3) (3) 找到所有是 n n n 的因子的数 i i i；
- ( 4 ) (4) (4) 计数器加一；
- ( 5 ) (5) (5) 如果计数器为 k k k 说明找到了第 k k k 个因子为 i i i，返回 i i i；
- ( 6 ) (6) (6) 如果全部枚举完，计数器都没有到 k k k，那么很显然，没有 k k k 个因子，直接返回 − 1 -1 −1 即可；
5、统计平方和三元组的数目
1. 问题描述
一个 平方和三元组 ( a , b , c ) (a,b,c) (a,b,c) 指的是满足 a 2 + b 2 = c 2 a^2 + b^2 = c^2 a2+b2=c2 的 整数 三元组 a a a， b b b 和 c c c。给你一个整数 n ( n ≤ 250 ) n(n \le 250) n(n≤250)，请你返回满足 1 ≤ a , b , c ≤ n 1 \le a, b, c \le n 1≤a,b,c≤n 的 平方和三元组 的数目。
2. 问题分析
首先，考虑最暴力的方法，就是三个数都枚举，然后判断等式是否成立，这样做的时间复杂度为 O ( n 3 ) O(n^3) O(n3)。但是我们可以明显的知道， c c c 一定是最大的，所以在枚举 c c c 的时候，可以从 a a a 和 b b b 当中的大者开始，并且当 a 2 + b 2 < c 2 a^2 + b^2 \lt c^2 a2+b2<c2 时，就没必要再枚举 c c c，可以跳出循环，大大降低算法的时间复杂度。
3. 源码详解
int max(int a, int b) {
return a > b ? a : b; // (1)
}
int countTriples(int n){
int a, b, c, sum, ans = 0;
for(a = 1; a <= n; ++a) {
for(b = 1; b <= n; ++b) {
sum = a*a + b*b; // (2)
for(c = max(a, b)+1; c <= n; ++c) {
// (3)
if(sum == c*c) {
++ans; // (4)
break;
}
if(sum < c*c) {
break; // (5)
}
}
}
}
return ans;
}
- ( 1 ) (1) (1) 提供一个函数，返回两者的最大值；
- ( 2 ) (2) (2) 两层循环枚举 a a a 和 b b b，得到它们的平方和 s u m sum sum；
- ( 3 ) (3) (3) 然后枚举 c c c， c c c 一定比 a a a 和 b b b 中的大者还要大，所以从
max(a,b)+1开始枚举； - ( 4 ) (4) (4) 找到一组满足条件的解后，退出循环；
- ( 5 ) (5) (5) 由于 c c c 是从小到大枚举的，一旦发现 a 2 + b 2 < c 2 a^2 + b^2 \lt c^2 a2+b2<c2，则 c c c 再大也不可能满足 a 2 + b 2 = c 2 a^2 + b^2 = c^2 a2+b2=c2 了，可以直接退出循环不再继续往下枚举了。
6、找出数组的最大公约数
1. 问题描述
给你一个整数数组 nums ，数组元素不大于 1000，返回数组中最大数和最小数的 最大公约数 。两个数的 最大公约数 是能够被两个数整除的最大正整数。
2. 问题分析
两个数的最大公约数的计算方法有很多，由于这个问题中，所有数字都不大于 1000，所以求最大公约数的方法，就可以从大到小枚举其中一个数的约数，然后判断是否是另一个数的约数，如果是，则直接返回就行。
3. 源码详解
int gcd(int a, int b) {
int i;
for(i = a; i >= 1; --i) {
if(a % i == 0 && b % i == 0) {
return i; // (1)
}
}
return 1;
}
int findGCD(int* nums, int numsSize){
int i;
int min = nums[0], max = nums[0];
for(i = 1; i < numsSize; ++i) {
if(nums[i] < min) min = nums[i]; // (2)
if(nums[i] > max) max = nums[i]; // (3)
}
return gcd(min, max); // (4)
}
- ( 1 ) (1) (1) 从大到小枚举其中一个数的约数，然后判断是否是另一个数的约数，如果是，则直接返回就行；
- ( 2 ) (2) (2) 选择一个最小的数；
- ( 3 ) (3) (3) 选择一个最大的数；
- ( 4 ) (4) (4) 根据题意，返回最小的数和最大的数的最大公约数；
7、最大三角形面积
1. 问题描述
给定包含 n ( n ≤ 50 ) n(n \le 50) n(n≤50) 个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
2. 问题分析
枚举三个点，然后以这三个点组成一个三角形，计算面积，去其中最大的即可。三点计算三角形面积，可以用各种高中学过的公式来做。我这里采用叉乘求解，叉乘的更多内容可参考：夜深人静写算法（四）- 计算几何入门。
3. 源码详解
double area(int *a, int *b, int *c) {
return fabs( (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0]) ) / 2;
}
double largestTriangleArea(int** points, int pointsSize, int* pointsColSize){
int i, j, k;
double a, maxa = 0;
for(i = 0; i < pointsSize; ++i) {
for(j = 0; j < pointsSize; ++j) {
for(k = 0; k < pointsSize; ++k) {
a = area(points[i], points[j], points[k]); // (1)
if(a > maxa) {
maxa = a; // (2)
}
}
}
}
return maxa; // (3)
}
- ( 1 ) (1) (1) 枚举三个点组成三角形计算面积；
- ( 2 ) (2) (2) 取面积最大的保存下来；
- ( 3 ) (3) (3) 返回最大的那个面积；
8、数组异或操作
1. 问题描述
给你两个整数， n n n 和 s t a r t start start。数组
nums定义为：nums[i] = start + 2*i（下标从 0 开始）且n == nums.length。请返回nums中所有元素按位异或 X O R XOR XOR 后得到的结果。
2. 问题分析
分两步模拟，先把所有数都通过规则生成出来。然后再将所有数异或，因为异或满足左结合律，所以可以一边生成，一边异或，最后返回所有数异或的和。
3. 源码详解
int xorOperation(int n, int start){
int i, ans = 0;
for(i = 0; i < n; ++i) {
ans ^= start + i*2; // (1)
}
return ans;
}
- ( 1 ) (1) (1) 根据规则一边生成，一边异或，最后返回所有数异或后的结果；
9、整数的各位积和之差
1. 问题描述
给你一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \le n \le 10^5) n(1≤n≤105)，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
2. 问题分析
首先，可以利用迭代将每位数字取出来，然后用两个变量，在迭代的过程中，分别保存它们的 积 与 和，然后再相减即可。
3. 源码详解
int subtractProductAndSum(int n){
int prod = 1, sum = 0, digit;
while(n) {
digit = n % 10; // (1)
prod *= digit; // (2)
sum += digit; // (3)
n /= 10; // (4)
}
return prod - sum; // (5)
}
- ( 1 ) (1) (1) 取当前数字的最低位；
- ( 2 ) (2) (2) 将各位数字的乘积存储在
prod上； - ( 3 ) (3) (3) 将给为数字的和存户在
sum上； - ( 4 ) (4) (4) 将数字除10；
- ( 5 ) (5) (5) 返回 乘积 – 和；
10、统计位数为偶数的数字
1. 问题描述
给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
2. 问题分析
对每个数字不断除10，然后统计多少位，如果位数为偶数则计数器加一，最后返回计数器。
3. 源码详解
int findNumbers(int* nums, int numsSize){
int i, bit, cnt = 0;
for(i = 0; i < numsSize; ++i) {
bit = 0;
while(nums[i]) {
nums[i] /= 10;
++bit; // (1)
}
if(bit % 2 == 0)
++cnt; // (2)
}
return cnt; // (3)
}
- ( 1 ) (1) (1) 对于每个数，不断除10，用
bit统计当前数的位数； - ( 2 ) (2) (2) 如果位数为偶数的数，则计数器自增一；
- ( 3 ) (3) (3) 返回计数器；
11、搜索旋转排序数组
1. 问题描述
整数数组
nums按升序排列，数组中的值 互不相同 。给你 旋转后 的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。
2. 问题分析
这个问题问了一大堆，最后其实就是在一个数组中找一个数，找不到就返回 -1。OK，直接搞，不要有顾虑， O ( n ) O(n) O(n) 还能怎么卡你？怎么卡都卡不住，一次遍历完事。
3. 源码详解
int search(int* nums, int numsSize, int target){
int i;
for(i = 0; i < numsSize; ++i) {
if(nums[i] == target) {
return i; // (1)
}
}
return -1; // (2)
}
- ( 1 ) (1) (1) 遍历数组，找到满足条件的数，返回对应下标；
- ( 2 ) (2) (2) 如果遍历完毕还没有找到，则返回 -1；
12、差的绝对值为 K 的数对数目
1. 问题描述
给你一个整数数组 n u m s nums nums 和一个整数 k k k，长度小于等于 200，请你返回数对 ( i , j ) (i, j) (i,j) 的数目，满足 i < j i < j i<j 且 ∣ n u m s [ i ] − n u m s [ j ] ∣ = = k |nums[i] – nums[j]| == k ∣nums[i]−nums[j]∣==k。
2. 问题分析
直接枚举两个下标，值相减等于 k k k 时计数器加一。枚举完毕，返回计数器。
3. 源码详解
int countKDifference(int* nums, int numsSize, int k){
int i, j, ans = 0;
for(i = 0; i < numsSize; ++i) {
for(j = i + 1; j < numsSize; ++j) {
if( abs(nums[i] - nums[j]) == k ) // (1)
++ans;
}
}
return ans;
}
- ( 1 ) (1) (1) 枚举任意两个数，如果两个数相差的绝对值等于 k k k 则计数器加一；
13、宝石与石头
1. 问题描述
给定字符串 J J J 代表石头中宝石的类型，和字符串 S S S 代表你拥有的石头。 S S S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J J J 中的字母不重复， J J J 和 S S S 中的所有字符都是字母。字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。
2. 问题分析
考虑到 J J J 中所有的字母要么是大写，要么是小写，即一定是 ASCII 字符，所以转换成整型后只有 [ 0 , 255 ] [0, 255] [0,255] 的值，可以开辟一个大小为 256 的哈希数组，然后遍历一遍字符串 J J J，对于出现的字符标记位 1。然后再遍历字符串 S S S，如果在哈希数组中找到对应的字符，则计数器加一。最后，返回计数器就是答案了。
3. 源码详解
int has[256];
int numJewelsInStones(char* jewels, char* stones){
int i;
int ans = 0;
memset(has, 0, sizeof(has));
for(i = 0; jewels[i]; ++i) {
has[ jewels[i] ] = 1; // (1)
}
for(i = 0; stones[i]; ++i) {
if( has[ stones[i] ] ) {
++ans; // (2)
}
}
return ans; // (3)
}
- ( 1 ) (1) (1) 遍历一遍字符串 J J J，对于出现的字符标记位 1；
- ( 2 ) (2) (2) 遍历字符串 S S S，如果在哈希数组中找到对应的字符，则计数器加一；
- ( 3 ) (3) (3) 返回计数器；
14、所有奇数长度子数组的和
1. 问题描述
给你一个长度为 n ( n ≤ 100 ) n (n \le 100) n(n≤100) 的正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。
2. 问题分析
这个问题输入的是一个数组，输出一个数。这个数是所有 奇数长度 子数组 的和。首先可以枚举长度，再枚举起点，然后就是统计一段区间的和， 时间复杂度为 O ( n 3 ) O(n^3) O(n3)，可以利用前缀和把时间复杂度降低到 O ( n 2 ) O(n^2) O(n2)，然而这个问题没必要，因为 n n n 的范围比较小。
3. 源码详解
int sumOddLengthSubarrays(int* arr, int arrSize){
int len, start, i, sum = 0;
for(len = 1; len <= arrSize; len += 2) {
// (1)
for(start = 0; start + len <= arrSize; ++start) {
// (2)
for(i = start; i < start + len; ++i) {
// (3)
sum += arr[i];
}
}
}
return sum;
}
- ( 1 ) (1) (1) 枚举长度；
- ( 2 ) (2) (2) 枚举区间起点；
- ( 3 ) (3) (3) 计算区间和累加到
sum；
15、缺失的第一个正数
1. 问题描述
给你一个 n ( n ≤ 5 × 1 0 5 ) n(n \le 5 \times 10^5) n(n≤5×105) 个元素的未排序的整数数组 n u m s nums nums，数组元素范围为整型，请你找出其中没有出现的最小的正整数。
2. 问题分析
1）定义 m a x n maxn maxn 为 500001；
2）如果在 1 到 m a x n maxn maxn 之间的数字，映射到哈希数组中；
3）然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
4）所有数字都遍历完毕，仍然没有找到，则答案为 n + 1 n+1 n+1。
3. 源码详解
#define maxn 500001
int hash[500001], cases = 0;
int firstMissingPositive(int* nums, int numsSize){
int i;
++cases;
for(i = 0; i < numsSize; ++i) {
if(nums[i] > 0 && nums[i] < maxn)
hash[ nums[i] ] = cases; // (1)
}
for(i = 1; i <= numsSize; ++i) {
if(hash[i] < cases) {
return i; // (2)
}
}
return numsSize + 1; // (3)
}
- ( 1 ) (1) (1) 如果在 1 到 m a x n maxn maxn 之间的数字，映射到哈希数组中；
- ( 2 ) (2) (2) 然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
- ( 3 ) (3) (3) 所有数字都遍历完毕，仍然没有找到，则答案为 n + 1 n+1 n+1；
16、排序数组
1. 问题描述
给你一个整数数组 nums，请你将该数组升序排列。
2. 问题分析
C语言有自带的排序函数qsort，四个参数如下：
1）待排序数组的首地址；
2）待排序数组的元素个数；
3）待排序数组的单个元素的字节数；
4）排序依据的仿函数；
3. 源码详解
int cmp(const void*a, const void* b) {
return *(int *)a - *(int *)b; // (1)
}
int* sortArray(int* nums, int numsSize, int* returnSize){
qsort(nums, numsSize, sizeof(int), cmp); // (2)
*returnSize = numsSize; // (3)
return nums; // (4)
}
- ( 1 ) (1) (1)
a作为数组中某个元素的地址，(int *)a代表将地址转换成指向整数的地址，*(int *)a则代表取实际地址上的值；对两个数值相减，返回三种数：小于零、等于零、大于零，来决定是否对数据元素进行交换； - ( 2 ) (2) (2) 调用快速排序的库函数；
- ( 3 ) (3) (3) 外部调用
sortArray时，只会返回一个指针首地址，具体有多少个元素是不知道的，所以需要一个returnSize作为返回值返回出去，让调用方知道返回的数组的数组长度是多少； - ( 4 ) (4) (4) 返回排完序的数组首地址；
17、根据字符出现频率排序
1. 问题描述
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
2. 问题分析
这题可以用来练习C语言中qsort的结构体排序，之后会大量用到。即排序的数组元素类型是一个结构体，通过一个cmp比较函数实现自定义的关键字比较，从而实现排序的过程。主要分为以下三步：
1）定义一个结构体，两个字段：一个是字符字段，用于标志；一个是数量字段，用于排序；
2）遍历一遍字符串，统计填充完这个长度为 256 的结构体数组（因为 ASCII 字符）；
3）对结构体执行数量递减排序；
4）按照排序后的结构体顺序，将字符填充到字符串供返回；
3. 源码详解
typedef struct Data {
// (1)
int cnt;
int ch;
}Data;
int cmp(const void* a, const void* b) {
// (2)
return - ((Data *)a)->cnt + ((Data *)b)->cnt;
}
char * frequencySort(char * s){
int i, size = 0;
Data ans[256];
for(i = 0; i < 256; ++i) {
// (3)
ans[i].cnt = 0;
ans[i].ch = i;
}
for(i = 0; s[i]; ++i) {
++ ans[ s[i] ].cnt; // (4)
}
qsort(ans, 256, sizeof(Data), cmp); // (5)
for(i = 0; i < 256; ++i) {
while( ans[i].cnt ) {
--ans[i].cnt;
s[size++] = ans[i].ch; // (6)
}
}
s[size] = 'typedef struct Data {
// (1)
int cnt;
int ch;
}Data;
int cmp(const void* a, const void* b) {
// (2)
return - ((Data *)a)->cnt + ((Data *)b)->cnt;
}
char * frequencySort(char * s){
int i, size = 0;
Data ans[256];
for(i = 0; i < 256; ++i) {
// (3)
ans[i].cnt = 0;
ans[i].ch = i;
}
for(i = 0; s[i]; ++i) {
++ ans[ s[i] ].cnt; // (4)
}
qsort(ans, 256, sizeof(Data), cmp); // (5)
for(i = 0; i < 256; ++i) {
while( ans[i].cnt ) {
--ans[i].cnt;
s[size++] = ans[i].ch; // (6)
}
}
s[size] = '\0'; // (7)
return s;
}
'; // (7)
return s;
}
- ( 1 ) (1) (1) 定义一个结构体，两个字段：一个是字符字段，用于标志；一个是数量字段，用于排序；
- ( 2 ) (2) (2) 排序依据，转换成
Data结构体后逆序排序； - ( 3 ) (3) (3) 初始化每个字符初始数量为 0；
- ( 4 ) (4) (4) 遍历一遍字符串，对每个字符进行计数；
- ( 5 ) (5) (5) 对结构体进行排序；
- ( 6 ) (6) (6) 按照排序顺序将字符一个一个填充进用于返回的字符串；
- ( 7 ) (7) (7) 字符串结尾加上结束标记；
18、二进制链表转整数
1. 问题描述
给你一个单链表的引用结点
head。链表中每个结点的值不是 0 0 0 就是 1 1 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值。
2. 问题分析
二进制转十进制的基础题，只不过将存储方式变成了链式存储，直接上代码。
3. 源码详解
int getDecimalValue(struct ListNode* head){
int s = 0;
while(head) {
s = s * 2 + head->val; // (1)
head = head->next; // (2)
}
return s;
}
- ( 1 ) (1) (1) 进制转换的递推；
- ( 2 ) (2) (2) 执行链表的遍历；
19、K 进制表示下的各位数字总和
1. 问题描述
给你一个十进制整数 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 和一个基数 k ( k ≤ 10 ) k(k \le 10) k(k≤10)，请你将 n n n 从 十进制 表示转换为 k k k 进制 表示，计算并返回转换后各位数字的 总和 。转换后，各位数字应当视作是 十进制数字，且它们的总和也应当按 十进制表示返回。
2. 问题分析
就是一个进制转换，顺便在转换的过程中，将每一位数字进行加和。利用 while 迭代除 k k k 求解。
3. 源码详解
int sumBase(int n, int k){
int sum = 0;
while(n) {
sum += n % k; // (1)
n /= k;
}
return sum;
}
- ( 1 ) (1) (1) 求出模 k k k 后的每一位，并且累加；
20、各位相加
1. 问题描述
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
2. 问题分析
对每个数字不断除10，每次迭代过程取最低位进行累加。得到的结果如果小于 10 则返回，否则继续递归计算。
3. 源码详解
int addDigits(int num){
int sum = 0;
if(num < 10) {
return num; // (1)
}
while(num) {
sum += num % 10; // (2)
num /= 10;
}
return addDigits(sum); // (3)
}
- ( 1 ) (1) (1) 递归出口；
- ( 2 ) (2) (2) 迭代相加每一位；
- ( 3 ) (3) (3) 递归重复计算；
21、七进制数
1. 问题描述
给定一个整数
num，将其转化为 七进制，并以字符串形式输出。
2. 问题分析
进制转换的基础题，需要考虑以下几点：
1）返回的字符串必须是堆内存，所以需要 malloc进行申请内存，不能用栈上的内存；
2）考虑负数的情况；
3）考虑零的情况；
4）用栈来存储中间结果；
5）返回C字符串需要用'\0'结尾；
3. 源码详解
#define maxn 20
char * convertToBase7(int num){
char *ret = (char *)malloc( maxn * sizeof(char) ); // (1)
int stack[maxn], top = 0;
int returnSize = 0;
if(num < 0) {
// (2)
ret[returnSize++] = '-';
num = -num;
}
if(num == 0) {
// (3)
stack[top++] = 0;
}else {
while(num) {
stack[top++] = num % 7; // (4)
num /= 7;
}
}
while(top--) {
// (5)
ret[returnSize++] = stack[top] + '0';
}
ret[returnSize] = '#define maxn 20
char * convertToBase7(int num){
char *ret = (char *)malloc( maxn * sizeof(char) ); // (1)
int stack[maxn], top = 0;
int returnSize = 0;
if(num < 0) {
// (2)
ret[returnSize++] = '-';
num = -num;
}
if(num == 0) {
// (3)
stack[top++] = 0;
}else {
while(num) {
stack[top++] = num % 7; // (4)
num /= 7;
}
}
while(top--) {
// (5)
ret[returnSize++] = stack[top] + '0';
}
ret[returnSize] = '\0'; // (6)
return ret;
}
'; // (6)
return ret;
}
- ( 1 ) (1) (1) 返回的字符串必须是堆内存，所以需要
malloc进行申请内存，不能用栈上的内存； - ( 2 ) (2) (2) 对于负数的情况，在返回的字符串前面加上一个负号
'-'； - ( 3 ) (3) (3) 0 的情况单独入栈一个 0 即可；
- ( 4 ) (4) (4) 否则，进行七进制的转换后将每个数位一一入栈；
- ( 5 ) (5) (5) 将所有数字位从栈顶弹出后组成字符串；
- ( 6 ) (6) (6) 字符串尾部加上结尾标记；
22、数字转换为十六进制数
1. 问题描述
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
1）十六进制中所有字母(a-f)都必须是小写。
2）十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
3）给定的数确保在32位有符号整数范围内。
4）不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
2. 问题分析
由于负数是采用补码的形式，而计算机内部存储也是用的补码，所以直接采用位运算更加方便。不用区分正数和负数，但是需要考虑 0 的情况。
3. 源码详解
char getChar(int num) {
// (1)
if(num <= 9) {
return num + '0';
}
return num - 10 + 'a';
}
char * toHex(int num){
int stack[20], top = 0;
char *ret = (char *)malloc(20*sizeof(char)); // (2)
int returnSize = 0;
if(num == 0) {
// (3)
ret[returnSize++] = '0';
ret[returnSize] = 'char getChar(int num) {
// (1)
if(num <= 9) {
return num + '0';
}
return num - 10 + 'a';
}
char * toHex(int num){
int stack[20], top = 0;
char *ret = (char *)malloc(20*sizeof(char)); // (2)
int returnSize = 0;
if(num == 0) {
// (3)
ret[returnSize++] = '0';
ret[returnSize] = '\0';
return ret;
}
while(num) {
stack[top++] = num & 0xf; // (4)
num >>= 4; // (5)
num &= ( (1<<28) - 1 ); // (6)
}
while(top--) {
ret[returnSize++] = getChar(stack[top]);
}
ret[returnSize] = '\0';
return ret;
}
';
return ret;
}
while(num) {
stack[top++] = num & 0xf; // (4)
num >>= 4; // (5)
num &= ( (1<<28) - 1 ); // (6)
}
while(top--) {
ret[returnSize++] = getChar(stack[top]);
}
ret[returnSize] = 'char getChar(int num) {
// (1)
if(num <= 9) {
return num + '0';
}
return num - 10 + 'a';
}
char * toHex(int num){
int stack[20], top = 0;
char *ret = (char *)malloc(20*sizeof(char)); // (2)
int returnSize = 0;
if(num == 0) {
// (3)
ret[returnSize++] = '0';
ret[returnSize] = '\0';
return ret;
}
while(num) {
stack[top++] = num & 0xf; // (4)
num >>= 4; // (5)
num &= ( (1<<28) - 1 ); // (6)
}
while(top--) {
ret[returnSize++] = getChar(stack[top]);
}
ret[returnSize] = '\0';
return ret;
}
';
return ret;
}
- ( 1 ) (1) (1) 提供一个将数字转换成字符的函数；
- ( 2 ) (2) (2) 申请一块用于返回的内存空间，切忌直接用栈上空间；
- ( 3 ) (3) (3) 当值为 0 时单独处理；
- ( 4 ) (4) (4) 相当于模上 16；
- ( 5 ) (5) (5) 相当于除上 16；
- ( 6 ) (6) (6) 负数右移，最高位会补1，所以需要把最高位的1去掉；
23、数组串联
1. 问题描述
给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2 n 2n 2n 的答案数组 a n s ans ans ，数组下标 从 0 开始计数 ，对于所有 0 ≤ i < n 0 \le i \lt n 0≤i<n 的 i i i ，满足下述所有要求： a n s [ i ] = = n u m s [ i ] a n s [ i + n ] = = n u m s [ i ] ans[i] == nums[i] \\ ans[i + n] == nums[i] ans[i]==nums[i]ans[i+n]==nums[i] 具体而言，ans 由两个 nums 数组 串联 形成。返回数组 ans 。
2. 问题分析
根据题意一层循环枚举即可，这个问题需要返回的是一个数组，所以涉及到malloc申请内存。
3. 源码详解
int* getConcatenation(int* nums, int numsSize, int* returnSize){
int i;
int *ret = (int *)malloc(2*numsSize*sizeof(int)); // (1)
*returnSize = 2 * numsSize; // (2)
for(i = 0; i < numsSize; ++i) {
ret[i+numsSize] = ret[i] = nums[i]; // (3)
}
return ret;
}
- ( 1 ) (1) (1) 申请一块数组内存，数组长度为
numsSize的两倍； - ( 2 ) (2) (2)
returnSize是一个指向一个变量地址的指针，这个变量的目的就是告诉调用方，这个getConcatenation函数返回的数组的长度，如果没有这个值，光凭返回值的数组首地址是无法知道数组实际长度的，而这里要求数组长度为numsSize的两倍，所以给returnSize指向的值赋值即可； - ( 3 ) (3) (3) 根据题意进行赋值；
24、重新排列数组
1. 问题描述
给你一个数组 nums ，数组中有 2 n 2n 2n 个元素，按 [ x 1 , x 2 , . . . , x n , y 1 , y 2 , . . . , y n ] [x_1,x_2,…,x_n,y_1,y_2,…,y_n] [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。请你将数组按 [ x 1 , y 1 , x 2 , y 2 , . . . , x n , y n ] [x_1,y_1,x_2,y_2,…,x_n,y_n] [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
2. 问题分析
根据数组的映射关系，对于第 i ( 0 ≤ i < 2 n ) i(0 \le i \lt 2n) i(0≤i<2n) 个位置，分为两种情况：
1）如果 i i i 为奇数，则为原先第 n + i 2 n + \frac i 2 n+2i 个位置上的值；
2）如果 i i i 为偶数，则为原先第 i + 1 2 \frac {i+1} 2 2i+1 位置上的值；
3. 源码详解
int* shuffle(int* nums, int numsSize, int n, int* returnSize){
int i;
int *ret = (int *)malloc( sizeof(int) * numsSize ); // (1)
for(i = 0; i < numsSize; ++i) {
if(i & 1) {
ret[i] = nums[n + i/2]; // (2)
}else {
ret[i] = nums[(i+1)/2]; // (3)
}
}
*returnSize = numsSize; // (4)
return ret;
}
- ( 1 ) (1) (1) 返回堆上内存，所以需要申请数组空间；
- ( 2 ) (2) (2) 如果 i i i 为奇数，则为原先第 n + i 2 n + \frac i 2 n+2i 个位置上的值；
- ( 3 ) (3) (3) 如果 i i i 为偶数，则为原先第 i + 1 2 \frac {i+1} 2 2i+1 位置上的值；
- ( 4 ) (4) (4) 设置返回的数组的长度；
25、打印从1到最大的n位数
1. 问题描述
输入数字 n n n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
2. 问题分析
输入 n n n，输出 [ 1 , 1 0 n ) [1, 10^n) [1,10n) 中的所有数。所以只需要利用 n n n 次循环计算 1 0 n 10^n 10n 然后再来一次循环对数组进行填充即可。
3. 源码详解
int* printNumbers(int n, int* returnSize){
int i;
int f = 1;
int *ret;
for(i = 0; i < n; ++i) {
f *= 10; // (1)
}
--f; // (2)
*returnSize = f; // (3)
ret = (int *)malloc( f * sizeof(int) ); // (4)
for(i = 1; i <= f; ++i) {
ret[i-1] = i; // (5)
}
return ret;
}
- ( 1 ) (1) (1) 计算 1 0 n 10^n 10n；
- ( 2 ) (2) (2) 计算 1 0 n − 1 10^n-1 10n−1；
- ( 3 ) (3) (3) 设置数组长度用于返回；
- ( 4 ) (4) (4) 申请堆内存用于填充；
- ( 5 ) (5) (5) 填充数组用于返回；
26、一维数组的动态和
1. 问题描述
给你一个数组 nums 。数组「 动态和 」的计算公式为： r u n n i n g S u m [ i ] = s u m ( n u m s [ 0 ] … n u m s [ i ] ) runningSum[i] = sum(nums[0]…nums[i]) runningSum[i]=sum(nums[0]…nums[i]) 请返回 nums 的动态和。
2. 问题分析
这个就是前缀和，直接转化成前缀和公式： r u n n i n g S u m [ i ] = { n u m s [ 0 ] i = 0 r u n n i n g S u m [ i − 1 ] + n u m s [ i ] i > 0 runningSum[i] = \begin{cases} nums[0] & i = 0\\ runningSum[i-1] + nums[i] & i > 0 \end{cases} runningSum[i]={
nums[0]runningSum[i−1]+nums[i]i=0i>0
3. 源码详解
int* runningSum(int* nums, int numsSize, int* returnSize){
int i;
int *ret = (int *)malloc( numsSize * sizeof(int) ); // (1)
for(i = 0; i < numsSize; ++i) {
ret[i] = nums[i]; // (2)
if(i) {
ret[i] += ret[i-1]; // (3)
}
}
*returnSize = numsSize; // (4)
return ret;
}
- ( 1 ) (1) (1) 分配一块数组的内存空间；
- ( 2 ) (2) (2)
i = 0的情况； - ( 3 ) (3) (3)
i > 0的情况； - ( 4 ) (4) (4) 填充数组长度用于返回；
27、有多少小于当前数字的数字
1. 问题描述
给你一个长度小于 500 的数组 n u m s nums nums，对于其中每个元素 n u m s [ i ] nums[i] nums[i]，请你统计数组中比它小的所有数字的数目。换而言之，对于每个 n u m s [ i ] nums[i] nums[i] 你必须计算出有效的 j j j 的数量，其中 j j j 满足 j < > i j <> i j<>i 且 n u m s [ j ] < n u m s [ i ] nums[j] < nums[i] nums[j]<nums[i]。以数组形式返回答案。
2. 问题分析
两次循环枚举，第一层循环枚举每个数，第二层循环，判断比它小的数的个数，满足则自增计数器。这里的计数器需要返回给调用方，所以需要在函数内申请内存。
3. 源码详解
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
int *ret = (int *)malloc(numsSize * sizeof(int));
int i, j;
for(i = 0; i < numsSize; ++i) {
// (1)
ret[i] = 0; // (2)
for(j = 0; j < numsSize; ++j) {
// (3)
if(nums[j] < nums[i]) {
++ret[i]; // (4)
}
}
}
*returnSize = numsSize;
return ret;
}
- ( 1 ) (1) (1) 枚举第 i i i 个数；
- ( 2 ) (2) (2) 初始化比第 i i i 个数小的数的个数为 0；
- ( 3 ) (3) (3) 循环遍历所有数；
- ( 4 ) (4) (4) 判断是否比第 i i i 个数小，满足则自增计数器；
28、找出所有子集的异或总和再求和
1. 问题描述
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。例如，数组 [ 2 , 5 , 6 ] [2,5,6] [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1。
给你一个元素个数不大于 12 个的数组 n u m s nums nums，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
2. 问题分析
元素个数最多才 12 个，每个元素取或不取，总共 2 12 2^{12} 212 种方案，设想一个数 x x x，将它转换成二进制以后，1 表示选， 0表示不选，就可以模拟子集了。
然后，枚举 [ 1 , 2 n ) [1, 2^{n}) [1,2n) 中的每个数 i i i，将它 进行二进制拆分以后，得到的 1 的位置进行 异或和，再将所以的这几个异或和相加，就是答案了。
3. 源码详解
int subsetXORSum(int* nums, int numsSize){
int i, j, ans;
int sum = 0;
for(i = 0; i < (1 << numsSize); ++i) {
// (1)
ans = 0;
for(j = 0; j < numsSize; ++j) {
// (2)
if(i & (1<<j)) {
// (3)
ans ^= nums[j]; // (4)
}
}
sum += ans; // (5)
}
return sum; // (6)
}
- ( 1 ) (1) (1) 枚举所有子集代表的二进制数 i i i；
- ( 2 ) (2) (2) 选择二进制数 i i i 的每一位；
- ( 3 ) (3) (3) 判断 i i i 的二进制位上为 1 的位；
- ( 4 ) (4) (4) 计算异或和；
- ( 5 ) (5) (5) 累加所有子集的异或和；
- ( 6 ) (6) (6) 返回异或和累加；
29、解码异或后的数组
1. 问题描述
未知 整数数组
arr由 n n n 个非负整数组成。经编码后变为长度为 n − 1 n – 1 n−1 的另一个整数数组encoded，其中encoded[i] = arr[i]⊕arr[i + 1]。例如，arr = [1,0,2,1]经编码后得到encoded = [1,2,3]。
给你编码后的数组encoded和原数组arr的第一个元素first（即arr[0]）。
请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
2. 问题分析
假设编码前的数组为：
a 0 a 1 a 2 a 3 a 4 . . . a n − 1 a_0 a_1 a_2 a_3 a_4 … a_{n-1} a0a1a2a3a4...an−1
编码后的数组为：
b 0 b 1 b 2 b 3 b 4 . . . b n − 2 b_0 b_1 b_2 b_3 b_4 … b_{n-2} b0b1b2b3b4...bn−2
其中， b 0 = a 0 ⊕ a 1 b_0 = a_0⊕a_1 b0=a0⊕a1，由于 a 0 a_0 a0 和 b 0 b_0 b0 都是已知的，所以 a 1 = a 0 ⊕ b 0 a_1 = a_0⊕b_0 a1=a0⊕b0。
同样，根据 b 1 = a 1 ⊕ a 2 b_1=a_1⊕a_2 b1=a1⊕a2，则有 a 2 = b 1 ⊕ a 1 a_2=b_1⊕a_1 a2=b1⊕a1。根据数学归纳法，可以得到：
a i = { f i r s t i = 0 b i − 1 ⊕ a i − 1 i > 0 a_i=\begin{cases} first & i=0 \\ b_{i-1}⊕a_{i-1} & i > 0\end{cases} ai={
firstbi−1⊕ai−1i=0i>0
3. 源码详解
int* decode(int* encoded, int encodedSize, int first, int* returnSize){
int *decode = (int *)malloc( (encodedSize+1) * sizeof(int));
int i;
*returnSize = encodedSize + 1;
decode[0] = first; // (1)
for(i = 1; i < *returnSize; ++i) {
decode[i] = (encoded[i-1] ^ decode[i-1]);// (2)
}
return decode;
}
- ( 1 ) (1) (1) 根据上文的公式，
decode即数组 a a a； - ( 2 ) (2) (2) 选择异或性质求解；
30、交换数字
1. 问题描述
编写一个函数，不用临时变量，直接交换
numbers = [a, b]中 a a a 与 b b b 的值。
2. 问题分析
这里，我们利用异或来实现变量交换。
3. 源码详解
int* swapNumbers(int* numbers, int numbersSize, int* returnSize){
numbers[0] = numbers[0] ^ numbers[1]; // (1)
numbers[1] = numbers[0] ^ numbers[1]; // (2)
numbers[0] = numbers[0] ^ numbers[1]; // (3)
*returnSize = numbersSize;
return numbers;
}
- 我们直接来看 ( 1 ) (1) (1) 和 ( 2 ) (2) (2) 这两句话，相当于
numbers[1]等于numbers[0] ^ numbers[1] ^ numbers[1]，根据异或的几个性质，我们知道，这时候的numbers[1]的值已经变成原先numbers[0]的值了。 - 而再来看最后一句话，相当于
numbers[0]等于numbers[0] ^ numbers[1] ^ numbers[0]，还是根据异或的几个性质，这时候，numbers[0]的值已经变成了原先numbers[1]的值。 - 从而实现了变量
numbers[0]和numbers[1]的交换。
31、位1的个数
1. 问题描述
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数。
2. 问题分析
假设某个数的低 k k k 位为 0，第 k + 1 k+1 k+1 位为 1，二进制表示如下： . . . 1 00…00 ⏟ k …1\underbrace{00…00}_{\rm k} ...1k
00...00 如果，我们把这个二进制数减去一，得到的就是： . . . 0 11…11 ⏟ k …0\underbrace{11…11}_{\rm k} ...0k
11...11 我们把这两个数进行位与运算，得到 . . . 0 00…00 ⏟ k …0\underbrace{00…00}_{\rm k} ...0k
00...00 这就代表可以通过 x & (x-1)这一步操作去掉低位数过来的第一个1，反复操作直到结果为 0，操作了多少次就代表有多少个1。
3. 源码详解
int hammingWeight(uint32_t n) {
int c = 0;
while(n) {
n &= (n - 1); // (1)
++c; // (2)
}
return c;
}
- ( 1 ) (1) (1) 去掉低位的 1；
- ( 2 ) (2) (2) 计数器加一；
32、数字范围按位与
1. 问题描述
给你两个整数 l l l 和 r r r，表示区间 [ l , r ] [l, r] [l,r]，返回此区间内所有数字 按位与 的结果（包含 l l l 、 r r r 端点）。
2. 问题分析
将数字从 0 开始，转换成二进制以后依次排列得到如下的形式：
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
我们发现，最低位是01循环，次低位是0011循环，第三低位是00001111循环，根据数学归纳法，第 i ( i ≥ 0 ) i (i \ge 0) i(i≥0) 低位一定是 2 i 2^i 2i 个0和 2 i 2^i 2i 个1的循环。
首先，计算区间长度 l e n = r − l + 1 len=r-l+1 len=r−l+1我们可以从低到高枚举每个位，对于第 i i i 低位，如果 l e n > 2 i len \gt 2^{i} len>2i，说明必然是有 0 的，所以位与以后，这一位必然是 0；否则，如果 l e n ≤ 2 i len \le 2^{i} len≤2i，只需要判断两个边界 l l l 和 r r r 的相应位，只有当两者的这一位都为 1 时，才说明中间所有的数的对应位都是 1，那么这一位的位与结果也是 1，否则，位与结果为零。
3. 源码详解
int rangeBitwiseAnd(int left, int right){
unsigned int l = left, r = right;
unsigned int len = r - l + 1; // (1)
unsigned int p2i;
unsigned int ans = 0;
int i;
for(i = 0; i < 31; ++i) {
p2i = (unsigned int)1 << i; // (2)
if(len > p2i) {
// (3)
continue;
}
if( (left & p2i) && (right & p2i) ) {
ans |= p2i; // (4)
}
}
return ans;
}
- ( 1 ) (1) (1) 长度有可能超出
int范围，所以转成unsigned int后再计算长度； - ( 2 ) (2) (2) 2 31 2^{31} 231 不在
int范围之内，所以左移时，1需要进行强制转换； - ( 3 ) (3) (3) 如果 l e n > 2 i len \gt 2^{i} len>2i，说明必然是有 0 的，所以位与以后，这一位必然是 0，直接跳过这一位，不作任何事情；
- ( 4 ) (4) (4) 如果 l e n ≤ 2 i len \le 2^{i} len≤2i，只需要判断两个边界 l l l 和 r r r 的相应位，只有当两者的这一位都为 1 时，才说明中间所有的数的对应位都是 1，那么这一位的位与结果也是 1；
33、颠倒二进制位
1. 问题描述
颠倒给定的 32 位无符号整数的二进制位。
2. 问题分析
将第 0 位和第 31 位交换，将第 1 位和第 30 位交换，将第 i i i 位和第 31 − i 31-i 31−i 位交换。所以我们首先需要提供一个获取一个数字的第 i i i 的接口。
如果第 i i i 和 31 − i 31-i 31−i 位不一样则执行交换逻辑，对于二进制来说，不一样的情况，一定是 (1 和 0) 或者
(0 和 1)。所以，交换实际上可以利用异或来完成。
3. 源码详解
bool getbit(uint32_t n, int k) {
return n & ((uint32_t)1 << k); // (1)
}
uint32_t reverseBits(uint32_t n) {
for(int i = 0; i < 16; ++i) {
bool biti = getbit(n, i);
bool bitn = getbit(n, 31 - i);
if(biti != bitn) {
// (2)
n ^= (uint32_t)1 << i; // (3)
n ^= (uint32_t)1 << 31 - i;
}
}
return n;
}
- ( 1 ) (1) (1) 利用位运算获取 n n n 的 第 k k k 位是否为 1；
- ( 2 ) (2) (2) 如果第 i i i 位和第 31 − i 31-i 31−i 位不同则执行交换逻辑；
- ( 3 ) (3) (3) 交换一定是 0 变 1, 1 变 0，所以可以采用异或来处理；
34、前 n 个数字二进制中 1 的个数
1. 问题描述
给定一个非负整数 n n n。对于 0 ≤ i ≤ n 0 \le i \le n 0≤i≤n 范围中的每个数字 i i i，计算其二进制数中的 1 的数目并将它们作为数组返回。
2. 问题分析
这个题是数学上非常有名的一种概念 —— 分型。就是由小数据推出大数据，也算是递推吧。话不多说，看下下面这个图基本就明白了。
所以我们可以得出如下的递推公式： f ( n ) = { 0 n = 0 1 n = 1 f ( n − 2 i − 1 ) 2 i ≤ n < 2 i + 2 i − 1 f ( n − 2 i − 1 ) + 1 2 i + 2 i − 1 ≤ n < 2 i + 1 f(n) = \begin{cases} 0 & n=0\\ 1 & n=1 \\ f(n – 2^{i-1})& 2^i \le n \lt 2^i + 2^{i-1} \\ f(n – 2^{i-1}) + 1& 2^i + 2^{i-1} \le n \lt 2^{i+1}\\ \end{cases} f(n)=⎩⎪⎪⎪⎨⎪⎪⎪⎧01f(n−2i−1)f(n−2i−1)+1n=0n=12i≤n<2i+2i−12i+2i−1≤n<2i+1
3. 源码详解
int* countBits(int n, int *returnSize) {
int i, flag;
int *bitCount = (int *)malloc( (n+1) * sizeof(int) );
*returnSize = n+1;
for(i = 0; i < n+1; ++i) {
bitCount[i] = -1;
}
bitCount[0] = 0;
if(n == 0) {
return bitCount;
}
bitCount[1] = 1;
if(n == 1) {
return bitCount;
}
for(i = 1; ; ++i) {
flag = 0;
for(int j = 1<<i; j < (1<<i+1); ++j) {
if(j < (1<<i) + (1<<i-1)) {
bitCount[j] = bitCount[j - (1<<i-1)];
}else {
bitCount[j] = bitCount[j - (1<<i-1)] + 1;
}
if(j >= n) {
flag = 1;
break;
}
}
if(flag) break;
}
return bitCount;
}
- 这段代码就是上文提到的递推公式，只有一个点需要注意就是：
1<<n代表的是 2 n 2^n 2n，剩下的就是循环进行递推。
35、好数对的数目
1. 问题描述
给你一个整数数组 nums 。每个数字都小于等于 100。如果一组数字 ( i , j ) (i,j) (i,j) 满足
nums[i] == nums[j]且 i < j i < j i<j，就可以认为这是一组 好数对。
返回好数对的数目。
2. 问题分析
对每个数进行计数，假设数 i i i 有 x x x 个，那么好数对的数目就是 C x 2 = x ( x − 1 ) 2 C_x^2 = \frac {x(x-1)} 2 Cx2=2x(x−1)。
3. 源码详解
int Hash[101];
int numIdenticalPairs(int* nums, int numsSize){
int i, x, ans = 0;
memset(Hash, 0, sizeof(Hash));
for(i = 0; i < numsSize; ++i) {
++Hash[ nums[i] ]; // (1)
}
for(i = 1; i <= 100; ++i) {
x = Hash[i];
ans += (x - 1) * x / 2; // (2)
}
return ans;
}
- ( 1 ) (1) (1) 遍历一遍数组，统计每个数字的数量；
- ( 2 ) (2) (2) 对于每个数字，用公式计算好数对，并累加；
36、判断句子是否为全字母句
1. 问题描述
全字母句 指包含英语字母表中每个字母至少一次的句子。给你一个仅由小写英文字母组成的字符串 sentence ，请你判断 sentence 是否为 全字母句 。如果是，返回 true ；否则，返回 false 。
2. 问题分析
遍历一遍字符串，映射到一个哈希计数器中；然后，再遍历哈希计数器的'a'-'z'位置，如果一旦有一个字母的计数器为0，则返回 false；否则，返回 true。
3. 源码详解
int Hash[256];
bool checkIfPangram(char * sentence){
int i;
memset(Hash, 0, sizeof(Hash));
for(i = 0; sentence[i]; ++i) {
++Hash[ sentence[i] ]; // (1)
}
for(i = 'a'; i <= 'z'; ++i) {
if(!Hash[i]) {
return false; // (2)
}
}
return true;
}
- ( 1 ) (1) (1) 遍历字符串，填充哈希计数器；
- ( 2 ) (2) (2) 遍历哈希计数器的
'a'-'z'位置，如果一旦有一个字母的计数器为0，则返回 false；
37、执行操作后的变量值
1. 问题描述
存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：
1）++X和X++使变量 X 的值 加 1；
2）--X和X--使变量 X 的值 减 1；
最初，X 的值是 0，给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。
2. 问题分析
遍历这个字符串数组，对于每个字符串，观察发现，只要字符串的第 1 个字符是 '+'，变量就要执行加一操作；否则，执行减一操作。
3. 源码详解
int finalValueAfterOperations(char ** operations, int operationsSize){
int i;
int x = 0;
for(i = 0; i < operationsSize; ++i) {
if(operations[i][1] == '+') {
++x; // (1)
}else {
--x; // (2)
}
}
return x;
}
- ( 1 ) (1) (1)
++X和X++使变量 X 的值 加 1； - ( 2 ) (2) (2)
--X和X--使变量 X 的值 减 1；
38、IP 地址无效化
1. 问题描述
给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
所谓无效化 IP 地址，其实就是用"[.]"代替了每个"."。
2. 问题分析
申请一块额外的辅助数组内存，用于接收需要处理的字符串，遍历一遍输入字符串，如果遇到 '.'字符，则在辅助数组中加入三个字符[.]，否则添加原字符。
3. 源码详解
char * defangIPaddr(char * address){
char *ret = (char *)malloc(1000 * sizeof(char));
int returnSize = 0;
int i;
for(i = 0; address[i]; ++i) {
if(address[i] == '.') {
// (1)
ret[ returnSize++ ] = '[';
ret[ returnSize++ ] = '.';
ret[ returnSize++ ] = ']';
}else {
// (2)
ret[ returnSize++ ] = address[i];
}
}
ret[ returnSize ] = 'char * defangIPaddr(char * address){
char *ret = (char *)malloc(1000 * sizeof(char));
int returnSize = 0;
int i;
for(i = 0; address[i]; ++i) {
if(address[i] == '.') {
// (1)
ret[ returnSize++ ] = '[';
ret[ returnSize++ ] = '.';
ret[ returnSize++ ] = ']';
}else {
// (2)
ret[ returnSize++ ] = address[i];
}
}
ret[ returnSize ] = '\0';
return ret;
}
';
return ret;
}
- ( 1 ) (1) (1) 处理
'.'字符的情况； - ( 2 ) (2) (2) 处理其它字符的情况；
39、统计一致字符串的数目
1. 问题描述
给你一个由不同字符组成的字符串
allowed和一个字符串数组words。如果一个字符串的每一个字符都在allowed中，就称这个字符串是 一致字符串 。请你返回words数组中 一致字符串 的数目。
2. 问题分析
还是利用哈希表：
1）将allowed字符串中的每个字符映射到哈希表中；
2）遍历字符串数组words中的每个字符串，对字符串中的每个字符检查是否在哈希表中，如果都在，则计数器加一；
3）返回计数器的值；
3. 源码详解
int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int Hash[256];
int i, j;
int ans = 0;
memset(Hash, 0, sizeof(Hash));
for(i = 0; allowed[i]; ++i) {
Hash[ allowed[i] ] = 1; // (1)
}
for(i = 0; i < wordsSize; ++i) {
for(j = 0; words[i][j]; ++j) {
if( !Hash[ words[i][j] ] ) {
break;
}
}
if(words[i][j] == 'int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int Hash[256];
int i, j;
int ans = 0;
memset(Hash, 0, sizeof(Hash));
for(i = 0; allowed[i]; ++i) {
Hash[ allowed[i] ] = 1; // (1)
}
for(i = 0; i < wordsSize; ++i) {
for(j = 0; words[i][j]; ++j) {
if( !Hash[ words[i][j] ] ) {
break;
}
}
if(words[i][j] == '\0') {
++ans; // (2)
}
}
return ans; // (3)
}
') {
++ans; // (2)
}
}
return ans; // (3)
}
- ( 1 ) (1) (1) 将
allowed字符串中的每个字符映射到哈希表中； - ( 2 ) (2) (2) 遍历字符串数组
words中的每个字符串，对字符串中的每个字符检查是否在哈希表中，如果都在，则计数器加一； - ( 3 ) (3) (3) 返回计数器的值；
40、反转字符串
1. 问题描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
2. 问题分析
翻转字符串类似将二进制位颠倒，其实就是第一个字符和最后一个字符进行交换，第二个和倒数第二个交换，以此类推，直到枚举到中间的字符。
3. 源码详解
void swap(char* a, char* b) {
// (1)
char tmp = *a;
*a = *b;
*b = tmp;
}
void reverseString(char* s, int sSize){
for(int i = 0; i < sSize / 2; ++i) {
// (2)
swap(&s[i], &s[sSize-i-1]);
}
}
- ( 1 ) (1) (1) 实现交换函数；
- ( 2 ) (2) (2) 交换的字符枚举到字符串中心即可；
41、左旋转字符串
1. 问题描述
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串
"abcdefg"和数字 2 2 2，该函数将返回左旋转两位得到的结果"cdefgab"。
2. 问题分析
这个问题，相当于将字符串做了一个平移，向左平移 k k k 个位置的话，相当于原本在 i i i 位置的字符被平移到了 ( i − k ) m o d n (i – k) \ mod \ n (i−k) mod n 的位置。所以，申请一个需要返回的数组，通过平移前的字符来填充相应位置即可。
3. 源码详解
char* reverseLeftWords(char* s, int k){
int i;
int n = strlen(s);
char *ret = (char *)malloc( (n + 1) * sizeof(char) );
for(i = 0; i < n; ++i) {
ret[i] = s[(i + k) % n]; // (1)
}
ret[n] = 'char* reverseLeftWords(char* s, int k){
int i;
int n = strlen(s);
char *ret = (char *)malloc( (n + 1) * sizeof(char) );
for(i = 0; i < n; ++i) {
ret[i] = s[(i + k) % n]; // (1)
}
ret[n] = '\0';
return ret;
}
';
return ret;
}
- ( 1 ) (1) (1) 平移 k k k 个位置；
42、检查两个字符串数组是否相等
1. 问题描述
给你两个字符串数组
word1和word2。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。
2. 问题分析
这个问题考察了C语言的两个基本的字符串操作函数：
1）字符串拼接函数：strcat；
2）字符串比较函数：strcmp；
3. 源码详解
char word[2][1010];
bool arrayStringsAreEqual(char ** word1, int word1Size, char ** word2, int word2Size){
int i;
word[0][0] = word[1][0] = 'char word[2][1010];
bool arrayStringsAreEqual(char ** word1, int word1Size, char ** word2, int word2Size){
int i;
word[0][0] = word[1][0] = '\0';
for(i = 0; i < word1Size; ++i) {
strcat(word[0], word1[i]); // (1)
}
for(i = 0; i < word2Size; ++i) {
strcat(word[1], word2[i]); // (2)
}
return strcmp(word[0], word[1]) == 0; // (3)
}
';
for(i = 0; i < word1Size; ++i) {
strcat(word[0], word1[i]); // (1)
}
for(i = 0; i < word2Size; ++i) {
strcat(word[1], word2[i]); // (2)
}
return strcmp(word[0], word[1]) == 0; // (3)
}
- ( 1 ) (1) (1) 将第一个字符串拼接成
word[0]； - ( 2 ) (2) (2) 将第二个字符串拼接成
word[1]； - ( 3 ) (3) (3) 比较两个字符串，相等则
strcmp函数返回 0；
43、复数乘法
1. 问题描述
复数 可以用字符串表示，遵循 “实部+虚部i” 的形式，并满足下述条件：
1）实部 是一个整数，取值范围是 [-100, 100]
2）虚部 也是一个整数，取值范围是 [-100, 100]
3） i 2 = − 1 i^2 = -1 i2=−1
给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。
2. 问题分析
这个问题比较综合，我们首先定义一个复数结构体。只要能够处理以下几个情况，我们的问题就可以迎刃而解了。
1）整数的序列化（整数 转 字符串）；
2）整数的反序列化（字符串 转 整数）；
3）复数结构体的序列化（复数结构体 转 字符串）；
4）复数结构体的反序列化（字符串 转 复数结构体）；
5）复数结构体的乘法（两个复数相乘返回复数）；
有了以上五个基础方法，我们只要对输入的两个字符串，反序列化成复数，然后执行复数乘法，再序列化成字符串返回就是答案了。
3. 源码详解
typedef struct Complex {
// (1)
int real;
int image;
}Complex;
Complex mul(const Complex a, const Complex b) {
// (2)
Complex ret;
ret.real = a.real * b.real - a.image * b.image;
ret.image = a.real * b.image + a.image * b.real;
return ret;
}
int getIntFromString(char *str, int s, int e) {
// (3)
int sign = 1, sum = 0;
if(str[s] == '-') {
sign = -1;
++s;
}
while(s <= e) {
sum = sum * 10 + str[s] - '0';
++s;
}
return sign * sum;
}
void getStringFromInt(int a, char* buffer) {
// (4)
int sign = 1, top = 0;
int bufferSize = 0;
char stack[20];
if(a == 0) {
buffer[0] = '0';
buffer[1] = '\0';
return ;
}
if(a < 0) {
a = -a;
buffer[bufferSize++] = '-';
}
while(a) {
stack[top++] = a % 10 + '0';
a /= 10;
}
while(top--) {
buffer[bufferSize++] = stack[top];
}
buffer[bufferSize] = '\0';
return;
}
Complex stringToComplex(char *a) {
// (5)
int i;
int len = strlen(a);
Complex ret;
ret.real = ret.image = 0;
for(i = 0; a[i]; ++i) {
if(a[i] == '+') {
break;
}
}
ret.real = getIntFromString(a, 0, i-1);
ret.image = getIntFromString(a, i+1, len-2);
return ret;
}
char *ComplexToString(const Complex x) {
// (6)
char *ret = (char *)malloc(100*sizeof(char));
char *tmp = (char *)malloc(100*sizeof(char));
ret[0] = '\0';
getStringFromInt(x.real, tmp);
strcat(ret, tmp);
strcat(ret, "+");
getStringFromInt(x.image, tmp);
strcat(ret, tmp);
strcat(ret, "i");
free(tmp);
return ret;
}
char * complexNumberMultiply(char * num1, char * num2){
// (7)
Complex a = stringToComplex(num1);
Complex b = stringToComplex(num2);
Complex c = mul(a, b);
return ComplexToString(c);
}
- ( 1 ) (1) (1) 定义一个复数的结构体，
real为实数部分，image为虚数部分； - ( 2 ) (2) (2) 根据复数定义，实现复数乘法；
- ( 3 ) (3) (3) 实现整数的反序列化，即字符串转整数，考虑 0 和 负数的情况；
- ( 4 ) (4) (4) 实现整数的序列化，即整数转字符串，考虑 0 和 负数的情况；
- ( 5 ) (5) (5) 实现复数的反序列化，即字符串转复数；
- ( 6 ) (6) (6) 实现复数的序列化，即复数转字符串；
- ( 7 ) (7) (7) 利用几个基本函数模拟复数的乘法过程。
44、开幕式焰火
1. 问题描述
给出一颗二叉树，要求结算二叉树上有多少不同值的结点，每个结点上的值是一个小于等于 1000 的正整数。
2. 问题分析
直接遍历二叉树，将值映射到一个哈希表中，然后统计哈希表中有值的元素个数就是答案
3. 源码详解
int Hash[1024];
void transfer(struct TreeNode* root) {
// (1)
if(root) {
Hash[root->val] = 1; // (2)
transfer(root->left);
transfer(root->right);
}
}
int numColor(struct TreeNode* root){
int i, sum = 0;
memset(Hash, 0, sizeof(Hash));
transfer(root);
for(i = 1; i <= 1000; ++i) {
if(Hash[i]) ++sum; // (3)
}
return sum;
}
- ( 1 ) (1) (1) 对二叉树进行递归遍历；
- ( 2 ) (2) (2) 遍历到的结点，将值记录到哈希表；
- ( 3 ) (3) (3) 在哈希表中的元素直接对计数器加一，最后返回计数器就是答案；
45、将数字变成 0 的操作次数
1. 问题描述
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。
如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
2. 问题分析
递归的经典问题。根据题意，令 f ( n ) f(n) f(n) 为变成 0 的步数，那么显然， f ( 0 ) = 0 f(0) = 0 f(0)=0；当 n n n 为偶数时， n n n 比 n / 2 n/2 n/2 多一步，即 f ( n ) = f ( n / 2 ) + 1 f(n) = f(n/2)+1 f(n)=f(n/2)+1；当 n n n 为奇数时， n n n 比 n − 1 n-1 n−1 多一步，即 f ( n ) = f ( n − 1 ) + 1 f(n) = f(n-1) + 1 f(n)=f(n−1)+1。直接求解即可。
3. 源码详解
int numberOfSteps(int num){
if(num == 0) {
return 0; // (1)
}
if(num % 2 == 1) {
return numberOfSteps(num-1)+1; // (2)
}else {
return numberOfSteps(num/2) + 1; // (3)
}
}
- ( 1 ) (1) (1) 递归出口；
- ( 2 ) (2) (2) 处理奇数的情况；
- ( 3 ) (3) (3) 处理偶数的情况；
46、层数最深叶子节点的和
1. 问题描述
给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
2. 问题分析
首先，我们需要确定某个结点是否是处于最深深度的，所以可以通过一次树的遍历，找出最深的深度值。再通过一次遍历，如果等于最深深度值的结点，将它的值进行累加。
两次遍历的时间复杂度均为 O ( n ) O(n) O(n)。
3. 源码详解
int depth[10001];
int max;
void getMaxDepth(struct TreeNode* root, int dep) {
// (1)
if(root == NULL) {
return ;
}
if(dep > max) {
max = dep;
}
getMaxDepth(root->left, dep + 1);
getMaxDepth(root->right, dep + 1);
}
int sumMaxDepthValue(struct TreeNode* root, int dep) {
// (2)
int lsum, rsum;
if(root == NULL) {
return 0;
}
if(dep == max) {
return root->val;
}
lsum = sumMaxDepthValue(root->left, dep+1);
rsum = sumMaxDepthValue(root->right, dep+1);
return lsum + rsum;
}
int deepestLeavesSum(struct TreeNode* root){
max = 0;
getMaxDepth(root, 0);
return sumMaxDepthValue(root, 0);
}
- ( 1 ) (1) (1)
getMaxDepth作为第一次遍历，将最大深度存储在全局变量max上； - ( 2 ) (2) (2)
sumMaxDepthValue作为第二次遍历，将深度值等于max的值累加；
47、二叉树的深度
1. 问题描述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
2. 问题分析
树的深度的定义：左子树 和 右子树 的深度中的大者 加 一。直接递归求解。
3. 源码详解
int max(int a, int b) {
return a > b ? a : b;
}
int maxDepth(struct TreeNode* root){
if(root == NULL) {
return 0; // (1)
} // (2)
return max( maxDepth(root->left), maxDepth(root->right) ) + 1;
}
- ( 1 ) (1) (1) 空树深度为0；
- ( 2 ) (2) (2) 取左右子树中深度大者，加一；
48、数组元素积的符号
1. 问题描述
已知函数
signFunc(x)将会根据 x x x 的正负返回特定值：
如果 x x x 是正数，返回 1 。
如果 x x x 是负数，返回 -1 。
如果 x x x 是等于 0 ，返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。返回signFunc(product)。
2. 问题分析
这个问题的陷阱很容易看出来，数字乘积有可能导致整型溢出从而影响判断，所以这个问题中，我们需要将它进行一个转换，任何正数 x x x 的 signFunc(x)和signFunc(1)是相同的；任何负数 x x x 的 signFunc(x)和signFunc(-1)是相同的；所以，只需要遍历一遍数组，
3. 源码详解
int arraySign(int* nums, int numsSize){
int i, prod = 1;
for(i = 0; i < numsSize; ++i) {
if(nums[i] == 0) {
prod = 0; // (1)
break;
}else if(nums[i] < 0) {
prod = -prod; // (2)
}
}
return prod;
}
- ( 1 ) (1) (1) 一旦出现 0，就是 0 了；
- ( 2 ) (2) (2) 出现负数，取反；出现正数，不影响符号；
49、删除中间节点
1. 问题描述
若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
例如，传入节点 c（位于单向链表a->b->c->d->e->f中），将其删除后，剩余链表为a->b->d->e->f
2. 问题分析
单向链表在删除链表结点时，需要知道被删除结点的前一个结点。目前，这个问题中，只知道需要删除的结点，而不知道上一个结点是什么。
所以，可以考虑将当前结点的下一个结点的值拷贝过来，然后删除它的后继结点。
3. 源码详解
void deleteNode(struct ListNode* node) {
node->val = node->next->val; // (1)
node->next = node->next->next; // (2)
}
- ( 1 ) (1) (1) 将后继结点的值拷贝过来；
- ( 2 ) (2) (2) 直接删除掉后继结点；
50、删除链表的节点
1. 问题描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
2. 问题分析
这题和 49 题不同，是有办法找到删除结点的前驱结点的。
考虑三种情况：
1）空链表；
2）头结点的值 和 给定值相等；直接返回头结点的后继结点；
3）头结点的值 和 给定值不等；迭代遍历链表，记录 前驱 和 当前，当前结点 等于 给定结点 时，直接将前驱指向后继即可。
3. 源码详解
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode *pre, *now;
if(head == NULL) {
return NULL; // (1)
}
if(head->val == val) {
// (2)
return head->next;
}
pre = head, now = head->next; // (3)
while(now) {
if(now->val == val) {
// (4)
pre->next = now->next;
break; // (5)
}
pre = now;
now = now->next; // (6)
}
return head; // (7)
}
- ( 1 ) (1) (1) 空链表直接返回空即可；
- ( 2 ) (2) (2) 等于头结点的情况，直接返回头结点的后继结点；
- ( 3 ) (3) (3) 记录 前驱结点 和 当前结点；
- ( 4 ) (4) (4) 找到需要删除的结点，直接让 它的前驱 指向 它的后继；
- ( 5 ) (5) (5) 由于题目要求只有一个，所以直接退出循环即可；
- ( 6 ) (6) (6) 前驱结点 和 当前结点 的指针都往前行进一格；
- ( 7 ) (7) (7) 返回列表头结点。
?让天下没有难学的算法?
C语言免费动漫教程，和我一起打卡！
?《光天化日学C语言》?
入门级C语言真题汇总
?《C语言入门100例》?
几张动图学会一种数据结构
?《画解数据结构》?
组团学习，抱团生长
?《算法入门指引》?
竞赛选手金典图文教程
?《夜深人静写算法》?
五、粉丝福利
语言入门：《光天化日学C语言》(示例代码)
语言训练：《C语言入门100例》试用版
数据结构：《画解数据结构》源码
算法入门：《算法入门》指引
算法进阶：《夜深人静写算法》算法模板
??
验证码 可通过搜索下方
公众号 获取??
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/151713.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...