9.16(33.(数组)搜索旋转排序数组 17.(字符串)电话号码的字母组合)

本文主要是介绍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.(字符串)电话号码的字母组合)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/860175

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA