2019獨角獸企業重金招聘Python工程師標準>>>

描述：

定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。
如把字符串abcdef左旋轉2位得到字符串cdefab。
請實現字符串左旋轉的函數，要求對長度為n的字符串操作的時間復雜度為O(n)，空間復雜度為O(1)

對應的詳細分析見：http://blog.csdn.net/v_july_v/article/details/6322882

實現：

下面給出兩個可靠的java實現：

package com.jiangdx.algrithmn;import java.util.Arrays;public class RotateShift {/*** 假設原數組序列為abcd1234，要求變換成的數組序列為1234abcd，即循環右移了4位。* 比較之后，不難看出，其中有兩段的順序是不變的：1234和abcd，可把這兩段看成兩個整體* 逆序排列abcd：abcd1234 → dcba1234；* 逆序排列1234：dcba1234 → dcba4321；* 全部逆序： dcba4321 → 1234abcd* * @param s* @param bit*/static void reverseRightShift(String[] s, int bit) {/** bit > length */int length = s.length;bit %= length;reverse(s, 0, length - bit - 1);reverse(s, length - bit, length - 1);reverse(s, 0, length - 1);}static void reverse(String[] s, int start, int end) {for (; start < end; start++, end--) {String t = s[start];s[start] = s[end];s[end] = t;}}/*** 所有序號為 (j+i *m) % n (j為0到gcd(n, m)-1之間的某一整數，i = 0:n-1，m表示左旋轉位數，n表示字符串長度)，* 會構成一個循環鏈（共有gcd(n,m)個，gcd為n、m的最大公約數），* * 每個循環鏈上的元素只要移動一個位置即可，最后整個過程總共交換了n次* （每一次循環鏈，是交換n/gcd(n,m)次，共有gcd(n,m)個循環鏈，所以，總共交換n次）。* example: [a, b, c, d, e, 1, 2, 3，4] 右移3位* gcd=3, 循環鏈=[a, d, 2] [b, e, 3] [c, 1, 4]* 循環鏈循環右移1個位置： [2, a, d] [3, b, e] [4, c, 1]* 結果： [2, 3, 4, a, b, c, d, e, 1]* * @param s* @param m*/static void rotateShift(String[] s, int m) {int length = s.length;int gcd = gcd(m, length);int count = length / gcd;for (int j = gcd - 1; j >= 0; j--) {String last = s[(j + (count - 2 + 1) * m) % length];int first = 0;for (int i = count - 2; i >= 0; i--) {first = (j + i * m) % length;s[(j + (i + 1) * m) % length] = s[(j + i * m) % length];}s[first] = last;}}/*** 求最大公約數: 1、[求余數]，令r=m%n，r為n除m所得余數（0<=r<n）；* 2、[余數為0?]，若r=0，算法結束，此刻，n即為所求答案，否則，繼續，轉到3； 3、[重置]，置m == n，n == r，返回步驟1.* * @param m* (m > 0)* @param n* (n > 0)*/static int gcd(int m, int n) {if (m < n) {int t = n;n = m;m = t;}int r = m % n;if (r == 0)return n;/** recursively find it */m = n;n = r;return gcd(m, n);}public static void main(String[] args) {String[] s = { "a", "b", "c", "d", "1", "2", "3", "4", "32" };System.err.println(Arrays.toString(s));// reverseRightShift(s, 5);rotateShift(s, 5);System.out.println(Arrays.toString(s));}}

轉載于:https://my.oschina.net/twinkling/blog/170303

總結

以上是生活随笔為你收集整理的分享字符串右移的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。