之和 随想录 随想day7

第九章 动态规划part17 ● 647. 回文子串 ● 516.最长回文子序列 ● 动态规划总结篇 今天 我们就要结束动态规划章节了，大家激不激动！！！ 详细布置 647. 回文子串 动态规划解决的经典题目，如果没接触过的话，别硬想 直接看题解。 https://programmercarl.co ......

01背包问题 二维 要求： 有一个背包，他只能装4KG，分别有三个物品： 1 15；3 20； 4 30 ——》需要物品价值最大 dp[i][j] 含义： 在放物品I 的时候在J背包容量下的物品最大值 递推公式： 1,不放当前物品：dp[i-1][j]2，放当前物品：(dp[i-1][j]) ->不 ......

问题描述 834. 树中距离之和 (Hard) 给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。 给定整数 n 和数组 edges ， edges[i] = [aᵢ, bᵢ] 表示树中的节点 aᵢ 和 bᵢ 之间有一条边。 返回长度为 n 的数组 answe ......

# 题目描述 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注 ......

343. 整数拆分 要求： 将一个正数拆分成N个正整数，使得这N个正整数的乘机是最大的 思路： DP数组：dp[n] N 的时候，它的乘机最大值 注意： 不是i*dp[n-i]就是最大值，因为如果用dp就证明要开始拆分了，如果我不拆分，就是用的这两个数的话，那么就是单纯的 i* (n-i) 代码： ......

#***一、easy_word*** #1.得到一个需要密码打开的docx，压缩包的备注里有密码提示，写个脚本爆破，得到密码 点击查看代码 ``` import string import hashlib hs = 'b75d1224' ls = string.ascii_letters + str ......

 是道挺明显的换根dp，但是我还是不会orz 首先暴力的思路是容易想的，比如以0为根节点，然后做一遍dfs ......

补发一下 前天的博客 就就讲一下代课的事情 发现现在的小孩子们都越来越不听话，不得不说，他们都有了自己的自我意识 不像我们小时候那种憨憨的劲 让我震惊的是 为啥一个新初三 连乘法都算不会！！！ 服了 ......

给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。 给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。 返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节 ......

62.不同路径 思路： 因为只能向左，和向下，因此只能是前面的加上左边的，递推公式较为简单 代码： 1 int uniquePaths(int m, int n) { 2 if (m == 1 || n == 1) return 1; 3 4 vector<vector<int>> nums(m, ......

509. 斐波那契数 思路： 运用动态规划的思想 1，先定义一个数组 2，初始化 3，递推公式 4，遍历 代码： 1 int fib(int n) 2 { 3 if (n == 0) return 0; 4 if (n == 1) return 1; 5 6 vector<int> selected ......

title: 2022 省队二轮集训培训日记 Day7 mathjax: true date: 2022-07-24 08:35:06 tags: - 培训日记 - DP - 凸包 - 网络流 feature: false categories: 做题记录 cover: https://pic.im ......

738.单调递增的数字 要求： 保证最大的一个数，它满足 每个位数都是递增的 思路1： 为了减少时间复杂度，当时打算，先判断最大的位数，从大-》小，看以后的位数是否满足当前数比前一个数大 思路2： 其实前面再往后想想：就是如果当前的数不满足，直接降级，然后后面都是9 就可以了 ——》一定要好好看例子 ......

435. 无重叠区间 要求： 给了多个区间，然后找出来删掉最少的区间数，从而可以让上下的区间不重叠 换个想法： 当前节点和上一个节点如果重叠，那么我就+1，然后缩小上一个节点，如果还是跟上一个节点重叠，那么就证明这个节点也要删除 小技巧： lamda函数不好用，每次比较的时候都会在定义一个cmp函数 ......

今天还是来理解空间复杂度 其实就是开摆一天 当讨论空间复杂度时，我们可以通过具体的代码示例来说明不同情况下的空间复杂度。 示例 1: 常数空间复杂度 O(1) void printNumber(int num) { int count = 0; // 常数级别的额外空间 for (int i = 0 ......

860.柠檬水找零 思路： 遇到20，先给10和5，再给三个5 代码： 1 bool lemonadeChange(vector<int>& bills) { 2 if (bills.size() == 0) return true; 3 4 map<int, int> currentMoney; ......

# 各位数字之和排序 [题目链接](https://acm.sdut.edu.cn/onlinejudge3/problems/1188?from=%2Fsets%2F11) 1. ```c #include int main(){ int n; int a[10];//进行交换位置的原数组 int ......

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1： 输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 ta ......

 # 排序+二分 可以先对数组排序，这样就拥有了单调性，就可以在其上做二分。 首先枚举第一个数a，然后枚 ......

1005.K次取反后最大化的数组和 思路： 仅排序一次，当前数<下一个数，就反转当前数，如果大于，那么就反转下一个 ——》也就是保证每次反转都是最小的数 注意：如果移动到最后一个节点了，K还没用完，那么就证明只能反转K 代码： 1 int largestSumAfterKNegations(vect ......

这里记录每周的所见所闻，周日发布。点击阅读原文可以直接访问文章链接。 # 工具 1. [Grafana Labs](https://grafana.com/zh-cn/grafana/?tab=revenue) 2. [Prometheus](https://prometheus.io/docs/i ......

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注意：答案中不可 ......

#### 【每日一题】[15. 三数之和](https://leetcode.cn/problems/3sum/) 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i ......

一个长度为 n 下标从 0 开始的整数数组 arr 的 不平衡数字 定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目： * 0 1 这里，sorted(arr) 表示将数组 arr 排序后得到的数组。 给你一个下标从 0 开始的整数数组 nums ，请你返回它所有子数 ......

 典中典，没啥好说的，主要练习一下Rust的二分查找API。 ```Rust impl Solution ......

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 如当一个算法的空间复杂度为一个常量，即不随被处理数据 ......

122.买卖股票的最佳时机II 注意： 1，第一个和最后一个 2，只有一个数的情况 3，2255，这种情况 思路： 1，买入：左：空/高/平 右：高 2，卖出：左：低 右：空/ 低/平 代码： 1 int maxProfit(vector<int>& prices) { 2 int result = ......

● 739. 每日温度 ● 496.下一个更大元素 I 单调栈 那有同学就问了，我怎么能想到用单调栈呢？ 什么时候用单调栈呢？ 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。 那么单调栈的原理是什么呢？为什么时间 ......

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字： 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 ![](htt ......

求两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = ......