On the shoulders of giants.

weekly-contest-181

按既定顺序创建目标数组

给你两个整数数组 numsindex。你需要按照以下规则创建目标数组:

  • 目标数组 target 最初为空。
  • 按从左到右的顺序依次读取 nums[i]index[i],在 target 数组中的下标 index[i] 处插入值 nums[i]
  • 重复上一步,直到在 numsindex 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1:

输入:nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出:[0,4,1,3,2]
解释:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

示例 2:

输入:nums = [1,2,3,4,0], index = [0,1,2,3,0]
输出:[0,1,2,3,4]
解释:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

示例 3:

输入:nums = [1], index = [0]
输出:[1]

提示:

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i
题解

直接模拟插入。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            result.insert(result.begin() + index[i], nums[i]);
        }
        return result;
    }
};

四因数

给你一个整数数组 nums,请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数,则返回 0

示例:

输入:nums = [21,4,7]
输出:32
解释:
21 有 4 个因数:1, 3, 7, 21
4 有 3 个因数:1, 2, 4
7 有 2 个因数:1, 7
答案仅为 21 的所有因数的和。

提示:

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^5
题解

除了 1本身 外,验证是否还存在两个因数。

时间复杂度:\(O(n\sqrt m)\)

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int result = 0;
        for(auto num : nums) {
            int total = 0, sum = 0;
            for(int i = 2; i <= sqrt(num); i++) {
                if(num % i) continue;
                sum += i;
                total += 1;
                if(num / i != i) {
                    sum += num / i;
                    total += 1;
                }
            }
            if(total == 2) result += sum + 1 + num;
        }
        return result;
    }
};

检查网格中是否存在有效路径

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是:

  • 1 表示连接左单元格和右单元格的街道。
  • 2 表示连接上单元格和下单元格的街道。
  • 3 表示连接左单元格和下单元格的街道。
  • 4 表示连接右单元格和下单元格的街道。
  • 5 表示连接左单元格和上单元格的街道。
  • 6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发,网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走

注意:不能 变更街道。

如果网格中存在有效的路径,则返回 true,否则返回 false

示例 1:

输入:grid = [[2,4,3],[6,5,2]]
输出:true
解释:如图所示,你可以从 (0, 0) 开始,访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2:

输入:grid = [[1,2,1],[1,2,1]]
输出:false
解释:如图所示,单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连,你只会停在 (0, 0) 处。

示例 3:

输入:grid = [[1,1,2]]
输出:false
解释:你会停在 (0, 1),而且无法到达 (0, 2) 。

示例 4:

输入:grid = [[1,1,1,1,1,1,3]]
输出:true

示例 5:

输入:grid = [[2],[2],[2],[2],[2],[2],[6]]
输出:true

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6
题解

搜索,一个正确的决策转移必定是:可到达的下一个格子也能回到之前的格子。

判断合法转移后,直接搜索是否能到达目标点。

时间复杂度:\(O(nm)\)

const int dt[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
const int nex[6][2] = {{2, 3}, {0, 1}, {1, 2}, {1, 3}, {0, 2}, {0, 3}};
class Solution {
private:
    vector<vector<int>> grid;
    vector<vector<bool>> vis;
    int n, m;
public:
    bool check(int x, int y) {
        return (x < 0 || n <= x || y < 0 || m <= y);
    }
    bool search(int x, int y) {
        if(x == n - 1 && y == m - 1) return true;
        vis[x][y] = true;
        int t = grid[x][y] - 1;
        for(int i = 0; i < 2; i++) {
            int dx = x + dt[0][nex[t][i]], dy = y + dt[1][nex[t][i]];
            if(check(dx, dy) || vis[dx][dy]) continue;
            int t_ = grid[dx][dy] - 1;
            for(int j = 0; j < 2; j++) {
                int dx_ = dx + dt[0][nex[t_][j]], dy_ = dy + dt[1][nex[t_][j]];
                if(dx_ == x && dy_ == y && search(dx, dy)) return true;
            }
        }
        return false;
    }
    bool hasValidPath(vector<vector<int>>& grid) {
        this->grid.assign(grid.begin(), grid.end());
        this->n = grid.size();
        this->m = grid[0].size();
        vis = vector<vector<bool>> (n, vector<bool> (m));
        return search(0, 0);
    }
};

最长快乐前缀

「快乐前缀」是在原字符串中既是 非空 前缀也是后缀(不包括原字符串自身)的字符串。

给你一个字符串 s,请你返回它的 最长快乐前缀

如果不存在满足题意的前缀,则返回一个空字符串。

示例 1:

输入:s = "level"
输出:"l"
解释:不包括 s 自己,一共有 4 个前缀("l", "le", "lev", "leve")和 4 个后缀("l", "el", "vel", "evel")。最长的既是前缀也是后缀的字符串是 "l" 。

示例 2:

输入:s = "ababab"
输出:"abab"
解释:"abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

示例 3:

输入:s = "leetcodeleet"
输出:"leet"

示例 4:

输入:s = "a"
输出:""

提示:

  • 1 <= s.length <= 10^5
  • s 只含有小写英文字母
题解

字符串哈希,构造哈希函数后,可以遍历前缀(从长到短),然后判断后缀是否相同。

时间复杂度:\(O(n)\)

const int N = 1E5 + 10, P = 233;
class Solution {
public:
    unsigned long long h[N], xp[N];
    unsigned long long getVal(int x, int y) {
        return h[y] - h[x - 1] * xp[y - x + 1];
    }
    string longestPrefix(string s) {
        int l = s.length();
        xp[0] = 1, h[1] = s[0];
        for(int i = 2; i <= l; i++) {
            h[i] = h[i - 1] * P + s[i - 1];
            xp[i - 1] = xp[i - 2] * P;
        }
        for(int k = l - 1; 1 <= k; k--) {
            if(getVal(1, k) == getVal(l - k + 1, l))
                return s.substr(0, k);
        }
        return "";
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注