定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数,要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1)。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数,要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1)。
以下算法实现了可以做旋转和右旋转....
原理:
abcde123456
根据要旋转的位数k,把数组分成两子串,例如K=6,进行右旋转,则把字符串分成 abcde 和 123456(K位)
划分技巧:右旋转,后面子串位数为K,剩下做为前面子串;若是左旋转,前面子串位数为K,剩下做为后面子串
如果上面 abcde123456 进行左旋转 K=6位,则字符串的划分是:abcde1(K位) 和 23456
接着对abcde和123456分别进行逆序操作结果:
edcba和654321
合并后成
edcba654321
再整体逆序123456abcde
优点: 3个reverse 操作都是线性操作,前两个时间复杂度和为0(n/2),最后一个整体逆序时间复杂度为0(n/2),总时间复杂度是O(n),比起普通的相同功能算法时间复杂度要低
package 左旋转字符串; import java.util.Scanner; /** * 左旋转字符串 * * @author ccf * */ public class test { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("输入一行字符串:"); Scanner input = new Scanner(System.in); char[] charArray = input.nextLine().toCharArray(); System.out.println("输入要移动的位数"); int shiftNum = Integer.parseInt(input.nextLine()); System.out.println("你输入的字符串为" + new String(charArray) + " 要移动问位数为" + shiftNum); // charArray = RightShift(shiftNum, charArray); charArray = LeftShift(shiftNum, charArray); System.out.println("移位结果为:" + String.valueOf(charArray)); } /** * 实现字符串的逆序 * * @param src * @param begin * @param end * @return */ private static char[] reverse(char[] src, int begin, int end) { char temp; for (; begin < end; end--, begin++) { temp = src[begin]; src[begin] = src[end]; src[end] = temp; } return src; } /** * * @param k * 偏移量 * @param src */ private static char[] RightShift(int k, char[] src) { src = reverse(src, 0, src.length - k - 1); src = reverse(src, src.length - k, src.length - 1); // 与左移位不同在于下标的选取,这里是取后面K位 src = reverse(src, 0, src.length - 1); return src; } private static char[] LeftShift(int k, char[] src) { src = reverse(src, 0, k - 1); // 与右移位不同在于下标的选取,这里是取前面K位 src = reverse(src, k, src.length - 1); src = reverse(src, 0, src.length - 1); return src; } }
相关推荐
文档中涵盖了两个字符串旋转的基本概念,包括如何判断一个字符串是否为另一个字符串的旋转,并介绍了如何在Java中实现该算法。此外,文档还包括一个逐步指南,介绍如何在Java中实现两个字符串旋转的代码,包括详细的...
通过这个练习,读者将学习如何在C++中编写代码来判断两个字符串是否是通过旋转得到的,并解决与字符串旋转相关的算法问题。 文档中包含了一系列的练习题,涵盖了字符串旋转的基本概念、实现方法和应用场景。通过...
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
1,strs.zip 实现字节数组, 同c中的字符数组一样好用(6KB) 2,modules.zip 字符串处理的12个例子(13KB) 3,strings.zip 字符串处理函数(4KB) 4,stringfuncs.zip 字符串处理函数(9KB) 5,search&...
主要介绍了C语言左旋转字符串与翻转字符串中单词顺序的方法,给出了相关的两道算法题目作为例子,需要的朋友可以参考下
search_and_replace.zip 字符串查找和替换的实现例子(1KB)<END><br>7,quiksort.zip 字符的快速排序算法(12KB)<END><br>8,parsestring.zip 分解字符串(3KB)<END><br>9,wordwrap6.zip 包装单并输出到文本...
6-1 复原IP地址-原理讲解 6-2 复原IP地址-代码演示 6-3 关联字符串-原理讲解 6-4 关联字符串-代码演示第7章 数据结构之“栈”数组具有栈的功能,如何用?如何用栈去解决自定义数学运算(棒球比赛)是不是很好奇?这...
LeetCode算法蛇形走位 leetcode 个人算法学习代码,欢迎一起学习讨论! 数据结构 数组 -[x] 实现动态扩容数组 -[x] 实现有序数组 -[x] 合并两个有序数组 -[x] 简单:169.多数元素 -[x] 简单:1.两数之和 -[x] 简单:...
第一章 字符串1.0 本章导读1.1 旋转字符串1.2 字符串包含1.3 字符串转换成整数1.4 回文判断1.5 最长回文子串1.6 字符串的全排列1.10 本
主要介绍了PHP实现字符串翻转功能的方法,结合实例形式对比分析了php使用递归与循环算法实现字符串反转功能的相关操作技巧,需要的朋友可以参考下
第一章 字符串 o 1.0 本章导读 o 1.1 旋转字符串 o 1.2 字符串包含 o 1.3 字符串转换成整数 o 1.4 回文判断 o 1.5 最长回文子串 o 1.6 字符串的全排列 o 1.10 本章习题 第二章 数组 o 2.0 本章导读 o 2.1 寻找最小的...
解码字符串 - 短字距 - 索引处的解码字符串 - 确定两个字符串是否接近 - 简化路径 - 反向字符串 - 大批 最大连续数 - 最大连续数 II - 重复的零 - 合并排序数组 - 删除元素 - 删除重复的排序数组 - 删除重复的排序...
32.1 朴素字符串匹配算法 32.2 Rabin\Karp算法 32.3 利用有限自动机进行字符串匹配 32.4 Knuth?Morris?Pratt算法 思考题 本章注记 第33章 计算几何学 33.1 线段的性质 33.2 确定任意一对线段...
LeetCode判断字符串是否循环 LeetCode 解题记录 编号 名称 完成日期 简要题解 难度 0001 两数之和 2020-07-26 暴力算法 ★ 0007 整数反转 2020-08-02 字符串,类型转换 ★ 0008 字符串转换整数 2021-02-07 经典字符...
置换字符串 - 所有子集 - 号码有效吗? —— 数字的力量 - 计算平方根 - 字符串 倒置句子中的单词 - , 删除重复项 - 删除空格 - 字符串分割 - XML 到树 - 查找所有回文子串 - 正则表达式 - 树木 检查两棵二叉树是否...
kmp算法源码,快速搜索字符串算法,用于文本抽取、文本编辑器开发参考。
亲密字符串 leetcode-js js算法学习笔记(leetcode刷题) 刷题线路 链表 链表访问 141.环形链表 142.环形链表II 202.快乐数 链表反转 206.反转链表 92.反转链表II 25.K个一组反转链表 61.旋转链表 24.两两交换链表的...
本书是原书的第2版,在第1版的基础之上增加了一些新的内容,涉及算法的作用、概率分析和随机化算法、线性规划,以及对第1版中详尽的、几乎涉及到每一小节的修订。这些修订看似细微,实际上非常重要。书中引入了...
LeetCode判断字符串是否循环 数据结构与算法 二维数组的查找 题目描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一...