每日两题--20211127

每日两题--2021/11/27 1588. 所有奇数长度子数组的和

描述

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。

思路

1. 尝试寻找数组中每一个数相加的次数，及系数
2. 对于第1个元素的系数a[1] = n / 2 + n % 2，n为数组长度；
3. 对于第2个元素的系数a[2] = a[1] - 1 + (n- 1) / 2 + (n -1) % 2；
4. 不难得出，对于第i个元素的系数a[i] = a[i] = a[i - 1] - (i / 2 + i % 2) + (n- i) / 2 + (n- i) % 2;
5. 将对应元素值与其系数相乘再相加即可得出结果

题解

int sumOddLengthSubarrays(int* arr, int arrSize)
{
    int a[100] = {0};
    int sum = 0;

    a[0] = arrSize / 2 + arrSize % 2;

    for(int i = 1; i < arrSize; i++)
    {
        a[i] = a[i - 1] - (i / 2 + i % 2) + (arrSize - i) / 2 + (arrSize - i) % 2;
    }

    for(int i = 0; i < arrSize; i++)
    {
        sum += arr[i] * a[i];
    }

    return sum;

}

面试题 17.13. 恢复空格

描述

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!“已经变成了"iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

示例：

输入：
dictionary = [“looked”,“just”,“like”,“her”,“brother”]
sentence = “jesslookedjustliketimherbrother”
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。

提示：

0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

思路
  首先想到的是动态规划，因为要返回的最少未匹配的字符数，所以对于串sentence ，可以先定义前i个字符串最少未匹配的字符数，再算出前i+1个字符串最少未匹配的字符数，只需要找出其中的关系即可

1. 状态定义，dp[i]用来表示前i个字符串最少未匹配的字符数
2. 状态转移，接下来表示dp[i + 1]
3. 第i+1个字符串不管匹不匹配，先以不匹配处理，即dp[i + 1] = dp[i] + 1（后续如果匹配到了，但是匹配后未匹配字数更多了，则不如不匹配）
4. 如果刚好有第idx~i的字符串与字典中匹配，则取dp[idx]和dp[i]的中的小值，更新dp[i + 1]，即dp[i + 1] = math.min(dp[idx], dp[i + 1])

题解

还是老实用java写方便，09afd9sjoqjihbn

class Solution {
    public int respace(String[] dictionary, String sentence) {
        //整了个set，后面好处理字符串
       Set dic = new HashSet<>(Arrays.asList(dictionary));
       int n = sentence.length();
       int[] dp = new int[n + 1];
       for(int i = 1; i < n + 1; i++){
           //先按未匹配处理加1；
           dp[i] = dp[i - 1] + 1;
           //如果匹配到了取小值
           for(int idx = 0; idx < i; idx++){
                if(dic.contains(sentence.substring(idx, i))){
                    dp[i] = Math.min(dp[i], dp[idx]);
                }
           }
       }

       return dp[n];
    }
}

拓展
  可以通过构造字典树来查询以第 i + 1 个字符为结尾的单词有哪些（构建字典树时将单词逆序插入即可），在进行匹配查找时可以减少时间复杂度，关于字典树，可以看字典树，用字典树优化解法如下

class Solution {
    public int respace(String[] dictionary, String sentence) {
        // 构建字典树
        Trie trie = new Trie();
        for (String word: dictionary) {
            trie.insert(word);
        }
        // 状态转移，dp[i] 表示字符串的前 i 个字符的最少未匹配数
        int n = sentence.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int idx: trie.search(sentence, i - 1)) {
                dp[i] = Math.min(dp[i], dp[idx]);
            }
        }
        return dp[n];
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 将单词倒序插入字典树
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            int c = word.charAt(i) - 'a';
            if (cur.children[c] == null) {
                cur.children[c] = new TrieNode();
            }
            cur = cur.children[c];
        }
        cur.isWord = true;
    }

    // 找到 sentence 中以 endPos 为结尾的单词，返回这些单词的开头下标。
    public List search(String sentence, int endPos) {
        List indices = new ArrayList<>(); 
        TrieNode cur = root;
        for (int i = endPos; i >= 0; i--) {
            int c = sentence.charAt(i) - 'a';
            if (cur.children[c] == null) {
                break;
            }
            cur = cur.children[c];
            if (cur.isWord) {
                indices.add(i);
            }  
        }
        return indices;
    }
}

class TrieNode {
    boolean isWord;
    TrieNode[] children = new TrieNode[26];

    public TrieNode() {}
}