教你弄懂LeetCode三道题

骑猪看日落 2022-11-14 14:56 163阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、消失的数字
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  二、青蛙跳台阶
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  三、字符串转换为整数
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  总结

--------------------

# 前言 #

--------------------

![在这里插入图片描述][20210330125410732.png]

# 一、消失的数字 #

#### 1.题目描述 ####

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]

#### 2.解题思路 ####

此题有两种解题思路：  
第一种：

1.计算出0到n的数字之和sum1  
2.计算数组中所有数字之和sum2  
3.用sum1减去sum2就是得到缺少的数字

第二种：  
1.用x异或0到n的数字  
2.再用x异或数组中数字  
3.结果就是缺少的数字  
代码如下（示例）：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    int MissingNumber(int nums[], int sz) //解法1所以数之和减去少一个数的和，复杂度1-n那就是n
    { 
    	int i = 0;
    	int j = 0;
    	int sum1 = 0;
    	int sum2 = 0;
    	int newlen = sz + 1;
    	for (i = 0; i < newlen; i++) 
    	{ 
    		sum1 = sum1 + i;  //0到n的和
    	}
    	for (j = 0; j < sz; j++)
    	{ 
    		sum2 = sum2 + nums[j]; //数组的和
    	}
    	return sum1 - sum2; 
    } 
    int MissingNumber(int nums[], int sz) //解法2异或，复杂度n+n+1=2n+1那么复杂度就是n
    { 
    	int x = 0;
    	int newlen = sz + 1;
    	int i = 0;
    	for (i = 0; i < newlen; i++)
    	{ 
    		x = x^i;   
    	}
    	for (i = 0; i < sz; i++)
    	{ 
    		x = x^nums[i];
    	}
    	return x;
    }
    int main()
    { 
    	int nums[] = { 0,1, 2, 3, 4, 6, 7 };
    	int sz = sizeof(nums) / sizeof(nums[0]);
    	int digit = MissingNumber(nums, sz);
    	printf("%d\n", digit);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

# 二、青蛙跳台阶 #

#### 1.题目描述 ####

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

#### 2.解题思路 ####

1.此题目可以类似斐波那契的数解法，由于递归求解算法效率太低，所有可以采用赋值法，注意判断n<2时的情况。  
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    int Jump(int n)
    { 
    	int a = 1;
    	int b = 2;
    	int c = a;
    	if (n == 0)
    	{ 
    		return 1;
    	}
    	else if (n == 1)
    	{ 
    		return 1;
    	}
    	else if (n == 2)
    	{ 
    		return 2;
    	}
    	while (n > 2)  //赋值法解决效率比递归方法更高!
    	{ 
    		c = a + b;
    		a = b;
    		b = c;
    		n--;
    	}
    	return c;
    }
    int main()
    { 
    	int n = 0;
    	scanf("%d", &n);
    	int sum = 0;
    	sum = Jump(n);
    	printf("%d\n", sum);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]

# 三、字符串转换为整数 #

#### 1.题目描述 ####

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

1.  首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
2.  当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
3.  该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
4.  注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
5.  在任何情况下，若函数不能进行有效的转换时，请返回 0。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]

#### 2.解题思路 ####

1.  处理空格
2.  判断正负号
3.  处理正负号
4.  字符串转换为整形

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<assert.h>
    int change(char* str)
    { 
    	assert(str);
    	int signal = 1;
    	int ret = 0;
    	while (*str == ' ')
    	{ 
    		str++;
    	}
    	if (*str == '-')
    	{ 
    		signal = -1;
    	}
    	if (*str == '-' || *str == '+')
    	{ 
    		str++;
    	}
    	if (*str <'0'||*str>'9' )
    	{ 
    		return 0;
    	}
    	while (*str >= '0'&&*str <= '9')
    	{ 
    		ret = ret * 10 + *str - '0';
    		str++;
    	}
    	ret = ret*signal;
    	return ret;
    }
    int main()
    { 
    	char a[] = "-30";
    	char b[] = "20";
    	int ret = change(a) + change(b);
    	printf("%d\n", ret);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]

--------------------

# 总结 #

以上就是今天要讲的三道题目，本文仅仅简单介绍了LeetCode三道简单题目的解决思路，我们务必掌握。另外，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210330125323869.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/db00a1208da844bb8e08a36d81f385ba.png
[20210330125410732.png]: /images/20221022/f625861f43964bc386559733a06d5c7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/f6437f4342524f049090336e21831806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/1173e7f70feb45889ccb9fc69f7f093c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/dd78c6480e7c4f649ab45b4cef23f5c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/c7ef5e41b9f041a69cc10952ffa122c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221022/9ab1b11e963349f08c1a6882fc22ef10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221022/51e7e8810f8e4c46932fe5737ce30737.png
[20210330125323869.png_pic_center]: /images/20221022/aef246cd39a14a9191cb0f5ed1d6f482.png