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

題解思路

使用動態(tài)規(guī)劃

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

遍歷一個節(jié)點翻轉一個節(jié)點

題解思路2

不用找到中間的節(jié)點,遍歷到最后,開始和頭節(jié)點比較,不過這樣要遍歷整個鏈表了

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.左邊空右邊不空,返回右邊上來的節(jié)點

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. 除自身以外數(shù)組的乘積

題解思路

想不到的地方是一個數(shù)等于他左邊的乘積乘以右邊的乘積
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;