【每日刷题】Day169
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 718. 最长重复子数组 - 力扣（LeetCode）
2. 2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）
3. [蓝桥杯 2013 省 AB] 错误票据 - 洛谷
1. 718. 最长重复子数组 - 力扣（LeetCode）
//思路：动态规划
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{
int n = nums1.size(),m = nums2.size(),ans = 0;
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i = n-1;i>=0;i--)
{
for(int j = m-1;j>=0;j--)
{
if(nums1[i]==nums2[j])
dp[i][j] = dp[i+1][j+1]+1;
ans = ans>dp[i][j]?ans:dp[i][j];
}
}
return ans;
}
};
2. 2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）
//思路：滑动窗口
//维护一个长度为 k 的滑动窗口，判断窗口内的值能否整除 num 即可
class Solution {
public:
int divisorSubstrings(int num, int k)
{
int nums = num,ans = 0;
vector<int> arr;
while(num)//将 num 每一位拆开
{
arr.push_back(num%10);
num/=10;
}
int size = arr.size();
string btf;
int left = size-1,right = size-1;
while(right>=0)
{
btf+=(arr[right]+'0');
if(btf.size()==k)//维护长度为 k 的窗口
{
int tmp = stoi(btf);
if(tmp&&nums%tmp==0) ans++;//判断能否整除
left--;
btf.erase(btf.begin());
}
right--;
}
return ans;
}
};
3. [蓝桥杯 2013 省 AB] 错误票据 - 洛谷
//思路：二进制求和
//本题思路与 Day167 中的 "寻找重复数" 完全一样，本题除了需要找出重复数，还需要找到缺失的数字。寻找缺失的数字的思路与寻找重复数字的思路一样。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> arr;
int val = 0;
while (cin>>val) arr.push_back(val);
unordered_map<int, int> ma1;//使用hash表来帮助我们记录二进制每一位为1的个数
unordered_map<int, int> ma2;int min = 2147483647, max = -2147483648, size = arr.size();
for (int i = 0; i < size; i++)
{
ma1[arr[i]]++;
min = min < arr[i] ? min : arr[i];//定位最小最大值，找出最小最大值组成的完整区间，用于找出重复数与缺失数
max = max > arr[i] ? max : arr[i];
}
for (int i = min; i <= max; i++) ma2[i]++;//记录最小最大值组成的完整区间内所有数字的每一位二进制位上1的个数int n = 0, m = 0;
for (auto pa : ma2)
{
int first = pa.first;
if (ma1.find(first) == ma1.end()) m = first;//缺失的二进制位就是缺失数字对应位置为1
else if (ma1[first] > ma2[first]) n = first;//同理，多出的二进制位就是多出数字对应位置为1
}cout << m << " " << n;
return 0;
}
