免费建站网站教程做地方网站论坛赚钱

当前位置： 首页 > news >正文

免费建站网站教程,做地方网站论坛赚钱,自动提取关键词的软件,静态企业网站下载题目部分 题目字符串划分难度难题目说明给定一个小写字母组成的字符串s#xff0c;请找出字符串中两个不同位置的字符作为分割点#xff0c;使得字符串分成的三个连续子串且子串权重相等#xff0c;注意子串不包含分割点。 若能找到满足条件的两个分割点#xff0c;请输出…题目部分 题目字符串划分难度难题目说明给定一个小写字母组成的字符串s请找出字符串中两个不同位置的字符作为分割点使得字符串分成的三个连续子串且子串权重相等注意子串不包含分割点。 若能找到满足条件的两个分割点请输出这两个分割点在字符串中的位置下标若不能找到满足条件的分割点请返回0,0。 子串权重计算方式为子串所有字符的ASCII码数值之和。输入描述输入为一个字符串字符串由 a ~ z26 个小写字符组成5 ≤ 字符串长度 ≤ 200。输出描述输出为两个分割点在字符串中的位置下标以逗号分隔。补充说明补充说明只考虑唯一解不存在一个输入多种输出解的情况。——————————————————示例示例1输入acdbbbca输出2,5说明以位置 2 和 5 作为分割点将字符串分割为 ac、bb、ca 三个子串每一个的子串权重都为 196输出为 2,5。示例2输入abcabc输出0,0说明找不到符合条件的分割点输出为0,0。 解读与分析 题目解读 给定一个字符串以字符串中的 2 个字符为分隔符把它分成 3 个子字符串不包含 2 个分隔符使字符串中所有字符的 ASCII 码之和相等。输出这 2 个分隔符的下标用 “,” 隔开如果不存在输出 “0,0”。 此题要么存在唯一解要么不存在解。 分析与思路 此题字符串的长度不超过 200 个比较简单的思路是尝试这 2 个分隔符是所有下标的情况判断每种情况下所分隔出 3 个字符串的 ASCII 码之和是否相等。 这种方法的时间复杂度为 O()空间复杂度为 O()。 以上方法可行不过我们还有性能更好的方法。 先计算字符串中所有字符的 ASCII 码之和设为 asciiSum与此同时找出可以作为分隔符的字母的最大和最小 ASCII 码值分别设为 minAscii 和 maxAscii。 分隔后设三个字符串的 ASCII 码之和的最大值为 maxAsciiSum则 maxAsciiSum 值为 asciiSum - minAscii * 2设ASCII 码之和的最小值为 minAsciiSum则 minAsciiSum 值为 asciiSum - maxAscii * 2。 分隔后每个字符串ASCII 码之和的取值范围为 [ minAsciiSum / 3,  maxAsciiSum / 3 ]。 顺序遍历字符串找到第一个子字符串 ASCII 码之和在取值范围内时第一个分隔符的所有可能下标。 倒序遍历字符串找到第三个子字符串 ASCII 码之和在取值范围内时第二个分隔符的所有可能下标。 根据第一个分隔符和第二个分隔符的所有下标组合判断是否三个字符串 ASCII 码之和是否相等。如果相等则输出这两个分隔符的下标否则输出 “0,0”。 此方法的时间复杂度为 O(n)空间复杂度为 O(n)。 代码实现 Java代码 import java.util.Scanner;/*** 字符串划分* since 2023.10.10* version 0.1* author Frank**/ public class StringDivision {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();processStringDivision( input );}}private static void processStringDivision( String input ){int asciiSum 0;int minAscii z; // min初始化成最大值int maxAscii a; // max初始化成最小值for( int i 0; i input.length(); i ){char curChar input.charAt( i );asciiSum curChar;if( i 0 i input.length() -1 ){if( curChar minAscii ){minAscii curChar;}if( curChar maxAscii ){maxAscii curChar;}}}int eachMinSum ( asciiSum - maxAscii * 2 ) / 3;int eachMaxSum ( asciiSum - minAscii * 2 ) / 3 1; // 向上取整避免漏掉一些情况int leftIndex 0; int leftSum 0;for( int i 0; i input.length() - 2; i ){int curChar input.charAt( i );leftSum curChar;leftIndex ;if( leftSum eachMinSum ){break;}} int rightIndex input.length() - 1;int rightSum 0;for( int i input.length() - 1; i 2; i – ){int curChar input.charAt( i );rightSum curChar;rightIndex –;if( rightSum eachMinSum ){break;}}while( leftSum eachMaxSum rightSum eachMaxSum leftIndex rightIndex ){if( leftSum rightSum ){int curChar input.charAt( leftIndex );if( leftSum curChar eachMaxSum ){break;}leftSum curChar;leftIndex ;}if( leftSum rightSum ){int curChar input.charAt( rightIndex );if( rightSum curChar eachMaxSum ){break;}rightSum curChar;rightIndex –;}if( leftIndex rightIndex ){break;}// 相等的情况int theOtherSum asciiSum - leftSum - rightSum - input.charAt( leftIndex ) - input.charAt( rightIndex );if( theOtherSum leftSum ){System.out.println( leftIndex , rightIndex);return;}// 如果 theOtherSum 不相等继续int curChar input.charAt( leftIndex );if( leftSum curChar eachMaxSum ){break;}leftSum curChar;leftIndex ;curChar input.charAt( rightIndex );if( rightSum curChar eachMaxSum ){break;}rightSum curChar;rightIndex –; }System.out.println( 0,0 );} } JavaScript代码 const rl require(readline).createInterface({ input: process.stdin }); var iter rlSymbol.asyncIterator; const readline async () (await iter.next()).value; void async function() {while (line await readline()) {processStringDivision(line);} }();function processStringDivision( input ) {var asciiSum 0;var minAscii z.charCodeAt(); // min初始化成最大值var maxAscii a.charCodeAt(); // max初始化成最小值for( var i 0; i input.length; i ){var curChar input.charCodeAt( i );asciiSum curChar;if( i 0 i input.length -1 ){if( curChar minAscii ){minAscii curChar;}if( curChar maxAscii ){maxAscii curChar;}}}var eachMinSum ( asciiSum - maxAscii * 2 ) / 3;var eachMaxSum ( asciiSum - minAscii * 2 ) / 3 1; // 向上取整避免漏掉一些情况var leftIndex 0; var leftSum 0;for( var i 0; i input.length - 2; i ){var curChar input.charCodeAt( i );leftSum curChar;leftIndex ;if( leftSum eachMinSum ){break;}} var rightIndex input.length - 1;var rightSum 0;for( var i input.length - 1; i 2; i – ){var curChar input.charCodeAt( i );rightSum curChar;rightIndex –;if( rightSum eachMinSum ){break;}}while( leftSum eachMaxSum rightSum eachMaxSum leftIndex rightIndex ){if( leftSum rightSum ){var curChar input.charCodeAt( leftIndex );if( leftSum curChar eachMaxSum ){break;}leftSum curChar;leftIndex ;}if( leftSum rightSum ){var curChar input.charCodeAt( rightIndex );if( rightSum curChar eachMaxSum ){break;}rightSum curChar;rightIndex –;}if( leftIndex rightIndex ){break;}// 相等的情况var theOtherSum asciiSum - leftSum - rightSum - input.charCodeAt( leftIndex ) - input.charCodeAt( rightIndex );if( theOtherSum leftSum ){console.log( leftIndex , rightIndex);return;}// 如果 theOtherSum 不相等继续var curChar input.charCodeAt( leftIndex );if( leftSum curChar eachMaxSum ){break;}leftSum curChar;leftIndex ;curChar input.charCodeAt( rightIndex );if( rightSum curChar eachMaxSum ){break;}rightSum curChar;rightIndex –; }console.log( 0,0 ); }(完)