每日刷题——相遇、宝石(模拟+数学)、相助(模拟+数组)、相依(dp的优化)

简介: 每日刷题——相遇、宝石(模拟+数学)、相助(模拟+数组)、相依(dp的优化)

相遇

原题链接登录—专业IT笔试面试备考平台_牛客网

题目描述

运行代码

#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a==b)
{ 
    cout<<"p";
} 
else if(a - b == 1 || (a == 1 && b == 3))
    {
        cout << "b";
    }
else 
{
    cout<<"a";
}
    return 0;    
}
 

代码思路

分析输赢情况,总结输出结果即可

宝石(模拟+数学)

原题链接登录—专业IT笔试面试备考平台_牛客网

题目描述

运行代码

#include<iostream>
#include<string.h>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b;
if(b<=2*a)
{
c=5*b+a;
}
else 
{
    c=11*a;
} 
    cout<<c<<endl;
    return 0;
}

代码思路

数学情况总结,观察路段最短路线

相助(模拟+数组)

原题链接登录—专业IT笔试面试备考平台_牛客网

题目描述

运行代码

#include<iostream>
using namespace std;
const int N = 5e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(n==1){
        cout<<"-1"<<endl;
        return 0;
    }
    if(a[1]==a[n])
    {
        cout<<1<<endl;
        return 0;
    }
    for(int i=2;i<n-1;i++){
        if(a[1]==a[i]&&a[i+1]==a[n])
        {
            cout<<"2"<<endl;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

代码思路

对给定的数据进行遍历查找,尝试找到两个相邻的相同元素,然后删除这两个元素。代码首先检查首尾两个元素是否相等,若相等则输出2即可;接着从第二个元素开始遍历,寻找与首尾相同的元素,若找到则输出2;如果没有找到任何符合条件的组合,则输出-1。

相依(dp的优化)

原题链接:登录—专业IT笔试面试备考平台_牛客网

题目描述

运行代码

#include <iostream>
#include<vector>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr); 
  int t = 1;
  while (t--) {
    int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<int> dp(n + 1, -1);
  vector<int> st(n + 1, -1);  
  dp[0] = 0;
  st[a[1]] = 1;
  for (int i = 2; i <= n; i++) {
    int x = st[a[i]];
    if (x != -1 && dp[x - 1] != -1) {
      dp[i] = dp[x - 1] + 1;      
      if (dp[i - 1] != -1 && dp[i - 1] < dp[x - 1]) {
        st[a[i]] = i;
      }
    } else {
      st[a[i]] = i;
    }
  } 
  cout << dp[n] << "\n";
  } 
  return 0;
}

代码思路

通过动态规划来求解最小的操作次数。首先,代码定义了一个名为dp的向量,用来存储每个位置上的最小操作次数。同时,还有一个名为st的向量,用来记录每个元素最近被删除的位置。st向量的值为-1表示该元素尚未被删除。

接下来,代码从第二个元素开始遍历整个数组。在遍历过程中,代码会比较当前位置的元素与之前元素的值,如果相等,说明可以通过删除一段区间内的元素来使数组变为空。此时,代码会更新dp向量,并将当前元素的索引存入st向量中。

需要注意的是,在遍历过程中,代码还会检查当前元素的前一个元素是否比当前元素的最小操作次数少。如果是的话,代码会更新st向量,以便反映新的最小操作次数。

最后,代码输出dp[n],即数组变为零的最小操作次数。如果无法使数组变为零,dp[n]的值将会是-1。

目录
打赏
0
1
1
0
26
分享
相关文章
|
4月前
|
Leecode第十六题(最接近的三数之和)
这篇文章介绍了LeetCode第16题“最接近的三数之和”的题目要求、解题思路和代码实现,该算法题目要求从给定的整数数组中找出三个数,使它们的和最接近给定的目标值。
77 0
|
9月前
|
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
53 1
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
【错题集-编程题】合唱团(动态规划 - 线性 dp)
【错题集-编程题】合唱团(动态规划 - 线性 dp)
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
|
9月前
|
每天一道C语言编程(3):有规律的数列输出
每天一道C语言编程(3):有规律的数列输出
78 0
[leetcode] 1675. 数组的最小偏移量 | 思维贪心 | 大疆笔试题
[leetcode] 1675. 数组的最小偏移量 | 思维贪心 | 大疆笔试题
128 0
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
166 0
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法