头像

zhaodaxing




在线 


活动打卡代码 LeetCode 90. 子集 II

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return res;
    }
    void dfs(int u, vector<int>& nums) {
        if (u == nums.size()) {
            res.push_back(path);
            return ;
        }

        int k = u;
        while (k < nums.size() && nums[k] == nums[u]) k ++ ;
        int cnt = k - u;

        for (int i = 0; i <= cnt; i ++ ) {
            dfs(k, nums);
            path.push_back(nums[u]);
        }

        for (int i = 0; i <= k - u; i ++ ) 
            path.pop_back();
    }
};



zhaodaxing
5分钟前
class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty() || array[0].empty()) return false;
        int n = array.size(), m = array[0].size() - 1;
        int row = 0, col = m;
        while (row < n && col >= 0) {
            if (array[row][col] > target) col --;
            else if (array[row][col] < target) row ++;
            else return true;
        }
        return false;
    }
};


活动打卡代码 LeetCode 74. 搜索二维矩阵

zhaodaxing
10分钟前
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        return matrix[l / m][l % m] == target;
    }
};


活动打卡代码 AcWing 77. 翻转单词顺序

zhaodaxing
15分钟前
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        for (int i = 0; i < s.size(); i ++ ) {
            int j = i + 1;
            while (j < s.size() && s[j] != ' ') j ++ ;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        return s;
    }
};



zhaodaxing
27分钟前
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i ++ )    
            res = (res * 2) + (n >> i & 1);
        return res;
    }
};



zhaodaxing
19小时前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        while (p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};



zhaodaxing
19小时前
/**
 * 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 BSTIterator {
public:
    stack<TreeNode*> stk;
    BSTIterator(TreeNode* root) {
        while (root) {
            stk.push(root);
            root = root->left;
        }
        // return root;
    }

    int next() {
        auto root = stk.top(); stk.pop();
        int val = root->val;
        root = root->right;
        while (root) {
            stk.push(root);
            root = root->left;
        }
        return val;
    }

    bool hasNext() {
        return stk.size();
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int n = 0;
        for (auto p = pListHead; p; p = p->next) n ++ ;
        if (k > n) return NULL;
        auto p = pListHead;
        for (int i = 0; i < n - k; i ++ ) p = p->next;
        return p;
    }
};


活动打卡代码 LeetCode 61. 旋转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return NULL;
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto p = dummy;
        auto b = dummy;
        int n = 0;
        for (auto p = head; p; p = p->next) {
            b = p;
            n ++ ;
        }

        if (k >= n)k = k % n;
        if (k == 0) return head;

        k = n - k;
        for (int i = 0; i < k; i ++ ) p = p->next;
        auto c = p->next;
        b->next = dummy->next;
        dummy->next = c;
        p->next = NULL;
        return dummy->next;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail = tail->next = l1;
                l1 = l1->next;
            }else {
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }
        if (l1) tail = tail->next = l1;
        if (l2) tail = tail->next = l2;
        return dummy->next;
    }
};