Google Onsite 9/23

whyvic13 发表于 2016-10-4 06:38
是要split放的，就是剩下的空间不够放下一整个sentence就要找最长的可能性把subsentence放进去，split是 ...

那直接先SPLIT然后用LC TEXT JUSTIFICATION方法做行么

whyvic13 发表于 2016-10-4 06:35
是有限制的，假设m远大于sentence长度

👍，这样可以基于sentence建一个转移矩阵，O(1)时间能算出来split的位置以及带到下一行的长度。总的时间复杂度应该是O(n)。

virpro 发表于 2016-10-5 06:53
👍，这样可以基于sentence建一个转移矩阵，O(1)时间能算出来split的位置以及带到下一行的长度。总 ...

你好，能详细讲讲怎么做吗

sunnyroom 发表于 2016-10-5 09:54
你好，能详细讲讲怎么做吗

简单写了一下code

    public int sentencesToFillAMatrix(int m, int n, String sentence) {
        int[] splits = new int[sentence.length()];
        int j = 0;
        for (int i = 0; i < sentence.length(); i++) {
            if (sentence.charAt(i) == ' ')
                j = i;
            splits[i] = j;
        }
        int carry = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            int len = m;
            if (carry != 0) {
                len = m - carry - 1;
                count++;
            }
            count += (len+1) / sentence.length();
            int left = (len+1) % sentence.length();
            if (splits[left] != 0) {
                carry = sentence.length() - left - 1;
            } else
                carry = 0;
        }
        return count;
    }

virpro 发表于 2016-10-5 11:46
简单写了一下code

    public int sentencesToFillAMatrix(int m, int n, String sentence) {

太感谢了

还想问一下楼主，第四题怎么用STACK做？比如STACK顶端如果不比自己大怎么办，那就要POP掉找第一个比自己大的？那这个和直接遍历复杂度差不多吧

liurudahai 发表于 2016-10-11 04:44
还想问一下楼主，第四题怎么用STACK做？比如STACK顶端如果不比自己大怎么办，那就要POP掉找第一个比自己大 ...

你可以用个例子跑一下比如：9,8,7,6,5,4,3,2,1,10,1,2,3,4,5,6...时间复杂度写一下就知道了，是O(n)的

whyvic13 发表于 2016-10-4 06:38
是要split放的，就是剩下的空间不够放下一整个sentence就要找最长的可能性把subsentence放进去，split是 ...

我怎么突然觉得这题就是text justification 那题，不过有几个区别，第一个这题就是那个句子SPLIT的单词，要反复重复放，直到整个矩阵放满，第二个text justification 如果有多余的空格，是要从前往后多加空格，但这个是每个单词之间就是1个空格（根据句子来），然后剩下的空格都放在末尾。 比如Jack and Jim kkkkkkkkkkkkk，最后比如那个kkkkkkkkkkkkk放不下了，就要放在下一行，但比如离宽度还差5个空格，Jack和and之间还是必须只保留一个空格，剩下的5个空格都放在末尾

补充内容 (2016-10-12 13:03):
没注意看楼主的要求，貌似这个太慢了

补充内容 (2016-10-12 13:17):
看了一下，楼上那个vipro的方法很巧妙，应该是对的

第二轮是不是其实就是topological sort的做法

qiuxuxing007 发表于 2016-10-12 13:15
第二轮是不是其实就是topological sort的做法

对的，就是拓扑排序