string Leetcode 字符串算法题

server/2024/11/12 19:56:25/

344.反转字符串

API: StringBuffer 内部是 append 实现字符串的改变,不会每次改变字符串都创建一个新对象

StringBuffer(String.valueOf(s)).reverse().toString()

不调用API, 使用双指针,分别从两端向中间聚拢

class Solution {public void reverseString(char[] s) {int l = 0, r = s.length - 1;while(l < r){char chL = s[l];char chR = s[r];s[l] = chR;s[r] = chL;++l;--r;}}
}

541.反转字符串 II

class Solution {public String reverseStr(String s, int k) {char[] str = s.toCharArray();int n = str.length;int l = 0;while(l < n){int r = (l-1) + k;if(r >= n) r = n - 1;int nextl = (l-1)+2*k+1;while(l < r){char ch = str[l];str[l] = str[r];str[r] = ch;++l;--r;}l = nextl;}return new String(str);}
}

122.路径加密/替换空格

API:

path.replaceAll(string">"\\.", string">" ");
class Solution {public String pathEncryption(String path) {char[] p = path.toCharArray();for(int i = 0; i < p.length; ++ i){if(p[i] == '.'){p[i] = ' ';}}return new String(p);}
}

182.动态口令/左旋字符串

stringbegin_len_74">substring(begin, len)

class Solution {public String dynamicPassword(String password, int target) {int n = password.length();return password.substring(target, n) + password.substring(0, target);}
}

StringBuilder

class Solution {public String dynamicPassword(String password, int target) {StringBuilder res = new StringBuilder();for(int i = target; i < password.length() + target; ++i){res.append(password.charAt(i % password.length()));}return res.toString();}
}

源字符串上操作

28.实现strStr

找第一个匹配子串的下标

KMP

求Next数组:

  1. Next 数组长度为 n + 1,用于获取 next[n],也就是整个字符串相同前后缀的长度
  2. 刚开始 Next[0] = -1, j = -1,便于观察当前是否已经退回到下标 0 了
  3. 可以求所有匹配位置,在 while 循环里判断 j 是否到n,然后让 j = next[j],继续匹配
class Solution {public int strStr(String haystack, String needle) {int n = needle.length(), m = haystack.length();int[] next = new int[n+1];next[0] = -1;int i = 0, j = -1;while(i < n){if(j == -1 || needle.charAt(j) == needle.charAt(i)){++j;++i;next[i] = j;}else{j = next[j];}}i = 0;j = 0;while(i < m && j < n){if(j == -1 || haystack.charAt(i) == needle.charAt(j)){++i;++j;}else{j = next[j];}}if(j == n){return i - n;}return -1;}
}

暴力

public class Solution {public int strStr(String haystack, String needle) {for(int i = 0; i < haystack.length(); ++i){String compare = haystack.substring(i, Math.min(i+needle.length(), haystack.length()));if(compare.equals(needle)){return i;}}return -1;}
}

459.重复的子字符串

求循环节

注意这里需要剔除特殊情况,防止后面的取模一直为0,

  • 避免 next[n] = 0,否则变成 n % n == 0
  • 避免 n = 1,否则 n % (n - 0) = 1 % 1 == 0
class Solution {public boolean repeatedSubstringPattern(String s) {int n = s.length();int[] next = new int[n+1];next[0] = -1;int i = 0, j = -1;while(i < n){if(j == -1 || s.charAt(j) == s.charAt(i)){++j;++i;next[i] = j;}else{j = next[j];}}if(next[n] != 0 && n != 1 && n % (n - next[n]) == 0){return true;}return false;}
}

93.复原IP地址

细节注意:

  • IP 地址不能超过 3 位
  • 不能前导 0 开头
  • 不能大于 255
  • 只有 4 节:终止条件
class Solution {List<String> res = new ArrayList<>();List<String> ans = new ArrayList<>();public List<String> restoreIpAddresses(String s) {dfs(s, 0, 0);return res;}public void dfs(String s, int beg, int num){if(num == 4 && beg == s.length()){String ip = string">"";for(int i = 0; i < ans.size(); ++ i){ip += ans.get(i) + ((i < ans.size() - 1) ? string">"." : string">"");}res.add(ip);return;}if(num > 4){return;}for(int i = beg; i < beg + 3 && i < s.length(); ++ i){String str = s.substring(beg, i+1);if(str.length() > 1 && str.charAt(0) == '0') continue;int strnum = Integer.parseInt(str);if(strnum < 0 || strnum > 255) continue;ans.add(str);dfs(s, i + 1, num+1);ans.remove(ans.size() - 1);}}}

可以用 StringBuilder 来累加节约空间

更方便的写法:

String.join(string">".", ans);

http://www.ppmy.cn/server/11676.html

相关文章

MTK6775/MT6775/曦力P70联发科处理器性能参数资料

联发科MT6775(曦力P70)芯片搭载强大的Arm Cortex-A73/A53八核CPU&#xff0c;并采用台积电12纳米FinFET制程工艺&#xff0c;相较于其他14纳米级别产品&#xff0c;功耗节省达到了15%。此外&#xff0c;曦力P70还配备了高效能的Arm Mali-G72 GPU&#xff0c;相比上一代产品曦力…

PAT——1013数素数(C++)

问题描述&#xff1a; 令 Pi​ 表示第 i 个素数。现任给两个正整数 M ≤ N ≤ &#xff0c;请输出 到 ​ 的所有素数。 输入格式&#xff1a; 输入在一行中给出 M 和 N&#xff0c;其间以空格分隔。 输出格式&#xff1a; 输出从 ​ 到 的所有素数&#xff0c;每 10 个数字占…

自定义Vue 2双向绑定指令:实现与解析

自定义Vue 2双向绑定指令&#xff1a;实现与解析 Vue.js以其简洁的语法和强大的数据绑定功能深受开发者喜爱。其中&#xff0c;内置的v-model指令实现了输入控件与数据模型之间的双向绑定&#xff0c;简化了表单交互的处理。然而&#xff0c;在某些特定场景下&#xff0c;我们…

BTP连接cloud connector中配置的SAP

登录地址 登录之后可以看到我们已经配置成功的后端系统SAP。 从cloud connector中获取location ID ,然后在BTP中配置Destination 选择目标标签页&#xff0c;点击‘新建目标’&#xff0c;如下图&#xff1a; 新建连接 暂时不知道错误原因 创建目标-HTTP  新建目标&…

XiaodiSec day021 Learn Note 小迪安全学习笔记

XiaodiSec day021 Learn Note 小迪安全学习笔记 记录得比较凌乱&#xff0c;不尽详细 javaweb 2024.01.30 0:11 知识点 javaWeb 相关 JWT 越权 开始 知识点 1 webgoat 在 github 中 8.22 版本 不会全讲&#xff0c;只是挑一部分 path traversal 第二关 上传到指定位…

浅谈如何学习微信小程序

这是一篇干巴巴的文章&#xff0c;有兴趣的可以继续往下阅读。本人毕业已经三年多了&#xff0c;从实习到现在接触了java、javascript、html、vue、MySQL、jquery、微信小程序等&#xff0c;经验也算是有一点&#xff0c;感觉不多&#xff0c;属于全栈开发吧&#xff0c;本次就…

NameError: name ‘init_detector’ is not defined

使用模型提取人体pose&#xff0c;遇到的问题记录。 1. 排查问题直接讲报错的地方拷贝在python中直接运行。 运行后提示&#xff1a; ModuleNotFoundError: No module named mmcv._ext 经过各种的地方去查找问题 github的issue Error in init_detector Issue #3354 ope…

美容预约小程序:简单三步,开启高效预约模式

在当今的数字化时代&#xff0c;一个小程序可以极大地提高美容院的效率和客户满意度。下面我们将详细说明如何通过以下步骤来搭建一个美容院预约小程序。 首先&#xff0c;你需要注册并登录到乔拓云网&#xff0c;这是 一个在线平台&#xff0c;可以帮助你快速创建并管理你的小…