头像

zyq2652192993

SJTU


访客:9642

离线:2天前



题目描述

You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

  • Choose array nums1 or nums2 to traverse (from index-0).
  • Traverse the current array from left to right.
  • If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

样例

Example 1:

img

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

  • 1 <= nums1.length <= 10^5
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^7
  • nums1 and nums2 are strictly increasing.

解法一:队列 + 贪心 + 双指针 + 前缀和

感觉这个题和前面比赛的Hard比较,也就是Medium的难度,其实这题很套路,对于有序列表:

  • 如果是两个列表,数据范围是$10^3$,大概率就是动态规划,如果是$10^5$,那么大概率就是双指针
  • 如果是多个有序列表,一般数据范围是$10^5$,基本上就是优先级队列

本题可以将每个数组进行切分,以第四个样例为例:

nums1 [1] (4) [5 8 9] (11) [19]
nums2 [2 3] (4) (11) [12]

其中()内的数字代表两个序列里相同的数字,每个[]内的数字是夹在两个()中间的数字,或者首尾两端的部分。()内的数字是必须要经过的,让结果存在区别的是[]内的数字,[]内的数字位置是连续的,所以可以用前缀和得到区间和。用两个队列存储两个序列里相同数字的下标,为了让每个序列的第一个[]好处理,两个队列里面都先加入数字0,显然两个队列的长度必然是相等的。如果队列的长度是1,意味着两个序列里没有相同的数字,那么直接计算两个数组的总和即可。

这样就可以计算两个()中间的[]产生的影响,留下每个数组末尾的[]单独处理。因为都只需要遍历一遍数组,时间复杂度$O(n)$,空间复杂度$O(n)$。

注意存在溢出,使用long long

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = nums1.size(), n = nums2.size();
        const int MODE = 1e9 + 7;
        queue<int> q1, q2;
        q1.push(0), q2.push(0);

        vector<long long> prefixSum1(m + 1, 0), prefixSum2(n + 1, 0);
        for (int i = 1; i <= m; ++i) prefixSum1[i] = prefixSum1[i - 1] + nums1[i - 1];
        for (int i = 1; i <= n; ++i) prefixSum2[i] = prefixSum2[i - 1] + nums2[i - 1];

        int pos = 0;
        for (int i = 0; i < m; ++i) {
            while (pos < n && nums2[pos] < nums1[i]) ++pos;
            if (pos >= n) break;
            if (nums1[i] == nums2[pos]) q1.push(i + 1), q2.push(pos + 1);
        }
        if (q1.size() == 1) return max(prefixSum1[m] % MODE, prefixSum2[n] % MODE);

        long long res = 0;
        while (q1.size() > 1) {
            int tmp1 = q1.front(); q1.pop();
            int tmp2 = q2.front(); q2.pop();

            res = max(res + gap(tmp1, q1.front() - 1, prefixSum1) + nums1[q1.front() - 1], 
                res + gap(tmp2, q2.front() - 1, prefixSum2) + nums2[q2.front() - 1]);
        }
        res = max(res + gap(q1.front(), m, prefixSum1), res + gap(q2.front(), n, prefixSum2));

        return res % MODE;
    }

    inline long long gap(int start, int end, vector<long long> & prefixSum)
    {
        return prefixSum[end] - prefixSum[start];
    }
};

解法二:对于解法一的空间优化,其实也可以不必计算前缀和,只需要用两个变量即可。空间复杂度优化到$O(1)$。

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = nums1.size(), n = nums2.size();
        const int MODE = 1e9 + 7;
        long long res = 0, sum1 = 0, sum2 = 0;
        int pos1 = 0, pos2 = 0;

        while (pos1 < m && pos2 < n) {
            if (nums1[pos1] < nums2[pos2]) sum1 += nums1[pos1++];
            else if (nums1[pos1] > nums2[pos2]) sum2 += nums2[pos2++];
            else {
                res += max(sum1, sum2) + nums1[pos1++];
                ++pos2;
                sum1 = sum2 = 0;
            }
        }

        if (pos1 < m) {
            for (int i = pos1; i < m; ++i) sum1 += nums1[i]; 
        }
        if (pos2 < n) {
            for (int i = pos2; i < n; ++i) sum2 += nums2[i];
        }

        res += max(sum1, sum2);

        return res % MODE;
    }
};



题目描述

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

样例

Example 1:

img

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

img

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

img

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 200
  • grid[i][j] is 0 or 1

要让主对角线上的数字全是0,翻译过来就是从每一行的末尾开始的连续0的个数要满足:假如当前行是第i行(从0开始计数),那么连续的0的个数需要满足zeroNum[i] >= n - i - 1

只能是行交换,意味着通过交换zeroNum内的数字使其满足条件。那么一个很自然的想法是zeroNum内的数字越大的越靠前,那么是不是排序并计算交换的次数(相当于计算逆序对次数,冒泡、归并、线段树搞一下),然后检验每一行是否满足条件即可呢?这种是存在问题的,比如最后三行末尾连续0的个数是3,4,5,此时无需交换也满足条件,但是排序则需要交换。

另外需要考虑的一点是,因为每次都是去寻找第一个能使当前行满足的zeroNum数字,是不是很类似首次适配的思想,是否可能存在第一个找到的数字满足了当前行的条件(设这一行为i),假如还有一行j也能让其满足条件,并且zeroNum[j] < zeroNum[i],为什么不选择第j行这个更接近的呢?这是因为既然ij行都能满足条件,那么当前行往下,第j行肯定也可以满足,并且第i行离当前行更近,交换的次数少,所以只需要每次选择第一个能使当前行末尾连续的0满足条件的数字即可。

因为需要统计每一行末尾连续的0的个数,最坏情况下$O(n^2)$,另外交换数字的最坏情况也是$O(n^2)$,空间复杂度$O(n)$。

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = grid.size();
        vector<int> zeroNum(n);

        for (int i = 0; i < n; ++i) {
            int j = n - 1;
            while (j >= 0 && grid[i][j] == 0) {
                ++zeroNum[i];
                --j;
            }
        }

        int res = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (zeroNum[i] < n - i - 1) {
                int j = i + 1;
                while (j < n && zeroNum[j] < n - i - 1) ++j;
                if (j == n) return -1;
                while (j > i) {
                    std::swap(zeroNum[j], zeroNum[j - 1]);
                    --j;
                    ++res;
                }
            }
        }

        return res;
    }
};



题目描述

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

样例

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints:

  • 2 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
  • arr contains distinct integers.
  • 1 <= k <= 10^9

解法一:模拟

一次比较之后总会有一个数添加到序列的末尾,那么实现这个过程可以有两种选择:队列或者链表。为了简单实现,选择普通的队列即可,当然也可以选择deque双端队列。注意到k的数据范围是1e9,说明肯定有办法缩小范围,一个序列最大的数连胜的次数是n - 1,所以当k >= n - 1的时候,直接返回数组的最大值即可。

这里我们用一个while循环来模拟整个过程,因为k < n - 1,可知数组内的最大值必然符合条件,即至少存在一个满足条件的数,所以有合理的退出条件,就不会造成死循环。让tmp模拟arr[0],队列的首端元素模拟arr[1]cnt用来统计连胜的次数。

考虑最坏的情况,假如前n - 1个数字都不符合连胜的要求,那么最后一个数肯定是最大的数字,并且前面的数字一定符合下面这种排列:每个[]内的第一个数字大于当前[]内的余下数字,下一个[]的第一个数字必然大于前一个[]内的第一个数字,这样才能实现连胜次数不合要求。

[] [] [] [] ... max_element

一个很自然的想法是会不会存在多次循环遍历数组,答案是不会的,因为数组中最大的元素是比赛终结者,到max_element这里必然得出结果,最坏的结果就是遍历数组两次,时间复杂度是$O(n)$,空间复杂度是$O(n)$。

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = arr.size();
        if (k >= n - 1) return *max_element(arr.begin(), arr.end());

        queue<int> q;
        for (int i = 1; i < n; ++i) q.push(arr[i]);

        int res = arr[0], tmp = arr[0];
        int cnt = 0;

        while (true) {
            if (tmp > q.front()) {
                q.push(q.front()); q.pop();
                ++cnt;
            }
            else {
                q.push(tmp);
                tmp = q.front(); q.pop();
                cnt = 1;
                res = tmp;
            }

            if (cnt >= k) break;
        }

        return res;
    }
};

解法二:
假如一个数字的连胜次数中断,那么意味着破坏这个连胜次数的数字肯定要大于其前面的数字,所以完全可以只遍历一遍数组。

如果还没有遍历到末尾就存在一个数字的连胜次数等于k,那么直接返回结果;如果到了末尾虽然没有数字连胜次数大于等于k,但是最后一个打破前面连胜次数的数字就必然是最终结果,因为可以想象,把前面的数字移动到末尾再去比较,肯定都会小于这个数字,根据解法一的分析知道必然存在一个结果,既然前面的数字都不满足,那么就只能是当前选择的这个数字了。

免去了用队列模拟,时间复杂度$O(n)$,空间复杂度$O(1)$。

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = arr.size();
        if (k >= n - 1) return *max_element(arr.begin(), arr.end());

        int cnt = 0, res = arr[0];
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                ++cnt;
                arr[i + 1] = arr[i];
            }
            else {
                res = arr[i + 1];
                cnt = 1;
            }

            if (cnt >= k) break;
        }

        return res;
    }
};



题目描述

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

样例

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

算法

(字符串哈希 + 哈希表)

如果一条Message该被打印,只可能是两种情况:

  • 之前这条Message没有出现过
  • 或者两次Message的时间戳的差大于等于10

于是很自然的联想到可以用一个Hash Table去记录前面出现的时间戳,大概表示成unordered_map<string, int>,一看到要用string做键,如果这个Message很长的话,既浪费时间复制,也浪费空间,所以想到可以用字符串哈希,用哈希值作为键。

C++ 代码

class Logger {
    typedef unsigned long long ull;
    static constexpr ull base = 13331;

    unordered_map<ull, int> um;

public:
    /** Initialize your data structure here. */
    Logger() {}

    ull getHash(const string & str)
    {
        int n = str.size();
        ull res = 0;
        for (int i = 0; i < n; ++i) {
            res = res * base + (int)str[i];
        }

        return res;
    }

    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        ull key = getHash(message);
        if (um.find(key) == um.end()) {
            um[key] = timestamp;
            return true;
        }

        if (timestamp - um[key] >= 10) {
            um[key] = timestamp;
            return true;
        }

        return false;
    }
};

/**
 * Your Logger object will be instantiated and called as such:
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
 */



题目描述

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

样例

Example 1:

11000
11000
00011
00011

Given the above grid map, return 1.

Example 2:

11011
10000
00001
11011

Given the above grid map, return 3.

Notice that:

11
1

and

 1
11

are considered different island shapes, because we do not consider reflection / rotation.
Note: The length of each dimension in the given grid does not exceed 50.


算法

(DFS + 字符串哈希) $O(mn)$

很明显需要用DFS去搜索岛屿的数量,关键就是如何判断岛屿的形状,很自然的就联想到哈希,以第二个样例为例,右下角的平移到左上角,其实相当于右下角岛屿所有点的横纵坐标都减去这部分岛屿的最小横纵坐标,相当于归一化。

定义一个结构体Node存储横纵坐标,并用一个数组seq保存属于同一个岛屿的Node,当一个DFS结束,我们先进行归一化,也就是所有元素减去对应部分的最小横纵坐标,然后排序。

接下来就是如何去判断序列是否一样了,如果保存所有的Node,占据的空间大,而且比较起来很费时间,联想到1496判断路径是否相交的方法,可以把序列里的节点坐标看成一个字符序列,注意每个Node的横纵坐标用,分隔。利用字符串哈希的办法,这样就很节省存储空间,最后其实只需要知道unordered_set的大小即可。

C++ 代码

class Solution {
    typedef unsigned long long ull;
    static constexpr ull base = 13331;
    unordered_set<ull> us;

    struct Node
    {
        int x, y;
        Node(int x, int y) : x(x), y(y) {}

        bool operator<(const Node & obj) const
        { return (x < obj.x) || (x == obj.x && y < obj.y); }
    };

    int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<Node> seq;
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    seq.push_back(Node(i, j));
                    int minX = i, minY = j;
                    DFS(grid, seq, i, j, minX, minY);
                    Hash(seq, minX, minY);
                    seq.clear();
                }
            }
        }

        return us.size();
    }

    void DFS(vector<vector<int>>& grid, vector<Node> & seq, int row, int col, int & minX, int & minY)
    {
        int m = grid.size(), n = grid[0].size();
        grid[row][col] = 0;

        for (int i = 0; i < 4; ++i) {
            int nextRow = row + direction[i][0];
            int nextCol = col + direction[i][1];
            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol]) {
                seq.push_back(Node(nextRow, nextCol));
                minX = min(minX, nextRow), minY = min(minY, nextCol);
                DFS(grid, seq, nextRow, nextCol, minX, minY);
            }
        }
    }

    void Hash(vector<Node> & seq, const int & minX, const int & minY)
    {
        sort(seq.begin(), seq.end());
        for (auto & e : seq) { e.x -= minX, e.y -= minY; }

        ull res = 0;
        const ull square = base * base, triple = square * base;

        for (auto & e : seq) {
            res = res * triple + e.x * square + (ull)(',') * base + e.y;
        }

        us.emplace(res);
    }
};



题目描述

A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum.

Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.

In other words, you need to choose the position of the service centre [xcentre, ycentre] such that the following formula is minimized:

img

Answers within 10^-5 of the actual value will be accepted.

样例

Example 1:

img

Input: positions = [[0,1],[1,0],[1,2],[2,1]]
Output: 4.00000
Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.

Example 2:

img

Input: positions = [[1,1],[3,3]]
Output: 2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843

Example 3:

Input: positions = [[1,1]]
Output: 0.00000

Example 4:

Input: positions = [[1,1],[0,0],[2,0]]
Output: 2.73205
Explanation: At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3.
Try to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205.
Be careful with the precision!

Example 5:

Input: positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]
Output: 32.94036
Explanation: You can use [4.3460852395, 4.9813795505] as the position of the centre.

Constraints:

  • 1 <= positions.length <= 50
  • positions[i].length == 2
  • 0 <= positions[i][0], positions[i][1] <= 100\

算法

(Weiszfeld算法)

Weber问题:求平面上的供给点到需求点的最小欧几里得距离和。

Weiszfeld算法:通过以下迭代式进行迭代更新,自定义求解精度。其中x, y代表上一轮的供给点的横纵坐标,x', y'代表新一轮的供给点横纵坐标。

image.png

初始化时,我们用横纵坐标的平均值作为初始点,然后不断迭代更新。注意可能存在分母为0的情况。

C++ 代码

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = positions.size();
        double eps = 1e-8;
        double x, y;
        double sum_x = 0, sum_y = 0;
        for (int i = 0; i < n; ++i) {
            sum_x += positions[i][0];
            sum_y += positions[i][1];
        }
        x = sum_x / n, y = sum_y / n;
        double pre_x = x, pre_y = y;

        while (true) {
            double sum1 = 0, sum2 = 0, sum3 = 0;
            for (int i = 0; i < n; ++i) {
                double tmp = dis(x, y, positions[i][0], positions[i][1]);
                if (tmp < eps) continue;
                sum1 += (double)positions[i][0] / tmp;
                sum2 += (double)positions[i][1] / tmp;
                sum3 += (double)1 / tmp;
            }
            if (sum3 < eps) break;

            pre_x = x, pre_y = y;
            x = sum1 / sum3, y = sum2 / sum3;
            if (abs(x - pre_x) < eps && abs(y - pre_y) < eps) break;
        }

        double res = 0;
        for (auto & e : positions) res += dis(x, y, e[0], e[1]);

        return res;
    }

    inline double dis(double x1, double y1, double x2, double y2)
    {
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }
};

本题相当于求费马点,模拟退火是一个比较常见的选择。求函数$f(x) = \sum_{i = 1} ^ n \text{dis}(x_i, y_i, x, y)$的极小值,其中$x, y$是需要求解的坐标,模拟退火的关键初始值:初始温度,温度下降比率,精度。一般我的选择是初始温度是n的3倍(比如洛谷-P1337 [JSOI2004]平衡点),下降比率在0.995-0.997之间选择,精度选择一般是1e-15,本题在1e-12也可以通过。模拟退火多进行几次可以提高准确率,但是运行太多次会浪费时间,我一般选择运行三次。

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = positions.size();
        double resX = 0, resY = 0;
        for (auto & e : positions) {
            resX += e[0], resY += e[1];
        }
        resX /= n, resY /= n;
        double resW = energy(resX, resY, positions);

        for (int i = 0; i < 3; ++i) {
            SA(resX, resY, resW, positions);
        }

        return resW;
    }

    double energy(double x, double y, vector<vector<int>>& positions)
    {
        double res = 0;
        for (auto & e : positions) {
            double tmpX = x - e[0];
            double tmpY = y - e[1];
            res += sqrt(tmpX * tmpX + tmpY * tmpY);
        }

        return res;
    }

    void SA(double & resX, double & resY, double & resW, vector<vector<int>>& positions)
    {
        double T = 3000;
        const double EPS = 1e-15;
        while (T > EPS) {
            double nextX = resX + ((long long)rand() * 2 - RAND_MAX) * T;
            double nextY = resY + ((long long)rand() * 2 - RAND_MAX) * T;
            double nextW = energy(nextX, nextY, positions);
            double delta = nextW - resW;

            if (delta < 0) {
                resX = nextX, resY = nextY, resW = nextW;
            }
            else if (exp(- delta / T) * RAND_MAX > rand()) {
                resX = nextX, resY = nextY;
            }

            T *= 0.995;
        }
    }
};



题目描述

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

样例

Example 1:

img

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

img

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

img

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

  • 2 <= n <= 10^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= succProb[i] <= 1
  • There is at most one edge between every two nodes.

算法

(BFS)

start开始,依次去更新与其相连的点,这些点作为源点再去更新其他点,数组d[i]记录从starti的最大概率乘积,很典型的BFS套路。

这道题其实是边权重的最大乘积的一种形式,此时边的权重是以概率的形式表示,如果是权重大于1的数,甚至很大,最后结果超过了unsigned long long呢?其实可以将边的权重取log,然后用一个path数组来记录路径,这样就将乘积转化为加法了。当然本题无需这么做也可以求解。

C++ 代码

class Solution {
    struct Node
    {
        int to;
        double probability;
        Node(int t, double p) : to(t), probability(p) {}
    };

public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<Node>> grid(n);
        for (int i = 0; i < edges.size(); ++i) {
            int from = edges[i][0], to = edges[i][1];
            grid[from].push_back(Node(to, succProb[i]));
            grid[to].push_back(Node(from, succProb[i]));
        }

        vector<double> d(n, 0); d[start] = 1;
        queue<int> q;
        q.push(start);

        while (!q.empty()) {
            int from = q.front(); q.pop();
            for (int i = 0; i < grid[from].size(); ++i) {
                int to = grid[from][i].to;
                double probability = grid[from][i].probability;
                if (d[to] < d[from] * probability) {
                    q.push(to);
                    d[to] = d[from] * probability;
                }
            }
        }

        return d[end];
    }
};



题目描述

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

样例

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

  • s[i] == '0' or s[i] == '1'
  • 1 <= s.length <= 10^5

算法

(双指针) $O(n)$

统计全是1的子串(需要连续),首先将字符串切分,提取出全是1的子串,比如第一个测试用例0110111,就切分成11111两个子串,然后看切分出来的子串能够提取出多少个全是1的子串,假设子串的长是m,那么每个提取出来的子串可以得到m * (m + 1) / 2个全1子串,累加即可。

所以关键在于将字符串切分,pre指向每个全1子串的起始位置,i指向全1子串的末尾,计算出长度m即可完成求解。只需要遍历一遍字符串,时间复杂度$O(n)$。

C++ 代码

class Solution {
public:
    int numSub(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size();
        long long res = 0;
        const int MODE = 1e9 + 7;

        int pre = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                pre = i;
                while (i < n && s[i] == '1') ++i;
                long long len = i - pre;
                res = (res + (len + 1) * (len) / 2) % MODE;
            }
        }

        return res;
    }
};



题目描述

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

样例

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

  • 1 <= n <= 10^5

算法

(动态规划)$O(n(\sqrt{n} + \log{n}))$

一个策略就是尝试所有小于n的平方数,看能否获胜,比如先尝试1,余下的就是n - 1,那么就变成了对手在n - 1的情况下先手能否获胜。那么如果我知道了在n-1情况下先手能否获胜,就可以直接得出结果。很自然的,想到用递归求解。但是注意到会存在很多重复计算,那么想到用动态规划来解决重复计算的情况。

d[i]表示石子数量为i时先手能否获胜,i = 1, 2时可以直接得出结果。首先如果这个数本身就是完全平方数,直接取走所有的石子,先手必胜。如果一个数不是完全平方数,并且要求每次必须取完全平方数的数量的石子,所以我们尝试所有小于等于n的完全平方数,假设取走的完全平方数是k,那么余下的就是n - k,只有此时n-k先手必输的情况下,先手取走k是一个必胜的策略。

于是我们预处理出所有不超过$10^5$的完全平方数,对于循环遍历到i,用二分查找的办法找到最后一个不超过i的完全平方数(也就是第一个大于i的位置的前一个位置),需要搜索的长度为$\sqrt n$,所以时间复杂度$O(n(\sqrt{n} + \log{n}))$。

C++ 代码

class Solution {
public:
    bool winnerSquareGame(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (n == 1) return true;
        if (n == 2) return false;

        vector<int> d(n + 1, 0);
        d[1] = 1; d[2] = 0;

        vector<int> seq;
        int cnt = 1;
        int limit = 1e5;
        while (cnt * cnt <= limit) {
            seq.push_back(cnt * cnt);
            ++cnt;
        }

        for (int i = 3; i <= n; ++i) {
            if (isSuqare(i)) {
                d[i] = 1;
            }
            else {
                int pos = (upper_bound(seq.begin(), seq.end(), i) - seq.begin()) - 1;
                for (int j = 0; j <= pos; ++j) {
                    if (!d[i - seq[j]]) { d[i] = 1; break; }
                }
            }
        }

        return d[n];
    }

    bool isSuqare(int n)
    {
        int k = sqrt(n);
        return k * k == n;
    }
};



题目描述

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

样例

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.

Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. 
The difference between the maximum and minimum is 1-0 = 1.

Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2

Example 4:

Input: nums = [1,5,6,14,15]
Output: 1

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

算法1

(排序 + 贪心) $O(n\log n)$

题目让求最大值与最小值差的最小值,想到两种思路,一种是二分,一种是贪心。

二分需要寻找单调性来缩小搜索区间,这个单调性却并不是很容易找到。这个题目其实有点类似CodeForces Minimizing Difference,让两端的极值往中间的数靠拢。

首先如果数组内元素的个数小于4,那么可以使数组内的数字都相同,所以直接返回0。

我们将问题一般化,题目虽然指出可以修改三次,如果允许修改k次呢?将数组排序,每次去计算nums[pos + len] - nums[pos],其中len = n - 1 - k,共计算k + 1次。假设最终最小的差值是左端点位于pos,右端点位于pos + len,那么把0pos - 1(如果pos > 1的话)的元素都修改为nums[pos],将pos + len + 1(前提是pos + len + 1 < n)到n - 1的元素全都修改为nums[pos + len],这样总共只会修改k个元素,修改完后所有的元素值都落在nums[pos]nums[pos + len]之间了。

可以看出,问题可以泛化到k < n,本题只是k = 3的特殊情况。

C++ 代码

class Solution {
public:
    int minDifference(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int k = 3, n = nums.size(); if (n <= 4) return 0;

        sort(nums.begin(), nums.end());
        int res = INT_MAX;
        int pos = 0, len = n - 1 - k;
        for (int cnt = 0; cnt < k + 1; ++cnt) {
            res = min(res, nums[pos + len] - nums[pos]);
            ++pos;
        }

        return res;
    }
};