本文主要是介绍9.16（33.（数组）搜索旋转排序数组 17.（字符串）电话号码的字母组合），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
33.（数组）搜索旋转排序数组
思路：
1.时间复杂度是(logn)，所以我想到了二分查找，但是本题和二分查找还有些不同，二分查找要求整体有序，target和nums[mid]比较以便确定下一步是向左还是向右。因此本体的关键是如何确定向左还是向右。
2.以nums = [4, 5, 6, 7, 0, 1, 2]为例,假如target是0，mid指向7，i指向4，j指向2。target<nums[mid],但是不能向左转。此时的限定条件是target>nums[i]&&target<nums[mid]，其他几种情况也是类似。总之判断左转还是右转的条件不再是简单的target和nums[mid]之间的判断。
程序代码如下：
//二分查找的变形，只需在判断条件上是稍微更改即可
class Solution
{
public:int search(vector<int>& nums, int target) {int i = 0, j = nums.size() - 1;//分别表示起始时的坐标if (nums.size() == 1) {if (nums[0] == target) return 0;else return -1;}while (i<j) {int mid = (i + j) / 2;if (target == nums[mid]) return mid;else if (target == nums[i]) return i;else if (target == nums[j]) return j;if (nums[mid] <= nums[j] && nums[mid] <=nums[i]) {//mid处的元素是大的部分，如示例的4、5、6、7if (target<nums[mid] || target>nums[i])j = mid - 1;else if (target<nums[i] && target>nums[mid])i = mid + 1;else return -1;}else if(nums[mid]>=nums[i]&&nums[mid]>=nums[j]){//mid处的元素是小的部分，如示例的0、1、2if (target > nums[i] && target < nums[mid])j = mid - 1;else if (target > nums[mid] || target < nums[j])i = mid + 1;else return -1;}else if (nums[mid] <=nums[j] && nums[mid]>=nums[i]) {//这种情况表示没有进行旋转就是普通的二分查找if (target<nums[mid] && target>nums[i])j = mid - 1;else if (target<nums[j] && target>nums[mid])i = mid + 1;else return -1;}}return -1;}
};17.（字符串）电话号码的字母组合
思路：分治+递归（我也不清楚这具体算是什么算法）。降低问题规模比如239可以分解成2和39的各种组合，39可以分解成3和9的的组合，递归基就是单个数字的情况。
程序代码如下：
class Solution {
public:string a[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//前两个为空便于后面的i直接使用vector<string> letterCombinations(string digits) {if (digits=="") {vector<string> arr(0);//这个能继续向里面push元素吗？cout<<""<<endl;return arr;//还必须得返回，那就返回空的吧}else if (digits.size() == 1) {int i = digits[0]-'0';//只有一个元素，该元素的数值是ivector<string> arr(a[i].size());for (int t = 0; t < a[i].size(); t++) {arr[t] = a[i][t];}return arr;}else {int i = digits[0]-'0';//表示第一个元素数值digits.erase(digits.begin());//除去开头的元素int len1 = a[i].size();//a[i]表示一个字符串int len2 = letterCombinations(digits).size();vector<string> result(len1*len2);//创建新的向量存放元素int m = 0;//表示新向量的坐标for (int j = 0; j < len1; j++) {for (int k = 0; k < len2; k++) {result[m++] = a[i][j] + letterCombinations(digits)[k];}}return result;}}
};
这篇关于9.16（33.（数组）搜索旋转排序数组 17.（字符串）电话号码的字母组合）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
