“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the 82nd day 🎈!
🚀 Algorithm 🚀

🌲 Example: Reverse string II

Given a string s and an integer k, invert the first K characters of the 2k character for every 2k character count from the beginning of the string.

  • If there are fewer characters leftk, all the remaining characters are reversed.
  • If the remaining characters are less than2k But greater than or equal tok, then reverse beforekThe rest of the characters remain unchanged.

Example 1:

Enter: s ="abcdefg", k = 2Output:"bacdfeg"
Copy the code

Example 2:

Enter: s ="abcd", k = 2Output:"bacd"
Copy the code

Tip:

  • 1 <= s.length <= 104
  • S consists of lowercase English only
  • 1 <= k <= 104

🌻C# method: simulation

We simulate directly as the problem suggests: invert each substring of length K starting at a multiple of 2K. If the substring length is less than k, the entire substring is reversed.

Code:

public class Solution {
    public string ReverseStr(string s, int k) {
        int n = s.Length;
        char[] arr = s.ToCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            Reverse(arr, i, Math.Min(i + k, n) - 1);
        }
        return new string(arr);
    }

    public void Reverse(char[] arr, int left, int right) {
        while (left < right) {
            chartemp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; }}}Copy the code

The execution result

By execution time:92Ms, in all CBeat 22.50% of users in # submissionsMemory consumption:37.8MB, in all C# beat 12.90% of users in submission
Copy the code

🌻Java method: emulation

Invert each substring of length K starting at a multiple of 2K. If the substring length is less than k, the entire substring is reversed.

Code:

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            chartemp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; }}}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits100.00% user memory consumption:38.1MB, beat out all Java commits98.40% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

💬 summary

  • Today is the 82nd day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!