区块链技术博客
www.b2bchain.cn

程序员进阶之算法练习(四十九)LeetCode求职学习资料

本文介绍了程序员进阶之算法练习(四十九)LeetCode求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

正文

题目1.两数之和

题目链接
题目大意:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目解析:
先不考虑复杂度,直接两个for循环,对于每个数字nums[i],寻找target-nums[i]是否也在数组;
这样的时间复杂度为O(N^2),可以牺牲一些空间来换取更快的速度:比如说把已经出现过的数字用hash表直接存下来,这样下次用hash表直接循环该数字是否存在。
题目的要求还要输出数组下标,那么可以用hash表的值来存数组下标。

class Solution {     unordered_map<int, int> mp; public:     vector<int> twoSum(vector<int>& nums, int target) {         mp.clear();         vector<int> ans;          for (int i = 0; i < nums.size(); ++i) {             if (mp[target - nums[i]]) {                 ans.push_back(i);                 ans.push_back(mp[target - nums[i]] - 1);                 break;             }             mp[nums[i]] = i + 1;         }         return  ans;     } }leetcode;

2.整数反转

题目链接
题目大意:
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

题目解析:
将负号单独拿出来考虑,只考虑整数的翻转。

因为最终结果可能超过int范围,那么可以用long long来处理。

class Solution { public:     int reverse(int x) {         lld ret = 0, flag = x < 0 ? -1 : 1;         lld tmp = abs(x), sz = 1;         while (tmp) {             ret = tmp % 10 + ret * 10;             tmp /= 10;         }         lld intLeft = -(1LL << 31), intRight = (1LL << 31) - 1;         if (ret < intLeft || ret > intRight) {             ret = 0;         }         return (int)ret * flag;     } }leetcode;

注意:
1在位移的时候,是按int来处理的,需要改成1LL;

3.字符串转换整数 (atoi)

题目链接
题目大意:
请你来实现一个 atoi 函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:
如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
输入: “42”
输出: 42

示例 2:
输入: ” -42″
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:
输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。

示例 4:
输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:
输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

题目解析:
按照题目的要求实现,拆分出来具体的过程。
1、还未进行数字转换的状态,hasConvert=false,此时可以允许空格跳过;
2、遇到+、-、数字之后,hasConvert=true,不允许空格跳过,遇到非数字符号结束转化;
3、符号和数字分开处理,超过int大小分别出来,可以用long long来暂存;

整体代码不复杂。

“`

正文

题目1.两数之和

题目链接
题目大意:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目解析:
先不考虑复杂度,直接两个for循环,对于每个数字nums[i],寻找target-nums[i]是否也在数组;
这样的时间复杂度为O(N^2),可以牺牲一些空间来换取更快的速度:比如说把已经出现过的数字用hash表直接存下来,这样下次用hash表直接循环该数字是否存在。
题目的要求还要输出数组下标,那么可以用hash表的值来存数组下标。

class Solution {     unordered_map<int, int> mp; public:     vector<int> twoSum(vector<int>& nums, int target) {         mp.clear();         vector<int> ans;          for (int i = 0; i < nums.size(); ++i) {             if (mp[target - nums[i]]) {                 ans.push_back(i);                 ans.push_back(mp[target - nums[i]] - 1);                 break;             }             mp[nums[i]] = i + 1;         }         return  ans;     } }leetcode;

2.整数反转

题目链接
题目大意:
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

题目解析:
将负号单独拿出来考虑,只考虑整数的翻转。

因为最终结果可能超过int范围,那么可以用long long来处理。

class Solution { public:     int reverse(int x) {         lld ret = 0, flag = x < 0 ? -1 : 1;         lld tmp = abs(x), sz = 1;         while (tmp) {             ret = tmp % 10 + ret * 10;             tmp /= 10;         }         lld intLeft = -(1LL << 31), intRight = (1LL << 31) - 1;         if (ret < intLeft || ret > intRight) {             ret = 0;         }         return (int)ret * flag;     } }leetcode;

注意:
1在位移的时候,是按int来处理的,需要改成1LL;

3.字符串转换整数 (atoi)

题目链接
题目大意:
请你来实现一个 atoi 函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:
如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
输入: “42”
输出: 42

示例 2:
输入: ” -42″
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:
输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。

示例 4:
输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:
输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

题目解析:
按照题目的要求实现,拆分出来具体的过程。
1、还未进行数字转换的状态,hasConvert=false,此时可以允许空格跳过;
2、遇到+、-、数字之后,hasConvert=true,不允许空格跳过,遇到非数字符号结束转化;
3、符号和数字分开处理,超过int大小分别出来,可以用long long来暂存;

整体代码不复杂。

“`

正文

题目1.两数之和

题目链接
题目大意:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目解析:
先不考虑复杂度,直接两个for循环,对于每个数字nums[i],寻找target-nums[i]是否也在数组;
这样的时间复杂度为O(N^2),可以牺牲一些空间来换取更快的速度:比如说把已经出现过的数字用hash表直接存下来,这样下次用hash表直接循环该数字是否存在。
题目的要求还要输出数组下标,那么可以用hash表的值来存数组下标。

class Solution {     unordered_map<int, int> mp; public:     vector<int> twoSum(vector<int>& nums, int target) {         mp.clear();         vector<int> ans;          for (int i = 0; i < nums.size(); ++i) {             if (mp[target - nums[i]]) {                 ans.push_back(i);                 ans.push_back(mp[target - nums[i]] - 1);                 break;             }             mp[nums[i]] = i + 1;         }         return  ans;     } }leetcode;

2.整数反转

题目链接
题目大意:
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

题目解析:
将负号单独拿出来考虑,只考虑整数的翻转。

因为最终结果可能超过int范围,那么可以用long long来处理。

class Solution { public:     int reverse(int x) {         lld ret = 0, flag = x < 0 ? -1 : 1;         lld tmp = abs(x), sz = 1;         while (tmp) {             ret = tmp % 10 + ret * 10;             tmp /= 10;         }         lld intLeft = -(1LL << 31), intRight = (1LL << 31) - 1;         if (ret < intLeft || ret > intRight) {             ret = 0;         }         return (int)ret * flag;     } }leetcode;

注意:
1在位移的时候,是按int来处理的,需要改成1LL;

3.字符串转换整数 (atoi)

题目链接
题目大意:
请你来实现一个 atoi 函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:
如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
输入: “42”
输出: 42

示例 2:
输入: ” -42″
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:
输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。

示例 4:
输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:
输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

题目解析:
按照题目的要求实现,拆分出来具体的过程。
1、还未进行数字转换的状态,hasConvert=false,此时可以允许空格跳过;
2、遇到+、-、数字之后,hasConvert=true,不允许空格跳过,遇到非数字符号结束转化;
3、符号和数字分开处理,超过int大小分别出来,可以用long long来暂存;

整体代码不复杂。

“`

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 程序员进阶之算法练习(四十九)LeetCode求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们