【算法】手摇算法反转部分字符串

怼烎@ 2024-03-17 11:14 60阅读 0赞

#### 文章目录 ####

*  什么是手摇算法？

## 什么是手摇算法？ ##

有一个场景，就是反转字符串中的字符。这个很简单，我们可以很快的写出如下代码：

/**
         * 反转倒置
         * 在由char[]转为Sting注意不要使用toSting方法
         */
        public static void reverse(char[] chr){
        
            int n=chr.length-1;
            //使用头尾两个指针从两边向中间扫，并且不断交换两个指针的内容
            for(int i=0;i<chr.length/2;i++){
        
                swap(chr,i,n--);
            }
        }

Leetcode上面会有一些题目，并不是要求你反转整个字符串，而只是反转字符串中两块元素的位置，该怎么做呢？

可能有的人会说，没问题，我们在开辟一块内存保存一部风的元素块到时候我们再复制两次就可以了  
那么如果题目加上限制，我们要求空间复杂度只能是O(1)，又该如何解决呢？  
这里我们就要引入手摇算法的概念了：  
手摇算法的处理方式非常的灵活，我们可以转换大小不均衡的元素块，那么他的原理该怎么解释呢？  
举例：A B C D E F,我们要求A B和C D E F转换位置  
1.我们先观察  
根据上面的逆序交换的手段，我们怎么通过逆序交换的手段来实现位置的转换呢：  
A B C D E F  
C D E F A B

首先：我们推导一遍就明白了  
A B C D E F  
B A F E D C  
C D E F A B (转换完成)  
所以说算法存在三次反转的过程，实如其名：  
1.反转前一段  
2.反转后一段  
2.反转整体  
很明显我们的空间复杂度仅仅只是交换操作的t，O(1)实至名归

package com.base.learn.string;
    
    /**
     * @author: 张锦标
     * @date: 2023/5/25 13:15
     * ReverseStr类
     */
    public class ReverseStr {
        
        /**
         * 用于反转字符数组中index1~index2位置的这一段
         * 左闭右开区间,index1<=下标<index2
         */
        public static void reverse(char[] chr,int index1,int index2){
        
            if(index2-index1 < 2) {
        
                return;
            }
            int j=index2-1;//右侧下标
            for(int i=index1;i<(index2+index1)/2;i++){
        
                swap(chr,i,j--);
            }
        }
    
        /**
         * 旋转
         * 使用三次反转，实现旋转
         * 数组注意区间取值
         * @param m 从位置m处进行旋转
         */
        public static void rotation(char[] chr,int m){
        
            //第一次倒置0~m位置
            reverse(chr,0,m);
            //第二次倒置m~最后位置
            reverse(chr,m,chr.length);
            //最后整体倒置
            reverse(chr,0,chr.length);
        }
    
        private static void swap(char[] arr,int index1,int index2){
        
            char temp=arr[index1];
            arr[index1]=arr[index2];
            arr[index2]=temp;
        }
    
        public static void main(String[] args) {
        
            String s = "123456";
            char[] chars = s.toCharArray();
            rotation(chars,2);
            System.out.println(chars);
        }
    }