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

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

什么是手摇算法?

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

/**
     * 反转倒置
     * 在由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);
    }
}


相关文章
|
3月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
1月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
73 1
两个字符串匹配出最长公共子序列算法
|
3月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
4月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
272 1
|
4月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
117 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
3月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
81 0
|
5月前
|
存储 算法 Cloud Native
C++ bcrypt算法 字符串加密,亲测有效
C++ bcrypt算法 字符串加密,亲测有效
|
5月前
|
存储 算法
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
|
4月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
6月前
|
算法
KPM算法求字符串的最小周期证明
公式 `ans = n - LPS[n-1]` 描述了最小周期,其中 `n` 是子串长度,`LPS[n-1]` 是前缀函数值。证明分为特殊情况和一般情况:对于完整周期字符串,`LPS[n-1] = 3*T`,故 `ans = T`;对于非完整周期,通过分析不同长度的 `[末部分]` 和 `[前部分]`,展示 `ans` 始终等于周期 `T` 或由 `[e][b]` 构成的最小周期,从而证明公式正确。