掌握算法学习之字符串经典用法

简介: 文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。

一、前言

字符串是我们编程最常使用的数据类型,在算法领域字符串的题目也非常多,本文通过分析字符串最经典的操作进行总结记录,对于我们沉淀字符串类的算法是有帮助的,算法虽难学,但是我相信多实操,多总结,总有一天可以提高我们的算法思维。

二、字符串经典用法

1、间接借助双指针法遍历字符串

我们对于字符串操作时,可以将字符串转换为字符数组,在数组中,我们有通过双指针法来完成多种形式遍历,这样在字符串中也完美借助了双指针法的能力。之前有总结双指针在数组中的经典应用,有兴趣的朋友可以收藏下。

通过双指针,我们能够轻松解决字符串整体反转,字符串部分反转等经典题目。

三、实战

leetcode344. 反转字符串

class Solution {
   
    public void reverseString(char[] s) {
   

        int start = 0;
        int end = s.length-1;
        while(start<end) {
   
            char a = s[start];
            char b = s[end];
            s[start] = b;
            s[end] = a;
            start++;
            end--;
        }

    }
}

上面通过双指针法实现字符串整体反转。

class Solution {
   
    public String reverseStr(String s, int k) {
   
        //0 2 0 1 2 3 4 5 6
        char[] chars = s.toCharArray();
        for(int i=0; i<s.length(); i = i + 2*k) {
   
            //下标从0开始,因此需要处理的结尾下标需要-1
            int temp = i + k -1;
            int end = 0;
            //不可以越界
            if(temp <= s.length()-1) {
   
                end = temp;
            } else {
   
                //不可以越界
                end = s.length() -1;
            }
            System.out.println(i+"="+end);
            reverseChars(chars, i, end);

        }

        return new String(chars);
    }

    public void reverseChars(char[] chars, int start, int end) {
   
        while(start < end) {
   
            char a =  chars[start];
            char b =  chars[end];
            chars[start] = b;
            chars[end] = a;
            start++;
            end--;
        }

    }
}

通过双指针法完成字符串部分反转

leetcode151. 反转字符串中的单词

class Solution {
   
    public String reverseWords(String s) {
   
        //移除空格
        StringBuilder ss = removeSpace(s);
        //使用双指针法实现原地反转
        //先整体反转一次 再单独反转每个单词

        char[] chars = ss.toString().toCharArray();

        //整体反转
        int start = 0;
        int end = chars.length - 1;

        while(start < end) {
   
            char a =  chars[start];
            char b =  chars[end];
            chars[start] = b;
            chars[end] = a;
            start++;
            end--;
        }

        //再每个单词单独反转
        for(int i=0; i<chars.length; ) {
   

            int e = i;// "the sky is blue"
            //遇到了空串,或者结尾了,就需要反转
            while(chars.length-1 == e ||( e < chars.length && chars[e] != ' ') ) {
   
                e++;
            }

            reverseChars(chars,i, e-1);
            System.out.println(i+"="+e);

            i=e+1;

        }
        //"the sky is blue"
        return new String(chars);
    }

    public void reverseChars(char[] chars, int start, int end) {
   
        while(start < end) {
   
            char a =  chars[start];
            char b =  chars[end];
            chars[start] = b;
            chars[end] = a;
            start++;
            end--;
        }

    }

    private StringBuilder removeSpace(String s) {
   

        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
   
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
   
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
}

通过双指针完成字符串整体反转和部分反转。

四、总结

双指针在数组中的用法,使用到了字符串上面,实现字符串原地处理字符数据的能力。

相关文章
|
2月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
9天前
|
算法 JavaScript 前端开发
第一个算法项目 | JS实现并查集迷宫算法Demo学习
本文是关于使用JavaScript实现并查集迷宫算法的中国象棋demo的学习记录,包括项目运行方法、知识点梳理、代码赏析以及相关CSS样式表文件的介绍。
第一个算法项目 | JS实现并查集迷宫算法Demo学习
|
13天前
|
XML JavaScript 前端开发
学习react基础(1)_虚拟dom、diff算法、函数和class创建组件
本文介绍了React的核心概念,包括虚拟DOM、Diff算法以及如何通过函数和类创建React组件。
15 2
|
2月前
|
机器学习/深度学习 人工智能 资源调度
【博士每天一篇文献-算法】连续学习算法之HAT: Overcoming catastrophic forgetting with hard attention to the task
本文介绍了一种名为Hard Attention to the Task (HAT)的连续学习算法,通过学习几乎二值的注意力向量来克服灾难性遗忘问题,同时不影响当前任务的学习,并通过实验验证了其在减少遗忘方面的有效性。
52 12
|
2月前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake(雪花)算法。为解决用户ID安全性与唯一性问题,Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位(固定为0)、41位时间戳、10位标识位(含数据中心与机器ID)及12位序列号组成。面对ID重复风险,可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID,确保不同节点产生的ID始终唯一。
go语言后端开发学习(六) ——基于雪花算法生成用户ID
|
2月前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之HNet:Continual learning with hypernetworks
本文提出了一种基于任务条件超网络(Hypernetworks)的持续学习模型,通过超网络生成目标网络权重并结合正则化技术减少灾难性遗忘,实现有效的任务顺序学习与长期记忆保持。
35 4
|
2月前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之RWalk:Riemannian Walk for Incremental Learning Understanding
RWalk算法是一种增量学习框架,通过结合EWC++和修改版的Path Integral算法,并采用不同的采样策略存储先前任务的代表性子集,以量化和平衡遗忘和固执,实现在学习新任务的同时保留旧任务的知识。
76 3
|
2月前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-综述】基于脑启发的连续学习算法有哪些?附思维导图
这篇博客文章总结了连续学习的分类,包括经典方法(重放、正则化和稀疏化方法)和脑启发方法(突触启发、双系统启发、睡眠启发和模块化启发方法),并讨论了它们在解决灾难性遗忘问题上的优势和局限性。
30 2
|
2月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
53 0
|
5天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
下一篇
无影云桌面