【搞定算法】字符串的翻转和旋转及其应用

灰太狼 2021-11-29 06:12 232阅读 0赞

### **目 录：** ###

**一、字符串的翻转**

1、StringBuilder 实现

2、双指针实现

3、字符串翻转应用

**二、字符串的旋转**

1、三步翻转实现旋转【重点】

2、String 的 substring 方法实现

--------------------

面试和笔试中我们也经常遇到字符串相关的翻转和旋转的题目。本文就对字符串的翻转和旋转做个简单的用法总结。

# 一、字符串的翻转 #

## 1、StringBuilder 实现 ##

可以直接利用 StringBuilder 类的 reverse 方法直接实现。

public class StringReverse {
    
        public static String reverseString(String str){
            if(str == null || str.length() < 1){
                return str;
            }
    
            StringBuilder sb = new StringBuilder(str);
            return sb.reverse().toString();
        }
    }

## 2、双指针实现 ##

public class StringReverse {
    
        public static String reverseString(String str){
            if(str == null || str.length() == 0){
                return str;
            }
            char[] res = str.toCharArray();
            int left = 0;
            int right = str.length() - 1;
            while(left < right){
                char temp = res[left];
                res[left++] = res[right];
                res[right--] = temp;
            }
            return String.valueOf(res);
        }
    }

## 3、字符串翻转应用 ##

LeetCode 151题：[https://leetcode-cn.com/problems/reverse-words-in-a-string/][https_leetcode-cn.com_problems_reverse-words-in-a-string]

**题目：给定一个字符串，逐个翻转字符串中的每个单词。**

> 示例 1：
> 
> 输入: "the sky is blue"  
> 输出: "blue is sky the"
> 
> 示例 2：
> 
> 输入: "  hello world!  "  
> 输出: "world! hello"  
> 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
> 
> 示例 3：
> 
> 输入: "a good   example"  
> 输出: "example good a"  
> 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。  
>

*  **说明：**

1、无空格字符构成一个单词；

2、输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括；

3、如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

public class ReverseWords_151 {
    
        public String reverseWords(String s) {
            if(s == null || s.length() < 1){
                return s;
            }
    
            // split("\s+") 按空格,制表符等进行拆分
            String str[] = s.trim().split("\\s+");
            String res = "";
            for(int i = str.length - 1; i > 0; i--){
                res += str[i] + " ";
            }
            // str[0]在这里加是避免在循环中加了后会在新的字符串结尾多一个空格
            return res + str[0];
        }
    }

知识点:

*  \\s表示 空格、回车、换行等空白符，+号表示一个或多个的意思；
 *  split("\\s+") 按空格、制表符等进行拆分；
 *  split(" +") 按空格进行拆分（也就是说只有按空格键流出来的空白才会是拆分的一句），这里用这个也可以。

> Example 1: Input: "Let's take LeetCode contest"
> 
> Output: "s'teL ekat edoCteeL tsetnoc"

public class Solution {  
        public String reverseWords(String s) {  
        String[] strs = s.split(" ");  
        StringBuilder sb = new  StringBuilder();  
        for(String str: strs){  
            StringBuilder temp = new StringBuilder(str);  
            sb.append(temp.reverse());  
            sb.append(" ");  
        }  
        // 去掉最后一个空格
        return sb.toString().trim();  
        }  
    }

--------------------

# 二、字符串的旋转 #

> **旋转字符串：给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)。**
> 
> 样例  
> 对于字符串 "abcdefg".
> 
> offset = 0 => "abcdefg"  
> offset = 1 => "gabcdef"  
> offset = 2 => "fgabcde"  
> offset = 3 => "efgabcd"

## 1、三步翻转实现旋转【重点】 ##

三步反转的思维比较巧妙，做法分为三步：

1、将字符串分为两部分，要移位的 m 个字符 X 和剩下的字符 Y。如 “abcdef”，则 X=“abc”，Y=“def”；

2、将 X 进行反转，得到 “cba”；将 Y 进行反转，得到 “fed”；

3、将反转后的 XY 合并字符串在进行反转，最后得到 “defabc”。

public class RotateString {
        /**
         * 字符串旋转
         * @param str ：原字符串
         * @param m ：要旋转的字符串长度
         * @return
         */
        private static String rotateString(String str, int m){
            char[] chars = str.toCharArray();
            reverseString(chars, 0, m - 1);             // 旋转前半部分
            reverseString(chars, m, str.length() - 1);  // 旋转后半部分
            reverseString(chars, 0, str.length() - 1);  // 旋转整个数组
            return String.valueOf(chars);
        }
    
        private static void reverseString(char[] chars, int left, int right){
            while(left < right){
                char temp = chars[left];
                chars[left++] = chars[right];
                chars[right--] = temp;
            }
        }
        public static void main(String[] args) {
            System.out.println(rotateString("abcdef", 2));  // cdefab
        }
    }

## 2、String 的 substring 方法实现 ##

public class RotateString {
    
        public static String rotateString2(String str, int m){
            if(str == null || str.length() < 1 || m < 0){
                return str;
            }
    
            if(m == str.length() - 1){
                return str;
            }else{
                return str.substring(m, str.length()) + str.substring(0, m);
            }
        }
    
        public static void main(String[] args) {
            System.out.println(rotateString2("abcdef", 3));  // cdefab
        }
    }

[https_leetcode-cn.com_problems_reverse-words-in-a-string]: https://leetcode-cn.com/problems/reverse-words-in-a-string/