用动态规化或者深度优先算法来数2英镑有多少种组合方法
英国的英镑硬币有 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), 和 £2 (200p). 比如我们可以用以下方式来组成2英镑 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p 问: 一共有多少种方式可以组成2英镑? 注意 不能有重复, 比如 …
Tag: 算法
组合数学中卡塔兰数的动态规化求解方法
卡塔兰数(Catalan Numbers) 是个很神奇的数列. 高中信息学竞赛很喜欢出有关卡塔兰数的问题, 特别是在初赛(笔试)的时候, 经常会有一题真空题就是卡塔兰数的应用. 在组合数学中, 卡塔兰数有着许多应用, 卡塔兰数的前几个数字是: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, …
浅谈虚拟货币交易所三角套利的算法
高频交易(HFT, High Frequency Trading) 指得是我们可以让程序调用交易所的API 来自动下买单或者卖单, 赚差价来达到挣钱的目的. 常见的高频交易策略有低买高卖, 本文介绍一种常见的三角套利的策略. 高频交易 (HFT) 简介 高频交易 (HFT) 是一种算法交易, 它使用计算机程序在金融市场上快速执行交易. 它是一种自动交易形式, 使用复杂的算法来分析市场数据并以闪电般的速度执行交易. 对冲基金和投资银行等大型机构投资者使用高频交易来利用市场中的微小价格差异. 高频交易者使用复杂的算法来识别和利用这些价格差异. 这些算法旨在扫描市场以寻找潜在机会, 并在发现机会后立即执行交易. 这使得高频交易者可以在价格差异消失之前利用它们. 高频交易者还使用复杂的风险管理技术来限制他们的风险敞口. 通过使用止损单和其他风险管理策略, 高频交易者可以在市场走势对他们不利时限制损失. 高频交易是一项复杂且具有风险的策略, 并不适合所有投资者. 在尝试使用高频交易之前了解与高频交易相关的风险非常重要. …
二叉树判断表兄弟表兄妹算法(递归, 深度优先)
这题比较有意思, 拿来分享一下: 在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y. 当且仅当对应于值x和y的节点是同类时, 才返回true. 例如: 1 2 3 2和3的父母是同一个, 所以不是表兄弟(妹) 1 2 3 4 5 4和5是, 因为来自不同的父母, 并且所以树的高度是一样的. 深度优先+递归 二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, …
做题送美人 Python 题解: (两质数相乘等于 707829217)
上个月去北爱游玩, 看朋友圈传这个, 一直拖延至今天才有点时间写写题解: 后来了解到, 这个是HR的套路, 并不是真的做题送美人, 不过这题还是挺有意思的, 至少能复习一下素数的一些相关算法. 暴力穷举 题目要求是两质数相乘 等于 707829217, 这数也不大, 至少不需要用于大整数 bignum, 2的31次方是: 2147483648. 因此我们可以从3开始暴力, 每次加2, 直到 根号(707829217)=26605即可, 这数很小, 现在的计算机秒秒就出结果了. 算到根号就可以了, 因为暴力小的数, 大的数自然可以用707829217一除即可. 然后我们分别判断一下是否是质数即可. 质数判断从2到 根号, …
经典二叉树的镜像(反转二叉树)的递归算法
操作给定的二叉树, 将其变换为源二叉树的镜像. 反转给定的二叉树 输入描述: 二叉树的镜像定义: 源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ …
袋鼠过河题解(动态规化+贪心算法)
一只袋鼠要从河这边跳到河对岸, 河很宽, 但是河中间打了很多桩子, 每隔一米就有一个, 每个桩子上都有一个弹簧, 袋鼠跳到弹簧上就可以跳的更远. 每个弹簧力量不同, 用一个数字代表它的力量, 如果弹簧力量为5, 就代表袋鼠下一跳最多能够跳5米, 如果为0, 就会陷进去无法继续跳跃. 河流一共N米宽, 袋鼠初始位置就在第一个弹簧上面, 要跳到最后一个弹簧之后就算过河了, 给定每个弹簧的力量, 求袋鼠最少需要多少跳能够到达对岸. 如果无法到达输出-1 输入描述: 输入分两行, 第一行是数组长度N (1 ≤ N ≤ 10000), 第二行是每一项的值, 用空格分隔. 输出描述: …