leetcode-392. 判断子序列
判断子序列给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
两个字符串都只由小写字符组成。
进阶:
如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
方法一用双指针非常容易想到
1234567891011class Solution {public: bool isSubsequence(string s, string t) { int i=0,j=0; while(i<s.size()&&j<t.size()){ if(s[i]==t[j]) i++; j++; } ...
leetcode-125. 验证回文串
验证回文串如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。
示例 1:
123输入: s = "A man, a plan, a canal: Panama"输出:true解释:"amanaplanacanalpanama" 是回文串。
示例 2:
123输入:s = "race a car"输出:false解释:"raceacar" 不是回文串。
示例 3:
1234输入:s = " "输出:true解释:在移除非字母数字字符之后,s 是一个空字符串 "" 。由于空字符串正着反着读都一样,所以是回文串。
题目很简单,主要考察了API的使用。
方法一1234567891011121314class Solution {public: bool isPa ...
leetcode-2864. 最大二进制奇数
最大二进制奇数给你一个 二进制 字符串 s ,其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位,使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式,表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
示例 1:
123输入:s = "010"输出:"001"解释:因为字符串 s 中仅有一个 '1' ,其必须出现在最后一位上。所以答案是 "001" 。
示例 2:
123输入:s = "0101"输出:"1001"解释:其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
题目很简单,先数出字符串中1的个数count,把1个1放在最后,其余count-1个1放在最前面。
这是我写的
1234567891011121314151617class ...
leetcode-28. 找出字符串中第一个匹配项的下标
找出字符串中第一个匹配项的下标给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
1234输入:haystack = "sadbutsad", needle = "sad"输出:0解释:"sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
123输入:haystack = "leetcode", needle = "leeto"输出:-1解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
方法一 暴力法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class ...
leetcode-6. Z 字形变换
Z字形变换将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
123P A H NA P L S I I GY I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数:
1string convert(string s, int numRows);
示例 1:
12输入:s = "PAYPALISHIRING", numRows = 3输出:"PAHNAPLSIIGYIR"
示例 2:
1234567输入:s = "PAYPALISHIRING", numRows = 4输出:"PINALSIGYAHRPI"解释:P I NA L S I GY A H RP I
示例 3:
12输入:s = ...
acwing-高精度加法
高精度加法给定两个正整数(不含前导 0),计算它们的和。
输入格式给定两个正整数(不含前导 00),计算它们的和。
输出格式共一行,包含所求的和。
数据范围1≤整数长度≤100000
这个算法用来计算大数之间的加法。
例:计算 567+28
用 a, b 两个字符串存储输入。a = 567, b = 28
为了将个位对齐,两个加数需要倒序存放在 A, B 两个整数数组中。 A = [7, 6, 5], B = [8, 2]
新建整数数组 C 保存结果,整型变量 t 保存进位,初始 t = 0.
将各个位上的数字相加,求出结果对应位上的数字和进位。
例如对个位计算: A[0] + B[0] = 7 + 8 = 15, 结果个位上是 5, 进位是 1. 所以C[0] = 5, 进位t = 1
最后把结果数组 C 中就保存了计算倒序结果,倒序输出就是答案
12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<vector ...
leetcode-151. 反转字符串中的单词
反转字符串中的单词给你一个字符串 s ,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
示例 1:
12输入:s = "the sky is blue"输出:"blue is sky the"
示例 2:
123输入:s = " hello world "输出:"world hello"解释:反转后的字符串中不能存在前导空格和尾随空格。
示例 3:
123输入:s = "a good example"输出:"example good a"解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
这道题的关键就是去掉多余的空格。用双指针找出每个单词就可 ...
leetcode-14. 最长公共前缀
最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
12输入:strs = ["flower","flow","flight"]输出:"fl"
示例 2:
123输入:strs = ["dog","racecar","car"]输出:""解释:输入不存在公共前缀。
以第一个字符串strs[0]为基准,逐个字符与其他字符串比较,直到找到不匹配的字符为止。
设置两层循环,第一层循环strs[0]的长度,第二层循环每一个字符串。
12345678910111213141516class Solution {public: string longestCommonPrefix(vector<string>& strs) { int n=strs.size(); if(!n) r ...
leetcode-58. 最后一个单词的长度
最后一个单词的长度给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串
示例 1:
123输入:s = "Hello World"输出:5解释:最后一个单词是“World”,长度为5。
非常简单。倒序处理,注意最后的空格
12345678910111213class Solution {public: int lengthOfLastWord(string s) { int n=s.size()-1; int ans=0; while(s[n]==' ') n--; while(n>=0&&s[n]!=' '){ //第一次把n>=0这个判断条件放在&&后边导致报错,一定注意。 ans++; n--; } ...
leetcode-12. 整数转罗马数字
整数转罗马数字罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表 ...