算法修养-腾讯云开发者社区

开发者社区

文档建议反馈控制台

腾讯云架构师技术同盟

文章/答案/技术大牛

发布

算法修养

专栏成员

674

文章

406676

阅读量

49

订阅数

Leetcode 2289. Steps to Make Array Non-decreasing (单调栈)

题目题解：对于每个元素，它只有当左边的元素大于它的时候才能被删去。维护一个数组，dp dp[i]表示第i个元素被删去需要多少步维护一个单调递减的栈，用来查找每个元素的左边的第一个大于它的元素的位置对于每个元素i，假设左边第一个大于的元素的位置是k,那么元素i需要等待区间[i-k]的元素都被删去才会达成让元素i删除的条件。注意这个时候元素i的左边第一个元素不一定是k，但是无论是不是k，元素i都满足被删除的条件。所以对于每个元素i，只需要求出在区间[i-k]的dp数组的最大值，加上1就是删除元素i所需

2022-06-05

4910

LeetCode 2040. Kth Smallest Product of Two Sorted Arrays

题解: 两个数组的元素乘积最小是-10^5 * 10^5 最大是10^5 * 10^5 我们可以在这个范围内做二分，那么问题的关键就是能不能给你一个数，让你找到有多少个元素乘积小于这个数，复杂度最多n*log(n) 其实可以的，很简单，就是对数组a的每个元素，二分查找数组b。注意数组是有负数的

2022-03-10

3880

LeetCode Weekly Contest 281

让你算出一个数组有多少对数字的乘积能被K整除。我们可以对数组中的每个数a[i], 来算a[i+1] - a[n]中有多少个数字和它的乘积是能被k整除的。如果我们可以知道最小的x,是的 x*a[i]能被k整除，那么a[i+1]-a[n]中的每个能整除x的数都是我们要找的数。那么这个最小的x怎么算呢，其实是k/gcd(k, a[i]), 所以我们事先要对k分解因数，然后把数组中能整除这些因数的元素的个数事先存好。然后针对每个元素a[i]，计算x，再计算a[i+1]-a[n]中能整除x的元素个数

2022-03-10

2670

LeetCode weekly contest 278 (amazon pay)

二叉树 hash word

第三题 O(n)的计算hash值。利用取模运算法则，从后往前先计算k个字符的hash 值，然后开始向左移动，每次移动都要先减去右边最后一个值，然后再乘以P，最后加上左边的

2022-03-10

2860

LeetCode 228. Summary Ranges

题目 class Solution { public: vector<string> summaryRanges(vector<int>& nums) { vector<string> ans; if(nums.size()==0) return ans; int left=nums[0]; int right; string str="";

2022-03-10

2360

LeetCode 227. Basic Calculator II(后缀表达式)

题目后缀表达式一把嗦。 class Solution { public: int s1[1000005]; int s2[1000005]; int s3[1000005]; int top1; int top2; int top3; int calculate(string s) { top1=0;top2=0;top3=0; string str=""; for(int i=0;i

2022-03-10

2960

LeetCode 226. Invert Binary Tree

题目翻转二叉树 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* invertTree(T

2022-03-10

2200

LeetCode 225 Implement Stack using Queues

题目 class MyStack { public: queue<int> q; /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { q.push(x); } /** Removes the element on top o

2022-03-10

3030

LeetCode 1931. Painting a Grid With Three Different Colors(DP)

题解，动态规划因为m 最大只有5，所以我们可以枚举5个相邻的块，最多有多少种可能，然后分析每个是否能与其他几个并排，然后就是简单的BP了

2021-10-09

2610

LeetCode 1803. Count Pairs With XOR in a Range (二叉树)

二叉树数组

题目在一个数组里面找到两个数异或的结果在某个范围之内。这种题目，就要用二叉树，代码写的又臭又长。。 struct Node { int value; int left; int right; int num; int pos; }tree[200005]; class Solution { public: int hight; int lower; int fun(int root, int number, int h, int l, int pos) { if(pos==

2021-06-22

3320

LeetCode 357. Count Numbers with Unique Digits

题目毫无意义的题目。 class Solution { public: int countNumbersWithUniqueDigits(int n) { if(n==0) return 1; int ans=0; for(int i=1;i<=n;i++) { ans+=fun(i); } return ans;

2021-05-10

2370

LeetCode 1766. Tree of Coprimes

题解：由于节点上的值在1-50之间，所以算互质很好算，事先算法。然后就是深度优先遍历树的时候维护路径上的节点的位置，利用1-50这个小范围，快速找到与当前节点值互质的值出现在哪些位置上

2021-04-01

3610

LeetCode 1739. Building Boxes

https://leetcode.com/problems/building-boxes/ 题意：在一个边长是n的立方体中放n个方块，方块可以叠加，但是被叠加的在下方的方块八面必须挨着墙或者别的方块。问最底部最少可以放多少个方块。

2021-03-02

4630

1745. Palindrome Partitioning IV (回文树)

题意：判断一个字符串是否可以由三个回文串组成题解：利用强大的回文树，计算出以每个字符为结尾的回文串，然后从字符串的最后一个字符开始，递归判断。

2021-03-02

2460

1755. Closest Subsequence Sum

题解：数组的长度为40，找出全部子集一共有240种可能性，如果把一个数组平均分成两部分，分别算出两部分的所有子集和，每部分有220种可能，然后再二分查找答案。

2021-03-02

4930

LeetCode 1723. Find Minimum Time to Finish All Jobs

题解：暴力DFS，但是要注意两个地方剪枝，首先在DFS的过程中判断当前的最大值是不是已经超过了已有答案。第二个剪枝的地方比较triky，由于我们对k组没有顺序要求的，所以当剩下的组都是空的时候，我们只需要DFS第一个组。

2021-02-04

3980

LeetCode 1632. Rank Transform of a Matrix

思路是贪心，将所有的元素从小到大排序。并且维护两个数组，一个数组代表每一行的当前已经填上的最大的rank，比如nrank[0]=2 表示第0行，目前已经填到了rank=2，下一个再填就一定是>=2的数字。同理列也是。一开始nrank[],和mrank[]都赋值为0。当我们贪心到一个元素的时候，它的rank，就是max(nrank[n], mrank[m])+1， , 然后在遍历所有元素的之前，我们需要用并查集把那些值相同并且行或者列相同的元素并起来，因为这些元素的rank值一定相同。

2021-01-02

8200

LeetCode 1595 Minimum Cost to Connect Two Groups of Points (动态规划)

动态规划二进制压缩

题解：动态规划，用二进制压缩状态，注意分析几种情况，就能推出来正确的状态转移方程。

2020-10-28

5500

LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

题意：一个只有0-9组成的字符串，每次选择任意一个子串，按照数字从小到大排序。问从源字符串能否经过若干次操作转换成目标字符串。

2020-09-22

5780

LeetCode 1553. Minimum Number of Days to Eat N Oranges

题意：一堆橘子，要么吃一个，如果橘子数量能被2整除就可以吃一半，如果橘子数量能被3整除就可以吃三分之二，请问最少几次能吃完？

2020-09-17

4480

点击加载更多

社区活动

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·干货材料·成员作品最新动态