算法笔记

HJ65 查找两个字符串a,b中的最长公共子串

#动态规划 查找两个字符串a,b中的最长公共子串

HJ66 配置文件恢复

配置文件恢复

有思路，未做

HJ70 矩阵乘法计算量估算

矩阵乘法计算量估算

已看答案，题目输入应该会保证所有括号优先级

比如 A(BC)(DE)F, 不会有ABC(DE)这种

HJ71 字符串通配符

#动态规划 可解 字符串通配符

转移方程：

• 基础部分

dp[0, 0] = 1;
dp[i, 0] = dp[i-1, 0] && (ch[i-1] == '*');
dp[0, j] = 0;

• dp[i, j]分情况:
  • ch == '*' 时, dp[i, j] = dp[i-1, j] || dp[i, j-1]
  • ch == '?' 时, dp[i, j] = dp[i-1, j-1]
  • ch1 == ch2 时, dp[i, j] = dp[i-1, j-1]

HJ77 火车进站

#深度优先搜索 火车进站

思路：

大致上视dfs为调度函数，每次调度可以进行进站和出站两个操作

stack<int> station;    // 站内火车栈表
deque<int> in;        // 等待进站火车队列
vector<int> out;    // 已出站火车队列

// 火车调度函数，每次调度只有两种情况：进站或出站
void schedule(deque<int> & in, vector<int> & out, stack<int> & station)
{
    if (in.empty() && station.empty()) {
        answer.push_back(out);
        return;
    }
 
    //进站分支
    if (!in.empty()) {
        // 保护现场
        auto temp = in.front();
 
        // 进站
        station.push(in.front());
        in.pop_front();
        schedule(in, out, station);
 
        // 还原现场
        in.push_front(temp);
        station.pop();
    }
 
    //出站分支
    if (!station.empty()) {
        // 保护现场
        auto temp = station.top();
 
        //出站
        out.push_back(station.top());
        station.pop();
        schedule(in, out, station);
 
        // 还原现场
        out.pop_back();
        station.push(temp);
    }
}

HJ93 数组分组

数组分组

import java.util.Scanner;
/* 构建二叉决策树，分别将每个元素划分到两个分组中
    利用递归实现 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }

            System.out.println(ParEqu(arr, 0, 0, 0));
        }

        in.close();
    }

    public static boolean ParEqu(int[] arr, int sum5, int sum3, int i) {

        if (i >= arr.length) {
            return sum5 == sum3;
        }

        if (arr[i] % 5 == 0) {
            return ParEqu(arr, sum5 + arr[i], sum3, i + 1);
        } else if (arr[i] % 3 == 0) {
            return ParEqu(arr, sum5, sum3 + arr[i], i + 1);
        } else {
            return ParEqu(arr, sum5 + arr[i], sum3, i + 1) || ParEqu(arr, sum5, sum3 + arr[i], i + 1);
        }
    }
}