企业官网建设流程全解析

谷歌推广费用多少,北京企业网站优化,石家庄房产,用二级域名做网站群942. 增减字符串匹配 问题描述 给定只含 I#xff08;增加#xff09;和 D#xff08;减少#xff09;的字符串 s#xff0c;令 n s.length。 根据 s 构造一个排列 perm#xff08;长度为 n 1#xff09;#xff0c;使得对于所有的 i#x…942. 增减字符串匹配问题描述给定只含I增加和D减少的字符串s令n s.length。根据s构造一个排列perm长度为n 1使得对于所有的i如果s[i] I则perm[i] perm[i 1]如果s[i] D则perm[i] perm[i 1]返回满足条件的任意一个排列perm。示例输入: s IDID 输出: [0,4,1,3,2] 解释: - I: 0 4 - D: 4 1 - I: 1 3 - D: 3 2 输入: s III 输出: [0,1,2,3] 输入: s DDI 输出: [3,2,0,1] 解释: - D: 3 2 - D: 2 0 - I: 0 1算法思路贪心核心思想使用两个指针low 0和high n遍历字符串s如果遇到I选择当前最小可用数字low然后low如果遇到D选择当前最大可用数字high然后high--最后将剩余的数字此时low high添加到结果末尾代码实现方法一双指针贪心classSolution{/** * 根据增减字符串构造排列 * * param s 只包含 I 和 D 的字符串 * return 满足条件的排列数组 */publicint[]diStringMatch(Strings){intns.length();int[]resultnewint[n1];intlow0;// 当前最小可用数字inthighn;// 当前最大可用数字// 遍历字符串s构造前n个元素for(inti0;in;i){if(s.charAt(i)I){// 遇到I选择最小的可用数字result[i]low;}else{// s.charAt(i) D// 遇到D选择最大的可用数字result[i]high--;}}// 最后一个位置此时low highresult[n]low;// 或者 result[n] high;returnresult;}}算法分析时间复杂度O(n)只需要遍历字符串一次空间复杂度O(1)只使用了常数个额外变量算法过程输入s IDID初始化low 0,high 4,result [?, ?, ?, ?, ?]i0,s[0]I→result[0] 0,low 1i1,s[1]D→result[1] 4,high 3i2,s[2]I→result[2] 1,low 2i3,s[3]D→result[3] 3,high 2最后result[4] 2结果[0,4,1,3,2]输入s DDI初始化low 0,high 3,result [?, ?, ?, ?]i0,D→result[0] 3,high 2i1,D→result[1] 2,high 1i2,I→result[2] 0,low 1最后result[3] 1结果[3,2,0,1]输入s IIIresult[0] 0,low 1result[1] 1,low 2result[2] 2,low 3result[3] 3结果[0,1,2,3]测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例Strings1IDID;int[]result1solution.diStringMatch(s1);System.out.println(Test 1: Arrays.toString(result1));// [0,4,1,3,2]// 验证结果verifyResult(s1,result1);// 应该输出 Valid// 测试用例2全增加Strings2III;int[]result2solution.diStringMatch(s2);System.out.println(Test 2: Arrays.toString(result2));// [0,1,2,3]verifyResult(s2,result2);// Valid// 测试用例3全减少Strings3DDD;int[]result3solution.diStringMatch(s3);System.out.println(Test 3: Arrays.toString(result3));// [3,2,1,0]verifyResult(s3,result3);// Valid// 测试用例4混合情况Strings4DDI;int[]result4solution.diStringMatch(s4);System.out.println(Test 4: Arrays.toString(result4));// [3,2,0,1]verifyResult(s4,result4);// Valid// 测试用例5单字符Strings5I;int[]result5solution.diStringMatch(s5);System.out.println(Test 5: Arrays.toString(result5));// [0,1]verifyResult(s5,result5);// ValidStrings6D;int[]result6solution.diStringMatch(s6);System.out.println(Test 6: Arrays.toString(result6));// [1,0]verifyResult(s6,result6);// Valid// 测试用例6长字符串Strings7IDIDIDIDID;int[]result7solution.diStringMatch(s7);System.out.println(Test 7: Length result7.length);// 11verifyResult(s7,result7);// Valid// 测试用例7交替模式Strings8IDIDID;int[]result8solution.diStringMatch(s8);verifyResult(s8,result8);// ValidSystem.out.println(Test 8: Valid isValidPermutation(result8,6));}privatestaticvoidverifyResult(Strings,int[]perm){booleanvalidtrue;for(inti0;is.length();i){if(s.charAt(i)Iperm[i]perm[i1]){validfalse;break;}if(s.charAt(i)Dperm[i]perm[i1]){validfalse;break;}}// 检查是否是0到n的排列boolean[]usednewboolean[perm.length];for(intnum:perm){if(num0||numperm.length||used[num]){validfalse;break;}used[num]true;}System.out.println(验证: (valid?Valid:Invalid));}privatestaticbooleanisValidPermutation(int[]perm,intn){boolean[]usednewboolean[n1];for(intnum:perm){if(num0||numn||used[num]){returnfalse;}used[num]true;}returntrue;}关键点贪心策略选择极值最小或最大为后续操作保留最大灵活性数字范围必须使用0到n的所有整数恰好一次双指针保证了这一点边界处理字符串长度为n结果数组长度为n1最后一个元素自动确定low high常见问题贪心策略选择极值不会限制后续的选择空间