zhaodaxing

1.2万

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


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


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();
*/


/**
* 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;
for (int i = 0; i < n - k; i ++ ) p = p->next;
return p;
}
};


/**
* 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) {
auto dummy = new ListNode(-1);

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


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