首页 > 代码库 > 算法设计--字符串偏移
算法设计--字符串偏移
最近准备校招,找了些设计题练练,顺便记录。
问题描述:将字符串向右偏移给定的偏移量,如abcd,偏移量2,则得到cdab。
思路:第一感觉是和数组插入很像。
数组插入过程:n长数组在i位置插入元素ele,从n-1下标开始逆向迭代,覆盖其下一个元素
for(int it=n;it>i;it--){
arr[it]=arr[it-1];
}
arr[i]=ele;
so,整理下思路,Java实现如下:
private static void shift(String s,int offset){//向右偏移 StringBuffer str=new StringBuffer(s); int len=str.length(),num=len; char start=str.charAt(0);//腾出数据偏移余地,保存原始数据 offset=offset%len; //防止offset大于len int i=0; char tmp; while(--num>0){//循环len-1次 tmp=str.charAt((i-offset+len)%len);//边界控制 str.setCharAt(i, tmp);//将n-offset位置的数据覆盖到n位置 i=(i-offset+len)%len; } str.setCharAt(i, start);//给腾出空间的0位置的数据安排房间 System.out.println(str.toString()); }空间基本无消耗,时间复杂度为O(n)。
算法设计--字符串偏移
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。