我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題58 - II. 左旋轉字串
題目
字串的左旋轉操作是把字串前面的若干個字符轉移到字串的尾部，請定義一個函式實作字串左旋轉操作的功能，比如，輸入字串"abcdefg"和數字2，該函式將回傳左旋轉兩位得到的結果"cdefgab"，
示例 1：
輸入: s = "abcdefg", k = 2
輸出: "cdefgab"
示例 2：
輸入: s = "lrloseumgh", k = 6
輸出: "umghlrlose"
限制：
- 1 <= k < s.length <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-兩次遍歷
- 第一次遍歷先拼接n之后的字符；
- 第二次遍歷拼接0-n之間的字符；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路2-一次遍歷
考慮把遍歷的范圍定為[n,n+length]，遍歷時下標取i%length，那么得到下標范圍為[n,length-1]和[0,n-1]，且是順序的；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月16日 下午11:30:08
* @Description: 面試題58 - II. 左旋轉字串
*
*/
public class LeetCode_Offer_58_2 {
}
class Solution_Offer_58_2 {
/**
* @author: ZhouJie
* @date: 2020年5月16日 下午11:31:12
* @param: @param s
* @param: @param n
* @param: @return
* @return: String
* @Description: 1-分兩次遍歷拼接到StringBuilder；
*
*/
public String reverseLeftWords_1(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder(len);
for (int i = n; i < len; i++) {
sb.append(s.charAt(i));
}
for (int i = 0; i < n; i++) {
sb.append(s.charAt(i));
}
return sb.toString();
}
/**
* @author: ZhouJie
* @date: 2020年5月16日 下午11:35:25
* @param: @param s
* @param: @param n
* @param: @return
* @return: String
* @Description: 2-利用取模%特性一次遍歷；
*
*/
public String reverseLeftWords_2(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder(len);
for (int i = n; i < len + n; i++) {
sb.append(s.charAt(i % len));
}
return sb.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/189843.html
標籤：Java
上一篇：LeetCode 面試題53 - II. 0～n-1中缺失的數字
下一篇：提升PHP執行效率的一些小細節