Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn’t contain any leading zero.
把两个二进制字符串相加，注意进位即可。 把while (i >= 0 && j >= 0)改成while (i >= 0 || j >= 0)，这样就只需要一个while循环了，只不过循环体里面求sum需要判断一下i,j。完整代码如下：
class Solution {
public:
string addBinary(string a, string b)
{
int i = a.size() – 1, j = b.size() – 1;
string ans = "";
bool carry = false;
while (i >= 0 || j >= 0) {
int sum = (i >= 0 ? (a[i] – ‘0’) : 0) + (j >= 0 ? (b[j] – ‘0’) : 0);
sum += carry ? 1 : 0;
if (sum >= 2) {
ans.push_back(sum – 2 + ‘0’);
carry = true;
}
else {
ans.push_back(‘0’ + sum);
carry = false;
}
i–;
j–;
}
if (carry)
ans.push_back(‘1’);
reverse(ans.begin(), ans.end());
return ans;
}
};
本代码提交AC，用时3MS。
二刷。更简洁的代码：
class Solution {
public:
string addBinary(string a, string b) {
int m = a.size(), n = b.size();
string ans = "";
int i = m - 1, j = n - 1;
int carry = 0;
while (i >= 0 || j >= 0) {
int u = i >= 0 ? a[i] - '0' : 0;
int v = j >= 0 ? b[j] - '0' : 0;
int sum = u + v + carry;
carry = sum / 2;
ans.push_back('0' + (sum % 2));
--i;
--j;
}
if (carry != 0)ans.push_back('1');
reverse(ans.begin(), ans.end());
return ans;
}
};
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.
If the last word does not exist, return 0.
Note: A word is defined as a maximal substring consisting of non-space characters only.
Example:
Input: "Hello World"
Output: 5
本题要求一个字符串中最后一个单词的长度，比如”Hello World”，则返回5。需要注意结尾包含空格的情况，比如”Hello World “，还是要返回5。所以需要先删除尾部空格，然后再从后往前查找第一个空格，返回空格到结尾的长度。 完整代码如下：
class Solution {
public:
int lengthOfLastWord(string s)
{
int e = s.size() – 1;
while (e >= 0 && s[e] == ‘ ‘) {
e–;
}
if (e < s.size() – 1) {
s = s.substr(0, e + 1);
}
size_t tPos = s.find_last_of(‘ ‘);
if (tPos == string::npos)
return s.size();
return s.size() – tPos – 1;
}
};
本代码提交AC，用时4MS。
二刷。上述代码也过于复杂，还有字符串的substr，下面是更简洁的版本：
class Solution {
public:
int lengthOfLastWord(string s)
{
int i = s.size() – 1;
while (i >= 0 && s[i] == ‘ ‘)
–i;
if (i < 0)
return 0;
int j = i – 1;
while (j >= 0 && s[j] != ‘ ‘)
–j;
return i – j;
}
};
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int ans = 0;
stack<int> stk;
stk.push(-1);
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
stk.push(i);
}
else {
if (!stk.empty())stk.pop();
if (stk.empty()) {
stk.push(i);
}
else {
ans = max(ans, i - stk.top());
}
}
}
return ans;
}
};
$$next[j]=\begin{cases} \max\{k|0<k<j|t_0t_1…t_{k-1}==t_{j-k}t_{j-k+1}…t_{j-1}\}, & \mbox{if this set is nonempty}\\-1, & \mbox{if }j==0\\ 0, & \mbox{otherwise}\end{cases}$$
hihoCoder week 84-1-Lucky Substrings
题目1 : Lucky Substrings
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters, output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once.
输入
A string consisting no more than 100 lower case letters.
输出
Output the lucky substrings in lexicographical order, one per line. Same substrings should be printed once.
样例输入
aabcd
样例输出
a
aa
aab
aabc
ab
abc
b
bc
bcd
c
cd
d
如果一个字符串中不同字母的个数是斐波那契数，则称这个字符串是Lucky的，问字符串S中哪些子串是Lucky子串。
要正确理解Lucky的定义，是不同字母的个数，而不是不同字母的个数序列。比如aabc是Lucky的，因为其有a,b,c共3种字母，而3在斐波那契数列中，所以aabc是Lucky的。不能理解为aabc中a出现2次，b,c分别出现1次，构成1,1,3是斐波那契数列，所以aabc是Lucky的。
所以只能枚举所有子串，判断每个子串是否为Lucky的。如果知道了S[i,…,j]中不同字母的个数，判断S[i,…,j+1]时，只要判断S[j+1]这个字母是否在之前出现过。所以通过保存之前不同字母的个数，可以快速判断S[i,…,j+1]的情况。
完整代码如下：
[cpp]
#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
set<int> FIB_NUM = { 1,2,3,5,8,13,21 };
int main() {
string s;
cin >> s;
set<string> ans;
int n = s.size();
for (int i = 0; i < n; i++) {
vector<bool> alphabet(26, false);
int cnt = 0;
for (int j = i; j < n; j++) {
if (!alphabet[s[j] – ‘a’]) {
alphabet[s[j] – ‘a’] = true;
cnt++;
}
if (FIB_NUM.find(cnt) != FIB_NUM.end()) {
ans.insert(s.substr(i, j – i + 1));
}
}
}
set<string>::iterator it = ans.begin();
while (it != ans.end()) {
cout << *it << endl;
it++;
}
return 0;
}
[/cpp]
本代码提交AC，用时17MS，内存0MB。]]>
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
SymbolValue
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: "III"
Output: 3
Example 2:
Input: "IV"
Output: 4
Example 3:
Input: "IX"
Output: 9
Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
It’s guaranteed the answer fits on a 32-bit signed integer.
Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
map<char, int> visited;
int ans = 0, start = -1;
for (int i = 0; i < s.size(); ++i) {
if (visited.find(s[i]) != visited.end())
start = max(start, visited[s[i]]);
visited[s[i]] = i;
ans = max(ans, i – start);
}
return ans;
}
};
