文档章节

一道二进制子串算法让面试官都解不出来?

达达前端
 达达前端
发布于 2019/12/31 08:14
字数 2336
阅读 8
收藏 0

3 月,跳不动了?>>>

file

作者 | Jeskson 来源 | 达达前端小酒馆 掘金 | https://juejin.im/user/5a16e1f3f265da43128096cb

算法题目:

给定一个字符串 s ,计算具有相同数量0和1非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的

重复出现的 子串要计算它们出现的次数。

示例1:

输入:"00110011" 输出:6 解释:有6个子串具有相同数量的连续1和0:

“0011”,“01”,“1100”,“10”,“0011”,“01”。

注意,一些重复出现的子串要计算它们出现的次数,另外, “00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。

示例2:

输入:“10101” 输出:4 解释:有4个子串,“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。

注意:s.length 在1到50,000之间的范围,s只包含“0”或“1”字符。

“000111”中有多少个有效的二进制子串,“11100”中有多少个有效的二进制子串?“00011100”呢?

这道题目,难度系数为简单题目,涉及到的知识点为字符串。

JavaScript的解法:

给定函数体:

/**

  • @param {string} s
  • @return {number} */ var countBinarySubstrings = function(s) {

};

题目理解:

通过看看这两个示例,字符串 s 给的都是二进制数,要求计算具有相同数量 0 和 1 的非空(连续)子字符串的数量,这句话里面的条件有三个:

第一 不为空,非空(连续)

第二 0 和 1 是要相同数量的

第三 0 和 1 要是连续出现的子字符串的数量

描述:

如果遇到10或者是01的情况,则说明连续的1或者是连续的0断了,那么可以拿到前面连续1或者是连续0的数量,然后再查找后面连续1或者是连续0的数量,作比较看看有多少个符合的子串。

目录:

file

第一种JavaScript:

var countBinarySubstrings = function(s) {
    // 前面一个数,和当前数
    let pre=0, count=0, count1=0, count2=0;
    // 循环字符串
    for(let i = 1; i < s.length; i++) {
    // 遇到10或01的情况,则说明连续的1或连续的0断了
    if(s[i] !== s[pre]) {
      if(count1 === 0) {
        // 拿到前面连续1或0的数量
        count1 = i - pre;
        pre = i;
      } else {
        count2 = i - pre;
        count += count1 > count2 ? count2 : count1;
        count1 = count2;
        count2 = 0;
        pre = i;
      }
    }
    if(i === s.length - 1) {
      count2 = s.length - pre;
      count += count1 > count2 ? count2 : count1;
    }
  }

  return count;
}

第二种JavaScript:

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    // 字符串的长度
    const len = s.length;
    // 次数为0,前一个为0,current当前为1。
    let n = 0, pre = 0, current = 1;
    // 循环字符串
    for(let i = 0; i<len; i++){
     if(s[i] === s[i+1]) {
      current++;
     }else {
      // 比如00011,就有2组
      if(pre > 0) {
       n += Math.min(pre.current);
      }
      pre = current;
      current = 1;
     }
    }
    return n;
};

JavaScript min() 方法

返回值:给定数值中最小的数。如果任一参数不能转换为数值,则返回NaN。

描述

由于 min 是 Math 的静态方法,所以应该像这样使用:Math.min(),而不是作为你创建的 Math 实例的方法(Math 不是构造函数)。

如果没有参数,结果为Infinity。如果有任一参数不能被转换为数值,结果为 NaN。

JavaScript Math 对象

定义和用法

min() 方法可返回指定的数字中带有最低值的数字。

Math.min.apply(null, arr)

var array=[2,6,5,8,7];
Math.min.apply(null,array);

file

第三种JavaScript:

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    // res 存储相邻连续字符串的个数
    let res = [];
    let temp = s[0];
    let count = 0;
    for(let i of s) {
     // 循环字符串
     if(i !== temp) {
      res.push(count);
      temp = i;
      count = 0;
     }
     count++;
    }
    res.push(count);
    let total = 0;
    for(let i=0; i<res.length-1; i++){
     total += Math.min(res[i], res[i+1]);
    }
    return total;
};

如何使用 min() 来返回指定数字中带有最低值的数字:

<script type="text/javascript">

document.write(Math.min(5,7) + "<br />")
document.write(Math.min(-3,5) + "<br />")
document.write(Math.min(-3,-5) + "<br />")
document.write(Math.min(7.25,7.30))
</script>

输出:

5
-3
-5
7.25

解题规律

file

  • 000111必定有三个子串
  • 00011必定有两个子串
  • 0111必定有1个子串

以此类推, 每两组数据之间长度最短的值为子串的数量 把字符串按数字分组切割,如:['00', '11', '00', '11'] 但是如果 是 1010100 这种,怎么解释才合理呢?

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
  let num = 0;
  const arr = s.match(/0+|1+/g); 
  // let n = 0, arr = s.match(/([1]+)|([0]+)/g)
  
  // 把字符串切割成['00', '11', '00', '11']这样的数组

  for(let i = 0, len = arr.length; i < len - 1; i++){
    num += Math.min(arr[i].length, arr[i+1].length);     
    // 相邻比较,长度更短的则为这一组的出现次数
  }

  return num;
}

代码注解

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    // 计算前一个字符连续出现的次数
     let pre = 0
    // 计算后一个字符连续出现的次数
     let cur = 1
    // 每当 pre >= cur 时,既满足条件一次 count++
    // 前面有两个0,后面它自己为1
    // 计数count一开始为0
     let count = 0
    
    // 循环字符串
     for(let i=1; i<s.length; i++) {
    // 如果前一个和后一个相等
         if(s[i] === s[i-1]) {
    // 本身当前它自己的数为1,那么两者相等,这个数就+1,为2
             cur++
    // 00
         } else {
    // 当出现不一样的字符时,现任变前任,现任重新计数
    // 01,001,10,101,不一样的前后,10,01
    // 请一个数字的数量为1,后一个数字的数量为1
           pre = cur
    // 01,10, 当前数还是1
           cur = 1
         }
    
    // 001, 110, 010, 101,
    // 只要  pre >= cur, 即可满足条件一次
         if(pre >= cur) {
             count++
         }
     }
     return count
};

看了代码解析应该是懂的了,不过在这里还是口述一下下。

满是条件为01或者是10,就是两者不同,计数加1,出现001,或者是110的情况下,为前面2个0,后面1个1,前面的数量大于后面的数量即为满足一次条件,110的情况也是如此,1的数量为2,0的数量为1。

那么我们来定义一个变量let pre这个变量,这个变量的意思为计算前一个字符串出现的次数,首先这个变量的初始化值为0。如果当前数为 1,那么前面就没有数字,即为它的数量为0。

这里我们需要设置当前数量为1,即出现一个数字,那么数量即为1个。满足条件为前面的数量大于等于后面的数量,即为pre>=cur时,我们计数满足条件加1的情况,定义计数为count,满足条件时,count++

// 计算前一个字符连续出现的次数
 let pre = 0
// 计算后一个字符连续出现的次数
 let cur = 1
// 每当 pre >= cur 时,既满足条件一次 count++
// 前面有两个0,后面它自己为1
// 计数count一开始为0
 let count = 0

注意:计算前一个字符连续出现的次数和计算后一个字符连续出现的次数不同哦!

然后我们给定一个字符串数字,“00110011”,我们需要循环这个字符串中的数字,比较前一个数字和后一个数字是否相等,如果相等,是什么情况呢?如:00或者是11的情况下,当前数cur就要加1。

如果出现不一样的字符时,即情况:10或者是01这些情况,那么计算前一个字符连续出现的次数从0变为1,它有数字,即开始有次数了。把当前cur的次数赋值给pre(计算前一个字符连续出现的次数)。看着01和10的情况,当前cur的次数赋值为1。

满足条件,有人问了,那么001的情况或者是110或者是1100或者是0011或者是111000或者是000111或者是1010等情况下呢?

即这些情况满足如下:计算前一个字符连续出现的次数大于等于计算后一个字符连续出现的次数,即为pre>=cur的条件下满足,计数情况count++,循环字符串后,返回我们需要的count计数。

总结:

好了,本章已结束,如果还有什么不懂的,请在下方评论进行商议!

❤️ 不要忘记留下你学习的脚印 [点赞 + 收藏 + 评论]

作者Info:

【作者】:Jeskson 【原创公众号】:达达前端小酒馆。 【福利】:公众号回复 “资料” 送自学资料大礼包(进群分享,想要啥就说哈,看我有没有)! 【转载说明】:转载请说明出处,谢谢合作!~

大前端开发,定位前端开发技术栈博客,PHP后台知识点,web全栈技术领域,数据结构与算法、网络原理等通俗易懂的呈现给小伙伴。谢谢支持,承蒙厚爱!!!


若本号内容有做得不到位的地方(比如:涉及版权或其他问题),请及时联系我们进行整改即可,会在第一时间进行处理。


请点赞!因为你们的赞同/鼓励是我写作的最大动力!

欢迎关注达达的CSDN!

这是一个有质量,有态度的博客

前端技术栈

© 著作权归作者所有

达达前端
粉丝 4
博文 226
码字总数 368531
作品 0
广州
程序员
私信 提问
加载中

评论(0)

太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

面试攒经验,let's go! 值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考...

闰土大叔
2018/06/07
0
0
Google 面试题 | 数组的度数

专栏 | 九章算法 网址 | http://www.jiuzhang.com 1.题目描述 给定元素全为非负整数的非空数组nums,数组的度等于出现最多的元素的次数。找到具有和nums相同度的连续子串的最小长度。 样 例 ...

2018/02/24
0
0
微软SDE面经(电面+onsite)

本人工作1年多了,正在准备跳槽中。刚刚参加完微软西雅图的面试,来分享一下自己的面试过程。一共7轮面试,其中1轮电面,6轮Onsite。 第一轮 电面1 第一轮是电面,先是让自我介绍,然后根据简...

abcdd1234567890
2017/06/14
0
0
面试体验:Facebook 篇

Google、Microsoft 和 Yahoo 都是去年的事情了,接下来说说今年的吧。其实我在豌豆荚非常爽,跟身边的设计师和工程师合作都很愉快,所以唯一能够诱惑我去面试的就只有 Facebook 了。最初接受...

linux服务器架构
2019/07/22
24
0
面试中是否应该说出问题的最好答案

大家觉得面试的时候能不能直接说出最好的答案? 比如说,面试官问一道算法题。也许你见过这个题,且知道最好的答案(假如是相对最好的,足以让面试官满意的)。你该不该直接说最佳答案?还是...

张二青
2012/05/09
553
3

没有更多内容

加载失败,请刷新页面

加载更多

为什么只能在头文件中实现模板? - Why can templates only be implemented in the header file?

问题: Quote from The C++ standard library: a tutorial and handbook : 引用来自C ++标准库:教程和手册 : The only portable way of using templates at the moment is to implement t......

javail
今天
19
0
Gradle 6 针对已有的构建如何创建一个构建扫描

有关构建扫描的定义为: 构建扫描(build scan)是一个中心化并且可以共享的构建记录。这个构建记录通常能够告诉在构建中发生了什么并且为什么会发生。 通过应用构建扫描插件到你的项目中,你...

honeymoose
今天
17
0
C语言动态内存分配:(一)malloc/free的实现及malloc实际分配/释放的内存

一、malloc/free概述 malloc是在C语言中用于在程序运行时在堆中进行动态内存分配的库函数。free是进行内存释放的库函数。 1、函数原型 #include <stdlib.h> void *malloc( size_t size ); v...

shzwork
今天
17
0
什么是JavaBean? - What is a JavaBean exactly?

问题: I understood, I think, that a "Bean" is a Java class with properties and getters/setters. 我认为,“ Bean”是具有属性和getter / setter的Java类。 As much as I understand,......

技术盛宴
今天
27
0
深圳援鄂最后一批工作人员归来,88万元关爱金发放至85人

中国公益在线3月31日深圳讯 深圳援鄂最后一批工作人员归来......深圳市民政局、深圳市卫健委和深圳市慈善会发起了“深爱战疫天使基金”项目,联合龙华区慈善会和 永贤慈善基金会,进行第二次...

传承天下融媒体中心
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部