leetcode解题思路分析（七十八）686

重复叠加字符串匹配
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

指针滑动b，循环检测a即可，如果找不到则返回-1

class Solution { 
public:
    static const int N = 10010;
    int ne[N + 1];
    int repeatedStringMatch(string a, string b) { 
        int n = b.size();
        int m = a.size();
        b = " " + b;
        // next数组
        for (int i = 2, j = 0; i <= n ; i ++ ) { 
            while (j && b[i] != b[j + 1]) j = ne[j];
            if (b[i] == b[j + 1]) j ++ ;
            ne[i] = j;
        }
        int i = 0, j = 0;
        // 终止条件
        while(i - j < m) { 
            while (j && b[j + 1] != a[i % m]) j = ne[j];
            if (a[i % m] == b[j + 1]) j ++ ;
            i ++ ;
            if (j == n) break;
        }        
        if (j == n) { 
            return (i % m == 0) ? i / m : i / m + 1;
        }
        else return - 1;
    }
};

最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。

DFS递归即可

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution { 
private:
    // 记录最大的同值路径（边数）
    int res = 0;
    int dfs(TreeNode* curr)
    { 
        if (curr == nullptr)
        { 
            return 0;
        }
        // 计算从自己开始最大值
        int left = 0;
        int right = 0;
        // 计算当前左右子节点最大值
        int leftLongest = dfs(curr->left);
        int rightLongest = dfs(curr->right);
        // 判断是否相等来决定是否要更新自己最大值
        if (curr->left != nullptr && curr->val == curr->left->val)
        { 
            left += leftLongest + 1;
        }
        if (curr->right != nullptr && curr->val == curr->right->val)
        { 
            right += rightLongest + 1;
        }
        // 比较获取最大值
        res = max(res, left+right);
        // 返回时候是取一边最大值，从而和父节点构建更大的同值路径
        return max(left, right);
    }
public:
    int longestUnivaluePath(TreeNode* root) { 
        dfs(root);
        return res;
    }
};

”马“在棋盘上的概率
“马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。求移动结束后，“马” 仍留在棋盘上的概率。

dp得解

const int dx[8]={ -1,-2,-2,-1, 1, 2, 2,1};
const int dy[8]={  2, 1,-1,-2,-2,-1, 1,2};
double d[105][30][30];
class Solution { 
public:
    int NN,KK;
    double knightProbability(int N, int K, int r, int c) { 
        NN = N;
        KK = K;
        memset(d,0,sizeof(d));
        d[0][r][c]=1;
        for(int k=0;k<K;++k){ 
            for(int i=0;i<N;++i){ 
                for(int j=0;j<N;++j){ 
                    if(d[k][i][j]==0.0){ 
                        continue;
                    }
                    for(int t=0;t<8;++t){ 
                        const int nx = i + dx[t];
                        const int ny = j + dy[t];
                        if(in_board(nx,ny)){ 
                            d[k+1][nx][ny] += d[k][i][j]/8;
                        }
                    }
                }
            }
        }
        double ans = 0;
        for(int i=0;i<N;++i){ 
            for(int j=0;j<N;++j){ 
                ans += d[K][i][j];
            }
        }
        return ans;
    }
    bool in_board(int x,int y){ 
        return x>=0 && x<NN && y>= 0 && y <NN;
    }
};

三个无重叠子数组的最大和
给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。

1，定义如下：
sums[i]代表以nums[i]结尾的前k个数的和
dp[i][j]代表截止到nums[i]形成的第j个无重叠子数组的最大和
path[i][j]代表截止到nums[i]形成的第j个无重叠子数组以哪个下标为结尾，用来回溯路径
2，状态转移方程为
dp[i][j] = max{dp[i - 1][j], sums[i] + dp[i - k][j - 1]};
对应的path[i][j] = path[i - 1][j]或i

class Solution { 
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { 
        vector<int> sum;
        int cur = 0;
        for(int i = 0; i < k; ++i){ 
            cur += nums[i];
        }
        sum.push_back(cur);
        for(int i = k; i < nums.size(); ++i){ 
            cur += nums[i] - nums[i - k];
            sum.push_back(cur);
        }
        int n = sum.size();
        vector<int> left(n, 0), right(n, n - 1);
        for(int i = 1; i < n; ++i){ 
            if(sum[i] > sum[left[i - 1]]) left[i] = i;
            else left[i] = left[i - 1];
        }
        for(int i = n - 2; i >= 0; --i){ 
            if(sum[i] >= sum[right[i + 1]]) right[i] = i;
            else right[i] = right[i + 1];
        }
        int mx = 0;
        vector<int> ans(3);
        for(int i = k; i < n - k; ++i){ 
            if(mx < sum[i] + sum[left[i - k]] + sum[right[i + k]]){ 
                mx = sum[i] + sum[left[i - k]] + sum[right[i + k]];
                ans = { left[i - k], i, right[i + k]};
            }
        }
        return ans;
    }
};

员工的重要性
现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。

哈希表存储后DFS或者广度优先均可

/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */
class Solution { 
public:
    unordered_map<int, Employee *> mp;
    int dfs(int id) { 
        Employee *employee = mp[id];
        int total = employee->importance;
        for (int subId : employee->subordinates) { 
            total += dfs(subId);
        }
        return total;
    }
    int getImportance(vector<Employee *> employees, int id) { 
        for (auto &employee : employees) { 
            mp[employee->id] = employee;
        }
        return dfs(id);
    }
};

贴纸拼词
我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

状态压缩动态规划求解

#define INF 0x3f3f3f3f
class Solution { 
public:
    int minStickers(vector<string>& stickers, string target) { 
        vector<int> dp(1 << 15, INF);
        int n = stickers.size(), m = target.size();
        vector<vector<int>> cnt(n, vector<int>(26));
        vector<vector<int>> can(26);
        for (int i = 0; i < n; ++i)
            for (char c : stickers[i]) { 
                int d = c - 'a';
                cnt[i][d]++;
                if (can[d].empty() || can[d].back() != i)
                    can[d].emplace_back(i);                
            }
        dp[0] = 0;
        for (int i = 0; i < (1 << m) - 1; ++i) { 
            if (dp[i] == INF)
                continue;
            int d;
            for (int j = 0; j < m; ++j) { 
                if (!(i & (1 << j))) { 
                    d = j;
                    break;
                }
            }
            d = target[d] - 'a';
            for (int k : can[d]) { 
                int nxt = i;
                vector<int> left(cnt[k]);
                for (int j = 0; j < m; ++j) { 
                    if (nxt & (1 << j))
                        continue;
                    if (left[target[j] - 'a'] > 0) { 
                        nxt += (1 << j);
                        left[target[j] - 'a']--;
                    }
                }
                dp[nxt] = min(dp[nxt], dp[i] + 1);
            }
        }
        return dp[(1 << m) - 1] == INF ? -1 : dp[(1 << m) - 1];
    }
};

前K个高频单词
给一非空的单词列表，返回前 k 个出现次数最多的单词。
哈希表+优先队列（堆）

class Solution {
public:

vector<string> topKFrequent(vector<string>& words, int k) { 
    unordered_map<string, int> cnt;
    for (auto& word : words) { 
        cnt[word]++;
    }
    auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) { 
        return a.second == b.second ? a.first < b.first : a.second > b.second;
    };
    priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
    for (auto& it : cnt) { 
        que.emplace(it);
        if (que.size() > k) { 
            que.pop();
        }
    }
    vector<string> ret(k);
    for (int i = k - 1; i >= 0; i--) { 
        ret[i] = que.top().first;
        que.pop();
    }
    return ret;
}