Lyuyk's Blog - 算法
type: channel
link: https://lyuyk.com/category/Algorithm/
items: 【LeetCode】剑指Offer——其它
items: 【LeetCode】剑指Offer——位运算
items: 【LeetCode】剑指Offer——数学
items: 【LeetCode】剑指Offer——动态规划
items: 【LeetCode】剑指Offer——排序
items: 【LeetCode】剑指Offer——搜索
items: 【LeetCode】剑指Offer——分治
items: 【LeetCode】剑指Offer——二分查找
items: 【LeetCode】剑指Offer——贪心思想
items: 【LeetCode】剑指Offer——树

【LeetCode】剑指Offer——其它
type: item
date: 2023-04-15T01:11:02+00:00
description: 17 打印从 1 到最大的 n 位数输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。示例 1:输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]说明：用返回一个整数列表来代替打印n 为正整数题解class Solution { public: vector<int> printNumbers(int n) { int max=pow(10,n)-1; vector<int> res; for(int i=1;i<=max;i++){ res.push_back(i); } return res; } }; /*若考虑大数则应换dfs全排列做法*/19（10） 正则表达式匹配请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。示例 1:输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。示例 2:输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3:输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。示例 4:输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5:输入: s = "mississippi" p = "mis*is*p*." 输出: falses 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。题解class Solution { public: bool isMatch(string s, string p) { int m = s.size() + 1, n = p.size() + 1; vector<vector<bool>> dp(m, vector<bool>(n, false)); dp[0][0] = true; // 初始化首行 for(int j = 2; j < n; j += 2) dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'; // 状态转移 for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { if(p[j - 1] == '*') { if(dp[i][j - 2]) dp[i][j] = true; // 1. else if(dp[i - 1][j] && s[i - 1] == p[j - 2]) dp[i][j] = true; // 2. else if(dp[i - 1][j] && p[j - 2] == '.') dp[i][j] = true; // 3. } else { if(dp[i - 1][j - 1] && s[i - 1] == p[j - 1]) dp[i][j] = true; // 1. else if(dp[i - 1][j - 1] && p[j - 1] == '.') dp[i][j] = true; // 2. } } } return dp[m - 1][n - 1]; } }; /*当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ： dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]：字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且s的第i个字符等于p的第j个字符; dp[i - 1][j - 1] 且 p[j - 1] = '.'： 字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且p的第j个字符为'.'; */来源：作者：Krahets链接：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/494128/jian-zhi-offer-19-zheng-ze-biao-…

【LeetCode】剑指Offer——位运算
type: item
date: 2023-04-12T10:22:06+00:00
description: 15（191） 二进制中 1 的个数编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。提示：请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。示例 1：输入：n = 11 (控制台输入 00000000000000000000000000001011) 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2：输入：n = 128 (控制台输入 00000000000000000000000010000000) 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3：输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3） 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。提示：输入必须是长度为 32 的 二进制串 。题解/*与运算*/ class Solution { public: int hammingWeight(uint32_t n) { int res=0; for(int i=0;i<32;i++) { if(n&1)res++; n>>=1; } return res; } }; /*n&(n-1)法*/ public: int hammingWeight(uint32_t n) { int res=0; while(n!=0) { n&=(n-1);//每次运算都会消去n最末尾的一个1 res++; } return res; } };56 - I 数组中数字出现的次数（数组中只出现一次的数字）一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。示例 1：输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]示例 2：输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]限制：2 <= nums.length <= 10000题解class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int x = 0, y = 0, n = 0, m = 1; for(int num: nums)//遍历异或 { n^=num; } while((n&m)==0)//记录x^=y首位1 { m<<=1; } for(int num:nums){ if(num&m)x^=num;//划分子数组，能保证相同的数必划分到同一数组中 else y^=num; } return vector<int>{x,y}; } };来源：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solutions/572857/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/56 - II 数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。示例 1：输入：nums = [3,4,3,3] 输出：4示例 2：输入：nums = [9,1,7,9,7,9,7] 输出：1限制：1 <= nums.length <= 100001 <= nums[i] < 2^31题解class Solution { public: int singleNumber(vector<int>& nums) { int ones = 0, twos = 0; for(int num :nums){ ones = ones^num & ~twos; twos = twos^num & ~ones; } return ones; } }; /*相对简单*/ class Solution { public: int singleNumber(vector<int>& nums) …

【LeetCode】剑指Offer——数学
type: item
date: 2023-04-12T08:13:13+00:00
description: 39（169） 数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2限制：1 <= 数组长度 <= 50000题解class Solution { public: int majorityElement(vector<int>& nums) { int x = 0, votes = 0, count=0; for(int num : nums){ if(votes==0)x=num; votes+=num==x?1:-1; } // 验证 x 是否为众数 for(int num : nums) if(num == x) count++; return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0 } };62 圆圈中最后剩下的数0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。示例 1：输入: n = 5, m = 3 输出: 3示例 2：输入: n = 10, m = 17 输出: 2限制：1 <= n <= 10^51 <= m <= 10^6题解class Solution { public: int lastRemaining(int n, int m) { int x = 0; for(int i=2;i<=n;i++){ x=(x+m)%i; } return x; } };来源：https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solutions/607638/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/43（233） 从 1 到 n 整数中 1 出现的次数输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。示例 1：输入：n = 12 输出：5示例 2：输入：n = 13 输出：6限制：1 <= n < 2^31题解class Solution { public: int countDigitOne(int n) { long long digit = 1, res = 0; int high = n / 10, cur = n % 10, low = 0; while (high != 0 || cur != 0) { if (cur == 0) res += high * digit; // 0 else if (cur == 1) res += high * digit + low + 1; // 1 else res += (high + 1) * digit; // 2-9 low += cur * digit; cur = high % 10; high /= 10; digit *= 10; } return res; } };来源：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/229751/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

【LeetCode】剑指Offer——动态规划
type: item
date: 2023-04-11T14:41:40+00:00
description: 10 - I 斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入：n = 2 输出：1示例 2：输入：n = 5 输出：5题解class Solution { public: int fib(int n) { int a = 0, b=1,sum; for(int i=0;i<n;i++){ sum=(a+b)%1000000007; a=b; b=sum; } return a; } };836 矩形覆盖矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。示例 1：输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true示例 2：输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false示例 3：输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3] 输出：false提示：rect1.length == 4rect2.length == 4-109 <= rec1[i], rec2[i] <= 109rec1 和 rec2 表示一个面积不为零的有效矩形题解class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) { if(rec1[0]==rec1[2]||rec1[1]==rec1[3]||rec2[0]==rec2[2]||rec2[1]==rec2[3]){ return false; } return !(rec1[2]<=rec2[0]|| //1右在2左的左边（左） rec1[3]<=rec2[1]|| //1上在2下的下边（下） rec1[0]>=rec2[2]|| //1左在2右的右边（右） rec1[1]>=rec2[3]); //1下在2上的上边（上） } };10 - II（70）跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入：n = 2 输出：2示例 2：输入：n = 7 输出：21示例 3：输入：n = 0 输出：1提示：0 <= n <= 100题解/*070*/ class Solution { public: int climbStairs(int n) { long long a = 1, b = 1, sum; for(int i = 0;i < n; i++) { sum=a+b; a=b; b=sum; } return a; } }; /*10-II*/ class Solution { public: int numWays(int n) { int a=1, b=1, sum; for(int i=0;i<n;i++){ sum=(a+b)%1000000007; a=b; b=sum; } return a; } };42（53）连续子数组的最大和输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1:输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。提示：1 <= arr.length <= 10^5-100 <= arr[i] <= 100题解class Solution { public: int maxSubArray(vector<int>& nums) { int res = nums[0]; for(int i=1;i<nums.size();i++) { nums[i] += max(nums[i-1],0);//dp 两种情况 res = max(re…

【LeetCode】剑指Offer——排序
type: item
date: 2023-04-10T13:30:59+00:00
description: 21 调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。提示：0 <= nums.length <= 500000 <= nums[i] <= 10000题解class Solution { public: vector<int> exchange(vector<int>& nums) { int i=0,j=nums.size()-1; while(i<j){ //i为奇数 if(nums[i]%2==1) { i++;continue; } //j为偶数 if(nums[j]%2==0) { j--;continue; } //j为奇数，该情况下i必为偶数 if(nums[j]%2==1) { swap(nums[i],nums[j]); j--; i++; continue; } } return nums; } }; //更简洁的写法 class Solution { public: vector<int> exchange(vector<int>& nums) { int i = 0, j = nums.size() - 1; while (i < j) { while(i < j && (nums[i] & 1) == 1) i++; while(i < j && (nums[j] & 1) == 0) j--; swap(nums[i], nums[j]); } return nums; } }; 作者：Krahets 链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solutions/115087/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4/这题可以想到双指针方法，但一开始没有想到左右指针从左右两端开始，这种方法感觉比一段开始更好。M45 把数组排成最小的数输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2] 输出: "102"示例 2:输入: [3,30,34,5,9] 输出: "3033459"提示:0 < nums.length <= 100说明:输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。提示：0 <= nums.length <= 500000 <= nums[i] <= 10000题解class Solution { public: string minNumber(vector<int>& nums) { vector<string> strs; string res; for(int i=0;i<nums.size();i++) strs.push_back(to_string(nums[i])); sort(strs.begin(), strs.end(), [](string& x, string& y){ return x+y<y+x;}); for(int i=0;i<strs.size();i++) res.append(strs[i]); return res; } }; /*快排实现*/ class Solution { public: string minNumber(vector<int>& nums) { vector<string> strs; for(int i = 0; i < nums.size(); i++) strs.push_back(to_string(nums[i])); quickSort(strs, 0, strs.size() - 1); string res; for(string s : strs) res.append(s); return res; } private: void quickSort(vector<string>& strs, int l, int r) { if(l >= r) return; int i = l, j = r; while(i < j) { while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j-…

【LeetCode】剑指Offer——搜索
type: item
date: 2023-04-07T03:31:00+00:00
description: 12（79） 矩阵中的路径给定一个 $m \times n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$ 存在于网格中，返回 $true$ ；否则，返回 $false$ 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true示例 2：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true示例 3：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false提示：$m == board.length$$n = board[i].length$$1 <= m, n <= 6$$1 <= word.length <= 15$$board$ 和 $word$ 仅由大小写英文字母组成题解class Solution { public: bool exist(vector<vector<char>>& board, string word) { rows = board.size(); cols = board[0].size(); for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(dfs(board,word,i,j,0))return true; } } return false; } private: int rows, cols; bool dfs(vector<vector<char>>& board, string word, int i, int j, int k){ if(i>=rows || i<0 || j>=cols || j<0 || board[i][j]!=word[k])return false; if(k==word.size()-1)return true; board[i][j]='\0'; bool res=dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1); board[i][j]=word[k]; return res; } };M13 机器人的运动范围地上有一个m行n列的方格，从坐标 $[0,0]$ 到坐标 $[m-1,n-1]$ 。一个机器人从坐标 $[0, 0] $的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？示例 1：输入：m = 2, n = 3, k = 1 输出：3示例 2：输入：m = 3, n = 1, k = 0 输出：1提示：$1 <= n,m <= 100$$0 <= k <= 20$题解class Solution { public: int movingCount(int m, int n, int k) { vector<vector<bool>> visited(m, vector<bool>(n,0)); return dfs(0,0,0,0,visited,m,n,k); } private: int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visited, int m, int n, int k){ if(i>=m || j>=n || k<si+sj || visited[i][j])return 0; visited[i][j]=true; return 1+dfs(i+1, j, (i+1)%10!=0?si+1:si-8,sj,visited,m,n,k)+ dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8,visited,m,n,k); } };38 字符串的排列输入一个字符串，打印出该字符串中字符的…

【LeetCode】剑指Offer——分治
type: item
date: 2023-04-06T13:01:45+00:00
description: 35（50） 数值的整数次方实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。示例 1：输入：x = 2.00000, n = 10 输出：1024.00000示例 2：输入：x = 2.10000, n = 3 输出：9.26100示例 3：输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25提示：-100.0 < x < 100.0-231 <= n <= 231-1n 是一个整数-104 <= xn <= 104题解class Solution { public: double myPow(double x, int n) { long long b = n; double res = 1.0; while(b){ if(b<0){ x=1/x; b=-b; } //按位与判断 if( b&1 == 1){ res=res*x; } x=x*x; b>>=1; //右移即删除最后一位 } return res; } };

【LeetCode】剑指Offer——二分查找
type: item
date: 2023-04-06T04:20:00+00:00
description: 11（154） 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。示例 1：输入：numbers = [3,4,5,1,2] 输出：1示例 2：输入：numbers = [2,2,2,0,1] 输出：0提示：n == numbers.length1 <= n <= 5000-5000 <= numbers[i] <= 5000numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转题解class Solution { public: int minArray(vector<int>& numbers) { int i = 0, j = numbers.size() - 1; while (i < j) { int m = (i + j) / 2; if (numbers[m] > numbers[j]) i = m + 1; else if (numbers[m] < numbers[j]) j = m; else j--; } return numbers[i]; } };53 - I 在排序数组中查找数字统计一个数字在排序数组中出现的次数。示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: 0提示：0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109题解class Solution { public: int helper(vector<int>& nums, int tar) { int i = 0, j = nums.size() - 1; while(i<=j){ int m = (i+j)/2; if(nums[m]<=tar)i=m+1; else j = m-1; } return i; } int search(vector<int>& nums, int target) { return helper(nums, target) - helper(nums, target -1); } };53 - II 0~n-1中缺失的数字一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例 1:输入: [0,1,3] 输出: 2示例 2:输入: [0,1,2,3,4,5,6,7,9] 输出: 8限制：1 <= 数组长度 <= 10000题解class Solution { public: int missingNumber(vector<int>& nums) { int i = 0, j = nums.size()-1; while(i<=j){ int m = (i+j)/2; if(nums[m]==m) i=m+1; else j=m-1; } return i; } };（34）在排序数组中查找元素的第一个和最后一个位置题解class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { return {searchLeftOrRightBound(nums,target,"left"),searchLeftOrRightBound(nums,target,"right")}; } private: int searchLeftOrRightBound(vector<int>& nums, int target, const string& bound) { int left = 0, right = nums.size() - 1; int res = -1; while(left <= right){ int mid = (left + right) >> 1; if(nums[mid] < target){ left = mid+1; } else if(nums[mid]>target){…

【LeetCode】剑指Offer——贪心思想
type: item
date: 2023-04-04T13:50:00+00:00
description: 14 - I（343） 剪绳子给你一根长度为 $n$ 的绳子，请把绳子剪成整数长度的 $m$ 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 $k[0],k[1]...k[m-1]$ 。请问 $k[0]*k[1]*...*k[m-1]$ 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。示例 1：输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1示例 2:输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示：$2 <= n <= 58$题解/*dp343*/ /* dp五部曲: 1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i] 2.状态转移:dp[i]有两种途径可以转移得到 2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个 2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2 两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值 3.初始化:初始化dp[1]=1即可 4.遍历顺序:显然为正序遍历 5.返回坐标:返回dp[n] */ class Solution { public: int integerBreak(int n) { vector<int> dp(n+1); dp[1]=1; for(int i=2;i<=n;i++) { for(int j=1;j<=i-1;j++) { int tmp = max(dp[j]*(i-j),j*(i-j)); dp[i] = max(tmp, dp[i]); } } return dp[n]; } };14 - II（343） 剪绳子 II给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1示例 2:输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示：2 <= n <= 1000题解class Solution { public int cuttingRope(int n) { if(n <= 3) return n - 1; int b = n % 3, p = 1000000007; long ret = 1; int lineNums=n/3; //线段被我们分成以3为大小的小线段个数 for(int i=1;i<lineNums;i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。 ret = 3*ret % p; if(b == 0) return (int)(ret * 3 % p); //刚好被3整数的，要算上前一段 if(b == 1) return (int)(ret * 4 % p); //被3整数余1的，要算上前一段 return (int)(ret * 6 % p); //被3整数余2的，要算上前一段 } } 63（121） 股票的最大利润假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？示例 1:输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。限制：0 <= 数组长度 <= 10^5题解class Solution { public: int maxProfit(vector<int>& prices) { int cost = __INT_MAX__, profit=0; for(int price: prices) { cost = min(cost, price); profit = max(profit,price - cost); } return profit; } };

【LeetCode】剑指Offer——树
type: item
date: 2023-04-04T13:10:50+00:00
description: 7（105）重建二叉树示例 1:给定两个整数数组 $preorder$ 和 $inorder$ ，其中 $preorder$ 是二叉树的先序遍历， $inorder$ 是同一棵树的中序遍历，请构造二叉树并返回其根节点。输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:输入: preorder = [-1], inorder = [-1] 输出: [-1]提示:$1 <= preorder.length <= 3000$$inorder.length == preorder.length$$-3000 <= preorder[i], inorder[i] <= 3000$$preorder$ 和 $inorder$ 均 无重复 元素$inorder$ 均出现在 $preorder$$preorder$ 保证 为二叉树的前序遍历序列$inorder$ 保证 为二叉树的中序遍历序列题解class Solution { public: unordered_map<int, int> map; TreeNode* build(vector<int>& preorder, vector<int>& inorder,int pre_root, int inorder_left,int inorder_right){ if(inorder_left > inorder_right) return NULL; TreeNode* root = new TreeNode(preorder[pre_root]); // 根节点在中序序列中位置，划分左右子树边界 int inorder_root = map[preorder[pre_root]]; // 左子树前序中根节点的位置在，pre_root+1，左子树在中序中边界，[inorder_left,inorder_root-1] root->left = build(preorder,inorder,pre_root+1,inorder_left,inorder_root-1); // 右子树在前序中的根节点位于：根节点+左子树长度+1 即 pre_root+inorder_root-inorder_left+1 // 右子树在中序中的边界：[inorder_root+1,inorder_right] root->right = build(preorder,inorder,pre_root+inorder_root-inorder_left+1,inorder_root+1,inorder_right); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // 中序序列用于查找根节点 for(int i=0;i< inorder.size();i++) { map[inorder[i]] = i; } return build(preorder,inorder,0,0,inorder.size()-1); } };26 树的子结构输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构， 即 A中有出现和B相同的结构和节点值。例如:给定的树 A:$ 3 / \ 4 5 / \ 1 2$给定的树 B：$ 4 / 1$返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。示例 1：输入：A = [1,2,3], B = [3,1] 输出：false示例 2：输入：A = [3,4,5,1,2], B = [4,1] 输出：true限制：0 <= 节点个数 <= 10000题解class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { return (A != NULL && B!=NULL )&&(recur(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B)); } bool recur(TreeNode *A, TreeNode *B){ if(B==NULL)return true; if(A==NULL|| A->val !=B->val)return false; return recur(A->left,B->left)&&recur(A->right,B->right); } };27（226） 二叉树的镜像请完成一个函数，输入一个二叉树，该函数输出它…