找特殊情况，分类讨论：三种情况
1）两个字符串的长度之差 大于1 直接返回false；
2）长度之差等于1， 判断长的字符串删掉不一样的字符，剩余的字符串是否相同；
3）长度之差等于0，判断不相同的字符个数，若超过一个返回false。
class Solution {
public:
/**
* @param s: a string
* @param t: a string
* @return: true if they are both one edit distance apart or false
*/
bool isOneEditDistance(string &s, string &t) {
// write your code here
if(s.size() > t.size())
swap(s, t); //保证t比s长
int diff = t.size() - s.size();
if(diff > 1)
return false;
if(diff == 1){
for(int i=0; i<s.size(); i++){
if(t[i] != s[i])
return (s.substr(i) == t.substr(i+1)); //t去掉索引为i的字符之后剩余的子串和s是否相同
}
return true;
}
if(diff == 0){
int cnt = 0;
for(int i=0; i<s.size(); i++){
if(s[i] != t[i])
cnt ++;
}
return (cnt==1);
}
}
};
题意：API ：int read4(char *buf) 每次读4个字符，想要实现read函数每次能读入任意字符。
ptr 是读入字符串的指针，bufferPtr是指向buffer队列的头指针，bufferCnt 是指向buffer队列的尾指针。
// Forward declaration of the read4 API.
int read4(char *buf); //return the actual number of characters read
class Solution {
public:
/**
* @param buf destination buffer
* @param n maximum number of characters to read
* @return the number of characters read
*/
char buffer[4];
int bufferPtr = 0, bufferCnt = 0; //队列的头指针和尾指针
int read(char *buf, int n) {
// Write your code here
int ptr = 0;
while(ptr < n){
if(bufferPtr == bufferCnt){
//队列为空,进队
bufferCnt = read4(buffer);
bufferPtr = 0;
}
if(bufferCnt == 0) //没有数据读入就退出
break;
while(ptr < n && bufferPtr < bufferCnt){
buf[ptr] = buffer[bufferPtr];
ptr++;
bufferPtr++;
}
}
return ptr;
}
};
class Solution {
public:
/*
* @param strs: a list of strings
* @return: encodes a list of strings to a single string.
*/
string encode(vector<string> &strs) {
// write your code here
string ans;
for(int i=0; i<strs.size(); i++){
string s = strs[i];
for(int j = 0; j<s.size(); j++){
if(s[j] == ':')
ans += "::"; //加一个转义符,把所有的：变为：：
else
ans += s[j];
}
ans += ":;"; //一个字符串结束后加上分隔符
}
return ans;
}
/*
* @param str: A string
* @return: dcodes a single string to a list of strings
*/
vector<string> decode(string &str) {
// write your code here
vector<string> ans;
string item;
int i = 0;
while(i<str.size()){
if(str[i] == ':'){
if(str[i+1] == ';'){
// ; 为分隔符
ans.push_back(item);
item = "";
i += 2;
}
else{
// ：为转义符
item += str[i+1];
i += 2;
}
}
else{
item += str[i];
i++;
}
}
return ans;
}
};
leetcode 388 & lintcode 643
class Solution {
public:
vector<string> split(string& str, char c){
char *cstr, *p;
vector<string> ret;
cstr = new char[str.size() + 1];
strcpy(cstr, str.c_str()); //将str拷贝给cstr
p = strtok(cstr, &c); //将cstr指向的字符数组以c来分割
while(p!=NULL){
ret.push_back(p);
p = strtok(NULL, &c);
}
return ret;
}
int lengthLongestPath(string input) {
int ans = 0;
vector<string> lines = split(input, '\n'); //用\n来分隔字符串
map<int, int> level_size;
level_size[-1] = 0; // 初始化在第0层
for(int i=0; i<lines.size(); i++){
string line = lines[i];
int level = line.find_last_of('\t') + 1;
// 查找字符串中最后一个出现\t。有匹配，则返回匹配位置；否则返回-1.
int len = (line.substr(level)).size(); //第level层字符串的长度
if(line.find('.') != string::npos){ //if(s.find('.') != -1)
//找到. 说明是文件
ans = max(ans, level_size[level - 1] + len);
}
else{
//每一行要加/ 故+1
level_size[level] = level_size[level - 1] + len + 1; //前缀和优化
}
}
return ans;
}
};
题意：party上有n个人，从0到n编号。存在一个名人，其余的n-1个人都认识他，但是他不认识这n-1个人。现在你要用最少的次数找到谁是这个名人。
要求在O(n)的时间内写出来。
思路：有大量的冗余。
若对1做名人检验：2，3，4认识1；而5 不认识1。
说明 1 不是名人，且 2，3，4也不会是名人。
即两个人中，总有一个人被去掉：若1和2 ，2认识1 说明2不是名人；若1和3，3不认识1 说明1不是名人。
// Forward declaration of the knows API.
bool knows(int a, int b); //return whether A knows B
//if true, A is not celebrity
//if false, B is not celebrity
class Solution {
public:
/**
* @param n a party with n people
* @return the celebrity's label or -1
*/
int findCelebrity(int n) {
// Write your code here
int ans = 0;
for(int i=1; i<n; i++){
if(knows(ans, i))
//第0个人认识第i个人说明第0个人不是celebri
ans = i; //每次去掉一个人
//最终得到一个人
}
//对上面最后剩下的人做一次名人检验
for(int i=0; i<n; i++){
if(ans!=i && knows(ans, i))
return -1;
if(ans != i && !knows(i, ans))
return -1;
}
return ans;
}
};
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> mp = {{'I',1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int r = mp[s[0]];
for(int i=1; i<s.size(); i++){
r += mp[s[i]];
if(mp[s[i-1]] < mp[s[i]])
r = r - 2*mp[s[i-1]];
}
return r;
}
};
class Solution {
public:
int romanToInt(string s) {
unordered_map<string, int> mp = {{"I",1}, {"V", 5}, {"X", 10}, {"L", 50}, {"C", 100}, {"D", 500}, {"M", 1000}};
int r = mp[s.substr(0, 1)];
for(int i=1; i<s.size(); i++){
r += mp[s.substr(i, 1)];
if(mp[s.substr(i-1, 1)] < mp[s.substr(i, 1)])
r -= 2*mp[s.substr(i-1, 1)];
}
return r;
}
};
class Solution {
public:
string intToRoman(int num) {
vector<int> value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,4,1};
vector<string> roman = {"M", "CM", "D","CD","C","XC","L","XL","X","IX","V","IV",
"I"};
string str;
int i = 0;
while(i<value.size()){
if(num >= value[i]){
num -= value[i];
str += roman[i];
}
else
i++;
}
return str;
}
};