动态规划问题(十四)自动换行问题

时间:2021-09-11 15:32:08   收藏:0   阅读:18

动态规划问题(十四)自动换行问题

问题描述

? 给你一系列的单词,现在要把这些单词放到文本域里,为了美观,要求将这些单词进行换行处理。现在已知每一行的宽度 width,求将这些单词放入文本域之后最少会浪费多少个单位字符的宽度(注意,单词与单词之间的间隔空格不算在其中),假定每个单词的宽度小于行的宽度。

? 例如,对于输入的单词序列:{"Geeks", "for", "Geeks", "presents", "word", "wrap", "problem"},每一行的宽度 width = 15, 那么最佳的排列方式为:

Geeks for Geeks
presents word  
wrap problem   

? 由于第二行和第三行分别浪费了 2 个和 3个字符,因此最少需要浪费 5 个字符的空间。

解决思路

? 参考:https://zh.wikipedia.org/wiki/自动换行

实现自动换行的两种算法:

实现

? 由于能力有限,以下代码来自 https://www.geeksforgeeks.org/word-wrap-problem-dp-19/

public class Solution {
    private void wrapLine(String[] words, final int width) {
        int N = words.length;

        int[] l = new int[N];
        for (int i = 0; i < N; i++) {
            l[i] = words[i].length();
        }

        final int[][]   lc      =   new int[N + 1][N + 1];
        // 记录插入 i-j 的元素后的可用空间
        final int[][]   extra   =   new int[N + 1][N + 1];
        final int[]     C       =   new int[N + 1];
        // 用于打印结果
        final int[]     p       =   new int[N + 1];

        for (int i = 1; i <= N; i++) {
            extra[i][i] = width - l[i - 1];
            for (int j = i + 1; j <= N; j++) {
                extra[i][j] = extra[i][j - 1] - l[j - 1] - 1;
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                if (extra[i][j] < 0) { 
                    lc[i][j] = Integer.MAX_VALUE;
                } else if (j == N && extra[i][j] >= 0) { // 刚好填满行的情况
                    lc[i][j] = 0;
                } else {
                    lc[i][j] = extra[i][j] * extra[i][j];
                }
            }
        }

        C[0] = 0;
        for (int j = 1; j <= N; j++) {
            C[j] = Integer.MAX_VALUE;
            for (int i = 1; i <= j; i++) {
                if (
                        C[i - 1] != Integer.MAX_VALUE
                                && lc[i][j] != Integer.MAX_VALUE
                                && C[i - 1] + lc[i][j] < C[j]
                ) {
                    C[j] = C[i - 1] + lc[i][j];
                    p[j] = i;
                }
            }
        }

        printSolution(words, p, N);
    }

    private int printSolution(String[] words, int[] p, int n) {
        int k;
        if (p[n] == 1)
            k = 1;
        else
            k = printSolution(words, p, p[n] - 1) + 1;

        for (int i = p[n]; i <= n; i++) {
            System.out.print(words[i - 1] + " ");
        }
        System.out.println();

        return k;
    }
}

参考:

原文:https://www.cnblogs.com/FatalFlower/p/15251842.html

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!