[数据结构与算法]LeetCode每日一题-063

LeetCode每日一题 —— 063

今天的每日一题依然是一个hard的题目，感到十分的头秃呀，不过所幸今天的题目其实还蛮简单的，就是久违地去排了好久自己的bug，有点怀念大一的时候天天排bug的时光了

题目介绍

题目链接： 68. 文本左右对齐 - 力扣（LeetCode） (leetcode-cn.com)


大概就是就是类似于我们的Word平时在干的自动换行的内容的一个简单的算法，虽然是Hard，但本质上比较简单。

算法分析

我的算法主要分为两部分，分别是对单词进行分组和添加空格。

但在实际操作的时候需要一定的处理。
下图为单词分组流程。

下图为添加空格流程，由于题目要求的左侧可以比右侧的空格多，计算时多计算一个需要多添加一个空格的空隙。

代码实现

这个不是我传在LeetCode上的代码，是用来本地测试的，因为在线跑比较慢，理解一下就好。

#include <iostream>
#include <vector>

using namespace std;

void checkpoint(int num){
    cout << "checkpoint" << num <<endl;
}

template<typename T> void show_vector(vector<T> & v,char endchar = ' ')
{
    for(int i  = 0 ; i < v.size() ; i++){
        cout << v[i] << v[i].size() << endchar;
    }
    cout << endl;
}


vector<string> fullJustify(vector<string>& words, int maxWidth) {
    //devide
    int count = 0; //count the number of characters
    vector<pair<int,int>> devide_points;    //前面存位置，后面存数量
    devide_points.push_back(make_pair(0,0));
    vector<string> result;
    //首先划分出来需要分割的位置，如 1 2 3 割为 1 2   3 时，入栈数字为2

    // cout << "开始分割" << endl;
    for(int i = 0; i < words.size(); i++){
        count += words[i].size();
        // count > maxWidth 表示长度超过限制
        if(count > maxWidth){
            devide_points.push_back(make_pair(i,count - words[i].size()));
            count = words[i].size();
        }
        count++;
    }
    devide_points.push_back(make_pair(words.size(),count));

    // cout << "分割结束 结果：" << devide_points.size() <<endl;
    //划归入新的vector里，并计算空格
    int nowarg = 0; //现在指向的词的下标
    
    //添加空格 构建新的vector
    for(int i = 1 ; i < devide_points.size() - 1; i++){
        //计算需要有多少空格
        // cout << "第" << i << " 次计算空格" << endl;
        int words_num = 0, total_count = 0; //num of words
        words_num = devide_points[i].first - devide_points[i - 1].first; //计算位置差（有几个单词）
        total_count = devide_points[i].second - words_num;//计算一个空格后的字符

        //计算
        int space_num = (maxWidth - total_count)/((words_num - 1)?words_num - 1:1);
        int residue = (maxWidth - total_count)%((words_num - 1)?words_num - 1:1);
        cout << residue << ' ' <<  space_num << endl;
        // cout << "residue = " << residue << endl;
        // cout << "第" << i << " 次添加空格" << endl;
        
        string temp_string = words[nowarg++]; //保存当前一行数据
        //对于只有一个单词的项目的修正
        if(words_num == 1) 
            for(int times = 0; times < space_num ; times++) temp_string += " ";

        for(;nowarg < devide_points[i].first ; nowarg++){
            for(int times = 0; times < space_num ; times++) temp_string += " ";
            if(residue) temp_string += " ", residue-- ;
            temp_string += words[nowarg];
        }
        // cout << "添加空格结束" << endl;

        result.push_back(temp_string);
    }
    string temp_string = words[nowarg++];
    for(;nowarg < words.size() ; nowarg++){
            temp_string += " ";
            temp_string += words[nowarg];
        }
    int residue = maxWidth - temp_string.size();
    while(residue--) temp_string += ' ';
    result.push_back(temp_string);
    return result;
}

int main()
{
    int width = 16;
    vector<string> words = {"What","must","be","acknowledgment","shall","be"};
    vector<string> sentences(fullJustify(words,width));
    cout << "执行完成" << endl;
    show_vector(sentences,'\n');
}