首页 > 代码库 > 数组，链表，字符串 的旋转(未完待续)
数组，链表，字符串 的旋转(未完待续)
字符串操作
题目一： 字符串的旋转（左旋操作）
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符‘a‘和‘b‘移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
题目出处：程序员编程艺术：面试和算法心得
微软面试100题 第二十六题
剑指Offer 第42题，翻转字符串vs 左旋转字符串
分析：
解法一：暴力法————循环移位，时间复杂度为O( m*n),不符合题目要求
解法二： 三步反转法
对于一个数组TS,要实现数组的旋转，先将各自字数组分别旋转，再 旋转整个数组，，即可得到ST
代码：
c/c++实现
#include<iostream>#include<string.h>using namespace std;void reverse(char *str,int start,int end){ while(start<end) //有文章采用 start！=end作为判断条件，这样是不行的，因为当字符数位偶数时， //start指针与end 指针会交错。不会相遇 { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; }}void rotatestr(char * str,int k){ if（str==NULL||strlen(str)==0||k<=0） return; int len = strlen(str); k = k%len; //若k==len,不旋转，但实际上将字符串旋转了两次 reverse(str,0,k-1); //先旋转前k个元素 reverse(str,k,len-1); reverse(str,0,len-1);}
考虑边界问题：
1.字符串为NULL时，
2.k的值为负数或或者
3. k大于等于字符串长度时这里采用k = k%len的方法。
Java实现
java 中的字符串String 是常量 ，不可改变，
但StringBuffer 是可变的，并且有reverse() 方法；
由于String 中字符串是常量，创建后不可更改，因此，不存在空间为O(1)的算法
1 public class reverseKStr 2 { 3 public String reversekelement(String str,k) 4 { 5 if(str==null || str.length()==0|| k<=0) return null; 6 int len = str.length(); 7 k= k%len; 8 StringBuffer sb1 = new StringBuffer(str.substring(0,k)); 9 StringBuffer sb2 = new StringBuffer(str.substring(k,len));10 sb1.reverse();11 sb2.reverse();12 sb1.append(sb2);13 return sb1.reverse().toString();14 }15 }
题目二： 字符串的旋转（右旋操作）
题目：
编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。
仍然三段法，第一段 0，len-m-1,第二段len-m,len
边界条件： m>=len,m<=0,时 返回不执行
题目三：句子的旋转
题目：
单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。
leetcode 中题目的描述：
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
click to show clarification.
Clarification:
- What constitutes a word?
A sequence of non-space characters constitutes a word.
- Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
- How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
分析：
1.空格分开单词
2.首尾空格要注意，返回的字符串中没有首尾字符
3.两个单词之间若有多个空格，返回后只需保留一个空格
解答：
java 实现，很容易想到java 实现，将字符串分词（split 函数）放入字符串数组，反向放入StringBuffer。
1 public class Solution { 2 public String reverseWords(String s) { 3 if(s==null) return s; 4 s.trim(); 5 String[] strarray = s.split(" "); 6 int len = strarray.length; 7 StringBuilder sb = new StringBuilder(); 8 for(int i=len-1;i>=0;i--) 9 {10 if(strarray[i].length()>0) // 防止误加入空格11 {12 sb.append(strarray[i]);13 sb.append(" ");14 }15 }16 return sb.toString().trim();17 }18 }
但是，面试过程中，考官更希望有底层的实现
c++实现
1 class Solution { 2 public: 3 void reverseWords(string &s) { 4 string str ; 5 int i =s.length()-1; 6 while(i>=0) 7 { 8 while(i>=0&&s[i]==‘ ‘) 9 i--;10 11 if(i<0) break; //如果已经没有非空格元素，则跳出12 if(str.length()!=0) str.append(" "); //如果，已经有了一个单词，则增加一个空格，前面一句话，保证了，后面还有单词添加进来；13 14 string temp;15 while(i>=0&&s[i]!=‘ ‘)16 { temp.push_back(s[i]);17 i--;18 }19 reverse(temp.begin(),temp.end());20 str.append(temp);21 }22 s=str; 23 } 24 };
整数的旋转：
Reverse Integer Total Accepted: 37856 Total Submissions: 94980 My Submissions Question Solution
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
click to show spoilers.
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer‘s last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).
注意：1.100,10这样的数的结果是什么，
2.是否考虑溢出
1 public class Solution { 2 public int reverse(int x) { 3 boolean flag = true; 4 if(x<0) 5 { 6 flag=false; 7 x = -1*x; 8 } 9 int newint = x%10;10 int temp=x/10;11 while(temp!=0)12 {13 if(flag&&newint>=214748364&&temp%10>=7) return Integer.MAX_VALUE;14 if(!flag&&newint>=214748364&&temp%10>=8) return Integer.MIN_VALUE;15 newint= newint*10+temp%10;16 temp=temp/10;17 }18 if(flag)19 return newint;20 else 21 return -1*newint; 22 }23 }
数组，链表，字符串 的旋转(未完待续)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。