[CareerCup] 11.5 Search Array with Empty Strings 搜索含有空字符串的数组-阿里云开发者社区

开发者社区> 李博 bluemind> 正文

[CareerCup] 11.5 Search Array with Empty Strings 搜索含有空字符串的数组

简介:
+关注继续查看

11.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
 EXAMPLE
 Input: find "ball" in {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}
 Output: 4

这道题给了我们一个有序的字符串数组,但是在中间加入了很多空字符串,让我们来查找一个给定字符串。如果没有这些空字符串,那么我们用二分查找法很容易搜索,但是这些空字符串就有很大的干扰作用。那么我们要在原有的二分查找法上做修改,类似的修改二分查找法的里有Search in Rotated Sorted Array 在旋转有序数组中搜索Search in Rotated Sorted Array II 在旋转有序数组中搜索之二。这道题我们的思路是,查找中间的字符串,如果是空字符串,那么我们用二分查找法来找周围最近的非空字符串,然后把mid移到飞空字符串的位置,继续二分查找。相当于二分查找中又嵌套了一个二分查找,参见代码如下:

class Solution {
public:
    int search(vector<string> strings, string str) {
        int first = 0, last = strings.size() - 1;
        while (first <= last) {
            int mid = first + (last - first) / 2;
            if (strings[mid].empty()) {
                int left = mid - 1, right = mid + 1;
                while (true) {
                    if (left < first && right > last) return -1;
                    else if (right <= last && !strings[right].empty()) {
                        mid = right; break;
                    }
                    else if (left >= first && !strings[left].empty()) {
                        mid = left; break;
                    }
                    ++right;
                    --left;
                }
            }
            int res = strings[mid].compare(str);
            if (res == 0) return mid;
            else if (res < 0) first = mid + 1;
            else last = mid - 1;
        }    
        return -1;
    }
};

 本文转自博客园Grandyang的博客,原文链接:搜索含有空字符串的数组[CareerCup] 11.5 Search Array with Empty Strings ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
json格式的字符串转为json对象遇到特殊字符问题解决
中午做后台发过来的json的时候转为对象,可是有几条数据一直出不来,检查发现json里包含了换行符,造成这种情况的原因可能是编辑部门在编辑的时候打的回车造成的 假设有这样一段json格式的字符串 1 var json={ 2 "school": [ 3 { 4 ...
613 0
Oracle 给字符串补空格、补0
利用lpad()、RPAD()函数来实现给字符串补空格或补0的功能: 一、lpad()lpad函数将左边的字符串填充一些特定的字符其语法格式如下:lpad(string,n,[pad_string])string:字符或者参数n:字符的长度,是返回的字符串的数量,如果这个数量比原字符串的长度要短,lpad函数将会把字符串截取成从左到右的n个字符;pad_string:可选参数,这个字符串是要粘贴到string的左边,若这个参数未写,lpad函数将会在string的左边粘贴空格。
1311 0
获取SQLSERVER2005 的连接字符串的另类方法
获取SQLSERVER2005 的连接字符串的另类方法,这个方法是我的一个很牛比的同事告诉我的。 很使用,而且很方面。 1 新建一个.txt文件 2 改名:aa.udl 或 aa.UDL   .后缀名为 udl . 3 双击 aa.udl     ------> 提供程序: 选择SQL Server版本:Micorsoft OLE DB Provider for SQL Server 4 下一步 :连接 (1)选择或输入服务器名称:写如你要连接的数据库服务器名称。
711 0
如何在个人博客引擎 Hexo 中添加 Swiftype 搜索组件
在您现在看到的我的博客站点,后台使用的是 Hexo 作为博客引擎,但是默认集成的搜索组件是进行 form 提交到 Google 进行搜索的,为了更好地体验,本文介绍如何在 Hexo 博客中集成 Swiftype 搜索组件。
1280 0
放松时刻——C#分割字符串
让我们来练习一下字符串的分割~把话倒过来说: private void change_button_Click(object sender, EventArgs e) { var after_text = before_TextBox.
546 0
.NET C# Tostring format 格式化字符串
一、数值型 formatCode 是可选的格式化代码字符串。必须用“{”和“}”将格式与其他字符分开。如果恰好在格式中也要使用大括号,可以用连续的两个大括号表示一个大括号,即: “{{”或者“}}”。
1175 0
巧用JSON.stringify()生成漂亮格式的JSON字符串
巧用JSON.stringify()生成漂亮格式的JSON字符串 使用JavaScript处理XML基本上就是一个杯具,这也是JSON在程序开发中广受欢迎的原因。我曾经写过一个 JavaScript函数来将XML转换为JSON,那种~duang~duang~的痛点简直是折腾得你欲死欲仙。
775 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载