2022-03-17每日刷题打卡

2022-03-17每日刷题打卡

力扣春季赛开始啦，佬们求求给战队点个赞吧：啊哈哈哈AC来咯

代码源——每日一题

快快变大 - 题目 - Daimayuan Online Judge

给定一个长度为 n 的数组 a1,a2,…,an，接下来进行 n−1 次操作。每次选择一个下标 xx ，将 ax 和 ax+1 合并成 (ax)×(ax+1)mod1000003 ，并且你会获得 (ax−ax+1)^2 的分数。

所以每次操作后，数组的长度将会减 1，当最后只剩下一个元素时停止操作。输出最终能获得的最大分数。

输入格式

第一行一个数字 n。

接下来一行 n 个整数 a1,a2,…,an。

输出格式

一个数，表示答案。

样例输入

3
1 2 3

样例输出

26

数据规模

所有数据保证 1≤n≤300,1≤ai≤10^6

今天这道题其实是我投的哦哼哼哼（叉腰）。

区间dp，这题做法和石子合并 - 题目 - Daimayuan Online Judge基本一样，如果没写过石子合并题可以来2月14每日打卡-CSDN博客这看下我以前写的题解。

我们先用一个二维数组预处理下各个区间的乘积和，s[i] [j]的意思是ai到aj的乘积。用一个二维动规数组f来做区间dp，dp[i] [j]意思是合并i到j可以得到的最大分数。然后我们从长度2开始枚举区间长度，来获得每个区间所能得到的最大分数。最后答案就是dp[1] [n]，状态转移方程：

 f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + (s[i][k]-s[k+1][j])* (s[i][k] - s[k + 1][j]));

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 1010, MOD = 1000003;
ll f[N][N], s[N][N],v[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        s[i][i] = 1;
        s[i][i-1] = 1;
        for (int j = i; j <= n; j++)
        {
            s[i][j] = (v[j] * s[i][j - 1]) % MOD;
        }
    }
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            for (int k = i; k < j; k++)
            {
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + (s[i][k]-s[k+1][j])* (s[i][k] - s[k + 1][j]));
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

飞书——每日一题

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

我们已经知道了，数组原本是有序的，但是经过了旋转变换。经过变换后数组实际上还是有序的，但是是分成了两部分，比如样例给的3 4 5 1 2，原本是1 2 3 4 5，经过旋转后变成了3 4 5 1 2，但我们把它分成两部分后就可以发现，35仍然是有序的，12也是有序的，我们可以找到两个相邻的点，使得数组从他们中间分成两个有序的部分，而这两个个分界点就是数组的最大值和最小值。我们可以用二分来找这两个点。

我们可以先取中间的点，然后看左半边是否是递增序，如果有序，就说明我们要找到点不在左半边，反之在左半边。就这样一直二分，最后找到的就是我们要的分界点了。

比如 5 6 7 8 9 1 3，我们第一次取得中点是8，左边是58，是递增有序的，右边是83，不是递增的，说明分界点在右边，然后我们再找点就是9，再看左边是有序右边无序，再去右边找；下个点是1，右边有序左边无序，去左边找，最后找到的就是我们要的点了。（二分写的不习惯，我找到的是最大值，但因为最大值和最小值挨着，所有我可以在最大值后面找到最小值，如果佬们二分写的好一个不会有这问题，毕竟思路没问题）

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size();
        int l=0,r=n-1;
        if(n==1||nums[(n-1)]>nums[0])return nums[0];
        else
        {
            
            while(l<r)
            {
                int mid=(l+r)/2;
                if(nums[l]<nums[mid])l=mid;
                else r=mid;
            }
        }
        return nums[l+1];
    }
};

力扣——每日一题

720. 词典中最长的单词 - 力扣（LeetCode） (leetcode-cn.com)

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

示例 1：

输入：words = [“w”,“wo”,“wor”,“worl”, “world”]
输出：“world”
解释： 单词"world"可由"w", “wo”, “wor”, 和 "worl"逐步添加一个字母组成。

我们先用哈希表记录每个单词的出现情况，然后再遍历数组枚举每个字符，并且把每个字符从尾部开始一个个去掉字母，每次去掉都判断是否在哈希表有记录，如果知道拆完都有记录那就说明这个字符串符合条件，然后记录下来，并在此过程中维护最长，字典序最小的那个。

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_map<string,int>mymap;
        string str;
        for(auto i:words)
            mymap[i]++;
        for(auto i:words)
        {
            if(i.size()>=str.size())
            {
                bool flag=true;
                string s=i;
                s.pop_back();
                while(s.size()!=0&&flag)
                {
                    
                    if(mymap[s]==0)
                    {
                        flag=false;
                    }
                    s.pop_back();
                }
                if(flag)
                {
                    if(i.size()>str.size())str=i;
                    else str=i>str?str:i;
                }
            }
        }
        return str;
    }
};