貴阳建设银行网站信创网站建设
反转字符串
难度：易。
问题描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
这个就是开头和结尾的字符交换，然后次开头和次结尾的字符交换。这个就是设计到双指针，因为它是原地修改数组，但是每次操作的是前后两个位置，所以思考到双指针。这两个指针同时移动，是最简单的情况。
下面是C++, JAVA, Python的实现。
class Solution {
public:void reverseString(vector<char>& s) {int len = s.size();for(int i = 0, j= len-1; i<len/2; i++, j--){swap(s[i],s[j]);}}
};
class Solution {public void reverseString(char[] s) {int len = s.length;for(int i = 0, j= len-1; i<len/2; i++, j--){char temp = s[i];s[i] = s[j];s[j] = temp;}}}
class Solution(object):def reverseString(self, s):""":type s: List[str]:rtype: None Do not return anything, modify s in-place instead."""length = len(s)for i in range(length/2):temp = s[i]j = length -1 - is[i] = s[j]s[j] = temp参考
- https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
541. 反转字符串II
难度：易。没有新的算法思想。只是加了条件限制。
问题描述：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
注意：边界条件，以及每次可以一段一段遍历。
库函数中的函数定义是左闭右开的。
遇到这种一段一段处理的可以成段跳。
下面是C++, JAVA, Python的代码。
注意reverse函数的用法。
class Solution {
public:string reverseStr(string s, int k) {for(int i = 0; i < s.length(); i+=2*k){if(i+k <= s.length()){reverse(s.begin()+i, s.begin()+i+k);//如果满足i+k在数组中的话就对k个进行反转continue;}reverse(s.begin()+i, s.begin()+s.length());//原来这个reverse这样使用}return s;}
};
JAVA这个好像没有现成的库函数。
class Solution {public String reverseStr(String s, int k) {int n = s.length();char[] arr = s.toCharArray();for(int i = 0; i < n; i += 2*k){reverse(arr, i, Math.min(i+k, n)-1);//这个设定的是闭区间}return new String(arr);//对数组进行操作然后重新变成字符串}public void reverse(char[] arr, int left, int right){while(left < right) {char temp = arr[left];//就是交换双指针法进行交换，也就是利用字符串反转中的arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}
都注意一下输入是字符串不是数组，处理前先转换成数组，然后输出最后结果的时候将数组转换成字符串。
class Solution:def reverseStr(self, s: str, k: int) -> str:t = list(s)for i in range(0, len(t), 2*k):t[i: i + k] = reversed(t[i: i+k])return "".join(t)
参考文献
- https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
54. 替换数字
又使用到双指针的思想。C++的效率更高一点。
#include <iostream>
using namespace std;
int main() {string s;while(cin >> s) {int sOldIndex = s.size()-1;//获得之前数组的长度int count = 0;//统计数字的个数for( int i =0; i < s.size(); i++){//统计数字的个数对数组进行扩充if(s[i] >= '0' && s[i] <= '9'){count++;}}//扩充字符串的大小，也就是将每个数字替换成“numbers的大小s.resize(s.size()+ count*5);int sNewIndex = s.size() - 1;//这个是扩充后的最后一个位置//从后往前将数字替换为"numberwhile(sOldIndex>=0){//因为这个是从后往前遍历，所以从数组的末尾开始if(s[sOldIndex]>='0'&& s[sOldIndex]<='9'){//该位置是数字就进行替换s[sNewIndex--] = 'r';s[sNewIndex--] = 'e';s[sNewIndex--] = 'b';s[sNewIndex--] = 'm';s[sNewIndex--] = 'u';s[sNewIndex--] = 'n';}else{s[sNewIndex--] = s[sOldIndex];}sOldIndex--;}cout << s << endl;//输出语句}
}
JAVA
import java.util.*;public class Main{public static void main(String[] args){//Scanner sc = new Scanner(System.in);//这个就是初始化Scanner这个对象String s = sc.next();//获取字符串int len = s.length();for (int i =0 ; i < s.length(); i++){if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){len += 5;//这个就是统计一下数字的个数}}char[] ret = new char[len];for(int i =0; i < s.length(); i++){//将旧的数组中的值赋值到新的数组中ret[i] = s.charAt(i);}for(int i = s.length() - 1, j = len -1; i >= 0; i--){//使用双指针的方法进行赋值if ('0' <= ret[i] && ret[i] <= '9') {ret[j--] = 'r';ret[j--] = 'e';ret[j--] = 'b';ret[j--] = 'm';ret[j--] = 'u';ret[j--] = 'n';} else {ret[j--] = ret[i];}}System.out.println(ret);}
}class Soluton:def change(self, s):lst = list(s)#python里面的string也是不可改的，需要额外的空间for i in range(len(lst)):if lst[i].isdigit():#统计一下数字个数lst[i] = "number"return ''.join(lst)
if __name__ == "__main__":solution = Soluton()# 获取用户输入,user_input = input()# 转换为大写print(solution.change(user_input))
参考文献
- https://programmercarl.com/kamacoder/0054.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html