Leetcode 题解 - 字符串

字符串循环移位包含

编程之美 3.1

s1 = AABCD, s2 = CDAA
Return : true

给定两个字符串 s1 和 s2,要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含。

s1 进行循环移位的结果是 s1s1 的子字符串,因此只要判断 s2 是否是 s1s1 的子字符串即可。

字符串循环移位

编程之美 2.17

s = "abcd123" k = 3
Return "123abcd"

将字符串向右循环移动 k 位。

将 abcd123 中的 abcd 和 123 单独翻转,得到 dcba321,然后对整个字符串进行翻转,得到 123abcd。

字符串中单词的翻转

程序员代码面试指南

s = "I am a student"
Return "student a am I"

将每个单词翻转,然后将整个字符串翻转。

两个字符串包含的字符是否完全相同

242. Valid Anagram (Easy)

s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

可以用 HashMap 来映射字符与出现次数,然后比较两个字符串出现的字符数量是否相同。

由于本题的字符串只包含 26 个小写字符,因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计,不再使用 HashMap。

public boolean isAnagram(String s, String t) {
    int[] cnts = new int[26];
    for (char c : s.toCharArray()) {
        cnts[c - 'a']++;
    }
    for (char c : t.toCharArray()) {
        cnts[c - 'a']--;
    }
    for (int cnt : cnts) {
        if (cnt != 0) {
            return false;
        }
    }
    return true;
}

计算一组字符集合可以组成的回文字符串的最大长度

409. Longest Palindrome (Easy)

Input : "abccccdd"
Output : 7
Explanation : One longest palindrome that can be built is "dccaccd", whose length is 7.

使用长度为 256 的整型数组来统计每个字符出现的个数,每个字符有偶数个可以用来构成回文字符串。

因为回文字符串最中间的那个字符可以单独出现,所以如果有单独的字符就把它放到最中间。

public int longestPalindrome(String s) {
    int[] cnts = new int[256];
    for (char c : s.toCharArray()) {
        cnts[c]++;
    }
    int palindrome = 0;
    for (int cnt : cnts) {
        palindrome += (cnt / 2) * 2;
    }
    if (palindrome < s.length()) {
        palindrome++;   // 这个条件下 s 中一定有单个未使用的字符存在,可以把这个字符放到回文的最中间
    }
    return palindrome;
}

字符串同构

205. Isomorphic Strings (Easy)

Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

记录一个字符上次出现的位置,如果两个字符串中的字符上次出现的位置一样,那么就属于同构。

public boolean isIsomorphic(String s, String t) {
    int[] preIndexOfS = new int[256];
    int[] preIndexOfT = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char sc = s.charAt(i), tc = t.charAt(i);
        if (preIndexOfS[sc] != preIndexOfT[tc]) {
            return false;
        }
        preIndexOfS[sc] = i + 1;
        preIndexOfT[tc] = i + 1;
    }
    return true;
}

回文子字符串个数

647. Palindromic Substrings (Medium)

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

从字符串的某一位开始,尝试着去扩展子字符串。

private int cnt = 0;

public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        extendSubstrings(s, i, i);     // 奇数长度
        extendSubstrings(s, i, i + 1); // 偶数长度
    }
    return cnt;
}

private void extendSubstrings(String s, int start, int end) {
    while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        start--;
        end++;
        cnt++;
    }
}

判断一个整数是否是回文数

9. Palindrome Number (Easy)

要求不能使用额外空间,也就不能将整数转换为字符串进行判断。

将整数分成左右两部分,右边那部分需要转置,然后判断这两部分是否相等。

public boolean isPalindrome(int x) {
    if (x == 0) {
        return true;
    }
    if (x < 0 || x % 10 == 0) {
        return false;
    }
    int right = 0;
    while (x > right) {
        right = right * 10 + x % 10;
        x /= 10;
    }
    return x == right || x == right / 10;
}

统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数

696. Count Binary Substrings (Easy)

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
public int countBinarySubstrings(String s) {
    int preLen = 0, curLen = 1, count = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            curLen++;
        } else {
            preLen = curLen;
            curLen = 1;
        }

        if (preLen >= curLen) {
            count++;
        }
    }
    return count;
}

热门文章

暂无图片
编程学习 ·

sqlserver:临时表的删除

遇到一个坑: 某天,定时作业失败了多次,但代码没变动,这就奇了怪了。。 结果:经检查,每次执行的时候,临时表若存在,就会失败。 分析:当初不写删除临时表,是查询了临时表的定义,会话内自动结束,不知道是哪出现了问题。 解决: if OBJECT_ID(tempdb..#tempList) is no…
暂无图片
编程学习 ·

Unity的学习(二):打砖块

一、新建项目创建成功后,进入了如下界面。二、场景的设计 在Hierarchy中鼠标右键创建Plane(地面)游戏物体,将其Transform组件重置,并将游戏物体重命名为Ground,如下图所示。调整地面的大小。在Assets下创建文件夹Materials,并在其中创建Ground的Material(材质)并在Gro…
暂无图片
编程学习 ·

【Android 内存优化】Bitmap 图像尺寸缩小 ( 考虑像素密度、针对从不同像素密度资源中解码对应的 Bitmap 对象 | inDensity | inTargetDensity )

文章目录一、像素密度对解码图片的影响二、不考虑像素密度会导致图片缩小尺寸不准确三、DisplayMetrics 源码阅读、研究手机资源获取规则四、像素密度参数设置取值 ( inDensity | inTargetDensity | setDensity )五、inDensity 与 inTargetDensity 设置六、新的图片缩小工具类代…
暂无图片
编程学习 ·

Vue&Element

Vue&Element Vue 快速入门 Vue 介绍Vue 是一套构建用户界面的渐进式前端框架。 只关注视图层,并且非常容易学习,还可以很方便的与其它库或已有项目整合。 通过尽可能简单的 API 来实现响应数据的绑定和组合的视图组件。 特点 易用:在有 HTML CSS JavaScript 的基础上,快…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

RS知识总结

1.静态路由相关&#xff1a; 静态路由的4个高级特性 TCP协议的三次握手和四次分手 2.RIP相关&#xff1a; RIP13个高级特性 RIP路由协议详解——计时器 3.EIGRP相关&#xff1a; EIGRP高级特性(汇总&#xff0c;偏移列表&#xff0c;SIA&#xff0c;Stub) EIGRP特性 4.OSPF相…
暂无图片
郑州普通话 ·

android音视频何俊林,最新大厂Android社招面试经验汇总

实习生: 对于实习生而言的话,可能对于android方面的要求并不是特别的高,比较注重基础,但是基本的得会,比如: 1.四大组件基本的概念以及使用。2.activity的生命周期流程,这是最基本的,但是你得清楚到底是啥时候调用各个方法,如一个页面(A)当前正在跟用户交互,弹出一个…
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…