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

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

image.png

3 分 - 根据数字二进制下 1 的数目排序
4 分 - 每隔 n 个顾客打折
5 分 - 包含所有三种字符的子字符串数目
6 分 - 有效的快递序列数目

根据数字二进制下 1 的数目排序

思路

  1. 先算位 1 的个数
  2. 存到 map
  3. 再导出成结果

答题

vector<int> sortByBits(vector<int>& arr) 
{
    map<int, vector<int>> _map;
    for (auto& n : arr)
    {
        int c = hammingWeight(n);
        _map[c].push_back(n);
    }
    vector<int> ans;
    for (auto& m : _map)
    {
        sort(m.second.begin(), m.second.end());
        for (auto& n : m.second)
        {
            ans.push_back(n);
        }
    }
    return ans;
}

int hammingWeight(uint32_t n)
{
    int sum = 0;
    while (n != 0)
    {
        n &= (n - 1);
        sum++;
    }
    return sum;
}

每隔 n 个顾客打折

思路

  1. 注意 products[i] 给出的数字其实是商品名称
  2. 注意打折的时候,中间任意数字计算的时候都要 double

答题

class Cashier {
public:
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices)
		: m_cnt(0), m_n(n), m_discount(discount)
	{
		for (int i = 0; i < products.size(); i++)
		{
			m_prices[products[i]] = prices[i];
		}
    }
    
    double getBill(vector<int> product, vector<int> amount)
	{
		m_cnt = (m_cnt + 1) % m_n;

		double ans = 0.f;
		for (int i = 0; i < product.size(); i++)
		{
			ans += m_prices[product[i]] * amount[i];
		}

		if (m_cnt == 0)
		{
			ans = ans * (double)(100 - m_discount) / (double)100.f;
		}
		return ans;
    }

private:
	int m_cnt;
	int m_n;
	int m_discount;
	unordered_map<int, int> m_prices;
};

包含所有三种字符的子字符串数目

思路

  1. 使用滑动窗口
  2. 当滑动窗口满足时,将窗口左右的字母个数乘起来,就是满足的子串
  3. 然后再滑,再加

答题

bool getAll(vector<int>& vi)
{
	for (auto n : vi)
	{
		if (n == 0) return false;
	}
	return true;
}

int numberOfSubstrings(string s) 
{
	int ans = 0;
	int left = 0;
	vector<int> vi(3, 0);
	queue<int> que;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'a' || s[i] == 'b' || s[i] == 'c')
		{
			//cout << endl << "[" << i << "]\t" << s[i] << endl;
			vi[s[i] - 'a']++;
			que.push(i);

			while (getAll(vi))
			{
				int a = que.front() - left + 1;
				int b = s.size() - i;
				ans += a * b;
				//cout << "a = " << a << ", b = " << b << ", a * b = " << a * b << endl;

				vi[s[que.front()] - 'a']--;
				que.pop();
				left = que.front();
				//cout << "left -> " << left << endl;
			}
		}
	}

	return ans;
}

有效的快递序列数目

// TODO:

答题

int countOrders(int n)
{
    long long res = 1;
    long long md = 1e9 + 7;
    for (int i = 1; i <= n; i++)
    {
        res = res * i;
        res = res * (2 * i - 1);
        res %= md;
    }
    return res;
}

致谢

欢迎大家热烈的交流!

1
展开全部 22 讨论