头像

Vodka编程菜菜

NYU + Gatech


访客:6569

离线:2天前


活动打卡代码 LeetCode 5. 最长回文子串

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;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2. 两数相加

/**
 * Definition for singly-linked list.
 * 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;

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


活动打卡代码 LeetCode 1. 两数之和

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代表第二个矩形的右下角

保证:l1 != r1 并且 l2 != r2

Have you met this question in a real interview?
Example
样例 1:

输入 : l1 = [0, 8], r1 = [8, 0], l2 = [6, 6], r2 = [10, 0]
输出 : true
样例 2:

输入 : [0, 8], r1 = [8, 0], l2 = [9, 6], r2 = [10, 0]
输出 : false


解题的核心是排除所有不相交的情况。

/**
 * 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) {
        // write your code here
        //派出不相交的情况

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



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

现在你需要按照如下规则对列表中的所有日志进行排序:

内容为字母的日志应该排在内容为数字的日志之前
内容为字母的日志, 按照内容的字典序排序, 当内容相同时则按照 ID 的字典序
内容为数字的日志, 按照输入的顺序排序
Example
样例 1:

输入:
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”
]
解释: “Act zoo” < “act car”,所以输出如上。
样例 2:

输入:
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”
]
解释:
由于 “Bctzoo” == “Bctzoo”, 所以比较”Tab”与”Tac”,有 “Tab” < “Tac”,故 “Tab Bctzoo” < “Tac Bctzoo”。
由于’ ‘ < ‘z’ ,所以 “a100 Act zoo” < “a100 Actzoo”。
Notice
日志总数不超过 5000
每行日志长度不超过 100
保证所有日志的 ID 不重复

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) {
        // Write your code here

        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;
    }
};




活动打卡代码 AcWing 893. 集合-Nim游戏

#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;
}


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


活动打卡代码 AcWing 892. 台阶-Nim游戏

#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;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 891. Nim游戏

#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;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 890. 能被整除的数

#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;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~