目录数组中的第k个元素IPO查找最小 k 堆数字和数据流的中位数二进制求和颠倒二进制位位 1 的个数只出现一次的数字只出现一次的数字二数字范围按位与回文数加一阶乘后的零x 的平方根Pow(x,n)直线上最多的数爬楼梯打家劫舍单词拆分数组中的第k个元素解法优先级队列class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint,vectorint,greaterint q; for(auto num: nums) { q.push(num); if(q.size() k) { q.pop(); } } return q.top(); } };IPO解法优先级队列思路有问题优先级队列按照比 w 小的最大的 profit 排在栈顶但这样实现出来只有第一次是对的第二次的参照物就不是 w而是 wprofitint sum 0; class Solution { public: struct cmp { bool operator()(const pairint,int p1, const pairint,int p2) { if(p1.second sum p2.second sum) { return p1.first - p1.second p2.first - p2.second; } if(p1.second sum) { return false; } return true; } }; int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { sum w; priority_queuepairint,int,vectorpairint,int,cmp q; int n profits.size(); for(int i 0; i n; i) { q.emplace(profits[i], capital[i]); } int ret w; while(k--) { // 这样的话,第一次最优,其他就不一定了 ret q.top().first; q.pop(); } return ret; } };正确思路使用 vector 按升序排序 capital每次那最大 profit 之前把比 w 小的数放到优先级队列中每次取最大后更新w w st.top()...直到取了 k 个后退出循环返回 wclass Solution { public: int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { vectorpairint,int v; int n profits.size(); for(int i 0; i n; i) { v.emplace_back(capital[i], profits[i]); } sort(v.begin(), v.end(), [](const pairint,int p1, const pairint,int p2) - bool{ return p1.first p2.first; }); priority_queueint st; int i 0, sum w; while(k--) { while(i n v[i].first w) { st.push(v[i].second); } if(!st.empty()) { w st.top(); st.pop(); } else { break; } } return w; } };查找最小 k 堆数字和解法贪心 最小堆假设nums1 [1, 7, 11],nums2 [2, 4, 6]。我们可以构建一个和的矩阵最小的数字和 ij在左上角下一个最小的数字和在i 1j或者ij1所以可以先把第一列按照 nums[i] nums2[j]ij 的格式放在最小堆中按照和进行排优先级每次拿完堆顶后把ij 1 坐标的值入堆...class Solution { public: struct cmp { bool operator()(const pairint,pairint,int p1, const pairint,pairint,int p2) { return p1.first p2.first; } }; vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { priority_queuepairint,pairint,int,vectorpairint,pairint,int,cmp st; int n nums1.size(), m nums2.size(); for(int i 0; i n; i) { st.emplace(nums1[i] nums2[0], make_pair(i, 0)); } vectorvectorint ret(k); for(int i 0; i k; i) { auto tmp st.top().second; st.pop(); int x tmp.first, y tmp.second; ret[i].push_back(nums1[x]); ret[i].push_back(nums2[y]); // 越界就存了 if(x n || (y 1) m) { continue; } st.emplace(nums1[x] nums2[y 1],make_pair(x, y 1)); } return ret; } };思路 2双指针 二分使用二分找一段区间使得该区间内数字组合之和 k使用右区间模板来解决使用双指针来统计在某个区间中数字组合个数 midclass Solution { public: int n,m; long long LessMid(int mid, vectorint nums1, vectorint nums2) { int pos1 0, pos2 m - 1, sum nums1[0] nums2[m - 1]; long long cnt 0; while(pos1 n pos2 0) { while(pos2 0 nums1[pos1] nums2[pos2] mid) { pos2--; } cnt pos2 1; pos1; } return cnt; } vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { n nums1.size(); m nums2.size(); // 1. 二分查找第 k 小的和是多少 int l nums1[0] nums2[0]; int r nums1[n - 1] nums2[m - 1]; while (l r) { int mid l (r - l) / 2; if (LessMid(mid, nums1, nums2) k) { r mid; } else { l mid 1; } } // 2. 收集结果 vectorvectorint ret; // 第一遍把所有和严格小于 l 的对子找出来 for (int i 0; i n; i) { for (int j 0; j m nums1[i] nums2[j] l; j) { ret.push_back({nums1[i], nums2[j]}); if (ret.size() k) return ret; // 虽然概率低但防万一 } } // 第二遍补充和等于 l 的对子直到够 k 个 for (int i 0; i n; i) { for (int j 0; j m nums1[i] nums2[j] l; j) { if (nums1[i] nums2[j] l) { ret.push_back({nums1[i], nums2[j]}); if (ret.size() k) return ret; } } } return ret; } };数据流的中位数第七题讲解思路class MedianFinder { public: priority_queueint st_left_Max; priority_queueint,vectorint,greaterint st_right_Min; int maxSum 0; int minSum 0; MedianFinder() { } void addNum(int num) { if(minSum maxSum) { st_right_Min.push(num); st_left_Max.push(st_right_Min.top()); st_right_Min.pop(); maxSum; } else { st_left_Max.push(num); st_right_Min.push(st_left_Max.top()); st_left_Max.pop(); minSum; } } double findMedian() { if(minSum maxSum) { return st_left_Max.top(); } return (st_left_Max.top() st_right_Min.top()) / 2.0; } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj new MedianFinder(); * obj-addNum(num); * double param_2 obj-findMedian(); */二进制求和解法模拟模拟加法求和进行解决class Solution { public: string addBinary(string a, string b) { int n a.size(), m b.size(); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int tmp 0, posA 0, posB 0; string ret; while(posA n || posB m) { if(posA n) { tmp a[posA] - 0; } if(posB m) { tmp b[posB] - 0; } ret (tmp % 2) 0; tmp / 2; } if(tmp) { ret tmp 0; } reverse(ret.begin(), ret.end()); return ret; } };颠倒二进制位解法模拟按照题目要求对值和二进制进行相互转换class Solution { public: int reverseBits(int n) { // 值 - 二进制 string tmp; while(n) { tmp (n % 2) 0; n / 2; } // 得到的 tmp 刚好是颠倒的二进制 // 补0变完整的2进制 for(int i tmp.size(); i 32;i) { tmp 0; } // 二进制 - 值 int ret 0, m tmp.size(), cnt 0; for(int i m - 1; i 0; i--) { ret pow(2, cnt) * (tmp[i] - 0); } return ret; } };位 1 的个数解法模拟n (n-1) 会把比特位的低 1 位给消除class Solution { public: int hammingWeight(int n) { int cnt 0; while(n) { cnt 1; n (n - 1); } return cnt; } };只出现一次的数字解法模拟异或会把相同数字进行消除class Solution { public: int singleNumber(vectorint nums) { int ret 0; for(auto num: nums) { ret ^ num; } return ret; } };只出现一次的数字二解法模拟进行比特位级别的相加再对各个比特位%3(消除出现三次的数字)最后把比特位还原为值就是答案class Solution { public: int singleNumber(vectorint nums) { int bit[32] {0}; for(auto num: nums) { int pos 0; for(int i 0; i 32;i) { bit[pos] (num i) 1; bit[pos] % 3; } } long long ret 0, pos 0; for(int i 0; i 32; i) { ret pow(2, pos) * bit[i]; } return ret; } };数字范围按位与解法模拟比如 100 和 111 结果是 100也就是要把后两比特位置 0如何得到 left 和 right 要置 0 的长度left ^ right 的比特位个数如果将 left 把 left ^ right 长度置 0右移后左移class Solution { public: int rangeBitwiseAnd(int left, int right) { int len bit_width((uint32_t)left ^ right); // return left ~((long long)pow(2,len) - 1); return left len len; } };回文数解法数学循环获取x最后一位进行组合比如1212 - 2 121 - 2 * 10 1 12 12class Solution { public: bool isPalindrome(int x) { if(x 0 || (x % 10 0 x ! 0)) { return false; } int sum 0; while(sum x) { int last x % 10; sum sum * 10 last; x / 10; } // 8888 和 88888 if(x sum || x sum / 10) { return true; } return false; } };加一解法模拟从右往前遍历如果加一后变成 10往左进行进位...直到最高位如果最高位为 10先尾插 0再把最高位变为 1class Solution { public: vectorint plusOne(vectorint digits) { for(int i digits.size() - 1; i 0; i--) { if(digits[i] 9) { digits[i]; return digits; } // 进位 digits[i] 0; } // 999 - 1000 digits.push_back(0); digits[0] 1; return digits; // int tmp 1; // for(int i digits.size() - 1; i 0; i--) // { // if(!tmp) // { // break; // } // digits[i] tmp; // tmp digits[i] / 10; // digits[i] % 10; // if(tmp i 0) // { // digits.insert(digits.begin(), tmp); // } // } // return digits; } };阶乘后的零解法数学求阶乘后的零不就是求 n ! 的过程有哪些情况的值相乘得到 10 ?那么 10 怎么来 通过 10 2 * 5 得到所以现在问题转为求有多少个 2多少个 5 相乘得到 10怎么办因数为 2 的值多还是因数为 5 的值多当然是 5因为每 2 个数就有一个数是 2 的因数所以问题再次转化为求 5 的个数当然不是5 * 5 25此时 25 后面也有 5所以问题应该是求 5 的因数class Solution { public: int trailingZeroes(int n) { // 10 2 * 5 - 5 出现的个数少 int tmp 5, ret 0; while(tmp n) { ret n / tmp; tmp * 5; } return ret; } };x 的平方根解法二分使用二分的右端点进行解答class Solution { public: int mySqrt(int x) { int l 0, r x; while(l r) { long long mid l ((long long)r - l 1) / 2; if(mid * mid x) { l mid; } else { r mid - 1; } } return l; // if(x 0) // { // return 0; // } // long long ret 1; // while(true) // { // if(ret * ret x) // { // return ret; // } // ret; // if(ret * ret x) // { // return ret - 1; // } // } // return -1; } };Pow(x,n)解法快速幂要解决这个问题必须使用快速幂从而缩短遍历。其核心思想是二分法如果 n 是偶数x^n (x^2)^{n/2}如果 n 是奇数x^n x \cdot (x^2)^{(n-1)/2}如果 n 为 1返回 x^n xclass Solution { public: double dfs(double x, long long n) { if(n 1) { return x; } else if(n % 2 0) { return dfs(x * x, n / 2); } return dfs(x * x, (n - 1) / 2) * x; } double myPow(double x, int n) { if(n 0) { return dfs(x, n); } else if(n 0) { return dfs(1/x, -(long long)n); } return 1; } };直线上最多的数解法暴力本质任取一个坐标为基准点与剩下坐标组合计算斜率斜率相同的说明再同一条直线上所以直线上最多的数就是看看有多少斜率相同的最多有多少个注意使用hash 统计时使用 double 保存斜率斜率不一定 / 之后是整数class Solution { public: int maxPoints(vectorvectorint points) { int n points.size(),ret 0; for(int i 0; i n; i) { auto t1 points[i]; // 使用 hash 统计出现斜率相同的最多个数 unordered_mapdouble,int hash; for(int j 0; j n; j) { if(i j) continue; auto t2 points[j]; int dy t2[1] - t1[1]; int dx t2[0] - t1[0]; double k dx 0 ? DBL_MAX : dy * 1.0 / dx; ret max(ret,hash[k]); } } return ret 1; } };爬楼梯解法动态规划斐波那契数列变形class Solution { public: int climbStairs(int n) { if(n 3) { return n; } long long a 2, b 3, c 0; for(int i 3; i n; i) { c a b; a b; b c; } return c; } };打家劫舍解法动态规划多状态类型题class Solution { public: int rob(vectorint nums) { int n nums.size(); vectorint steal(n),unSteal(n); steal[0] nums[0]; for(int i 1; i n; i) { steal[i] max(unSteal[i - 1] nums[i], steal[i - 1]); unSteal[i] max(steal[i - 1], unSteal[i - 1]); } return max(steal[n - 1], unSteal[n - 1]); } };单词拆分解法动态规划dp[i]表示取 s 【0i】的子串在不在单词列表在为true不在为false设 j0 j i来辅助构建方程dp[i] dp[i - 1] s.substr(j1, i - (j1) 1) 的子串在不在单词列表中s 空出一个空格好些循环class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_mapstring,bool hash; int n s.size(); for(auto word: wordDict) { hash[word] true; } s s; vectorbool dp(n 1, false); dp[0] true; for(int i 1; i n; i) { // for(int j 0; j i; j) for(int j i; j 0; j--) { dp[i] dp[j] hash[s.substr(j1,i-(j1)1)]; if(dp[i] true) { couti ; break; } } } return dp[n]; } };以上便是全部内容有问题欢迎在评论区指正感谢观看
面试150——第八周
目录数组中的第k个元素IPO查找最小 k 堆数字和数据流的中位数二进制求和颠倒二进制位位 1 的个数只出现一次的数字只出现一次的数字二数字范围按位与回文数加一阶乘后的零x 的平方根Pow(x,n)直线上最多的数爬楼梯打家劫舍单词拆分数组中的第k个元素解法优先级队列class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint,vectorint,greaterint q; for(auto num: nums) { q.push(num); if(q.size() k) { q.pop(); } } return q.top(); } };IPO解法优先级队列思路有问题优先级队列按照比 w 小的最大的 profit 排在栈顶但这样实现出来只有第一次是对的第二次的参照物就不是 w而是 wprofitint sum 0; class Solution { public: struct cmp { bool operator()(const pairint,int p1, const pairint,int p2) { if(p1.second sum p2.second sum) { return p1.first - p1.second p2.first - p2.second; } if(p1.second sum) { return false; } return true; } }; int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { sum w; priority_queuepairint,int,vectorpairint,int,cmp q; int n profits.size(); for(int i 0; i n; i) { q.emplace(profits[i], capital[i]); } int ret w; while(k--) { // 这样的话,第一次最优,其他就不一定了 ret q.top().first; q.pop(); } return ret; } };正确思路使用 vector 按升序排序 capital每次那最大 profit 之前把比 w 小的数放到优先级队列中每次取最大后更新w w st.top()...直到取了 k 个后退出循环返回 wclass Solution { public: int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { vectorpairint,int v; int n profits.size(); for(int i 0; i n; i) { v.emplace_back(capital[i], profits[i]); } sort(v.begin(), v.end(), [](const pairint,int p1, const pairint,int p2) - bool{ return p1.first p2.first; }); priority_queueint st; int i 0, sum w; while(k--) { while(i n v[i].first w) { st.push(v[i].second); } if(!st.empty()) { w st.top(); st.pop(); } else { break; } } return w; } };查找最小 k 堆数字和解法贪心 最小堆假设nums1 [1, 7, 11],nums2 [2, 4, 6]。我们可以构建一个和的矩阵最小的数字和 ij在左上角下一个最小的数字和在i 1j或者ij1所以可以先把第一列按照 nums[i] nums2[j]ij 的格式放在最小堆中按照和进行排优先级每次拿完堆顶后把ij 1 坐标的值入堆...class Solution { public: struct cmp { bool operator()(const pairint,pairint,int p1, const pairint,pairint,int p2) { return p1.first p2.first; } }; vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { priority_queuepairint,pairint,int,vectorpairint,pairint,int,cmp st; int n nums1.size(), m nums2.size(); for(int i 0; i n; i) { st.emplace(nums1[i] nums2[0], make_pair(i, 0)); } vectorvectorint ret(k); for(int i 0; i k; i) { auto tmp st.top().second; st.pop(); int x tmp.first, y tmp.second; ret[i].push_back(nums1[x]); ret[i].push_back(nums2[y]); // 越界就存了 if(x n || (y 1) m) { continue; } st.emplace(nums1[x] nums2[y 1],make_pair(x, y 1)); } return ret; } };思路 2双指针 二分使用二分找一段区间使得该区间内数字组合之和 k使用右区间模板来解决使用双指针来统计在某个区间中数字组合个数 midclass Solution { public: int n,m; long long LessMid(int mid, vectorint nums1, vectorint nums2) { int pos1 0, pos2 m - 1, sum nums1[0] nums2[m - 1]; long long cnt 0; while(pos1 n pos2 0) { while(pos2 0 nums1[pos1] nums2[pos2] mid) { pos2--; } cnt pos2 1; pos1; } return cnt; } vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { n nums1.size(); m nums2.size(); // 1. 二分查找第 k 小的和是多少 int l nums1[0] nums2[0]; int r nums1[n - 1] nums2[m - 1]; while (l r) { int mid l (r - l) / 2; if (LessMid(mid, nums1, nums2) k) { r mid; } else { l mid 1; } } // 2. 收集结果 vectorvectorint ret; // 第一遍把所有和严格小于 l 的对子找出来 for (int i 0; i n; i) { for (int j 0; j m nums1[i] nums2[j] l; j) { ret.push_back({nums1[i], nums2[j]}); if (ret.size() k) return ret; // 虽然概率低但防万一 } } // 第二遍补充和等于 l 的对子直到够 k 个 for (int i 0; i n; i) { for (int j 0; j m nums1[i] nums2[j] l; j) { if (nums1[i] nums2[j] l) { ret.push_back({nums1[i], nums2[j]}); if (ret.size() k) return ret; } } } return ret; } };数据流的中位数第七题讲解思路class MedianFinder { public: priority_queueint st_left_Max; priority_queueint,vectorint,greaterint st_right_Min; int maxSum 0; int minSum 0; MedianFinder() { } void addNum(int num) { if(minSum maxSum) { st_right_Min.push(num); st_left_Max.push(st_right_Min.top()); st_right_Min.pop(); maxSum; } else { st_left_Max.push(num); st_right_Min.push(st_left_Max.top()); st_left_Max.pop(); minSum; } } double findMedian() { if(minSum maxSum) { return st_left_Max.top(); } return (st_left_Max.top() st_right_Min.top()) / 2.0; } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj new MedianFinder(); * obj-addNum(num); * double param_2 obj-findMedian(); */二进制求和解法模拟模拟加法求和进行解决class Solution { public: string addBinary(string a, string b) { int n a.size(), m b.size(); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int tmp 0, posA 0, posB 0; string ret; while(posA n || posB m) { if(posA n) { tmp a[posA] - 0; } if(posB m) { tmp b[posB] - 0; } ret (tmp % 2) 0; tmp / 2; } if(tmp) { ret tmp 0; } reverse(ret.begin(), ret.end()); return ret; } };颠倒二进制位解法模拟按照题目要求对值和二进制进行相互转换class Solution { public: int reverseBits(int n) { // 值 - 二进制 string tmp; while(n) { tmp (n % 2) 0; n / 2; } // 得到的 tmp 刚好是颠倒的二进制 // 补0变完整的2进制 for(int i tmp.size(); i 32;i) { tmp 0; } // 二进制 - 值 int ret 0, m tmp.size(), cnt 0; for(int i m - 1; i 0; i--) { ret pow(2, cnt) * (tmp[i] - 0); } return ret; } };位 1 的个数解法模拟n (n-1) 会把比特位的低 1 位给消除class Solution { public: int hammingWeight(int n) { int cnt 0; while(n) { cnt 1; n (n - 1); } return cnt; } };只出现一次的数字解法模拟异或会把相同数字进行消除class Solution { public: int singleNumber(vectorint nums) { int ret 0; for(auto num: nums) { ret ^ num; } return ret; } };只出现一次的数字二解法模拟进行比特位级别的相加再对各个比特位%3(消除出现三次的数字)最后把比特位还原为值就是答案class Solution { public: int singleNumber(vectorint nums) { int bit[32] {0}; for(auto num: nums) { int pos 0; for(int i 0; i 32;i) { bit[pos] (num i) 1; bit[pos] % 3; } } long long ret 0, pos 0; for(int i 0; i 32; i) { ret pow(2, pos) * bit[i]; } return ret; } };数字范围按位与解法模拟比如 100 和 111 结果是 100也就是要把后两比特位置 0如何得到 left 和 right 要置 0 的长度left ^ right 的比特位个数如果将 left 把 left ^ right 长度置 0右移后左移class Solution { public: int rangeBitwiseAnd(int left, int right) { int len bit_width((uint32_t)left ^ right); // return left ~((long long)pow(2,len) - 1); return left len len; } };回文数解法数学循环获取x最后一位进行组合比如1212 - 2 121 - 2 * 10 1 12 12class Solution { public: bool isPalindrome(int x) { if(x 0 || (x % 10 0 x ! 0)) { return false; } int sum 0; while(sum x) { int last x % 10; sum sum * 10 last; x / 10; } // 8888 和 88888 if(x sum || x sum / 10) { return true; } return false; } };加一解法模拟从右往前遍历如果加一后变成 10往左进行进位...直到最高位如果最高位为 10先尾插 0再把最高位变为 1class Solution { public: vectorint plusOne(vectorint digits) { for(int i digits.size() - 1; i 0; i--) { if(digits[i] 9) { digits[i]; return digits; } // 进位 digits[i] 0; } // 999 - 1000 digits.push_back(0); digits[0] 1; return digits; // int tmp 1; // for(int i digits.size() - 1; i 0; i--) // { // if(!tmp) // { // break; // } // digits[i] tmp; // tmp digits[i] / 10; // digits[i] % 10; // if(tmp i 0) // { // digits.insert(digits.begin(), tmp); // } // } // return digits; } };阶乘后的零解法数学求阶乘后的零不就是求 n ! 的过程有哪些情况的值相乘得到 10 ?那么 10 怎么来 通过 10 2 * 5 得到所以现在问题转为求有多少个 2多少个 5 相乘得到 10怎么办因数为 2 的值多还是因数为 5 的值多当然是 5因为每 2 个数就有一个数是 2 的因数所以问题再次转化为求 5 的个数当然不是5 * 5 25此时 25 后面也有 5所以问题应该是求 5 的因数class Solution { public: int trailingZeroes(int n) { // 10 2 * 5 - 5 出现的个数少 int tmp 5, ret 0; while(tmp n) { ret n / tmp; tmp * 5; } return ret; } };x 的平方根解法二分使用二分的右端点进行解答class Solution { public: int mySqrt(int x) { int l 0, r x; while(l r) { long long mid l ((long long)r - l 1) / 2; if(mid * mid x) { l mid; } else { r mid - 1; } } return l; // if(x 0) // { // return 0; // } // long long ret 1; // while(true) // { // if(ret * ret x) // { // return ret; // } // ret; // if(ret * ret x) // { // return ret - 1; // } // } // return -1; } };Pow(x,n)解法快速幂要解决这个问题必须使用快速幂从而缩短遍历。其核心思想是二分法如果 n 是偶数x^n (x^2)^{n/2}如果 n 是奇数x^n x \cdot (x^2)^{(n-1)/2}如果 n 为 1返回 x^n xclass Solution { public: double dfs(double x, long long n) { if(n 1) { return x; } else if(n % 2 0) { return dfs(x * x, n / 2); } return dfs(x * x, (n - 1) / 2) * x; } double myPow(double x, int n) { if(n 0) { return dfs(x, n); } else if(n 0) { return dfs(1/x, -(long long)n); } return 1; } };直线上最多的数解法暴力本质任取一个坐标为基准点与剩下坐标组合计算斜率斜率相同的说明再同一条直线上所以直线上最多的数就是看看有多少斜率相同的最多有多少个注意使用hash 统计时使用 double 保存斜率斜率不一定 / 之后是整数class Solution { public: int maxPoints(vectorvectorint points) { int n points.size(),ret 0; for(int i 0; i n; i) { auto t1 points[i]; // 使用 hash 统计出现斜率相同的最多个数 unordered_mapdouble,int hash; for(int j 0; j n; j) { if(i j) continue; auto t2 points[j]; int dy t2[1] - t1[1]; int dx t2[0] - t1[0]; double k dx 0 ? DBL_MAX : dy * 1.0 / dx; ret max(ret,hash[k]); } } return ret 1; } };爬楼梯解法动态规划斐波那契数列变形class Solution { public: int climbStairs(int n) { if(n 3) { return n; } long long a 2, b 3, c 0; for(int i 3; i n; i) { c a b; a b; b c; } return c; } };打家劫舍解法动态规划多状态类型题class Solution { public: int rob(vectorint nums) { int n nums.size(); vectorint steal(n),unSteal(n); steal[0] nums[0]; for(int i 1; i n; i) { steal[i] max(unSteal[i - 1] nums[i], steal[i - 1]); unSteal[i] max(steal[i - 1], unSteal[i - 1]); } return max(steal[n - 1], unSteal[n - 1]); } };单词拆分解法动态规划dp[i]表示取 s 【0i】的子串在不在单词列表在为true不在为false设 j0 j i来辅助构建方程dp[i] dp[i - 1] s.substr(j1, i - (j1) 1) 的子串在不在单词列表中s 空出一个空格好些循环class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_mapstring,bool hash; int n s.size(); for(auto word: wordDict) { hash[word] true; } s s; vectorbool dp(n 1, false); dp[0] true; for(int i 1; i n; i) { // for(int j 0; j i; j) for(int j i; j 0; j--) { dp[i] dp[j] hash[s.substr(j1,i-(j1)1)]; if(dp[i] true) { couti ; break; } } } return dp[n]; } };以上便是全部内容有问题欢迎在评论区指正感谢观看
