头像

不会算法的小菜鸡




离线:2天前


最近来访(48)
用户头像
sypng
用户头像
今天你AC了吗
用户头像
Yuu
用户头像
dare
用户头像
ZYX@123
用户头像
逍遥曹大仙
用户头像
kk同学
用户头像
开一个罐头
用户头像
枝江纯路人
用户头像
无人圣地
用户头像
Chasing-
用户头像
又眠秋雨时
用户头像
dzzx666
用户头像
yan扬
用户头像
wdsyyds
用户头像
清风乍起
用户头像
EastTree
用户头像
acw_林少
用户头像
Uranus.
用户头像
._7265


class Solution {
public:
    int insert(int num) {
        int res = 23;
        while(num != 1) {
            if(num % 2 == 1) {
                num = num * 3 + 1;
                res++;
        }   else {
                num = num / 2;
                res++;
        }
        }
        return res;
    }
    int getKth(int lo, int hi, int k) {
        vector<pair<int,int>> q;
        for(int i = lo; i <= hi; i ++) {
            int tmp = insert(i);
            q.push_back({tmp,i});
        }
         sort(q.begin(),q.end());
        return q[k-1].second;
    }
};



class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int,int>mp;
        for(auto p : reservedSeats) {
            mp[p[0]] |= (1 << (p[1] -1));
        }
        int res = 0;

        for(auto x : mp) {
            int s1=(1<<1)+(1<<2)+(1<<3)+(1<<4);
            int s2=(1<<3)+(1<<4)+(1<<5)+(1<<6);
            int s3=(1<<5)+(1<<6)+(1<<7)+(1<<8);
            int a=s1&x.second,b=s2&x.second,c=s3&x.second;
            if(!a&&!c)res+=2;
            else if(!a||!b||!c)res++;
        }
        return res + 2 * (n-mp.size());
    }
};



class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int res = 0;
        for(int i = 0; i < arr1.size(); i ++) {
            bool falg = false;
            for(int j = 0; j < arr2.size(); j ++) {
                if(abs(arr1[i] - arr2[j]) <= d)
                {
                    falg = true;
                    break;
                }
            }
            if(!falg) res++;
        }
        return res;
    }
};



 if(ans) return ans;
         ans =  dfs(node -> right,u);
        if(ans) return ans;
        return nullptr;

之所以要这样写,如果你不记录递归函数值的话,只要根节点不等于目标节点就会返回null,其他节点返回的值也是返回给上一个函数,但上一个函数返回的值与递归函数的返回值无关(因为他只会关心自己是否等于目标节点),所以要记录返回值,来确定当前节点是否等于目标节点

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
    TreeNode* dfs(TreeNode* node,TreeNode* u) {
        if(!node) return nullptr;
        if(node -> val == u -> val) return node;
        TreeNode* ans = dfs(node -> left,u);
        if(ans) return ans;
         ans =  dfs(node -> right,u);
        if(ans) return ans;
        return nullptr;
    }
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return dfs(cloned,target);
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 const int INF = 2e9;
struct Node{
    int mi,mx,sum;
    bool is_b; 
 };


class Solution {
    int ans = 0;
    Node dfs(TreeNode* u) {
    if (!u) return {INF, -INF, 0, true};
        auto l = dfs(u->left);
        auto r = dfs(u->right);

        bool is_b = false;
        if (u->val > l.mx && u->val < r.mi) // 要求此结点值介于左边最大和右边最小之间
            is_b = l.is_b && r.is_b; // 并且左右子树都是二叉搜索树

        int sum = 0;
        if (is_b) sum = l.sum + r.sum + u->val;
        ans = max(ans, sum);

        int mi = min({l.mi, u->val, r.mi});
        int mx = max({l.mx, u->val, r.mx});

        return {mi, mx, sum, is_b};


}
public:
    int maxSumBST(TreeNode* root) {
       dfs(root);
       return ans;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int res = 0;
    int dfs(TreeNode *position,int cnt,bool d) {
        if(position == nullptr) return cnt -1;
        if(!d) return max(dfs(position -> left,1,0),dfs(position -> right,cnt+1,1));
        return max(dfs(position -> left,cnt+1,0),dfs(position -> right,1,1));
    }
public:
    int longestZigZag(TreeNode* root) {
        return max(dfs(root -> left,1,0),dfs(root -> right,1,1));
    }
};



class Solution {
public:
    int findTheLongestSubstring(string s) {
         int n = s.size();
         char a[5] = {'a','e','i','o','u'};
         vector<int> f(32,n+1);
         int ans = 0;
         int state = 0;
         f[0] = -1;

         for(int i = 0; i < n; i++)
         {
             for(int j = 0; j < 5; j ++)
             {
                 if(s[i] == a[j])
                 {
                     state ^= 1 << j;
                 }
             }
             ans = max(ans,i - f[state]);
             f[state] = min(f[state],i);
         }
    return ans;
    }
};



class Solution {
public:
    string sortString(string s) {
        string result = "";
        int n = s.length();
        sort(s.begin(),s.end());
        bool st[27] = {false};
        while(result.length() != n)
        {
            memset(st,0,sizeof st);

            for(int i = 0; i < n; i ++) {
                if(!st[s[i]-'a']) 
                {
                    result += s[i];
                    st[s[i] - 'a'] = true;
                }
            }
            memset(st,0,sizeof st);
            if(result.length() != n) {
                for(int i = n-1; i >= 0; i --) {
               if(!st[s[i]-'a']) 
                {
                    result += s[i];
                    st[s[i] - 'a'] = true;
                }
            }
            }

        }
        return result;

    }
};



class Solution {
public:
int get_year(const string &d) {
        int y = 0;
        for (int i = 0; i < 4; i++)
            y = y * 10 + d[i] - '0';
        return y;
    }

    int get_month(const string &d) {
        return (d[5] - '0') * 10 + d[6] - '0';
    }

    int get_day(const string &d) {
        return (d[8] - '0') * 10 + d[9] - '0'; 
    }

    bool is_leap(int y) {
        if (y % 400 == 0) return true;
        return y % 100 != 0 && y % 4 == 0;
    }
    int daysBetweenDates(string date1, string date2) {
        int y1, m1, d1;
        int y2, m2, d2;

        y1 = get_year(date1);
        y2 = get_year(date2);

        m1 = get_month(date1);
        m2 = get_month(date2);

        d1 = get_day(date1);
        d2 = get_day(date2);

        const int m[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

       if (y1 > y2 || (y1 == y2 && m1 > m2) || (y1 == y2 && m1 == m2 && d1 > d2)) {
            swap(y1, y2);
            swap(m1, m2);
            swap(d1, d2);
        }
        int ans = 0;
        while(y1 != y2 || m1 != m2 || d1 != d2) {
            ans ++;
            d1++;
            if(is_leap(y1) && m1 == 2)
            {
                if(d1 > 29)
                {
                    d1 = 1;
                    m1 ++;
                }
            } else {
                if(d1 > m[m1]) 
                {
                    d1 = 1;
                    m1 ++;
                }
            }
            if(m1 == 13) 
            {
                y1 ++;
                m1 = 1;
                d1 = 1;
            }
        }
        return ans;

    }
};



class Solution {
public:
    int countOrders(int n) {
        long long  last = 1;
        for(int i = 2; i <= n; i ++)
        {
            last = last * i * (2*i - 1) % 1000000007;
        }
        return last;
    }
};