題目描述

字串的左旋轉操作是把字串前面的若干個字符轉移到字串的尾部，請定義一個函式實作字串左旋轉操作的功能，比如，輸入字串"abcdefg"和數字2，該函式將回傳左旋轉兩位得到的結果"cdefgab"，

示例 1：
輸入: s = "abcdefg", k = 2
輸出: "cdefgab"

示例 2：
輸入: s = "lrloseumgh", k = 6
輸出: "umghlrlose"

題解

字串復制法

定義一個輔助字串指標h，通過單重回圈先將后半部分讀入h指向的記憶體空間，再將前半部分讀入，實作旋轉，演算法的時間空間復雜度均為O(n)，

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* reverseLeftWords(char* s, int n) {
    int length = strlen(s);
    int i, j = 0;
    char* h = (char*)malloc(sizeof(char)*(length+n));
    for (i = n; i <= length-1; i++) {
        h[j++] = s[i];
    }
    for (i = 0;i <= n-1; i++) {
        h[j++] = s[i];
    }
    h[j] = '\0';
    return h;
}

int main() {
	char* s = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

王道雙指標

這題是LeetCode劍指第一題，竟然還是考研真題，王道書上對于這操作叫部分字串左移，王道的方法就是定義一個以字符為單位的交換函式，呼叫三次，分別交換[0，n-1]、[n，length-1]和[0，length-1]，時間復雜度仍為O(n)，但是空間復雜度只與中轉變數temp有關，為O(1)，

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* reverseLeftWords(char s[], int n) {//The char* pointer points to the string constant area and it cannot be modified, so it is changed to a chartype array, but it can be submitted with a pointer on the LeetCode.
    int length = strlen(s);
    char temp;
    int low, high;
    for (low = 0, high = n-1;low <= high;low ++, high--) {
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    for (low = n, high = length-1;low <= high;low ++, high--) {
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    for (low = 0, high = length-1;low <= high;low ++, high--) {
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    return s;
}

int main() {
	char s[] = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

切片函式

采用java中的切片函式substring()時空間效率無提升，但是可以將代碼精簡至一行，C中沒有這個函式，我自己定義了一個strcut()函式實作類似功能，也將旋轉函式精簡至一行，不過LeetCode會顯示對h指向的記憶體分配空間時記憶體溢位，暫時還沒解決，但是這個代碼在編譯器上是可以圓滿完成要求的，

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* strcut(char* s, int begin, int end) {
    int i = 0, j = 0;
    char* h = (char*)malloc(end-begin);
    for (i = begin;i <= end; i++) {
        h[j++] = s[i];
    }
    h[j] = '\0';
    return h;
}

char* reverseLeftWords(char* s, int n) {
    return strcat(strcut(s, n, strlen(s)-1), strcut(s, 0, n-1));
}

int main() {
	char* s = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

運行結果

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276275.html

標籤：其他

上一篇：W10 安裝Node-red工具的程序和遇到的問題處理方式

下一篇：圖的題目基礎類與方法