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。
输出格式
一个数，表示答案。
样例输入
31 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;}};
版权归原作者 你好_Ä 所有， 如有侵权，请联系我们删除。