力扣 LeetCode 2161. 根据给定数字划分数组 - 力扣（LeetCode） 2161. 根据给定数字划分数组 - 给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立： * 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。 * 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。 * 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。 * 更正式的，考虑每一对 pi，pj ，pi 是初始时位置... 思路 把小于 pivot 和大于 pivot 的数分别放到新的List中，然后重新构造nums。 代码 class Solution { public int[] pivotArray(int[] nums, int pivot) { int n = nums.length; List<Integer> less = new ArrayList<>(n); List<Integer> gather = new ArrayList<>(n); for (int num : nums) { if (num < pivot) { less.add(num); } else if (num > pivot) { gather.add(num); } } int idx = less.size(); for (int i = 0; i < idx; i++) { nums[i] = less.get(i); } int eq = n - idx - gather.size(); for (int i = 0; i < eq; i++) { nums[idx + i] = pivot; } idx += eq; for (int i = 0; i < gather.size(); i++) { nums[idx + i] = gather.get(i); } return nums; } } 6-7 2196. 根据描述创建二叉树 思路 补下昨天的题，用 hash 存储 parent 节点。 遍历 descriptions ，将节点关系补全，同时记录当前节点是否有父节点。 最后遍历一遍 hash 找到没有父节点的节点。 代码 class Solution { public TreeNode createBinaryTree(int[][] descriptions) { TreeNode[] nodes = new TreeNode[100001]; int[] nodeState = new int[100001]; for (int[] description : descriptions) { int parent = description[0]; int child = description[1]; int isLeft = description[2]; nodeState[parent] |= 1; nodeState[child] |= 2; if (nodes[child] == null) { nodes[child] = new TreeNode(child); } if (nodes[parent] == null) { nodes[parent] = new TreeNode(parent); } if (isLeft == 1) { nodes[parent].left = nodes[child]; } else { nodes[parent].right = nodes[child]; } } for (int i = 0; i < nodeState.length; i++) { if (nodeState[i] == 1) { return nodes[i]; } } return null; } } 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 2574. 左右元素和的差值 - 力扣（LeetCode） 2574. 左右元素和的差值 - 给你一个下标从 0 开始的长度为 n 的整数数组 nums。 定义两个数组 leftSum 和 rightSum，其中： * leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。 * rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。 返回长度为 n 数组 answer，其中 answer[i] =... 昨天数位 DP 实在是不太会，就去随便挑了一道中等题做了。 今天这题就很常规了。 思路 其实就是在计算前缀和与后缀和的绝对差。不过额外空间可以只使用结果数组，先在结果数组中生成前缀，然后动态生成后缀并计算结果即可。 代码 class Solution { public: vector<int> leftRightDifference(vector<int>& nums) { // 就是在考察前缀后缀，额外空间只需要结果数组 int n=nums.size(); vector<int> res(n,0); // 先生成前缀 for(int i=1;i<n;i++){ res[i]=res[i-1]+nums[i-1]; } // 再根据后缀得到结果 int rightSum=nums[n-1]; for(int i=n-2;i>=0;i--){ res[i]=abs(res[i]-rightSum); rightSum+=nums[i]; } return res; } }; 2 个帖子 - 2 位参与者 阅读完整话题
力扣 LeetCode 1871. 跳跃游戏 VII - 力扣（LeetCode） 1871. 跳跃游戏 VII - 给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处： * i + minJump <= j <= min(i + maxJump, s.length - 1) 且 * s[j] == '0'. 如果你可以到达 s 的下标 s.length -... 思路 首先题目明显的无后效性，可以用动态规划作答。 容易想到遍历一遍，从 [minJump..maxJump] 进行递推，但是看数据量 1 <= minJump <= maxJump < s.length <= 10^5 大概率会超时。线段树似乎可以，但是太重了。 逆向思考下，如果能够到达 x 点，那么在 [x-maxJump..x-minJump] 至少有一个点可以到达。这点借助前缀和可以在 O(1) 的复杂度内解决，那动态规划的方程式就由 O(n^2) 降到了 O(n) 。 代码 class Solution { public boolean canReach(String s, int minJump, int maxJump) { int n = s.length(); // 是否可以跳到坐标 boolean[] dp = new boolean[n]; dp[0] = true; // 到当前坐标为止能够到达的坐标数量 int[] prefix = new int[n]; // 本来prefix[0]应该设为1，但是这样需要把[0..minJump)都设为1，所以在不影响计算的情况下此处保持0 // prefix[0]= 1; // 初始化边界，[minJump..maxJump]只要为0均可到达 for (int i = minJump; i <= maxJump; i++) { prefix[i] = prefix[i - 1]; if (s.charAt(i) == '0') { dp[i] = true; prefix[i] += 1; } } // 只要前面 [i-maxJump..i-minJump] 范围内有点能够到达此处就能到达 for (int i = maxJump + 1; i < n; i++) { prefix[i] = prefix[i - 1]; if (s.charAt(i) == '0' && prefix[i - minJump] - prefix[i - maxJump - 1] > 0) { dp[i] = true; prefix[i] += 1; } } return dp[n - 1]; } } 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 1340. 跳跃游戏 V - 力扣（LeetCode） 1340. 跳跃游戏 V - 给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到： * i + x ，其中 i + x < arr.length 且 0 < x <= d 。 * i - x ，其中 i - x >= 0 且 0 < x <= d 。 除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i,... 还有第五关？！( °ヮ° ) 思路 最开始看到这题脑子里会想能不能用栈做，一看输入规模，好像 O(n^2) 时间复杂度也可以接受。看了一眼提示后顿悟了，这题可以用动态规划。 动态规划 dp[i] 表示从 i 下标开始能跳跃的次数。 问题来了，我从哪个地方开始、按什么顺序递推呢？ 开始的地方应当不依赖于任何其他 dp 状态，符合这个要求的显然是 最低的一个柱子 ，这样的地方 p 无法跳到其他任何地方，自然有 dp[p]=0 （只能访问自身，一次都跳不了） 递推的时候我们只关注一个地方 i 能跳到哪些 更矮的地方 ，然后可以尝试 从这些地方中跳跃次数最多的柱子 上转移过来。因此递推顺序也是沿着柱子高度来的。 我们可以按照柱子高度对下标进行排序，顺着排序后的下标递推。 递推的过程中可以不断用 \max(\cdot) 更新最终结果。 思路 class Solution { public: int maxJumps(vector<int>& arr, int d) { // 每个位置 i 可以跳到 [i-d, i+d] 区间内除 i 外的位置 // 只能跳到更低的地方，且中间其余柱子都是更低的 // 看了提示才知道是动态规划，但是从哪里开始递推呢？ // 当然是最矮的那个柱子，从矮的到高的，最矮的柱子哪都别想跳 int n=arr.size(); vector<int> idxs; for(int i=0;i<n;i++){ idxs.emplace_back(i); } // 对下标按照柱子高度进行排序 sort(idxs.begin(),idxs.end(),[&](const int& a,const int& b){ return arr[a]<arr[b]; }); // dp[i] 表示从 i 开始跳，能跳跃的下标个数 int dp[n]; memset(dp,0,sizeof(dp)); // dp[idxs[0]]=0; int res=0; for(int i:idxs){ // 从低到高处理 // 往左、右走试试，只往更低的地方走，找到比 arr[i] 更低的柱子中能跳得最多的 for(int k=1;k<=d;k++){ if(i-k<0){ break; } if(arr[i-k]>=arr[i]){ break; } // 能走到这个柱子这里，看看能不能更新跳跃次数 dp[i]=max(dp[i],dp[i-k]+1); } for(int k=1;k<=d;k++){ if(i+k>=n){ break; } if(arr[i+k]>=arr[i]){ break; } // 能走到这个柱子这里，看看能不能更新跳跃次数 dp[i]=max(dp[i],dp[i+k]+1); } res=max(res,dp[i]); } // 最终要的是能访问的下标数而不是跳数，所以 +1 return res+1; } }; 2 个帖子 - 2 位参与者 阅读完整话题
力扣 LeetCode 2657. 找到两个数组的前缀公共数组 - 力扣（LeetCode） 2657. 找到两个数组的前缀公共数组 - 给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。 A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。 请你返回 A 和 B 的 前缀公共数组 。 如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。 示例 1： 输入：A = [1,3,2,4], B =... 思路 Hash记录出现过的数值，如果再次出现则公共值增1。 代码 class Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; // 记录遇到数值的数量 int[] set = new int[n + 1]; int[] ans = new int[n]; int total = 0; for (int i = 0; i < n; i++) { if (A[i] == B[i]) { // 如果相等可以忽略计数 ans[i] = ++total; } else { // 如果不相等，需要分别计数 total += set[A[i]]++; total += set[B[i]]++; ans[i] = total; } } return ans; } } 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 1345. 跳跃游戏 IV - 力扣（LeetCode） 1345. 跳跃游戏 IV - 给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。 每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ： * i + 1 需满足：i + 1 < arr.length * i - 1 需满足：i - 1 >= 0 * j 需满足：arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。 注意：任何时候你都不能跳到数组外面。 示例... 思路 还挺明显的BFS，每次尝试移到当前位置所能跳转的所有位置，并做记录以便剪枝。这样时间复杂度就是 O(n) 。 代码 class Solution { public int minJumps(int[] arr) { int n = arr.length; if (n <= 2) { return n - 1; } // 存储相同的值(可直接跳转) Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < arr.length; i++) { map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i); } Queue<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{0, 0}); boolean[] vis = new boolean[n]; vis[0] = true; // bfs while (!queue.isEmpty()) { int[] idxStep = queue.poll(); int idx = idxStep[0], step = idxStep[1]; if (idx == arr.length - 1) { return step; } step++; // 直接跳转 List<Integer> sameValue = map.remove(arr[idx]); if (sameValue != null) { for (int i : sameValue) { if (!vis[i]) { vis[i] = true; queue.offer(new int[]{i, step}); } } } // 左移 if (idx - 1 >= 0 && !vis[idx - 1]) { vis[idx - 1] = true; queue.offer(new int[]{idx - 1, step}); } // 右移 if (idx + 1 < arr.length && !vis[idx + 1]) { vis[idx + 1] = true; queue.offer(new int[]{idx + 1, step}); } } return -1; } } 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 2770. 达到末尾下标所需的最大跳跃次数 - 力扣（LeetCode） 2770. 达到末尾下标所需的最大跳跃次数 - 给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。 你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ： * 0 <= i < j < n * -target <= nums[j] - nums[i] <= target 返回到达下标 n - 1 处所需的 最大跳跃次数 。 如果无法到达下标 n - 1 ，返回 -1 。 示例... 思路 注意是求 最大的跳跃次数 。 题目条件： 每一步只能往后跳； 且跳转后的值和当前值的差的绝对值要在 [0, target] 范围内。 对于每个位置，我可能从前面每个满足上述条件的位置转移过来，因此对于每个位置存储其状态【到达这个位置所需的最大跳跃次数】，然后递推即可。 因此很明显是一道一维动态规划题。 代码 class Solution { public: int maximumJumps(vector<int>& nums, int target) { // 每一步只能往后跳 // 且跳到的值和当前值的差的绝对值要在 [0, target] 区间 // 注意这题找的是**最大**跳跃次数 // 应该是能用动态规划的 int n=nums.size(); // dp[i] 表示从 0 下标跳到 i 需要的最大跳跃次数 int dp[n]; dp[0]=0; // 显然 0 跳到 0 最大跳跃次数就是 0 for(int j=1;j<n;j++){ dp[j]=-1; for(int i=0;i<j;i++){ if(dp[i]==-1){ // 如果 dp[i] 没法跳到就跳过 continue; } int sub=nums[j]-nums[i]; if(-target<=sub&&sub<=target){ // 可以从 i 跳到 j，则看看能不能更新到 j 的最大跳跃次数 dp[j]=max(dp[j],dp[i]+1); } } } return dp[n-1]; } }; 2 个帖子 - 2 位参与者 阅读完整话题
力扣 LeetCode 2615. 等值距离和 - 力扣（LeetCode） 2615. 等值距离和 - 给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。 返回数组 arr 。 示例 1： 输入：nums = [1,3,1,1,2] 输出：[5,0,3,4,0] 解释： i = 0 ，nums[0] == nums[2]... 思路 也就是对于每个下标 i 对应的数字 nums[i] ，要找到与其相等的 所有其他数字 nums[j] ，累加 abs(i-j) 。 题目输入规模可能很大，时间复杂度要控制在 O(n\log n) 以下。 咱们在意的是某个数字 nums[i] 在数组内出现的所有下标，但如果直接按数字分组维护列表，扫描所耗费的时间从总体上看来是难以接受的。 既要涉及求和，而且还需要尽量是线性时间复杂度，能猜到可能能用到前缀和思想。 对于一个下标 i ，我可以计算前缀中所有 i-j 之和，再计算其后缀中所有 j-i 之和，这个位置的前缀加后缀就是最终结果 arr[i] 了。 怎么生成这样的前缀和呢？从计算某个位置的前缀 prefix[i] 来思考： 比如 [1,3,1,1,1,2] 这个数组，若要计算 prefix[4] 首先 nums[4]=1 ，要 从上一个前缀和处转移过来 ，我们可以用哈希表存上一个 1 出现的地方： 3 prefix[4] 可转移自 prefix[3] ，但是怎么从 prefix[3] 计算出 prefix[4] ？ prefix[3] 等于 (3-0) + (3-2) 。而 prefix[4] 则等于 (4-0) + (4-2) + (4-3) ，如果把 prefix[3] 的部分代入进去可以发现是 prefix[3] + (4-3) + (4-3) + (4-3) ，也就是在 prefix[3] 的基础上重复累加离上一个 1 出现的位置的距离多次。很显然这个次数就是 1 之前出现的次数。 因此在递推的时候可以用哈希表维护 nums[i] 上一次出现的下标 以及 nums[i] 之前出现过的次数 。递推得到前缀和和后缀和即可。 代码 写出来感觉还是挺直白的，应该还有很大可优化空间。 class Solution { public: vector<long long> distance(vector<int>& nums) { int n=nums.size(); vector<long long> res(n,0); // 也就是要找到所有相等元素的下标距离的和 // 输入规模比较大，可以分组做前缀和后缀和 vector<long long> prefix(n,0); // 某个数字 -> (其最后一次出现的下标, 这个数字出现的次数) unordered_map<int,pair<int,int>> iMap; for(int i=0;i<n;i++){ int appearCnt=0; if(iMap.count(nums[i])>0){ // 之前这个数字出现过 // 比如 1 ... 1 1 // 第三次出现的 1 的和前缀相当于 [前两个 1 的距离] + [第三次 1 和第二次 1 的距离] * [前面 1 出现的次数 = 2] int prevIdx=iMap[nums[i]].first; appearCnt=iMap[nums[i]].second; prefix[i]=prefix[prevIdx]+(i-prevIdx)*appearCnt; // cout<<"prefix["<<i<<"]="<<prefix[i]<<endl; } iMap[nums[i]]=make_pair(i,appearCnt+1); } // 接着边生成后缀边得到结果 vector<long long> postfix(n,0); iMap.clear(); for(int i=n-1;i>=0;i--){ int appearCnt=0; if(iMap.count(nums[i])>0){ int prevIdx=iMap[nums[i]].first; appearCnt=iMap[nums[i]].second; postfix[i]=postfix[prevIdx]+(prevIdx-i)*appearCnt; } res[i]=prefix[i]+postfix[i]; iMap[nums[i]]=make_pair(i,appearCnt+1); } return res; } }; 1 个帖子 - 1 位参与者 阅读完整话题
下标有点眼熟啊哈哈 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 1855. 下标对中的最大距离 - 力扣（LeetCode） 1855. 下标对中的最大距离 - 给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。 下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。 返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0... 思路 注意到两个序列都已经有序，这题可以考虑双指针或者二分查找做法。 咱觉得双指针的思路很自然，假设 i 指定 nums1 的元素， j 指定 nums2 的元素： 如果 nums1[i] > nums2[j] ，则后移 i ，直至 i 移动到尽头或者满足 nums1[i] <= nums2[j] 。 （因为在 nums1[i] > nums2[j] 时，就算 j 更大，因为序列是 非递增 的，必然还是会有 nums1[i] > nums2[j] ） 若满足第一条，就可以后移一次 j ，更新结果。 （因为距离是下标距离，我希望能在保持 nums1[i] <= nums2[j] 的同时 j-i 尽量大） 理清这两步后写起来就很容易了。 代码 class Solution { public: int maxDistance(vector<int>& nums1, vector<int>& nums2) { // 注意 nums1 和 nums2 都是有序的 // 因此这题能用上双指针 // 注意距离是下标差，因此 nums1 中每个数 X 尽量要在 nums2 中找到最后一个 Y>=X int p1=0,p2=0; int n1=nums1.size(),n2=nums2.size(); int res=0; while(p1<n1&&p2<n2){ while(p1<n1&&nums2[p2]<nums1[p1]){ // 不满足 nums2[j] >= nums1[i] 时前移 i p1++; } res=max(res,p2-p1); p2++; } return res; } }; 接着再复习一些题 （点击了解更多详细信息） 1 个帖子 - 1 位参与者 阅读完整话题
36氪获悉，创源股份公告，公司拟与宁波酷乐潮玩及其实际控制人邬胜峰签订《投资意向协议》，受让后者新设的浙江创酷未来文化创意有限公司90%股权。标的公司将装入30家以上酷乐潮玩体系内成熟门店的经营性资产及团队。交易定价以标的公司2025年度经审计模拟合并净利润的8倍市盈率为基准，且承诺该年度净利润不少于1000万元。为表达合作诚意，公司拟支付股权转让意向金3000万元。