【Java算法】模拟

 🔥个人主页： 中草药 

 🔥专栏：【算法工作坊】算法实战揭秘

🧣 一.模拟算法

        模拟算法和传统的算法有一些不同之处，更多的是对题目要求的理解，通过代码的方式去模拟实现一道题目在现实中的实现方法，比较直观通俗易懂，比较直线的去推导某个流程，完整的实现了求解的过程，我个人认为这就是部分题暴力算法

        模拟算法是一种通过逐步模拟现实世界中的过程或系统行为来解决问题的方法。这种算法通常用于那些可以通过一系列明确步骤来描述其行为的场景。模拟算法可以应用于各种领域，包括物理模拟、经济建模、交通流量分析、游戏开发等。

基本步骤

1. 定义问题：

   • 明确你要模拟的系统或过程是什么。
   • 确定模拟的目标，即通过模拟你想获得什么结果。

2. 建立模型：

   • 设计一个抽象模型来表示系统的行为。
   • 定义系统的状态和影响状态变化的各种因素。
   • 确定状态变化的规则和条件。

3. 初始化状态：

   • 设置模拟的初始状态。
   • 确定初始条件和参数。

4. 执行步骤：

   • 通过一系列预定的步骤来逐步推进模拟过程。
   • 每一步根据模型中定义的规则更新系统状态。

5. 终止条件：

   • 设定模拟结束的条件。
   • 当达到终止条件时停止模拟。

6. 分析结果：

   • 收集模拟过程中产生的数据。
   • 分析数据以获取有用的信息或结论。

案例

交通流量模拟

假设我们要模拟一条街道上的车流量，并评估不同交通信号灯配置的效果。

1. 定义问题：

   • 目标是找到最优的信号灯配置，以减少交通拥堵。

2. 建立模型：

   • 模型包括街道长度、车辆进入频率、信号灯位置和切换周期等参数。
   • 规则包括车辆前进、停止、转弯等行为。

3. 初始化状态：

   • 设置初始时间、车辆数量和位置。
   • 设置信号灯的初始状态（红或绿）。

4. 执行步骤：

   • 每个时间步长更新车辆的位置。
   • 根据信号灯状态决定车辆是否停止。
   • 模拟车辆到达和离开路口。

5. 终止条件：

   • 当所有车辆都通过了模拟区域后停止模拟。

6. 分析结果：

   • 计算总的等待时间和平均速度。
   • 分析不同信号灯配置下的效果差异。

优点和缺点

优点

• 灵活性：可以模拟复杂系统的行为。
• 可控制性：可以通过调整参数来研究不同条件下的结果。
• 可视化：模拟结果可以直观展示，便于理解和沟通。

缺点

• 性能瓶颈：大规模模拟可能需要较长的运行时间和较大的计算资源。
• 精确度依赖于模型：模型的准确性直接影响模拟结果的可靠性。
• 难以捕捉所有细节：实际系统可能比模拟模型更为复杂，某些因素可能无法完全建模。

👗二. 1576.替换所有问号

题目链接：1576.替换所有问号

代码

 public String modifyString(String s) {
        char[] ch=s.toCharArray();
        for(int i=0;i<ch.length;i++){
            if(ch[i]=='?'){
                for(char tmp='a';tmp<='z';tmp++){
                    //注意这个if条件 十分巧妙 做了边界情况的处理
                    if((i==0||tmp!=ch[i-1])&&(i==ch.length-1||tmp!=ch[i+1])){
                        ch[i]=tmp;
                        break;
                        //有一个符合条件的结果即可break跳出循环
                    }
                }
            }
        }
        return new String(ch);
    }

算法原理 

这道题，模拟起来非常简单，for循环遍历24个字母，来反复推导，其中 if 语句的设置十分巧妙，做了边界处理，优化了模拟算法的全过程

遍历字符数组： 

for (int i = 0; i < ch.length; i++) {
    if (ch[i] == '?') {
        // 处理 '?' 字符
    }
}

• 遍历字符数组 ch，找到所有的 '?' 字符，并进行替换。

替换 '?' 字符：

for (char tmp = 'a'; tmp <= 'z'; tmp++) {
    if ((i == 0 || tmp != ch[i - 1]) && (i == ch.length - 1 || tmp != ch[i + 1])) {
        ch[i] = tmp;
        break;
    }
}

• 对于每个 '?' 字符，尝试用 'a' 到 'z' 的所有小写字母进行替换。
• 使用一个内层循环，从 'a' 开始逐个尝试替换。
• 替换的条件是：
  • 当前位置 i 为字符串的第一个字符，或者 tmp 不等于前一个字符 ch[i - 1]。
  • 当前位置 i 为字符串的最后一个字符，或者 tmp 不等于后一个字符 ch[i + 1]。
• 如果找到了一个符合条件的字符 tmp，就将 ch[i] 替换为 tmp 并退出内层循环。

• 将修改后的字符数组 ch 转换回字符串并返回。

为什么能保证替换后的字符不与相邻字符相同？

• 边界条件处理：

  • 当 i 为0时，即当前位置为字符串的第一个字符，只需检查 tmp 是否与后一个字符 ch[i + 1] 相同。
  • 当 i 为 ch.length - 1 时，即当前位置为字符串的最后一个字符，只需检查 tmp 是否与前一个字符 ch[i - 1] 相同。
  • 对于其他位置，需要同时检查前后字符。

• 逐个尝试替换：

  • 从 'a' 开始逐个尝试替换，如果某个字符 tmp 满足条件，则立即替换并退出内层循环。
  • 这样可以保证找到的第一个符合条件的字符 tmp 被使用，从而避免了不必要的替换。

🎒三. 495.提莫攻击

题目链接：495.提莫攻击

代码

public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret=0;
        for(int i=0;i<timeSeries.length-1;i++){
            int tmp=0;
            //算出每两个数的差值
            tmp=timeSeries[i+1]-timeSeries[i];
            if(tmp<=duration){
                ret+=tmp;
            }else{
                ret+=duration;
            }
        }
        return ret+=duration;
    }

算法原理

        为了方便理解此处运用到的模拟算法，可以将上述代码进行拓展，申请额外的空间来理解此问题

public int findPoisonedDuration1(int[] timeSeries, int duration) {
        int[] tmp=new int[timeSeries.length-1];
        for(int i=0;i<timeSeries.length-1;i++){
            //算出每两个数的差值
            tmp[i]=timeSeries[i+1]-timeSeries[i];
        }
        int ret=0;
        //判断差值
        for(int i=0;i<tmp.length;i++){
            if(tmp[i]<=duration){
                ret+=tmp[i];
            }else{
                ret+=duration;
            }
        }
        //最后加上最后一次中毒时间
        return ret+=duration;
    }

由于中毒时间 duration 是固定的，只要间隔时间小于等于它，只需在总时长加上，两次攻击间隔的时间，如果两次间隔时间大于它，只加上一次duration就行

遍历时间序列：

for (int i = 0; i < timeSeries.length - 1; i++) {
    ...
}

• 遍历时间序列 timeSeries 中的每个元素（除了最后一个元素）。

计算相邻攻击时间差：

int tmp = 0;
tmp = timeSeries[i + 1] - timeSeries[i];

• 计算相邻两次攻击之间的时间差 tmp。

判断攻击持续时间：

if (tmp <= duration) {
    ret += tmp;
} else {
    ret += duration;
}

• 如果相邻两次攻击之间的时间差 tmp 小于等于 duration，则说明第二次攻击发生在第一次攻击的持续时间内，因此攻击的总持续时间为两次攻击之间的时间差 tmp。
• 如果相邻两次攻击之间的时间差 tmp 大于 duration，则说明第二次攻击发生在第一次攻击结束后，因此攻击的总持续时间为 duration。

处理最后一次攻击：

return ret += duration;

• 最后一次攻击没有后续攻击，因此需要加上最后一次攻击的持续时间 duration。

为什么能计算出攻击的总持续时间？

• 攻击持续时间叠加：如果两次攻击之间的时间差小于等于 duration，则第二次攻击是在第一次攻击的持续时间内发生的，因此两次攻击的总持续时间为两次攻击之间的时间差。
• 独立攻击持续时间：如果两次攻击之间的时间差大于 duration，则两次攻击相互独立，每次攻击的持续时间为 duration。

👑四. 6.Z字形变换

题目链接：6.Z字形变换

代码

public String convert(String s, int numRows) {
        //处理边界情况
        if(numRows==1){
            return s;
        }
        int diff=2*numRows-2;
        StringBuilder stb=new StringBuilder();
        //处理第一行
        for(int i=0;i<s.length();i+=diff){
            stb.append(s.charAt(i));
        }
        //处理中间行
        for(int i=1;i<numRows-1;i++){
            //注意理解这里的for循环，以及内置条件
            for(int j=i,k=diff-i;j<s.length()||k<s.length();j+=diff,k+=diff){
                if(j<s.length()){
                    stb.append(s.charAt(j));
                }
                if(k<s.length()){
                    stb.append(s.charAt(k));
                }
            }
        }
        //处理最后一行
        for(int i=numRows-1;i<s.length();i+=diff){
            stb.append(s.charAt(i));
        }
        return stb.toString();
    }

算法原理

这道题的模拟相对比较复杂，需要将这个字符串拆解为三部分，第一行，中间行，最后一行三部分，然后总结每一行的规律，模拟这个填放的过程，并且算出间隔值diff用于辅助处理各个目标  额外，要处理边界情况

处理边界情况：

if (numRows == 1) {
    return s;
}

• 如果 numRows 为1，则不需要进行任何变换，直接返回原字符串 s。

初始化变量：

int diff = 2 * numRows - 2;
StringBuilder stb = new StringBuilder();

• 计算每行字符之间的间隔距离 diff，即每行字符的下标之差。
• 初始化一个 StringBuilder 对象 stb 用于构建新的字符串。

处理第一行：

for (int i = 0; i < s.length(); i += diff) {
    stb.append(s.charAt(i));
}

• 遍历字符串 s，每隔 diff 个字符取一个字符，这些字符属于第一行。

处理中间行：

for (int i = 1; i < numRows - 1; i++) {
    for (int j = i, k = diff - i; j < s.length() || k < s.length(); j += diff, k += diff) {
        if (j < s.length()) {
            stb.append(s.charAt(j));
        }
        if (k < s.length()) {
            stb.append(s.charAt(k));
        }
    }
}

• 对于中间的每一行，需要取两个位置的字符：一个在斜线上，另一个在斜线下方。
• 内层循环中，j 表示斜线上的字符位置，k 表示斜线下方的字符位置。
• 取 j 和 k 位置的字符，直到它们超出字符串长度。

处理最后一行：

for (int i = numRows - 1; i < s.length(); i += diff) {
    stb.append(s.charAt(i));
}

• 遍历字符串 s，每隔 diff 个字符取一个字符，这些字符属于最后一行。

为什么能实现“Z”字形排列？

• 每行字符的间隔：每行字符之间的间隔为 diff，即 2 * numRows - 2。
• 第一行和最后一行：第一行和最后一行的字符每隔 diff 个字符取一个。
• 中间行：中间行的字符需要在斜线和斜线下方两个位置取字符，这两个位置的间隔分别为 i 和 diff - i。

🧥五. 38.外观数列

题目链接：38.外观数列

代码

 public String countAndSay(int n) {
        String ret = "1";
        for (int i = 0; i < n - 1; i++) {
            int len = ret.length();
            StringBuilder stb = new StringBuilder();
            for (int left = 0, right = 0; right < len; ) {
                //为防止元素越界，注意while里面的条件
                while (right < len && ret.charAt(right) == ret.charAt(left)) {
                    right++;
                }
                stb.append(right - left);
                stb.append(ret.charAt(left));
                left = right;
            }
            ret = stb.toString();
        }
        return ret;
    }

算法原理 

个人认为 这道题可以类比斐波那契函数的那道题，都是模拟出这个外观函数的推导过程，算出第n个是什么，只需模拟出题目要求即可

初始化结果变量：

String ret = "1";

• 初始化结果字符串 ret 为 "1"，这是序列的第一项。

循环生成序列：

for (int i = 0; i < n - 1; i++) {
    ...
}

• 循环 n - 1 次，因为序列的第一项已经初始化为 "1"。

生成下一项：

int len = ret.length();
StringBuilder stb = new StringBuilder();
for (int left = 0, right = 0; right < len;) {
    while (right < len && ret.charAt(right) == ret.charAt(left)) {
        right++;
    }
    stb.append(right - left);
    stb.append(ret.charAt(left));
    left = right;
}
ret = stb.toString();

• 遍历当前字符串 ret，使用双指针 left 和 right 来确定连续相同字符的数量。
• 当 right 指针遇到不同的字符时，计算 right - left，这表示从 left 到 right 之间的相同字符的数量。
• 将字符数量和字符本身追加到 StringBuilder 对象 stb 中。
• 更新 left 指针为 right 指针，继续寻找下一个不同的字符。
• 将 StringBuilder 对象转换为字符串，并将其赋值给 ret，作为生成的下一项。

🎓六. 1419.数青蛙

题目链接：1419.数青蛙

代码

 public int minNumberOfFrogs(String croakOfFrogs) {
        String t="croak";
        int n=t.length();
        char[] croakOfFrog=croakOfFrogs.toCharArray();
        //这个哈希表用于作为解决问题
        int[] hash=new int[n];
        //这是一个哈希映射表，用来映射每个字符的下标
        HashMap<Character,Integer> map=new HashMap<>();
        //将映射表补充完整
        for(int i=0;i<n;i++){
            map.put(t.charAt(i),i);
        }

        for(char ch:croakOfFrog){
            //用一个if解决问题
            if(ch==t.charAt(0)){
                //若有青蛙完成呱呱，则可以进行下一次，由他去负责下一次呱呱
                if(hash[n-1]!=0){
                    hash[n-1]--;
                }
                hash[0]++;
            }else{
                int i=map.get(ch);
                if(hash[i-1]==0){
                    return -1;
                }
                hash[i-1]--;
                hash[i]++;
            }
        }
        //不符合要求
        for(int i=0;i<n-1;i++){
            if(hash[i]!=0){
                return -1;
            }
        }
        return hash[n-1];
    }

算法原理

这道题要理解清楚模拟的过程，需要两个哈希表，一个哈希表作为哈希映射表，用于记录 叫声 croak 每个字符对应的下标，另一个哈希表帮助我们来实现问题，具体模拟是，遍历字符串的每个字符 第一个字符进行特殊处理 首先判断最后一个字符 k 对应的value是否有值，有值代表，已经有青蛙完成了一次croak，可以进行下一次croak因此相当于从k处拿一只青蛙，去进行故 hash[n-1]-- hash[0]++ ,在遍历其他值是 如果它所对应的数的上一个的value值为0，则直接返回-1，因为不符合题目要求 若符合要求 hash[i-1]--;hash[i]++;在进行此工作之后，在最后遍历一次哈希表，如果除最后一个位置其他值的value值不为0，则代表有冗余，直接返回-1

初始化变量：

String t = "croak";
int n = t.length();
char[] croakOfFrog = croakOfFrogs.toCharArray();
int[] hash = new int[n];
HashMap<Character, Integer> map = new HashMap<>();

• 初始化字符串 t 为 "croak"。
• 将输入字符串 croakOfFrogs 转换成字符数组 croakOfFrog。
• 初始化一个长度为5的整数数组 hash，用于记录 "croak" 每个字符的状态。
• 初始化一个 HashMap map，用于存储 "croak" 中每个字符对应的索引。

填充哈希映射表：

for (int i = 0; i < n; i++) {
    map.put(t.charAt(i), i);
}

• 将每个字符及其对应的索引存入 map 中。例如，'c' 对应索引0，'r' 对应索引1，等等。

遍历字符数组：

for (char ch : croakOfFrog) {
    if (ch == t.charAt(0)) {
        if (hash[n - 1] != 0) {
            hash[n - 1]--;
        }
        hash[0]++;
    } else {
        int i = map.get(ch);
        if (hash[i - 1] == 0) {
            return -1;
        }
        hash[i - 1]--;
        hash[i]++;
    }
}

• 遍历输入字符数组 croakOfFrog。
• 如果当前字符 ch 是 'c'（即 "croak" 的第一个字符），则：
  • 如果有青蛙已经完成了 "croak"，则将 hash[n - 1] 减1（表示一只青蛙完成了一次 "croak"）。
  • 将 hash[0] 加1（表示一只新青蛙开始发出 "croak"）。
• 如果当前字符 ch 不是 'c'，则：
  • 获取该字符对应的索引 i。
  • 如果 hash[i - 1] 为0，则返回 -1（表示不可能完成 "croak" 序列）。
  • 将 hash[i - 1] 减1，并将 hash[i] 加1（表示当前字符 ch 已经发出）。

检查最终状态：

for (int i = 0; i < n - 1; i++) {
    if (hash[i] != 0) {
        return -1;
    }
}
return hash[n - 1];

• 检查 hash 数组的前四个位置是否全部为0。如果不是，则返回 -1（表示不可能完成 "croak" 序列）。
• 返回 hash[n - 1]，即完成 "croak" 的青蛙数量。

为什么能计算出最少需要多少只青蛙？

• 状态记录：通过 hash 数组记录每个字符的状态，每个位置对应 "croak" 中的一个字符。
• 哈希映射：通过 map 快速查找每个字符对应的索引。
• 逻辑判断：通过判断当前字符是否为 'c' 或者是否符合 "croak" 序列的要求来更新状态。
• 最终状态检查：通过检查 hash 数组的最终状态来验证是否所有 "croak" 序列都被正确完成。