Sword finger Offer 24. Reverse the linked list

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1, the title

Left-rotation of a string moves several characters from the beginning to the end of the string. Define a function to rotate the string left. For example, if you enter the string “abcdefg” and the number 2, the function will return “cdefgab” as a result of the left rotation.

Example 1:

Enter: s = “abcdefg”, k = 2

Output: “cdefgab”

Example 2:

Enter: s = “abcdefg”, k = 2

Output: “cdefgab”

Tip:

  • 1 <= k < s.length <= 10000

2, train of thought

Method one:

  1. Interception is neededMoves to the string portion at the end of the stringSave by character
  2. Use replace to replace the truncated part of the original array""To make the substitution
  3. After the substitution is complete, the StringBuffer is used for stitching.

Method 2:

  1. Take the string [a, b, c, D, e, f, g] as an example. First, we reverse the string S to get [G, f, e, D, c, b, a].
  2. The willMoves to the string portion at the end of the stringIt’s called s1, and the part we don’t have to deal with is called S2, so s is equal to s1 plus s2. Suppose s = “gfedvba”, k = 2. So s1 is “ba”, s2 is “gfeDC”.
  3. Flip S2, then s2 = “gfedc”, s = “abgfedc”.
  4. If s1 = “ab”, s = “cdefgab”.
  5. Return s. So three flips, and we’re done.

Less nonsense ~~~~~ on the code!

3, code,

Commit AC for the first time

class Solution {
    public String reverseLeftWords(String s, int n) {
        String s1 = s.substring(0, n);
        String replace = s.replace(s1, "");
        StringBuffer sb = new StringBuffer(replace);
        sb.append(s1);
        returnsb.toString(); }}Copy the code

Commit the SECOND TIME

class Solution {
    public String reverseLeftWords(String s, int n) {
        char c[] = s.toCharArray();
        int l = c.length;
        reverse(c, 0, l - 1);
        reverse(c, 0, l - n -1);
        reverse(c, l - n, l - 1);
        return new String(c);
    }
    public static void reverse(char c[], int left, int right){
        while(left < right){
            chartemp = c[left]; c[left] = c[right]; c[right] = temp; left++; right--; }}}Copy the code

4, summarize

The use of substr is the same as the time complexity of the inversion, both O(n), but the use of substring requires additional space, so the space complexity is O(n), while the space complexity of the inversion method is O(1).

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

Offer 58-II. Rotate string left