【动态规划】【逆向思考】【C++算法】960. 删列造序 III

简介: 【动态规划】【逆向思考】【C++算法】960. 删列造序 III

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

动态规划汇总

LeetCode960. 删列造序 III

给定由 n 个小写字母字符串组成的数组 strs ,其中每个字符串长度相等。

选取一个删除索引序列,对于 strs 中的每个字符串,删除对应每个索引处的字符。

比如,有 strs = [“abcdef”,“uvwxyz”] ,删除索引序列 {0, 2, 3} ,删除后为 [“bef”, “vyz”] 。

假设,我们选择了一组删除索引 answer ,那么在执行删除操作之后,最终得到的数组的行中的 每个元素 都是按字典序排列的(即 (strs[0][0] <= strs[0][1] <= … <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= … <= strs[1][strs[1].length - 1]) ,依此类推)。

请返回 answer.length 的最小可能值 。

示例 1:

输入:strs = [“babca”,“bbazb”]

输出:3

解释:

删除 0、1 和 4 这三列后,最终得到的数组是 strs = [“bc”, “az”]。

这两行是分别按字典序排列的(即,strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1])。

注意,strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。

示例 2:

输入:strs = [“edcba”]

输出:4

解释:如果删除的列少于 4 列,则剩下的行都不会按字典序排列。

示例 3:

输入:strs = [“ghi”,“def”,“abc”]

输出:0

解释:所有行都已按字典序排列。

提示:

n == strs.length

1 <= n <= 100

1 <= strs[i].length <= 100

strs[i] 由小写英文字母组成

动态规划

逆向思考:最少删除就是最多保留。

动态规划的状态表示

dp[i]表示,以第i列结尾的最长序列的最长长度。

## 动态规划的的转移方程

dp[i] =Maxj = 0 : i − 1 全部第 i 列大于等于第 j 列 \Large_{j=0:i-1}^{全部第i列大于等于第j列}j=0:i1全部第i列大于等于第j(pre[j+1)

代码

核心代码

class Solution {
public:
  int minDeletionSize(vector<string>& strs) {
    m_c = strs.front().size();
    vector<int> dp(m_c,1);
    for (int i = 1; i < m_c; i++)
    {
      for (int j = 0; j < i; j++)
      {
        if (GreateEqual(strs, i, j))
        {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
    return strs[0].length()- *max_element(dp.begin(),dp.end());
  }
  bool GreateEqual(const vector<string>& strs, int i,int j)
  {
    for (const auto& s : strs)
    {
      if (s[i] < s[j])
      {
        return false;
      }
    }
    return true;
  }
  int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  vector<string> strs;
  {
    Solution sln;
    strs = { "abbba" };
    auto res = sln.minDeletionSize(strs);
    Assert(res, 1);
  }
  {
    Solution sln;
    strs = { "babca", "bbazb" };
    auto res = sln.minDeletionSize(strs);
    Assert(res,3);
  }
  {
    Solution sln;
    strs = { "edcba" };
    auto res = sln.minDeletionSize(strs);
    Assert(res, 4);
  }
  {
    Solution sln;
    strs = { "ghi","def","abc" };
    auto res = sln.minDeletionSize(strs);
    Assert(res, 0);
  }
  
}

2023年1月版

class Solution {

public:

int minDeletionSize(vector& strs) {

m_r = strs.size();

m_c = strs[0].length();

vector dp(m_c, 1);

for (int i = 0; i < m_c; i++)

{

for (int j = i + 1; j < m_c; j++)

{

bool bVilid = true;

for (int k = 0; k < m_r; k++)

{

if (strs[k][i] > strs[k][j])

{

bVilid = false;

}

}

if (bVilid)

{

dp[j] = max(dp[j], dp[i] + 1);

}

}

}

return m_c - *std::max_element(dp.begin(), dp.end());

}

int m_r;

int m_c;

};

2023年7月

class Solution {

public:

int minDeletionSize(vector& strs) {

m_r = strs.size();

m_c = strs[0].size();

//换过解法: 保留最多列 pre[i]表示以i结尾能保留多少列

vector pre;

for (int i = 0; i < m_c; i++)

{

int iMaxHas = 1;

for (int j = 0; j < pre.size(); j++)

{

bool bCan = true;

for (int r = 0; r < m_r; r++)

{

if (strs[r][i] < strs[r][j])

{

bCan = false;

}

}

if (bCan)

{

iMaxHas = max(iMaxHas, pre[j] + 1);

}

}

pre.emplace_back(iMaxHas);

}

return m_c - *std::max_element(pre.begin(), pre.end());

}

int m_r, m_c;

};


目录
打赏
0
1
1
0
36
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
3月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
90 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等