TOP 100 65 - 70

221. 最大正方形

我的思路

在最大矩形的基础上再选择正方形.有个问题是最大矩形的短边不一定是最大正方形的边。所以就直接选择能够成为矩形的较短边中的最大边。（不是成为最大矩形）注意代码中被注释掉的部分

for (int i = 0; i < vec.size(); ++i) {
    while (!st.empty() && vec[st.top()] > vec[i]) {
        int cur = st.top();
        st.pop();
        int left = st.top() + 1;
        // if (vec[cur] * (i - left) > smax) {
        //     smax = vec[cur] * (i - left);
            minlen = min(vec[cur], i - left);
            maxminlen = max(maxminlen, minlen);
        // }
    }
    st.push(i);
}

题解思路

使用动态规划

226. 翻转二叉树

我的思路

递归呗

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return root;
    }
    TreeNode* node = root -> right;
    root -> right = invertTree(root -> left);
    root -> left = invertTree(node);
    return root;
}

234. 回文链表

我的思路

使用递归来完成栈的操作，找到中点slow，判断奇偶，从中间开始回退，p从中间往右走，比较值。

    void ergodic(ListNode* head) {        
        if (head == p -> next) {
            if (!odd) {
                p = p -> next;
            }
            return;
        }
        ergodic(head -> next);
        flag = flag && (p -> val == head -> val);
        p = p -> next;
    }

题解思路1

遍历一个节点翻转一个节点

题解思路2

不用找到中间的节点,遍历到最后,开始和头节点比较,不过这样要遍历整个链表了

void check(ListNode* head) {        
    if (head == nullptr) {
        return;
    }
    check(head -> next);
    if (p -> val != head -> val) flag = false;
    p = p -> next;
}

236. 二叉树的最近公共祖先

题解思路

递归调用，判断左边或右边是否有p q中的一个,把是否有p q作为判断条件
1.左边不空,右边不空,就说明最大公共祖先为当前root
2.左边不空右边空,返回左边返回上来的值
3.左边空右边不空,返回右边上来的节点

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) {
        return nullptr;
    }
    if (root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root -> left, p, q);
    TreeNode* right = lowestCommonAncestor(root -> right, p, q);
    if (left != nullptr && right != nullptr) {
        return root;
    }
    if (left) {
        return left;
    }
    if (right) {
        return right;
    }
    return nullptr;
}

238. 除自身以外数组的乘积

题解思路

想不到的地方是一个数等于他左边的乘积乘以右边的乘积
Tricks是使用k = 1再乘以nums[i]

vector<int> res(nums.size(), 1);
int k = 1;
for (int i = 0; i < nums.size(); ++i) {
    res[i] = k;
    k *= nums[i];
}
k = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
    res[i] *= k;
    k *= nums[i];
}
return res;