头像

锤子科技未来产品经理

老罗与他的朋友科技有限公司




离线:24分钟前



1.基础


1. 二分

2.双指针、滑动窗口




字符串处理

(暴力枚举) $O(n^3)$ but实际运行远远小于

1.对于数字的位处理转换成字符串处理更加简单

2.枚举所有长度在low 和 high 之间的字符串,判断该数字是否符合规范

3.枚举出来的数字一旦大于当前的high,就可以返回答案

C++ 代码

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        string lower = to_string(low);
        string higher = to_string(high);
        int n = lower.size();
        int m = higher.size();

        vector<int> ans;
        for(int i = n; i <= m; i++) // 枚举区间长度
        {
            for(int j = 1; j <= 9 - i + 1; j++) // 枚举可以选择的第一个数字
            {
                string temp = "";
                int index = j;
                for(int k = 1; k <= i; k++) // 补全当前数字开头的当前长度的数字
                {
                    temp += to_string(index ++);
                }

                int now = atoi(temp.c_str());
                if(now > high) return ans;

                if(now >= low && now <= high)
                    ans.push_back(now);                
            }
        }

        return ans;
    }
};


新鲜事 原文

进入下半场了
图片


新鲜事 原文

喜报喜报网站yxc同学在本次Leetcode周赛勇夺世界第19名哈哈哈哈




贪心 + dp

排序 $O(nlogn)$ dp $O(n^n)$ 总体 $O(n^n)$
1.将所有对应的年纪和分数组成一个pair并按照年龄的升序排序
2.dp: 类似于求最长上升子序列的方法 f[i]表示以位置i结尾,并且选择第i个元素的情况下的最大值
3.状态转移: 因为之前已经按照年龄的升序排序,所以后面人的年龄一定不低于前面人的年龄
则,如果当前人的分数不小于前面人的分数就可以转移,否则不可以
这里先进行排序主要是排除以下情况
age: 2 1 3
sco: 4 1 2
明显age[0]和age[1]可以转移, age[0]和age[2]不可以转移, age[1]和age[2]可以转移。如果不进行排序
那么上述情况age[0]可以以age[1]作为媒介进行转移, 最后结果发生错误

C++ 代码

class Solution {
public:

    static bool cmp(pair<int, int> a, pair<int, int> b)
    {
        if(a.first == b.first)
            return a.second < b.second;
        return a.first < b.first;
    }

    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();

        vector<pair<int, int>> temp;
        for(int i = 0; i < scores.size(); i++)
            temp.push_back({ages[i], scores[i]});

        sort(temp.begin(), temp.end(), cmp);

        vector<int> f(n, 0);
        f[0] = temp[0].second;
        for(int i = 1; i < n; i++)
        {
            f[i] = temp[i].second;
            for(int j = 0; j < i; j++)
            {
                if(temp[i].first > temp[j].first && temp[i].second < temp[j].second)
                {
                    continue;
                }
                else
                    f[i] = max(f[i], f[j] + temp[i].second);
            }
        }

        int maxv = 0;
        for(auto item : f)
        {
            maxv = max(maxv, item);
        }

        return maxv;
    }
};




贪心 $O(13n)$

外层从a开始枚举, 内层枚举字符串的前半部分,如果第一次出现了两者不等的情况,
比较两个结果: 结果一在当前位置用该字符替换原来字符, 结果二在回文串后半部分对应位置替换字符
返回两者更小的那个

C++ 代码

class Solution {
public:
    string breakPalindrome(string p) {
        if(p.size() <= 1) return "";
        int pos = p.size() / 2 - 1;
        for(int i = 0; i < 26; i++)
        {
            char now = 'a' + i;
            for(int j = 0; j <= pos; j++)
                if(p[j] != now)
                {
                    string temp1 = p, temp2 = p;
                    temp1[j] = now;
                    temp2[p.size() - 1 - j] = now;
                    return min(temp1, temp2);
                }
        }

        return "";
    }
};



题目描述

In some cultures, children are named after ancestors and there is a number following which represents how many ancestors have shared that name. They are often shown as Roman Numerals

in Roman numerals, a value ts not repeated more than three times At that point. a smaller value precedes a larger value to indicate subtraction. For example the letter I represents the number 1, and Represents s Reason through the formation of I to 1o below, and see how it is appied in the following lines

样例

For example, f you are given the names [Steven XL, Steven XVI, David IX, Mary XV, Mary XIII, Mary XX]
the result of the sort is (David IX, Mary XIII, Mary XV, Mary XX, Steven XVI, Steven XL)
The resul with Roman numerals is the expected return  value.
Written with the numbers in decimal, they are [David 9. Mary 13. Mary I5, Mary 20, Steven 16 Steven 40] 

算法1

(字符串处理)

C++ 代码

unordered_map<char, int> words;

string deal(string str)
{
    int pos = str.find(' ');
    string a1 = str.substr(0, pos);
    string a2 = str.substr(pos + 1);

    int ans = 0;

    for (int i = 0; i < a2.size(); i++) 
    {
        if (i != a2.size() - 1 && words[a2[i + 1]] > words[a2[i]]) 
        {
            ans += words[a2[i + 1]] - words[a2[i]];
            i++;
        }
        else
            ans += words[a2[i]];
    }

    return a1 + " " + to_string(ans);
}

vector<string> ancestralNames(vector<string> &names)
{
    words['I'] = 1; words['V'] = 5;
    words['X'] = 10; words['L'] = 50; 
    words['C'] = 100; words['D'] = 500;
    words['M'] = 1000;

    for(int i = 0; i < names.size(); i++)
    {
        names[i] = deal(names[i]);
    }
    sort(names.begin(), names.end());
    return names;
}



题目描述

Alex is given n piles of boxes of equal or unequal heights. In one step. Alex can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height

样例

n = 3;
boxinpiles = [5, 2, 1]

In the first step, remove 3 boxes from boxinpiles[0], and the new array is boxinpiles = [2,2,1] 
Now reduce the two taller piles by 1 box each to match the height of the shortest plle This takes 
2 steps because each step is performed on only one pile. The final number of steps requlred is 3    


排序

(排序 + 贪心) $O(nlog(n))$

从大到小排序,每一次找到当前值和下一个值的差距,从开始到当前值都需要减去这个差距才可以和下一个值

的高度保持一致,因此直接遍历累加答案即可

C++ 代码

int pilesOfBox(int n, vector<int> &piles)
{
    sort(piles.begin(), piles.end(), greater<int>());
    int ans = 0;
    for(int i = 0; i + 1 < piles.size(); i++)
    {
        int gap =  piles[i] - piles[i + 1];
        ans += gap * (i + 1);
    }
    return ans;
}


新鲜事 原文

卡在这道题了,有人有啥思路吗(不是单调的,用三分求最高点的方法无效,因为有区间极大值)
图片



题目描述

A prisoner is planning to escape from prison! The prison s gate consists of horizontal and vertical bars that are spaced one unit apart so the area of each hole between the bars is 1 x 1. The prisoner manages to remove certain bars to make some bigger holes. Determine the area of the largest hole in the gate after the bars are removed

样例

n = 6
m = 6
h = [4];
v = [2];

In the images below. the left image depicts the initial 
prison gate with n 6 horizontal and m=6 vertical bars. 
The area of the biggest hole in the bars is 1 x 1. The 
right image depicts that same gate after the prisoner 
removes horizontal bar 4 and vertical bar 2, at which 
point the area of the biggest hole in the bars becomes 
2 x2=4  


贪心

(类似此题: https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/)

C++ 代码

int prisonBreak(int n, int m, vector<int> &h, vector<int> &v)
{
    unordered_set<int> h_(h.begin(), h.end());
    unordered_set<int> v_(v.begin(), v.end());

    int maxh = 0, maxv = 0;
    int pre = -1;
    for(int i = 1; i <= n; i++)
    {
        if(h_.find(i) != h_.end()) continue;
        else
        {
            if(pre != -1)
                maxh = max(maxh, i - pre);
            pre = i;
        }
    }

    if(pre == -1) return -1;

    pre = -1;

    for(int i = 1; i <= m; i++)
    {
        if(v_.find(i) != v_.end()) continue;
        else
        {
            if(pre != -1)
                maxv = max(maxv, i - pre);
            pre = i;
        }
    }

    if(pre == -1) return -1;

    return maxh * maxv;
}