OptimalSolution(4)--字符串问题（1）简单
一、判断两个字符串是否互为变形词
问题：给定两个字符串str1和str2，如果str1和str2中出现的字符种类一样且每种字符出现的次数也一样，那么str1与str2互为变形词。
举例：str1=“123”，str2=“231”，返回true。str1=“123”，str2=“2331”，返回false。
思路：如果str1和str2长度不同，直接返回false。如果长度相同，假设出现字符的编码值在0~255之间，那么先申请一个长度为256的整型数组map。map[a]=b代表字符串编码为a的字符出现了b次。初始始map都为0。然后遍历str1，统计每种字符出现的数量，比如遍历到字符‘a’，则令map[97]++，这样map就成了str1中每种字符的词频统计表。然后遍历str2，没遍历一个字符都在map中把词频减去1，如果减少之后的值小于0，直接返回false。如果遍历完str2，map中也没出现负值，返回true。
public boolean isDeformation(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() != str2.length()) {
return false;
}
char[] chas1 = str1.toCharArray();
char[] chas2 = str2.toCharArray();
int[] map = new int[256];
for (int i = 0; i < chas1.length; i++) map[chas1[i]]++;
for (int i = 0; i < chas2.length; i++) {
if (map[chas2[i]]-- == 0) return false;
}
return true;
}
判断两个字符串是否互为变形词
二、字符串中数字子串的求和
题目：给定一个字符串str，求其中全部数字串所代表的数字之和。其中：1.忽略小数点字符，例如“A1.3”，其中包含两个数字1和3。2.如果紧贴数字子串的左侧出现字符‘-’，当连续出现的数量为奇数时，则数字视为负，连续出现的数量为偶数时，则数字视为正。例如“A-1BC--12”，其中包含-1和12
解法：（1）生成三个变量，整型变量res表示目前的累加和；整型变量num表示当前收集到的数字；布尔型变量posi，表示如果把num累加到res里，num是正还是负。初始时，res=0，num=0，posi=true。（2）如果遍历到的字符cha是‘0’~‘9’，则cha-‘0’的值记为cur，posi表示cur的符号。例如：str=“123”，初始时num=0，posi=true。则num=0*10+1，num=1*10+2，num=12*10+3。假设str=“-123”，那么posi=false，此时num=0*10+(-1)，num=-1*10+(-2)，num=-12*10+(-3)，因此有num=num * 10 + (posi ? cur : -cur)（3）如果遍历到的字符cha不是‘0’~‘9’，说明前一阶段的数已经明确是num了，因此先令res+=num，然后令num=0。此时如果cha不是‘-’，令posi=true。如果cha是‘-’，此时看cha的前一个字符，如果cha的前一个字符也是‘-’，则posi=！posi；否则令posi=false。（4）还需要注意的是，由于res+=num发生在非数字字符之前，如果字符串最后一位是数字字符，就使得最后一个num无法加到res上，因此最后还需要res+=num。
public int numSum(String str) {
if (str == null) return 0;
char[] charArr = str.toCharArray();
int res = 0;
int num = 0;
boolean posi = true;
int cur = 0;
for (int i = 0; i < charArr.length; i++) {
cur = charArr[i] - '0';
if (cur < 0 || cur > 9) {
res += num;
num = 0;
if (charArr[i] == '-') {
if (charArr[i - 1] == '-') {
posi = !posi;
} else {
posi = false;
}
} else {
posi = true;
}
} else {
num = num * 10 + (posi ? cur : -cur);
}
}
res += num;
return res;
}
字符串中数字子串的求和
三、去掉字符串中连续出现k个0的子串
题目：给定一个字符串str和一个整数k，如果str中正好有连续的k个‘0’字符出现时，把k个连续的‘0’字符去除，返回处理后的字符串。
解法：（1）生成两个变量。整型变量count表示目前连续个‘0’的数量；整型变量start表示连续出现连续个‘0’的开始位置。初始时，count=0，start=-1（2）如果cha是字符‘0’，令start = start== -1 ？ i ： start，即如果start不等于-1，说明之前就已经处在连续的‘0’的阶段，所以start不变，count++（3）如果cha不是‘0’，如果count等于k，说明之前发现的连续k个‘0’可以从start位置开始去掉，如果不等于，说明之前发现的连续的‘0’的数量不是k个，因此不能去掉，最后令count=0，start=-1。（4）如果str是以‘0’结尾的，可能会出现最后一组k个连续的‘0’没有去掉的情况，所以要检查一下count是否等于k。
注意：下面这段代码中，chas[start++] = 0;表示的是，ASCII码表中0表示null，因此如果str“a0000b000c00”，k=4，则结果为“a b000c00”
if (count == k) {
while (count-- != 0) {
chas[start++] = 0;
}
}
完整代码：
public String removeKZeros(String str, int k) {
if (str == null || k < 1) return str;
char[] chas = str.toCharArray();
int count = 0, start = -1;
for (int i = 0; i < chas.length; i++) {
if (chas[i] == '0') {
count++;
start = start == -1 ? i : start;
} else {
if (count == k) {
while (count-- != 0) {
chas[start++] = 0;
}
}
count = 0;
start = -1;
}
}
if (count == k) {
while (count-- != 0) {
chas[start++] = 0;
}
}
return String.valueOf(chas);
}
去掉字符串中连续出现k个0的子串
四、判断两个字符串是否互为旋转词
题目：如果一个字符串str，把字符串str前面任意的部分挪到后面形成的字符串叫做str的旋转词。例如str=“12345”，则str的旋转词为“12345”，“23451”，“34512”，“45123”和“51234”
解法：如果a和b的长度不一样那么返回false。如果a和b长度一样，先生成变量String b2 = b + b，然后看b2中是否包含字符串a。例如，a=“cdab”，b=“abcd”，那么b2=“abcdabcd”，则b2[0...3]、b2[1...4]、b2[2...5]、b2[3...6]、b2[4...7]都是b的旋转词。即如果一个字符串b的长度为N，在通过b生成的b2中，任意长度为N的子串都是b的旋转词，而且b2中包含字符串b的所有旋转词。（可以通过KMP算法实现时间复杂度为O(N)）
public boolean isRotation(String a, String b) {
if (a == null || b == null || a.length() != b.length()) {
return false;
}
String b2 = b + b;
return b2.contains(a);
}
判断两个字符串是否为旋转词
五、替换字符串中连续出现的指定字符串
问题：给定三个字符串str、from和to，把str中所有from的子串全部替换成to字符串，对连续出现from的部分要求只替换成一个to字符串。
例如：str=“123abc”，from=“abc”，to=“4567”，返回“1234567”。str=“123abcabc”，from=“abc”，to=“X”，返回“123X”
思路：把str中from部分所有位置的字符编码设为0（即空字符），例如str=“12abcabca4”，from=“abc”，处理后str为[‘1’,‘2’,0,0,0,0,0,0,‘a’,‘4’]，然后把不为0的区域拼在一起，连续为0的部分用to代替，即“12” + to + “a4”
解法：（1）生成整型变量match，表示目前匹配到from字符串的什么位置，初始时，match=0（2）如果str[i]==from[match]。如果match是from的最后一个字符的位置，说明str中发现了from字符串，则从i位置向左的M个位置，都把字符编码设为0，M为from的长度，然后令match=0，如果match不是from最后一个字符的位置，令match++，继续遍历str的下一个字符串（3）如果str[i]!=from[match]，说明匹配失败，令match=0,（4）拼接字符串。
注意：对于连续的0的区域的处理方式
if (chas[i] == 0 && (i == 0 || chas[i - 1] != 0)) {
res = res + cur + to;
cur = "";
}
完整代码：
public String replace(String str, String from, String to) {
if (str == null || from == null || str.equals("") || from.equals("")) {
return str;
}
char[] chas = str.toCharArray();
char[] chaf = from.toCharArray();
int match = 0;
for (int i = 0; i < chas.length; i++) {
if (chas[i] == chaf[match++]) {
if (match == chaf.length) {
clear(chas, i, chaf.length);
match = 0;
}
} else {
match = 0;
}
}
String res = "";
String cur = "";
for (int i = 0; i < chas.length; i++) {
if (chas[i] != 0) {
cur = cur + String.valueOf(chas[i]);
}
if (chas[i] == 0 && (i == 0 || chas[i - 1] != 0)) {
res = res + cur + to;
cur = "";
}
}
if (!cur.equals("")) res = res + cur;
return res;
}
public void clear(char[] chas, int end, int len) {
while (len -- != 0) {
chas[end--] = 0;
}
}
替换字符串中连续出现的指定字符串
六、字符串的统计字符串
题目1：给定一个字符串str，返回str的统计字符串，例如，“aaabbadddffc”的统计字符串为“a_3_b_2_a_1_d_3_f_2_c_1”
解法：（1）如果str为空，那么统计字符串不存在（2）如果str不为空，生成String类型的变量res表示统计字符串，整型变量num代表当前字符的数量。初始时res只包含str[0]，同时num=1（3）从str[1]开始遍历，如果str[i] == str[i-1]，说明当前连续的字符str[i-1]还没结束，令num++。（4）如果str[i]!=str[i-1]，说明到str[i-1]已经结束，令res=res+“_”+num+“_”+str[i]，然后令num=1（5）当遍历结束时，最后的字符还没有放入res，所以令res=res+“_”+num
public String concat(String s1, String s2, String s3) {
return s1 + "_" + s2 + (s3.equals("") ? s3 : "_" + s3);
}
public String getCountString(String str) {
if (str == null || str.equals("")) {
return "";
}
char[] chs = str.toCharArray();
String res = String.valueOf(chs[0]);
int num = 1;
for (int i = 1; i < chs.length; i++) {
if (chs[i] != chs[i - 1]) {
res = concat(res, String.valueOf(num), String.valueOf(chs[i]));
num = 1;
} else {
num++;
}
}
return concat(res, String.valueOf(num), "");
}
返回字符串的统计字符串
题目2：给定一个字符串的统计字符串cstr，再给定一个整数index，返回cstr所代表的原始字符串上的第index个字符。
解法：（1）生成布尔型变量stage，stage为true时表示要遇到字符，为false表示要遇到字符统计。字符型变量cur表示在上一个遇到字符阶段时，遇到的是cur字符。整型变量num，表示在上一个遇到连续字符统计的阶段，字符出现的数量。整型变量sum，表示目前遍历到cstr的位置相当于原字符串什么位置。初始时，stage=true，cur=0（空字符），num=0，sum=0（2）以cstr=“a_100_b_2_c_4”,index=105为例，遍历完str[0]='a'后cur=‘a’；遇到str[1]='_'，stage=!stage；表示接下来几个字符表示出现次数，依次为num=1，num=10，num=100；然后是下划线，此时stage=!stage，表示要遇到的是字符；遇到str[6]='b'，即一个新的字符出现了，此时sum+=num，即sum=100，也就是原字符串有100个a，由于100<105，因此继续遍历；...每次遇到一个新字符，都把上一个num加到sum上，如果sum已经到达index，那么就返回上一个字符cur。
注意：num = num * 10 + chs[i] - '0';将字符串因此转换成整数
public char getCharAt(String cstr, int index) {
if (cstr == null || cstr.equals("")) {
return 0;
}
char[] chs = cstr.toCharArray();
boolean stage = true;
int sum = 0;
int num = 0;
char cur = 0;
for (int i = 0; i < chs.length; i++) {
if (chs[i] == '_') {
stage = !stage;
} else if (stage) {
sum += num;
if (sum > index) {
return cur;
}
num = 0;
cur = chs[i];
} else {
num = num * 10 + chs[i] - '0';
}
}
return sum + num > index ? cur : 0;
}
根据统计字符串及索引范返回原字符串中的字符
七、字符串的调整与替换
问题1：给定一个字符类型的数组chas，chas右半区全是空字符，左半区不含有空字符。将左半区左右的空格字符替换成“%20”，假设chas右半区足够大，可以满足替换所需要的空间。例如“a b c空字符”，替换后左半区为“a%20b%20%20c”
解法：（1）先遍历一次，可以得到两个信息，chas的左半区长度记为len，左半区空格记为num，即空格被“%20”替换后长度为len+2*num。（2）从左半区的最后一个字符开始倒着遍历，同时将字符复制到新长度的最后的位置，并依次向左倒着复制。遇到空格就依次把“0”、“2”和“%”进行复制。
注意：1.一个for方法可以同时得到len和num，这种技巧值得学习。2.从右往左倒着遍历。
public void replace(char[] chas) {
if (chas == null || chas.length == 0) {
return;
}
int num = 0;
int len = 0;
for (len = 0; len < chas.length && chas[len] != 0; len++) {
if (chas[len] == ' ') {
num++;
}
}
int j = len + num * 2 - 1;
for (int i = len - 1; i > -1; i--) {
if (chas[i] != ' ') {
chas[j--] = chas[i];
} else {
chas[j--] = '0';
chas[j--] = '2';
chas[j--] = '%';
}
}
}
问题2：给定一个字符类型的数组chas，其中只含有数字字符和“*”字符，想将“*”字符挪到chas的左边，数字字符挪到chas的右边。例如“12**345”，调整后为“**12345”。
解法：和问题1一样，依然是从右往左复制，遇到数字直接复制，遇到“*”不复制，当把数字字符复制完，把左半区全部设置成“*”即可。
注意：for(; j > -1;) { chas[j--] = '*'; }这种表达。
public void modify(char[] chas) {
if (chas == null || chas.length == 0) {
return;
}
int j = chas.length - 1;
for(int i = chas.length - 1; i > -1; i--) {
if (chas[i] != '*') {
chas[j--] = chas[i];
}
}
for(; j > -1;) {
chas[j--] = '*';
}
}
八、反转字符串
问题1：给定字符类型数组chas，在单词键做依序调整。例如：“dog loves pig”为“pig loves dog”。“I'm a student.”为“student. a I'm”
解法：先把chas整体逆序，在把每个单词逆序。例如：“gip sevol god” →“pig loves dog”
注意：不能用String提供给你的reverse方法，要自己实现才行。
public void reverse(char[] chas, int start, int end) {
char tmp = 0;
while (start < end) {
tmp = chas[start];
chas[start] = chas[end];
chas[end] = tmp;
start++;
end--;
}
}
整体方法：注意for循环里面对于双指针l和r的使用技巧，这种高级表达要关注。
public void rorateWord(char[] chas) {
if (chas == null || chas.length == 0) {
return;
}
reverse(chas, 0, chas.length - 1);
int l = -1;
int r = -1;
for (int i = 0; i < chas.length; i++) {
if (chas[i] != ' ') {
l = i == 0 || chas[i - 1] == ' ' ? i : l;
r = i == chas.length - 1 || chas[i + 1] == ' ' ? i : r;
}
if (l != -1 && r != -1) {
reverse(chas, l, r);
l = -1;
r = -1;
}
}
}
问题2：给定字符类型数组chas和整数size，把大小为size的左半区整体移到右半区。例如“ABCDE”且size=3，则“DEABC”
解法1：先把chas[0...size-1]部分逆序，再把chas[size...N-1]部分逆序，最后把chas整体逆序。
public void rorate1(char[] chas, int size) {
if (chas == null || size <= 0 || size >= chas.length) {
return;
}
reverse(chas, 0, size - 1);
reverse(chas, size, chas.length - 1);
reverse(chas, 0, chas.length - 1);
}
九、找到指定的新类型字符
问题：新类型字符是长度为1或者2的字符串。表现形式为：仅一个小写字母；大写+小写；大写+大写。给定字符串str，找出第k个的新类型字符串。例如：str=“aaABCDEcBCg”，当k=7时，返回“Ec”。
思路：str=“aaABCDEcBCg”可以被拆成“a”，“a”，“AB”，“CD”，“Ec”，“BC”，“g”。k=7时，uNum=5；k=4时，uNum=2；k=10时，uNum=2。
解法：（以小写字母为分隔符）从k-1位置开始，向左统计连续出现的大写字母的数量uNum，遇到小写字母就停止。如果uNum为奇数，str[k-1...k]就是要找的；如果uNum为偶数且str[k]是大写字母，str[k...k+1]就是要找的；如果uNum为偶数且str[k]是小写字母，则str[k]是要找的。
注意：if ((uNum & 1) == 1)用来判断uNum是奇数还是偶数
public String pointNewChar(String s, int k) {
if (s == null || s.equals("") || k < 0 || k >= s.length()) {
return "";
}
char[] chas = s.toCharArray();
int uNum = 0;
for(int i = k - 1; i >= 0; i--) {
if (!Character.isUpperCase(chas[i])) {
break;
}
uNum++;
}
if ((uNum & 1) == 1) {
return s.substring(k - 1, k + 1);
}
if (Character.isUpperCase(chas[k])) {
return s.substring(k, k + 2);
}
return String.valueOf(chas[k]);
}
最新文章
- Linux From Scratch（从零开始构建Linux系统，简称LFS）- Version 7.7（一）
- oracle 11g RAC 补丁升级方法
- TSkinData 皮肤控件后最大最小提示英文Close的解决方法
- 【Mail】JavaMail发送带附件的邮件（二）
- [Leetcode] Palindrome Partitioning
- yii去除index.php的入口脚本显示为seo友好的url
- 关于setInterval和setTImeout中的this指向问题
- Android tab导航的几种方法:ActionBar tab +fragment,Viewpager+pagerTitleStrip,开源框架ViewPageIndicator 和 ViewPager
- 22. Generate Parentheses——本质：树，DFS求解可能的path
- Android——计算器
- JS常用的设计模式(13)——组合模式
- lcov收集覆盖率
- SRM 395(1-250pt)
- 在Prefetcher中取消robots.txt的限制
- python进阶八_警告和异常
- matlab中运用项目思维分析问题并解决问题
- php基础语法（20161021）
- css实现超出部分用...代替
- css基础语法一（选择器与css导入方式）
- 记一次win10+oracle11.2安装