leetcode刷题第一日<两数和问题>
2019-02-25 16:09:28来源:博客园 阅读 ()
开始就用到了c++的哈希表是真的恶心,首先学习一波基础知识
https://blog.csdn.net/u010025211/article/details/46653519
下面放下大佬的代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>a; a.push_back(-1); for(int i=0;i<nums.size();i++) { for(int j=i+1;j<nums.size();j++) if(nums[i]+nums[j]==target) { a[0]=i; a[1]=j; return a; } } } };
这里是完整版代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>a; a.push_back(-1); for(int i=0;i<nums.size();i++) { for(int j=i+1;j<nums.size();j++) if(nums[i]+nums[j]==target) { a[0]=i; a[1]=j; return a; } } } }; void trimLeftTrailingSpaces(string &input) { input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) { return !isspace(ch); })); } void trimRightTrailingSpaces(string &input) { input.erase(find_if(input.rbegin(), input.rend(), [](int ch) { return !isspace(ch); }).base(), input.end()); } vector<int> stringToIntegerVector(string input) { vector<int> output; trimLeftTrailingSpaces(input); trimRightTrailingSpaces(input); input = input.substr(1, input.length() - 2); stringstream ss; ss.str(input); string item; char delim = ','; while (getline(ss, item, delim)) { output.push_back(stoi(item)); } return output; } int stringToInteger(string input) { return stoi(input); } string integerVectorToString(vector<int> list, int length = -1) { if (length == -1) { length = list.size(); } if (length == 0) { return "[]"; } string result; for(int index = 0; index < length; index++) { int number = list[index]; result += to_string(number) + ", "; } return "[" + result.substr(0, result.length() - 2) + "]"; } int main() { string line; while (getline(cin, line)) { vector<int> nums = stringToIntegerVector(line); getline(cin, line); int target = stringToInteger(line); vector<int> ret = Solution().twoSum(nums, target); string out = integerVectorToString(ret); cout << out << endl; } return 0; }
这貌似有点高深但是算法复杂度是非常低的,貌似是4msj解决,我们再利用基础的c暴力解决下,
双重循环遍历,代码如下
int* twoSum(int* nums, int numsSize, int target) { int *a; a=(int *)malloc(2*sizeof(int)); for(int i=0;i<numsSize-1;i++) { for(int j=i+1;j<numsSize;j++) { if((nums[i]+nums[j])==target) { a[0]=i; a[1]=j; } } } return a;
但是这个不是最优的,最优算法貌似是采用二分法 代码像这样
int* twoSum(int* nums, int numsSize, int target) { int *a; a=(int *)malloc(2*sizeof(int)); int mid=numsSize/2; for(int i=0;i<mid;i++) { for(int j=mid;j<numsSize;j++) { if((nums[i]+nums[j])==target) { a[0]=i; a[1]=j; } } } return a;
最后在用python解决下吧
def twoSum(self, nums, target): hashmap={} for index, num in enumerate(nums): another_num = target - num if another_num in hashmap: return [hashmap[another_num], index] hashmap[num] = index return None
原文链接:https://www.cnblogs.com/kk328/p/10433487.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- leetcode 反转链表 2020-06-06
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- [题记]字符串转换整数-leetcode 2020-04-03
- [题记]有效括号的嵌套深度-leetcode 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash