【344. 翻转字符串】
/**
* 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
* <p>
* 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
*/
public class reverseString_344 {
public void reverseString(char[] s) {
int len = s.length;
for (int i = 0, j = len - 1; i < len / 2; i++, j--) {
swap(s, i, j);
}
}
private void swap(char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
【541. 翻转字符串 II】
/**
* 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
* <p>
* 如果剩余字符少于 k 个，则将剩余字符全部反转。
* 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
* <p>
* 示例 1：
* <p>
* 输入：s = "abcdefg", k = 2
* 输出："bacdfeg"
* 示例 2：
* <p>
* 输入：s = "abcd", k = 2
* 输出："bacd"
*/
public class reverseStringII_541 {
public static void main(String[] args) {
System.out.println(reverseStr("abcdefg", 2));
}
public static String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length; i += 2 * k) {
int start = i;
// 判断尾部 够不够 k个来决定 end指针的位置
int end = Math.min(ch.length - 1, start + k - 1);
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
【offer05. 替换空格】
/**
* 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
* <p>
* 示例 1：
* <p>
* 输入：s = "We are happy."
* 输出："We%20are%20happy."
*/
public class replaceSpace_offer05 {
public static void main(String[] args) {
String str = "We are happy.";
System.out.println(replaceSpace(str));
}
public static String replaceSpace(String s) {
if (s == null || s.length() == 0) {
return s;
}
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
str.append(" ");
}
}
if (str.length() == 0) {
return s;
}
// 左指针：指向原始字符串的最后一个位置
int left = s.length() - 1;
s += str.toString();
// 右指针：指向扩展字符串的最后一个位置
int right = s.length() - 1;
char[] chars = s.toCharArray();
while(left >= 0){
// 从后向前 写入 %20
if (chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
} else {
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
}
【151. 翻转字符串里的单词】
/**
* 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
* 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
* 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
* 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
*
* 示例 1：
* 输入：s = "the sky is blue"
* 输出："blue is sky the"
*
* 示例 2：
* 输入：s = " hello world "
* 输出："world hello"
* 解释：反转后的字符串中不能存在前导空格和尾随空格。
*
* 示例 3：
* 输入：s = "a good example"
* 输出："example good a"
* 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
*/
public class reverseWords_151 {
public static void main(String[] args) {
System.out.println(reverseWords("the sky is blue"));
}
public static String reverseWords(String s) {
// 去除多余空格
StringBuilder sb = removeSpace(s);
// 翻转字符串
reverseString(sb, 0, sb.length()-1);
// 翻转各个单词
reverseEachWord(sb);
return sb.toString();
}
private static StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') {
start++;
}
while (s.charAt(end) == ' ') {
end--;
}
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' '){
sb.append(c);
}
start++;
}
return sb;
}
public static void reverseString(StringBuilder sb, int start, int end){
while( start < end){
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end,temp);
start++;
end--;
}
}
private static void reverseEachWord(StringBuilder sb){
int start = 0;
int end = 1;
int n = sb.length();
while(start < n){
// 到达空格或者串尾，说明一个单词结束
while(end < n && sb.charAt(end) != ' '){
end++;
}
reverseString(sb, start, end - 1 );
start = end + 1;
end = start + 1;
}
}
}
【offer58. 左旋字符串】
/**
* 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
* <p>
* 示例 1：
* <p>
* 输入: s = "abcdefg", k = 2
* 输出:"cdefgab"
* 示例 2：
* <p>
* 输入: s = "lrloseumgh", k = 6
* 输出:"umghlrlose"
*/
public class reverseLeftWords_offer58 {
public String reverseLeftWords(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder(s);
// 翻转区间前 n 的子串
reverseString(sb, 0, n - 1);
// 翻转区间为 n到末尾的字串
reverseString(sb, n, len - 1);
return sb.reverse().toString();
}
public static void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}
网友评论