Leetcode Weekly Contest 65题解

浏览: 206 发布日期: 2018-01-01 分类: c

Reach a Number

题意

最开始数字是0,第i步可以+i或者-i,求最少需要步到达target

思路

首先如果target是负数的话把他取绝对值一下,因为负数和正数是对称的,求绝对值后结果不变,这样我们就只考虑正数的情况

题目需要求的是?0 + ?1 + ?2 + ?3 + ... = target,其中?代表符号,可能是+或者-

我们先把所有的?看作+,也就是一直往后累加直到累加和大于等于target,累加和记作sum

这个时候,如果sum等于target,那么累加了多少次就是答案。关键是当sum大于target时,应该把哪些数字的符号变为负号(其实最少的情况是只需要把其中一个数字的符号变成负号就可以了,原因见下面)

容易发现,如果我们把某一个数字的符号变成-(比如把i的符号变为-),那么也就意味着sum需要减去2i,而且显然2i是偶数,所以这里决定了sum - target必须是偶数,所以当sum - target不是偶数时,我们让sum继续往后累加,直到sum - target是偶数。这个时候再把(sum - target)/2的符号变为-就得到target

所以实质上就是把sum一直累加,直到sum大于target并且sum - target是偶数,累加了多少次答案就是多少

到这里这道题已经完美的解决了,不然可以求出步数,还可以求出具体的步骤

代码

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int step = 0;
        long long cur = 0;
        int i = 0;
        for (i = 1; cur < target; ++i, ++step) {
            cur += i;
        }
        while ((cur - target) & 1) {
            cur += i;
            ++i;
            ++step;
        }
        return step;
    }
};

Pour Water

题意

把地面分成n分,从0到n-1标号,heights[i]代表第i个地面的高度。然后在第K个地面上滴V滴水,水会往低处流,也就是水如果往heights[j]流的话,必须heights[j] <= height[i]。现在滴完水后,水会按照以下规则流动:

  1. 如果水流能向左流,并且向左流到最低点后,高度比height[K]小,那么向左流
  2. 如果水流不能向左流,则尝试向右流,同样的,向右流到最低点后,高度要比height[K]
  3. 如果水流不能向左向右流,那就停在K这个位置上

每滴水流完之后停在哪里,哪里的高度就会+1,求出V滴水后每个地面的高度

思路

这题难就难在题意上,题意读懂后按照题目意思模拟就行了。

有一个trick就是,如果水能向左流,但是向左流了之后高度没变,那实际上会放弃左边,尝试向右流,举个栗子:[2, 2, 2, 2, 1], 1, 2,水流最开始在2这个位置上,然后发现左边是可以流的,但是高度并不会变,所以会放弃左边尝试向右流,然后发现右边是可以流的并且高度比heights[K]小,那么久向右流,最后答案是[2, 2, 2, 2, 2]

代码

class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int V, int K) {
        if (heights.empty() || !V) {
            return heights;
        }
        int n = heights.size();
        for (int i = 1; i <= V; ++i) {
            int left = K;
            int left_min_idx = left;
            while (left - 1 >= 0 && heights[left - 1] <= heights[left]) {
                if (heights[left - 1] < heights[left]) {
                    left_min_idx = left - 1;
                }
                --left;
            }
            if (left_min_idx != K) {
                ++heights[left_min_idx];
                continue;
            }
            
            int right = K;
            int right_min_idx = right;
            while (right + 1 < n && heights[right + 1] <= heights[right]) {
                if (heights[right + 1] < heights[right]) {
                    right_min_idx = right + 1;
                }
                ++right;
            }
            if (right_min_idx != K) {
                ++heights[right_min_idx];
                continue;
            }
            
            ++heights[K];
        }
        return heights;
    }
};

Pyramid Transition Matrix

题意

有一个类似于杨辉三角的金字塔三角形,给出了底部,还有一些规则。规则的格式是ABCC的左儿子允许A出现,C的右儿子允许B出现。根据底部和这些规则,求出能不能构造出一个金字塔三角形

思路

想到DP的做法,用dp[i][j][k]表示第i行第j列能否放第k个字母

那么就枚举第i行第j列是字母几,然后判断左儿子和右儿子的状态能否达到

代码

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (const string& str : allowed) {
            allow[str[2] - 'A'].emplace_back(make_pair(str[0] - 'A', str[1] - 'A'));
        }

        int depth = bottom.length();
        for (int i = 1; i <= depth; ++i) {
            dp[depth][i][bottom[i - 1] - 'A'] = true;
        }

        for (int i = depth - 1; i >= 1; --i) {
            for (int j = 1; j <= i; ++j) {
                for (int k = 0; k < 7; ++k) {
                    dp[i][j][k] = false;
                    for (size_t l = 0; l < allow[k].size(); ++l) {
                        int left = allow[k][l].first;
                        int right = allow[k][l].second;
                        dp[i][j][k] |= dp[i + 1][j][left] & dp[i + 1][j + 1][right];
                        if (dp[i][j][k]) {
                            break;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < 7; ++i) {
            if (dp[1][1][i]) {
                return true;
            }
        }
        return false;
    }
private:
    bool dp[110][110][7];
    vector<pair<int, int>> allow[7];
};

Set Intersection Size At Least Two

题意

有若干个区间[a, b](a < b),现在选出一个最小的整数集合,让这个集合和每一个区间的交集都大于等于2

思路

考虑贪心做法

我们先把区间按右端点排序,然后把是包含关系的区间预处理一下,比如区间[2, 3][1, 4]处理为[2,3],这是显然的,因为区间有包含关系的时候,小区间如果选了2个数字后,大区间就不用再选了

然后贪心的策略是,如果这个区间需要选新的数字,就尽量选右端点,这样的话可以和后面的区间尽量有重叠

代码

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        auto cmp = [](const vector<int> &lhs, const vector<int> &rhs) {
            if (lhs[1] == rhs[1]) {
                return lhs[0] < rhs[0];
            }
            return lhs[1] < rhs[1];
        };
        sort(intervals.begin(), intervals.end(), cmp);

        vector<vector<int>> new_intervals;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (size_t i = 1; i < intervals.size(); ++i) {
            if (intervals[i][1] == right) {
                left = intervals[i][0];
            } else if (intervals[i][0] > left) {
                new_intervals.emplace_back(vector<int> {left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        new_intervals.emplace_back(vector<int> {left, right});

        /*for (vector<int> vec : new_intervals) {
            cout << vec[0] << " " << vec[1] << endl;
        }*/

        int first = new_intervals[0][1] - 1;
        int second = first + 1;
        int ret = 0;
        for (size_t i = 1; i < new_intervals.size(); ++i) {
            if (new_intervals[i][0] <= second) {
                if (new_intervals[i][0] <= first) {
                    continue;
                } else {
                    first = second;
                    second = new_intervals[i][1];
                    ++ret;
                }
            } else {
                ret += 2;
                first = new_intervals[i][1] - 1;
                second = first + 1;
            }
        }
        ret += 2;
        return ret;
    }
};

leetcode周赛题解每周更新,请关注微信公众号 [leetcode周赛题解] 或 [lc_tijie]

返回顶部