扬州网站建设公元国际,百度推广登录入口官网,网页开发模板,建商城网站作者推荐
利用广度优先或模拟解决米诺骨牌
本文涉及的基础知识点
二分查找算法合集
题目
给你一个下标从 1 开始的整数数组 numbers #xff0c;该数组已按 非递减顺序排列 #xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 n…作者推荐
利用广度优先或模拟解决米诺骨牌
本文涉及的基础知识点
二分查找算法合集
题目
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。 示例 1 输入numbers [2,7,11,15], target 9 输出[1,2] 解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。 示例 2 输入numbers [2,3,4], target 6 输出[1,3] 解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。 示例 3 输入numbers [-1,0], target -1 输出[1,2] 解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2] 。 参数范围 2 numbers.length 3 * 104 -1000 numbers[i] 1000 numbers 按 非递减顺序 排列 -1000 target 1000 仅存在一个有效答案
解法一二分查找
枚举第一个数然后二分查找是否存在。 class Solution { public: vector twoSum(vector numbers, int target) { for (int i 0; i numbers.size(); i) { const int iNeed target - numbers[i]; auto it std::equal_range(numbers.begin() i 1, numbers.end(), iNeed); if (it.second - it.first 0) { return vector{ i 1,(int)(it.first - numbers.begin() 1 )}; } } return { 1,2 }; } };
解法二哈希映射
用哈希映射记录可能的第二个数及索引枚举第一个数的时候直接从哈希映射查询。 class Solution { public: vector twoSum(vector numbers, int target) { unordered_mapint, int mValueIndex; for (int i numbers.size() - 1; i 0; i–) { const int iNeed target - numbers[i]; if (mValueIndex.count(iNeed)) { return vector{i 1, mValueIndex[iNeed] 1}; } mValueIndex[numbers[i]] i; } return { 1,2 }; } };
解法三双指针
如果numbers[left] numbers[right]小于目标数则将则left抛弃right取任何数结果都小于目标数。 如果numbers[left] numbers[right]大于目标数则将则right抛弃left取任何数结果都大于目标数。 class Solution { public: vector twoSum(vector numbers, int target) { int left 0, right numbers.size() - 1;//结果一定在[left,right]中 while (right left) { if (numbers[left] numbers[right] target) { right–; } else if (numbers[left] numbers[right] target) { left; } else { return vector{left 1, right 1}; } } return { 1,2 }; } };
测试用例
template void Assert(const T t1, const T t2) { assert(t1 t2); }
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { Assert(v1[i], v2[i]); } }
int main() { vector numbers, res; int target; { numbers { 2, 7, 11, 15 }; target 9; Solution slu; res slu.twoSum(numbers, target); Assert(res, vector{1,2}); } { numbers { 2,3,4 }; target 6; Solution slu; res slu.twoSum(numbers, target); Assert(res, vector{1, 3}); } { numbers { -1,0 }; target -1; Solution slu; res slu.twoSum(numbers, target); Assert(res, vector{1, 2}); }
//CConsole::Out(res);}
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
