hexo主题开发中的洗牌算法
背景今天打开博客页面，发现主页这么呈现： 很明显是因为随机封面算法是真随机，于是找到现在在用的主题butterfly中，随机封面的算法如下： 123456789const randomCoverFn = () => { const { cover: { default_cover: defaultCover }, } = hexo.theme.config; if (!defaultCover) return false; if (!Array.isArray(defaultCover)) return defaultCover; const num = Math.floor(Math.random() * defaultCover.length); return...
每日一题-股票价格跨度
问题Link 设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度 。 当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。 实现 StockSpanner 类： StockSpanner() 初始化类对象。 int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。 难度：一般 思路 一维数组的第一个小于/大于问题应该用单调栈解法； 定义一个递减单调栈，每个元素是索引与price的二元组； 每次返回栈顶元素与该元素索引差。 代码123456789101112131415161718192021222324var StockSpanner = function () { this.stack = [[-1, Number.MAX_VALUE]]; this.index = -1;};/** * @param...
每日一题-买卖股票的最佳时机含手续费
问题Link 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。 难度：一般 思路 使用动态规划思想解题 定义状态：dp[i][0]表示第i天手上没有股票的利润，dp[i][1]表示第i天手上有股票的利润 状态转移方程与初始状态： 1234dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[0][0] = 0;dp[0][1] = -price[0]; 每天的状态只和前一天有关，无需存储整个数组，所以状态转移方程为： 12buy = max(buy, sell -...
每日一题-买卖股票的最佳时机III
问题Link 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 难度：困难 思路 题目限定了只能进行两笔交易，显然贪心算法这种方法不考虑交易不行 使用动态规划解法，定义状态dp[i]代表第i天结束时手里的钱数 定义状态sell1,buy1,sell2,buy2代表买了一次，买卖一次，买卖一次+买了二次，买买二次 每天的状态只和前一天有关，无需存储整个数组，所以状态转移方程为：1234buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]); 接下来考虑初始状态，第0天如果手里买进了，就是-prices[0]，没有就是0。 代码1234567891011121314151617/** * @param...
每日一题-买卖股票的最佳时机II
问题Link 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 思路题目没说不可以同一天卖了又买。所以贪心算法，将折线图中所有上坡都收集到，就是最大利润。 代码1234567891011121314/** * @param {number[]} prices * @return {number} */var maxProfit = function (prices) { let ans = 0; for (let i = 1; i < prices.length; i++) { let profit = prices[i] - prices[i - 1]; if (profit > 0) { ans += profit; } } return...
每日一题之打家劫舍III
问题Link 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。 思路 子问题是节点k的左右节点的最大收获。 我们可以用f(o)表示选择o节点的情况下，o节点的子树上被选择的节点的最大权值和；g(o)表示不选择o节点的情况下，o节点的子树上被选择的节点的最大权值和； 当o被选中时，左右节点不能选中，也就是f(o)=g(l)+g(r)+o 当o不选中时，g(o)=max{f(l),g(l)}+max{f(r),g(r)} 使用深度优先遍历二叉树 代码123456789101112131415161718192021222324import java.util.HashMap;import...
每日一题之打家劫舍II
问题Link 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 思路 和昨天的问题一样，属于动态规划问题 房子排成环形，只需要分类讨论，第一间房子偷不偷，区间是[0,k-2],[1,k-1] 特殊情况是只有1间或两间房子。 同样可以节省空间，两个变量循环存储dp数组 代码1234567891011121314151617181920212223class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } else if (n == 2) { return...