Vodka编程菜菜

NYU + Gatech

class Solution {
public:
int length_valid_palindrome(string s, int l, int r){
while(l>=0 && r<=s.size()-1 && s[l] == s[r]){
l--;
r++;
}
return r-l-1;
}

string longestPalindrome(string s) {
if(s.size()<=1) return s;
string res = "";
for(int i = 0;i < s.size()-1; ++i){
int odd_case = length_valid_palindrome(s,i,i);
if(odd_case> res.size()){
res = s.substr(i-odd_case/2, odd_case);
}
int even_case = length_valid_palindrome(s,i,i+1);

if(even_case> res.size()){
res = s.substr(i-even_case/2+1, even_case);
}
}
return res;
}
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()<=1) return s.size();
int l = 0;
unordered_map<char, int> chr_count;
int res = -1;
for(int r = 0; r < s.size(); ++r) {
chr_count[s[r]]++;
while(chr_count[s[r]]>1) {
chr_count[s[l]]--;
l++;
}
res = max(res, r-l+1);
}
return res;
}
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* res = new ListNode(0);
ListNode* dummy = res;
int carry = 0;
while(l1 || l2) {
int l1_val = l1 ? l1->val : 0;
int l2_val = l2 ? l2->val : 0;
int tmp = l1_val + l2_val + carry;
carry = tmp /10;
dummy->next = new ListNode( tmp%10);
dummy = dummy->next;
// note here
if(l1) l1  = l1->next;
if(l2) l2  = l2->next;
}
if (carry) dummy->next = new ListNode(carry);
return res->next;

}
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
if(nums.size()<=1) return {-1,-1};
unordered_map<int,int> val_idx;
for(int i = 0; i < nums.size(); ++i) {
int another_num = target-nums[i];
if(val_idx.count(another_num)) return {val_idx[another_num], i};
else val_idx.emplace(nums[i], i);
}
return {-1,-1};

}
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Description

English

l1代表第一个矩形的左上角
r1代表第一个矩形的右下角
l2代表第二个矩形的左上角
r2代表第二个矩形的右下角

Have you met this question in a real interview?
Example

/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/

class Solution {
public:
/**
* @param l1: top-left coordinate of first rectangle
* @param r1: bottom-right coordinate of first rectangle
* @param l2: top-left coordinate of second rectangle
* @param r2: bottom-right coordinate of second rectangle
* @return: true if they are overlap or false
*/
bool doOverlap(Point &l1, Point &r1, Point &l2, Point &r2) {
//派出不相交的情况

return !((l2.x>r1.x) ||(r1.y>l2.y) ||(r2.x<l1.x) ||(l1.y<r2.y));
}
};


1. 日志排序
中文English
给定一个字符串列表 logs, 其中每个元素代表一行日志. 每行日志信息由第一个空格分隔成两部分, 前面是这一行日志的 ID, 后面是日志的内容(日志的内容中可能包含空格). 一条日志的内容要么全部由字母和空格组成, 要么全部由数字和空格组成.

Example

logs = [
“zo4 4 7”,
“a100 Act zoo”,
“a1 9 2 3 1”,
“g9 act car”
]

[
“a100 Act zoo”,
“g9 act car”,
“zo4 4 7”,
“a1 9 2 3 1”
]

logs = [
“zo4 4 7”,
“a100 Actzoo”,
“a100 Act zoo”,
“Tac Bctzoo”,
“Tab Bctzoo”,
“g9 act car”
]

[
“a100 Act zoo”,
“a100 Actzoo”,
“Tab Bctzoo”,
“Tac Bctzoo”,
“g9 act car”,
“zo4 4 7”
]

Notice

class Solution {
public:
/**
* @param logs: the logs
* @return: the log after sorting
*/
bool all_num(string& str){
//cout << str  << endl;
for(auto chr : str){
if(chr<'0' || chr>'9') return false;
}
return true;
}

bool is_num_content(string& str) {
stringstream ss(str);
int cnt = 0;
string token;
while(getline(ss, token, ' ')){
if(cnt>0 && all_num(token)) return true;
else if(cnt>0) return false;
cnt++;
}
return false;
}

int get_pos(const string& str){
for(int i=0; i < str.size(); ++i){
if(str[i]==' ') return i+1;
}
return -1;
}

vector<string> logSort(vector<string> &logs) {

vector<string> num_content;
vector<string> str_content;
for(auto& str : logs){
if(is_num_content(str)) {
num_content.emplace_back(str);
}else{
str_content.emplace_back(str);
}
}
//note lambda expression should capture this, when use public function inside the class.
sort(str_content.begin(), str_content.end(),[this](const string& str1, const string& str2){
int pos1=get_pos(str1), pos2 = get_pos(str2);
if(str1.substr(pos1) == str2.substr(pos2)) return str1 < str2;
return str1.substr(pos1) < str2.substr(pos2);
});
for(auto item : num_content){
str_content.emplace_back(item);
}
return str_content;
}
};



#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

const int N =1E4+5;
vector<int> f(N,-1);

int sg(int x, vector<int>& s) {
if(f[x]!=-1) return f[x];
unordered_set<int> included;
for(auto item : s){
if(x>=item) included.emplace(sg(x-item, s));
}

for(int i=0;;++i){
if(!included.count(i)) return f[x]=i;
}

}

int main(){

int k;
cin >> k;
vector<int> s(k,0);
for(int i=0; i <k; ++i) cin >> s[i];
int n;
cin >> n;
int res =0;
for(int i=0; i <n; ++i){
int x;
cin >> x;
res ^= sg(x, s);
}
if(res) cout << "Yes" << endl;
else cout << "No" <<endl;

return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


#include<iostream>
using namespace std;

int main(){
int n;
cin >> n;
int res =0;
for(int i =1; i <=n; ++i){
int num;
cin >> num;
if(i%2) res ^= num;
}
if(res) cout <<"Yes" << endl;
else cout <<"No"<<endl;

return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


#include<iostream>
using namespace std;

int main(){
int n ;
cin >> n;
int res = 0;
for(int i=0; i < n; ++i){
int num;
cin >> num;
res ^= num;
}
if(res) cout << "Yes" <<endl;
else cout << "No"<<endl;

return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


#include<iostream>
#include<vector>
using namespace std;
using LL = long long;

int main(){
int n ,m;
cin>>n>>m;
vector<int> p(m,0);
for(int i =0; i < m; ++i) {
cin >> p[i];
}
int res = 0;
// use bit to show whether relevant index is selected.
for(int i=1; i < 1<<m; ++i) {
int t=1, cnt =0;
for(int j=0; j < m; ++j) {
if(i>>j & 1){
cnt ++;
if((LL)t*p[j]>n){
t = -1;//mark as failed
break;
}
t *= p[j];
}
}

if(t != -1){
if(cnt %2) res += n/ t;
else res -= n/t;

}

}
cout << res<< endl;

return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~