您的位置:首页 > 健康 > 美食 > 楼市最新消息:2023年房价走势_汕头论坛_百度关键词工具在哪里_百度域名收录

楼市最新消息:2023年房价走势_汕头论坛_百度关键词工具在哪里_百度域名收录

2025/3/17 22:25:26 来源:https://blog.csdn.net/qq_15711195/article/details/146292906  浏览:    关键词:楼市最新消息:2023年房价走势_汕头论坛_百度关键词工具在哪里_百度域名收录
楼市最新消息:2023年房价走势_汕头论坛_百度关键词工具在哪里_百度域名收录

目录

一、题目描述

二、解题思路

【C++】

【Java】


Leetcode-2272. Substring With Largest Variancehttps://leetcode.com/problems/substring-with-largest-variance/description/2272. 最大波动的子字符串 - 力扣(LeetCode)2272. 最大波动的子字符串 - 字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。给你一个字符串 s ,它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。子字符串 是一个字符串的一段连续字符序列。 示例 1:输入:s = "aababbb"输出:3解释:所有可能的波动值和它们对应的子字符串如以下所示:- 波动值为 0 的子字符串:"a" ,"aa" ,"ab" ,"abab" ,"aababb" ,"ba" ,"b" ,"bb" 和 "bbb" 。- 波动值为 1 的子字符串:"aab" ,"aba" ,"abb" ,"aabab" ,"ababb" ,"aababbb" 和 "bab" 。- 波动值为 2 的子字符串:"aaba" ,"ababbb" ,"abbb" 和 "babb" 。- 波动值为 3 的子字符串 "babbb" 。所以,最大可能波动值为 3 。示例 2:输入:s = "abcde"输出:0解释:s 中没有字母出现超过 1 次,所以 s 中每个子字符串的波动值都是 0 。 提示: * 1 <= s.length <= 104 * s  只包含小写英文字母。https://leetcode.cn/problems/substring-with-largest-variance/description/

一、题目描述

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aababbb"
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
- Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
- Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
- Variance 3 for substring "babbb".
Since the largest possible variance is 3, we return it.

Example 2:

Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

二、解题思路

  • 时间复杂度:O(n * 26)
  • 空间复杂度:O(1)

【C++】

class Solution {
public:int largestVariance(string s) {int f0[26][26]{}, f1[26][26];memset(f1, -0x3f, sizeof(f1));int res = 0;for (auto& ch : s) {int a = ch - 'a';for (int b = 0; b < 26; ++b) {if (a == b) {continue;}f0[a][b] = max(f0[a][b], 0) + 1; // a为主频次(允许不含b)时的频次差f1[a][b]++; // a为主频次时的频次差,含b时有效;不含b时为很小的负数值f1[b][a] = f0[b][a] = max(f0[b][a], 0) - 1; // b为主频次(这里一定含a)时的频次差res = max(max(res, f1[a][b]), f1[b][a]);}}return res;}
};

【Java】

class Solution {public int largestVariance(String s) {int f0[][] = new int[26][26], f1[][] = new int[26][26];for (int[] row : f1) {Arrays.fill(row, Integer.MIN_VALUE);}int res = 0;for (char ch : s.toCharArray()) {int a = ch - 'a';for (int b = 0; b < 26; ++b) {if (a == b) {continue;}f0[a][b] = Math.max(f0[a][b], 0) + 1;f1[a][b]++;f1[b][a] = f0[b][a] = Math.max(f0[b][a], 0) - 1;res = Math.max(Math.max(res, f1[a][b]), f1[b][a]);}}return res;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com