讨论/题目交流/🐱 第 15 场夜喵双周赛/
🐱 第 15 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

2 分 - 有序数组中出现次数超过25%的元素
4 分 - 删除被覆盖区间
5 分 - 字母组合迭代器
7 分 - 下降路径最小和 II

展开讨论
力扣 (LeetCode)发起于 2019-12-14
最近编辑于 2019-12-15

答题

有序数组中出现次数超过25%的元素

因为是非递减的 有序 整数数组,所以从前往后挨着数,超过25%的返回就对了。

int findSpecialInteger(vector<int>& arr) 
{
	int cnt = 0;
	int pre = INT_MAX;
	for (auto n : arr)
	{
		if (pre == n)
		{
			cnt++;
			continue;
		}
		if (cnt > arr.size() / 4) break;
		pre = n;
        cnt = 1;
    }
	return pre;
}

删除被覆盖区间

将区间按照左小右大的方式排序,这样就可以保证如果有需要删除的子区间,一定会在母区间的后面。
然后每一个区间只需要跟它前面的区间比较,如果需要删除记个数。

int removeCoveredIntervals(vector<vector<int>>& intervals) 
{
	sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b)
		{
			if (a[0] == b[0])
			{
				return b[1] < a[1];
			}
			return (a[0] < b[0]);
		});

	int cnt = 0;
	for (size_t i = 1; i < intervals.size(); i++)
	{
		for (size_t j = 0; j < i; j++)
		{
			if (intervals[i][0] >= intervals[j][0]
				&& intervals[i][1] <= intervals[j][1])
			{
				cnt++;
				break;
			}
		}
	}
	return intervals.size() - cnt;
}

字母排列迭代器

这题最重要的是阅读理解。
举个例子:

输入:abcde,3
所有的输出:
abc, abd, abe,
acd, ace,
ade,

bcd, bce,
bde,

cde

  1. next()
    11. 从后往前对要返回的字符串strNext的字符判断,是否在源数据characters中后面还有字符
    12. 如果有,就把这个字母换了之后就可以返回了
    13. 如果最后一位的字符已经是最后的字符了,那么倒数第二位的字符就可以往后换一个字符,并且最后的字符是其之后的字符

    abe --> acd

    1. 按照这个规则不断往前推,推到第0位字符更新时,更新后如果整个长度不够,就说明没有后续的组合了
  2. hasNext()
    21. 提前计算并保存下一个strNext,调用next()时,使用临时变量保存,再更新
    22. 判断strNext是否为空就行了

  3. 使用unordered_map<char, size_t> um;记录字符和索引的对应关系

class CombinationIterator 
{
public:
    CombinationIterator(string characters, int combinationLength) 
        : chs(characters), len(combinationLength)
    {
        for (size_t i = 0; i < chs.size(); i++)
        {
            um[chs[i]] = i;
        }
		for (size_t i = 0; i < len; i++)
		{
			strNext.push_back(chs[i]);
		}
    }

    string next()
    {
        string ret = strNext;
        for (size_t i = strNext.size() - 1; i < strNext.size(); i--)
        {
            auto di = um[strNext[i]] + 1;
            if (di + len - i - 1 < chs.size())
            {
                strNext[i] = chs[di];
                while ((++i) < strNext.size())
                {
					strNext[i] = chs[++di];
                }
                return ret;
            }
        }
		strNext = "";
		return ret;
    }

    bool hasNext() 
    {
        return strNext != "";
	}

private:
    string chs;
	string strNext;
    int len;
    unordered_map<char, size_t> um;
};

下降路径最小和 II

动态规划。

如果决定使用第i行j列的数值,那么需要i - 1行中除了自己这列之外最小的值与自己相加。
即 arr[i][j] + min(arr[i - 1][all], 除去arr[i - 1][j])

所以每行寻找第一最小值和第二最小值。
把最小值的列下一行的值加上第二最小值,其他列的下一行都加上第一最小值。

直接在原数组上改了。
最后返回最后一行的最小值。

int minFallingPathSum(vector<vector<int>>& arr) 
{
	for (size_t i = 0; i < arr.size() - 1; i++)
	{
		size_t min1 = arr[i][0] < arr[i][1] ? 0 : 1;
		size_t min2 = arr[i][0] < arr[i][1] ? 1 : 0;
		for (size_t j = 2; j < arr[0].size(); j++)
		{
			if (arr[i][min1] > arr[i][j])
			{
				min2 = min1;
				min1 = j;
			}
			else if (arr[i][min2] > arr[i][j])
			{
				min2 = j;
			}
		}
		for (size_t j = 0; j < arr[0].size(); j++)
		{
			if (j == min1)
			{
				arr[i + 1][j] += arr[i][min2];
			}
			else
			{
				arr[i + 1][j] += arr[i][min1];
			}
		}
	}

	int ans = INT_MAX;
	for (size_t j = 0; j < arr[0].size(); j++)
	{
		ans = min(ans, arr[arr.size() - 1][j]);
	}
	return ans;
}

致谢

纪念第一次明明可以4道全做完,却审题不清,静不下心,结果只提交了2题。
虽然是题简单,但也算进步吧。

感谢观看,希望大家坚持并进步!

2
展开全部 9 讨论