头像

acw_zhw


访客:881

离线:6小时前


活动打卡代码 AcWing 85. 最大矩形

acw_zhw
1天前

largest rectangle/trapping water的2D版本
1.枚举每一行,并累积每一列的高度和
2.对累积的高度用largest rectangle的做法,求凸型的除两边界外的面积 @ stk.top()是左边界,i是右边界,last是高度

e.g.
[
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]

拓展一个最右边的点为了能够取出矩阵最右边的高度, 需要尽量保持拓展的点足够小, 这样才可以取出m-1的高度,所以取-1

计算面积时只考虑所有凸型
第一行 1, 0, 1, 0, 0, -1 -> [1, 0] [0, 1, 0]
第二行 2, 0, 2, 1, 1, -2 -> [2, 0] [0, 2, 1] [0, 1, 1, -2]
第三行 3, 1, 3, 2, 2, -3 -> [3, 1] [1, 3, 2] [1, 2, 2, -3]



class Solution 
{
public:
    int maximalRectangle(vector<vector<char>>& matrix) 
    {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> heights(m + 1, 0); heights[m] = -1;

        // 枚举每一行
        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            // heights会累积每一行同列的高度 @ 
            for (int j = 0; j < m; j ++ )
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j] ++;

            stack<int> stk;
            for (int j = 0; j <= m; j ++)
            {
                while (!stk.empty() && heights[stk.top()] > heights[j])
                {
                    int last = stk.top(); stk.pop();
                    if (stk.empty()) res = max<int>(res, heights[last] * j);
                    else res = max<int>(res, heights[last] * (j - stk.top() - 1));
                }
                stk.push(j);
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 87. 扰乱字符串

acw_zhw
4天前

区间dp @ 类似基础课的合并石子 @ 通过枚举区间内的一个点来拆分成两个子区间的局部解,需要从小到大枚举区间长度来更新
– attribute @ true/false
– set @ f[i1][j1][i2][j2] @ 分别表示两个区间的两边界 (both are inclusive boundaries)

– last different point @ pick a point k to partition a set into two in length of k and len - k respectively
– subset & transition @ 枚举每一个可能的中间的点,只要
正着来: f[i1][i1 + k][i2][i2 + k] && f[i1 + k + 1][j1][i2 + k + 1][j2]

反着来: f[i1][i1 + k][j2 - k][j2] && f[i1 + k + 1][j1][i2][j2 - k - 1]
是有效的, 那么f[i1][j1][i2][j2]就是有效的

– init @ f[i][i][j][j] = s1[i] == s[j]

复杂度: O(n^4)


class Solution 
{
public:
    bool isScramble(string s1, string s2) 
    {
        // base case
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;

        int n = s1.size();

        int cnt1[26] = {0}, cnt2[26] = {0};
        for (int i = 0; i < n; i ++ ) 
            cnt1[s1[i] - 'a'] ++, cnt2[s2[i] - 'a'] ++;
        for (int i = 0; i < 26; i ++ )
            if (cnt1[i] != cnt2[i]) return false;

        // init
        bool f[n][n][n][n];
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++ )
                f[i][i][j][j] = s1[i] == s2[j];

        // dp @ 枚举长度
        for (int len = 2; len <= n; len ++)
            // 枚举区间
            for (int i1 = 0; i1 <= n - len; i1 ++)
            {
                int j1 = i1 + len - 1;
                for (int i2 = 0; i2 <= n - len; i2 ++)
                {
                    int j2 = i2 + len - 1;
                    f[i1][j1][i2][j2] = false;
                    // 枚举拆分点
                    for (int k = 0; k < len - 1; k ++)
                        if (f[i1][i1 + k][i2][i2 + k] && f[i1 + k + 1][j1][i2 + k + 1][j2]
                           || f[i1][i1 + k][j2 - k][j2] && f[i1 + k + 1][j1][i2][j2 - k - 1])
                            f[i1][j1][i2][j2] = true;
                }
            }
       return f[0][n - 1][0][n - 1];
    }
};

优化一下空 @ 没必要枚举完两区间的两边界,我们只要枚举区间长度和起点就是能确定一个区间

– set @ f[l][i1][i2] @ 确定区间起点和长度就能表示整个区间

– last different point @ pick a point k to partition two a set into two
– subset & transition @ 枚举每一个可能的中间的点,只要
正着来: f[k][i1][i2] && f[l-k][i1+k][i2+k]

反着来: f[k][i1][i2 + l - k] && f[l-k][i1+k][i2]
是有效的, 那么f[l][i1][i2]就是有效的

class Solution 
{
public:
    bool isScramble(string s1, string s2) 
    {
        // base case
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;

        int n = s1.size();

        int cnt1[26] = {0}, cnt2[26] = {0};
        for (int i = 0; i < n; i ++ ) 
            cnt1[s1[i] - 'a'] ++, cnt2[s2[i] - 'a'] ++;
        for (int i = 0; i < 26; i ++ )
            if (cnt1[i] != cnt2[i]) return false;

        // init
        bool f[n + 1][n][n];
        memset(f, false, sizeof f);
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++ )
                f[1][i][j] = s1[i] == s2[j];


        // 区间dp
        for (int len = 2; len <= n; len ++ )
            for (int i1 = 0; i1 <= n - len; i1 ++ )
                for (int i2 = 0; i2 <= n - len; i2 ++ )
                    for (int k = 1; k < len; k ++ )
                        if (f[k][i1][i2] && f[len - k][i1 + k][i2 + k]
                            || f[k][i1][i2 + len - k] && f[len - k][i1 + k][i2])
                            {
                                f[len][i1][i2] = true;
                            }
        return f[n][0][0];
    }
};


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

acw_zhw
5天前
// dfs-backtrack

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return res;
    }
private:
    void dfs(int u, vector<int> &a)
    {
        // base case 
        if (u == n)
        {
            res.push_back(path);
            return;
        }
        // recursion @ count # of a[u]
        int k = 1, v = u + 1;
        while (v < n && a[v] == a[v - 1]) k ++, v ++;
        for (int i = 0; i <= k; i ++ )
        {
            dfs(v, a);
            path.push_back(a[u]);
        }

        for (int i = 0; i <= k; i ++ ) path.pop_back();
    }
    int n;
    vector<int> path;
    vector<vector<int>> res;
};


活动打卡代码 AcWing 89. 格雷编码

acw_zhw
5天前

字节的模拟面试里做过这个
公式:顺序下来第i个grey code为i ^ (i >> 1)
数电学过k map的可能都知道

class Solution 
{
public:
    vector<int> grayCode(int n) 
    {
        vector<int> res;
        for (int i = 0; i < (1 << n) ; i ++ )
            res.push_back(i ^ ( i >> 1));
        return res;
    }
};




acw_zhw
5天前
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 从后往前merge因为num1后面的是空置的
        int i = m - 1, j = n - 1, idx = m + n - 1;
        while(i >= 0 && j >= 0)
        { 
            if (nums1[i] > nums2[j]) nums1[idx --] = nums1[i --];
            else nums1[idx --] = nums2[j --];
        }

        while (j >= 0) nums1[idx --] = nums2[j --];
    }
};


活动打卡代码 LeetCode 86. 分隔链表

acw_zhw
5天前
class Solution 
{
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // store two list
        auto v1 = new ListNode(-1), v2 = new ListNode(-1);

        auto curr = head, lt = v1, ge = v2;
        while (curr)
        {
            if (curr->val < x) lt->next = curr, lt = lt->next;
            else ge->next = curr, ge = ge->next;
            curr = curr->next;
        }

        // 两个链表中必有一个最末的点是应该设置成null的但因为最后要合起来可以考虑下覆盖法
        if (ge->next) ge->next = nullptr;
        lt->next = v2->next;

        return v1->next;
    }
};



acw_zhw
5天前

NOTE 进阶题lc85

都是单调栈但有两种处理方式

Implementation 1
枚举当前高度作为计算面积的高度
然后单调栈找出左右第一个比当前高度小的点作为两边界
总共是three pass

Implementation 2
枚举当前高度作为右边界, stk.top()作为左边界, last作为计算面积的高度(last比两边界都高) @ 需要往数组最右边拓展意味无穷小的高度, -1 就可以了
只要one pass


class Solution 
{
public:
    int largestRectangleArea(vector<int>& h) 
    {
        h.push_back(-1);
        int n = h.size();
        // 找出每个枚举高度的左边界
        stack<int> stk;
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            while (!stk.empty() && h[stk.top()] > h[i])
            {
                int last = h[stk.top()]; stk.pop();
                int area;
                if (!stk.empty()) area = last * (i - stk.top() - 1);
                else area = last * i;
                res = max<int>(res, area);
            }
            stk.push(i);
        }

        return res;
    }
};



acw_zhw
5天前
class Solution 
{
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        auto curr = head;
        while (curr)
        {
            while(curr->next && curr->next->val == curr->val) curr->next = curr->next->next;
            curr = curr->next;
        }
        return head;
    }
};



acw_zhw
5天前
/*
head可能被删除所以用dummy head吧
*/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return nullptr;

        auto vhead = new ListNode(-1, head);
        auto curr = vhead;
        while (curr)
        {
            if (curr->next && curr->next->next 
                && curr->next->val == curr->next->next->val)
            {
                int t = curr->next->val;
                auto nextt = curr->next;
                while (nextt && nextt->val == t) nextt = nextt->next;
                curr->next = nextt;
            }
            else curr = curr->next;
        }
        return vhead->next;
    }
};



acw_zhw
5天前
/*
有重复元素就很恶心比如
1 1 1 1 1 1 3 1 @ 光看a[l], a[r], a[mid] 判断不出单调性在哪边
必须得混合O(logn)和O(n)手段来做了
O(n) 当a[l] = a[mid] = a[r] 直接去掉a[l], a[r]
*/

class Solution 
{
public:
    bool search(vector<int>& a, int target) 
    {
        if (a.size() == 0) return false;

        int l = 0, r = a.size() - 1, mid;
        while (l < r)
        {
            // base case
            mid = (l + r) >> 1;
            if (a[l] == target || a[r] == target || a[mid] == target) return true;
            // corner case
            if (a[l] == a[mid] && a[mid] == a[r]) l ++, r --;
            // 单调性在左边
            else if (a[l] <= a[mid])
            {
                if (a[l] < target && target < a[mid]) r = mid;
                else l = mid + 1;
            }
            // 单调性在右边
            else 
            {
                if (a[mid] < target && target < a[r]) l = mid + 1;
                else r = mid;
            }
        }
        return a[l] == target;
    }
};