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

雨点打透心脏的1/2处 2022-10-05 01:59 118阅读 0赞

1.  重复叠加字符串匹配  
    给定两个字符串 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;
        }
    };

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;
        }
    };

1.  ”马“在棋盘上的概率  
    “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 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;
        }
    };

1.  三个无重叠子数组的最大和  
    给定数组 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;
        }
    };

1.  员工的重要性  
    现在输入一个公司的所有员工信息，以及单个员工 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);
        }
    };

1.  贴纸拼词  
    我们给出了 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];
        }
    };

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;
        }
    };