首页 > 数据库 >[Oracle] LeetCode 696 Count Binary Substrings

[Oracle] LeetCode 696 Count Binary Substrings

时间:2022-08-24 06:22:06浏览次数:69  
标签:Count Binary 696 int number Substrings occur

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Solution

由于连续的 \(0\) 和连续的 \(1\), 所以我们只需要统计相邻区间 \(0,1\) 的个数,取最小即可,因为方案数就是最小个数的 \(0/1\)

点击查看代码
class Solution {
private:
    int ans=0;
    vector<int> cnt;
public:
    int countBinarySubstrings(string s) {
        int n =s.size();
        int cur=1;
        for(int i=0;i<n-1;i++){
            if(s[i]==s[i+1])cur++;
            else{
                cnt.push_back(cur);cur=1;
            }
        }
        cnt.push_back(cur);
        for(int i=0;i<cnt.size()-1;i++){
            //cout<<cnt[i]<<" "<<cnt[i+1]<<endl;
            ans += min(cnt[i], cnt[i+1]);
        }
        return ans;
    }
};

标签:Count,Binary,696,int,number,Substrings,occur
From: https://www.cnblogs.com/xinyu04/p/16618479.html

相关文章

  • CountDownLatch demo演示裁判和选手赛跑
    #CountDownLatchdemo演示裁判和选手赛跑packagecom.example.core.mydemo;importjava.util.concurrent.CountDownLatch;importjava.util.concurrent.ExecutorServ......
  • CountDownLatch demo演示数据分片多线程处理
    #CountDownLatchdemo演示数据分片多线程处理packagecom.example.core.mydemo;importorg.springframework.scheduling.concurrent.ThreadPoolTaskExecutor;import......
  • LeetCode 811. Subdomain Visit Count
    原题链接在这里:https://leetcode.com/problems/subdomain-visit-count/题目:Awebsitedomain "discuss.leetcode.com" consistsofvarioussubdomains.Atthetople......
  • P3605 [USACO17JAN]Promotion Counting P 题解
    solution考虑权值线段树合并:首先离散化,然后对于一个节点,我们将它的所有子树合并上来,并统计所有能力指数的个数(权值线段树基本操作),查询时只需查询\(p_i+1\simn\)的和即......
  • Time Needed to Rearrange a Binary String
    TimeNeededtoRearrangeaBinaryStringYouaregivenabinarystring$s$.Inonesecond,alloccurrencesof 01 aresimultaneouslyreplacedwith 10 .This......
  • 102.binary-tree-level-order-traversal 二叉树的层序遍历
    利用queue先进先出的特性进行处理,利用queue.size()来识别元素是否在二叉树的同一层,同时要注意不能直接i<q.size()来判断,因为q.size()是不断变化的。classSolution{......
  • 107.binary-tree-level-order-traversal-ii 二叉树的层序遍历II
    参考102.binary-tree-level-order-traversal二叉树的层序遍历,翻转一下结果数组就好了。classSolution{public:vector<vector<int>>levelOrderBottom(TreeNode......
  • Binary Classification
    给定m个样本,根据每个样本拥有的n个特征对它们分类。最基础的分类问题是BinaryClassification,输出结果为Yes或No。Logisticregression相较于线性回归假设因......
  • CountDownLatch
    CountDownLatchCountDownLatch是一种通用的同步工具CountDownLatch内部的实现主要是依靠AQS的共享模式。当一个线程把CountDownLatch初始化了一个count之后,其他的线程......
  • [Google] LeetCode 366 Find Leaves of Binary Tree
    Giventherootofabinarytree,collectatree'snodesasifyouweredoingthis:Collectalltheleafnodes.Removealltheleafnodes.Repeatuntilthetre......