Java C++ 算法leetcode828统计子串中唯一字符乘法原理

目录
  • 题目要求
  • 思路:模拟
    • java
    • C++
    • Rust

题目要求

思路:模拟

解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符

  • 所以在计算答案时的算式和示例中给出的是不一样的;
  • 在计算每个字符“贡献”【即当前向左向右分别可组成的答案个数】的时候要用到乘法原理

对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置,分别记为l[i]l[i]l[i]和r[i]r[i]r[i],这两个位置中间构成的就是s[i]s[i]s[i]能够作为唯一字符的最长子串,在这个最长的子串中还有若干个较短的子串,此时s[i]s[i]s[i]的“贡献”可由到左边和到右边的距离相乘计算得出。

java

class Solution {
    public int uniqueLetterString(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, res = 0;
        int[] l = new int[n], r = new int[n];
        int[] letters = new int[26];
        Arrays.fill(letters, -1);
        for (int i = 0; i < n; i++) {
            int idx = cs[i] - 'A';
            l[i] = letters[idx]; // 左边第一个相同的字符所在位置
            letters[idx] = i; // 更新当前字母最新左位置
        }
        Arrays.fill(letters, n);
        for (int i = n - 1; i >= 0; i--) {
            int idx = cs[i] - 'A';
            r[i] = letters[idx]; // 右边第一个相同的字符所在位置
            letters[idx] = i; // 更新当前字母最新右位置
        }
        for (int i = 0; i < n; i++)
            res += (i - l[i]) * (r[i] - i);
        return res;
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

C++

  • 因为memset初始化问题,所以在构成结果的时候多一步判断。
class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.size(), res = 0;
        cout << n << endl;
        int l[n], r[n];
        int letters[26];
        memset(letters, -1, sizeof(letters));
        for (int i = 0; i < n; i++) {
            int idx = s[i] - 'A';
            l[i] = letters[idx]; // 左边第一个相同的字符所在位置
            letters[idx] = i; // 更新当前字母最新左位置
        }
        memset(letters, -1, sizeof(letters));
        for (int i = n - 1; i >= 0; i--) {
            int idx = s[i] - 'A';
            r[i] = letters[idx]; // 右边第一个相同的字符所在位置
            letters[idx] = i; // 更新当前字母最新右位置
        }
        for (int i = 0; i < n; i++) {
            int ri = r[i] == -1 ? n : r[i];
            res += (i - l[i]) * (ri - i);
        }
        return res;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

Rust

  • 用Rust的遍历稍微改一下,思路一样……
impl Solution {
    pub fn unique_letter_string(s: String) -> i32 {
        let cs = s.as_bytes();
        (0..s.len()).into_iter().map(|i| {
            let (mut l, mut r) = (i - 1, i + 1);
            while l < s.len() && cs[l] != cs[i] {
                l -= 1;
            }
            while r < s.len() && cs[r] != cs[i] {
                r += 1;
            }
            ((i - l) * (r - i)) as i32
        }).sum::<i32>()
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

以上就是Java C++ 算法leetcode828统计子串中唯一字符乘法原理的详细内容,更多关于Java C++ 统计子串唯一字符的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

  • java算法Leecode刷题统计有序矩阵中的负数

    目录 leecode 1351. 统计有序矩阵中的负数 示例 1 提示 参考代码 定义一颗树 JAVA Morris leecode 1351. 统计有序矩阵中的负数 [Java 刷题打卡] 那就干吧! 这个专栏都是刷的题目都是关于二分法的,我会由浅入深.循序渐进,刷题就是这样需要连续不断的记忆--艾宾浩斯记忆法2121112.二分法的内容不多,但是都是每个程序员必备的 给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列. 请你统计并返回 grid 中 负

  • java实现的统计字符算法示例

    本文实例讲述了java实现的统计字符算法.分享给大家供大家参考,具体如下: 统计字符: 概述:给定字符串,将它们进行分类,分别的去统计它们的个数及其字符 分类的有:字母 数字 中文 空格 等等 算法思路分析: 分别统计即可: 下面给出代码:(代码仅供参考) package javastudy; public class Testit6 { public static void main(String[] args) { String str = "...天2气 :[1] aA"; //

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法leetcode828统计子串中唯一字符乘法原理

    目录 题目要求 思路:模拟 java C++ Rust 题目要求 思路:模拟 解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符: 所以在计算答案时的算式和示例中给出的是不一样的: 在计算每个字符“贡献”[即当前向左向右分别可组成的答案个数]的时候要用到乘法原理. 对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置,分别记为l[i]l[i]l[i]和r[i]r[i]r[i],这两个位置中间构成的就是s[i]s[i]

  • java字符串遍历以及统计字符串中各类字符

    本文实例为大家分享了java字符串遍历,以及java统计字符串中各类字符的具体代码,供大家参考,具体内容如下 1.需求:获取字符串中的每一个字符 分析: A:如何能够拿到每一个字符呢?   char charAt(int index) B:我怎么知道字符到底有多少个呢? int length() public class StringTest { public static void main(String[] args) { // 定义字符串 String s = "helloworld&qu

  • java统计字符串中重复字符出现次数的方法

    本文实例讲述了java统计字符串中重复字符出现次数的方法.分享给大家供大家参考,具体如下: package com; import org.junit.Test; /** * 统计一个字符串的重复字符出现的次数 * * @author zdw * */ public class StringTest { @Test public void test() { String s = "fdfaacceeeeeeeeeeeegghikkkkkoooo"; count(s); } public

  • java统计文件中每个字符出现的个数

    本文实例为大家分享了java统计文件中字符个数的具体代码,供大家参考,具体内容如下 package com.zhu.io; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.Map; import java.util.Set; import java.util.TreeMap; public clas

  • js实现统计字符串中特定字符出现个数的方法

    本文实例讲述了js实现统计字符串中特定字符出现个数的方法.分享给大家供大家参考,具体如下: //js统计字符串中包含的特定字符个数 function getPlaceholderCount(strSource) { //统计字符串中包含{}或{xxXX}的个数 var thisCount = 0; strSource.replace(/\{[xX]+\}|\{\}/g, function (m, i) { //m为找到的{xx}元素.i为索引 thisCount++; }); return th

  • JavaScript统计字符串中每个字符出现次数完整实例

    本文实例讲述了JavaScript统计字符串中每个字符出现次数的方法.分享给大家供大家参考,具体如下: 这是一个面试题,要求随便给你一个字符串,让你求出字符串中每个字符出现的次数. 先来看看运行效果截图: 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&

  • C C++算法题解LeetCode1408数组中的字符串匹配

    目录 题目描述 整理题意 解题思路分析 优化 具体实现 复杂度分析 代码实现 暴力 暴力 + 优化 KMP 总结 题目描述 题目链接:1408. 数组中的字符串匹配 给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo

  • python统计字符串中指定字符出现次数的方法

    本文实例讲述了python统计字符串中指定字符出现次数的方法.分享给大家供大家参考.具体如下: python统计字符串中指定字符出现的次数,例如想统计字符串中空格的数量 s = "Count, the number of spaces." print s.count(" ") x = "I like to program in Python" print x.count("i") PS:本站还提供了一个关于字符统计的工具,感兴

  • 使用php统计字符串中中英文字符的个数

    复制代码 代码如下: <?phpecho $str = "43fdf测试fdsfadaf43543543职工问防盗锁防盗锁5345gfdgd";preg_match_all("/[0-9]{1}/",$str,$arrNum);preg_match_all("/[a-zA-Z]{1}/",$str,$arrAl);preg_match_all("/([/x{4e00}-/x{9fa5}]){1}/u",$str,$arr

  • java实现统计字符串中字符及子字符串个数的方法示例

    本文实例讲述了java实现统计字符串中字符及子字符串个数的方法.分享给大家供大家参考,具体如下: 这里用java实现统计字符串中的字符(包括数字.大写字母.小写字母以及其他字符)个数,以及字符串的子字符串的个数. 运行效果图如下: 具体代码如下: import java.util.Scanner; public class Counter { static Scanner scanner = new Scanner(System.in); public static void count(Str

随机推荐