- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
字符串的题目,通常涉及到对字符串进行各种操作,由于JAVA提供了非常多的库函数,所以在很多题目中我们可以使用库函数快速使这道题解决,但是这与我们训练算法和编码能力相违背.
所以我们在本章专题里面,主要是使用我们自己构造的函数对字符串进行,操作加深我们对字符串操作的理解,当我们训练熟悉后可以使用库函数直接执行.
题意:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出.
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题.
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符.
示例 1: 输入:["h","e","l","l","o"] 输出:["o","l","l","e","h"] 。
示例 2: 输入:["H","a","n","n","a","h"] 输出:["h","a","n","n","a","H"] 。
在此我们考虑不使用额外空间的一种做法,我们可以使用一个在头,一个在尾部的双指针对字符串做一个反转.
每次双指针所指向的字符进行交换,当两个指针穿越的时候就表示已经处理完整个字符串.
class Solution {
public void reverseString(char[] s) {
int n = s.length;
int l = 0, r = n - 1;
while (l < r) {
swap(s, l, r);
l ++;
r --;
}
}
public void swap(char[] s, int i, int j) {
if (i == j) return ; // 如果没有这行当交换相同元素时结果会是0
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
题意:给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符.
如果剩余字符少于 k 个,则将剩余字符全部反转.
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样.
示例
输入: s = "abcdefg", k = 2 输出: "bacdfeg" 。
本题逻辑并不能,但是存在多种情况,导致在编写代码的可能有多个if-else,并且对某个特点的情况存在遗漏.
为了解决这个问题,我们可以每次移动2k个区间,如何判断是否有要翻转的区间.
class Solution {
public String reverseStr(String s, int k) {
char[] ca = s.toCharArray();
int n = ca.length;
for (int i = 0; i < n; i += 2 * k) {
if (i + k <= n) { // 剩余区间大于等于k
reverse(ca, i, i + k - 1);
continue;
}
reverse(ca, i, n - 1); // 剩余区间小于k
}
return new String(ca);
}
public void reverse(char[] s, int start, int end) {
for (int i = start, j = end; i < j; i ++, j --) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
题意:请实现一个函数,把字符串 s 中的每个空格替换成"%20".
示例 1: 输入:s = "We are happy." 输出:"We%20are%20happy." 。
如果不限制使用 O(1) 的空间,我们可以直接使用一个StringBuilder进行操作,这样的代码不能直接写成,在此我们继续讨论限制 O(1) 的空间复杂度进行操作.
我们可以先对字符串进行扩充,然后从后向前遍历。我们不在前面进行扩充的原因:如果在前面扩充,如果我们要添加一个元素,就得把一个元素往后移动,这样我们每次操作的时间复杂度就为 O(n2) 。
其实很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。 ——代码随想录 。
我们设置两个指针一个i指向原字符串的末尾,一个j指向扩充后的末尾,如果此时 s[i] != ' ' ,我们把 s[j] = s[i] 。反之我们把空格替换为 %20 ,j再往后移动2位.
class Solution {
public String replaceSpace(String s) {
if (s == null || s.length() == 0) return s; // 空字符串跳过
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ++ ) {
if (s.charAt(i) == ' ')
sb.append(" ");
}
if (sb.length() == 0) return s; // 没有空格
int oldSize = s.length();
s += sb.toString();
int newSize = s.length();
char[] ca = s.toCharArray();
for (int i = oldSize - 1, j = newSize - 1; i < j; i --, j --) {
if (ca[i] != ' ') {
ca[j] = ca[i];
} else {
ca[j] = '0';
ca[j - 1] = '2';
ca[j - 2] = '%';
j -= 2;
}
}
return new String(ca);
}
}
题意:给定一个字符串,逐个翻转字符串中的每个单词.
示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 。
示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括.
示例 3: 输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个.
在之前,我们已经通过自己实现的 reverse() 对字符串进行了翻转,本题在之前翻转字符串的问题的基础上进行了扩展,我们要去掉字符串前后多余的空格和单词之前多余的空格.
值得注意的是,每个单词之间必须保留一个空格。然后在此基础上我们先翻转整个字符串,再翻转每个单词即可.
本题的重难点其实不在翻转,而是在去除空格。我们采用与之前“移除元素”那题的逻辑书写一个函数去除空格.
public char[] removeExtraSpaces(char[] s) {
int slow = 0; // 表示处理完的字符串的末尾
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一个单词就先在前面加一个空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow); // 重设大小后拷贝
return newChars;
}
class Solution {
public String reverseWords(String s) {
char[] ca = s.toCharArray();
ca = removeExtraSpaces(ca);
reverse(ca, 0, ca.length - 1);
for (int i = 0, j = 0; i <= ca.length; i ++ ) {
if (i == ca.length || ca[i] == ' ') { // 先特判最后一个单词
reverse(ca, j , i - 1);
j = i + 1; // j重新指向下一个单词的开头
}
}
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
public char[] removeExtraSpaces(char[] s) {
int slow = 0;
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一个单词就先在前面加一个空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow);
return newChars;
}
}
题意:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab".
示例 1: 输入: s = "abcdefg", k = 2 输出: "cdefgab" 。
示例 2: 输入: s = "lrloseumgh", k = 6 输出: "umghlrlose" 。
限制: 1 <= k < s.length <= 10000 。
在本题中我们还是利用整体-局部翻转的方法来实现左旋转字符串的操作,通过简单的模拟我们不难得出:我们可以先翻转前k个字符串,再翻转剩下的字符,最后整体翻转即可实现左旋转的效果.
class Solution {
public String reverseLeftWords(String s, int n) {
char[] ca = s.toCharArray();
reverse(ca, 0, n - 1);
reverse(ca, n, ca.length - 1);
reverse(ca, 0, ca.length - 1);
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
}
题意:给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1.
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2 。
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1 。
说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符.
本题是一道经典的KMP,KMP是为了快速找到一个字符串是否是另一个字符串的子串。为了实现KMP算法,我们必须要求一个前缀表,即next数组.
最后此篇关于代码随想录-day3的文章就讲到这里了,如果你想了解更多关于代码随想录-day3的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我试图查看当天的车辆销量,并创建另外两个列来告诉我过去 10 天的销量和过去 20 天的销量。同一天和同一辆车可能有多个销售。我的目标是获取不同的车辆和日期并查看他们的销售数量。 N 天计数应与该行中
我需要每天 12 小时在 azure 上使用 VM,在 EOD 时关闭并在第二天早上再次启动。我习惯使用 WASABi block 进行自动缩放。 What strategy should I use
我只需要显示天/天的后缀,我该如何实现?它不起作用: java.lang.IllegalStateException: No field to apply suffix to.. privat
尝试使用 HTML 表单和 PHP 更新数据库字段时出现上述错误消息。不确定我的代码有什么问题(我知道它不安全,我只是将它用于个人用途)。我已经检查过,数据库 days 确实存在。 HTML:
谷歌搜索这个,但找不到答案。想知道这两个脚本是否有区别? +3 天: echo date( 'd.m.Y H:i:s', strtotime( '+3 day' ) ); +3 天: echo dat
我试图在某一天显示文本“A Day”,然后在第二天显示“B Day”。我可以使用偶数或奇数函数来执行此操作,然后配置 getDay 对象,但我尝试执行此操作,无论日、月或年如何。 例如,今天可能是“A
在 stack-overflow 中,有一个名为“爱好者”的徽章,通过“连续 30 天每天访问该网站”获得 如何在sql server中编写这个查询? 最佳答案 创建一个表 Id, LastVisit
$('') .attr('label', day) .attr('value', day) if(myDate.getDate(
如果我使用这个函数 pd.DatetimeIndex(dfTrain['datetime']).weekday 我得到了日期,但是我找不到任何给出日期名称的函数...所以我需要将 0 转换为星期一,将
I know I can use relativedelta to calculate difference between two dates in the calendar. However
我正在使用 DayPickerInput,我将其设置为 this (具有 2 天选择器输入的范围)。我想始终显示覆盖,我不想隐藏它。我知道 showOverlay Prop ,但它只在初始渲染期间显示
如何将类添加到 react-day-picker 的今天按钮? 从文档中似乎是可能的: http://react-day-picker.js.org/api/DayPicker#classNames
我需要将一个简单的“3.days”字符串转换为在屏幕上打印“3 days”的内容,该字符串将根据语言使用适当的语言环境来打印单词。 我想可能有一种我似乎找不到的在 Rails 上执行此操作的简单方法。
我想从 Github API GET,每天的贡献数。我正在制作一个网络应用程序,将 github 贡献的数量与我玩的 Dota 2 比赛的数量进行比较。 这张图应该能更清楚地说明事情。 http://
我想在一个月的第三天和最后一天运行一项作业。 下面的 cron 表达式正确吗? “0 0 3 3,L * * ?” 当我在 www.cronmaker.com 中尝试它时,它说这是一个无效的表达式。
我正在尝试为图像中的特定事件设置重复提醒。代码工作正常,但发生了一些正在改变创建事件的事情。请检查以下详细信息。 如果我尝试从循环中设置提醒,它会起作用,但如果重复出现,就会出现上述问题。 检查图像上
我知道新的一天(或小时/分钟,就此而言)没有事件监听器。但在我的 Chrome 扩展程序中,我需要知道新的一天何时开始,这意味着我必须使用 setInterval 函数来确定一天何时发生变化。但是,我
我有一个名为 stockins 的 table 和一个 column stock。因为我想在一周的第一天和一周的最后一天之间找到 max(stock)。 为此,我使用以下查询 select max(s
我们如何将 t.integer :missed 与 t.text :committed 集成,以便 当用户在 :level 中检查他 :missed 3 :committed 天时,他必须重新启动 :
我是一名优秀的程序员,十分优秀!