tgs

tgs
6天前
void mirror(TreeNode* root) {
if (!root) return;
TreeNode *right = root->right;
mirror(right);
TreeNode* left = root->left;
mirror(left);
root->left = right;
root->right = left;
return;
}


tgs
6天前
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot1 || !pRoot2) return false;
if (isSame(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}

bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot2) return true;
if (!pRoot1 || pRoot1->val != pRoot2->val) return false;
return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
}
};


tgs
6天前
class Solution {
public:
bool isPopOrder(vector<int> &pushed, vector<int> &popped)
{

int sz = pushed.size();
int sz2 = popped.size();
if (sz != sz2) return false;
stack<int> s;

int j = 0;
for (int x : pushed)
{
s.push(x);
while (!s.empty() && j < sz && s.top() == popped[j])
{
s.pop();
j++;
}
}

return j == sz;
}
};


tgs
6天前
• Two Stacks
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
s.push(x);
if (min_s.empty() || x <= min_s.top())
min_s.push(x);
}

void pop() {
if (s.top() == min_s.top())
min_s.pop();
s.pop();
}

int top() {
return s.top();
}

int getMin() {
return min_s.top();
}

private:
stack<int> s;
stack<int> min_s;
};

• One stack
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
min = INT_MAX;
}

void push(int x) {
if (x <= min) {
s.push(min);
min = x;
}
s.push(x);
}

void pop() {
int t = s.top();
s.pop();
if (t == min) {
min = s.top();
s.pop();
}
}

int top() {
return s.top();
}

int getMin() {
return min;
}

private:
stack<int> s;
int min;
};


tgs
6天前
    vector<int> printMatrix(vector<vector<int> > matrix) {
int size;
vector<int> res;

if ((size = matrix.size()) == 0)
return res;

int r1 = 0, r2 = size - 1;
int c1 = 0, c2 = matrix[0].size() - 1;

while (r1 <= r2 && c1 <= c2)
{
for (int c = c1; c <= c2; c++)
res.push_back(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++)
res.push_back(matrix[r][c2]);

if (r1 < r2 && c1 < c2)
{
for (int c = c2 - 1; c > c1; c--)
res.push_back(matrix[r2][c]);
for (int r = r2; r > r1; r--)
res.push_back(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}

return res;
}


tgs
7天前
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) {}
};

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *r = new ListNode();
ListNode *s = r;

while (l1 && l2)
{
if (l1->val <= l2->val)
{
s->next = l1;
l1 = l1->next;
}
else
{
s->next = l2;
l2 = l2->next;
}
s = s->next;
}
if (l1)
s->next = l1;
else
s->next = l2;

return r->next;
}



tgs
7天前
ListNode *reverseListIteratively(ListNode *head)
{
ListNode *prev = NULL;  // first node of new list
ListNode *next = NULL;

while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

ListNode *reverseListRecursively(ListNode *head)
{
}



tgs
17天前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* pListHead, int k) {
int i = 1;
while (q && q->next && i < k) {
q = q->next;
i++;
}
if (i < k) return NULL;
while (q->next) {
p = p->next;
q = q->next;
}
return p;
}
};


tgs
17天前
• 维护有序性
class Solution {
public:
void reOrderArray(vector<int> &array) {
int i, j, n = array.size();
for (i = 0; i < n - 1; i++)
for (j = i + 1; j > 0; j--)
if (array[j] % 2 == 1 && array[j - 1] % 2 == 0)
swap(array[j], array[j - 1]);
}
};

• 不维护有序性
class Solution {
public:
void reOrderArray(vector<int> &array) {
int l = 0, r = array.size() - 1;
while (l < r) {
while (l < r && array[l] % 2 == 1) l ++ ;
while (l < r && array[r] % 2 == 0) r -- ;
if (l < r) swap(array[l], array[r]);
}
}
};



tgs
17天前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* dummy = new ListNode(-1);