算法

打家劫舍问题

算法

朋友圈问题

算法

股票买卖问题

算法

零钱兑换问题

算法

搜索二维矩阵问题

朋友圈问题
11月1日 · 2020年

朋友圈问题

401 0
朋友圈 班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/friend-circles著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。...
路径总和问题
10月25日 · 2020年

路径总和问题

330 0
一、路径总和 I 递归 public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return root.val == sum; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}...
搜索二维矩阵问题
10月18日 · 2020年

搜索二维矩阵问题

326 1
搜索二维矩阵问题 前言 搜索二维矩阵 I和搜索二维矩阵 II两道题在解题思路上都是围绕二分查找展开的,搜索二维矩阵 I比较简单,纯暴力或直接套二分查找的公式(二维的二分查找)即可,而搜索二维矩阵 II的解题方法就比较特别,个人感觉有点意思,故在此记录下~...
零钱兑换问题
10月18日 · 2020年

零钱兑换问题

378 0
一、零钱兑换 I 自顶向下、使用备忘录(HashMap)的递归解法 // 备忘录Map<Integer, Integer> memoMap = new HashMap<>();public int coinChange(int[] coins, int amount) { // 查备忘录,避免重复计算 if (memoMap.containsKey(amount)) { return memoMap.get(amount); } // base case if (amount == 0) return 0; // 下面的递归入参,假如 amount - coin < 0,则返回 -1 if (amount < 0) return -1; // 最差的情况,就是使用 amount 个面值为 1 的硬币,而 amount + 1 就是个不存在的值,下面要比较最小值,则每次递归都使用 amount + 1 比较求最小值即可 int res = amount + 1; for (int coin : coins) { // 子问题(目标金额减去当前 coin) int subProblem = coinChange(coins, amount - coin); if (subProblem == -1) continue; // 求最值,即 res 与 子问题加上一个 coin(与上面`目标金额减去当前 coin`相对应,即自顶向下的思想) 求最值 res = Math.min(res, subProblem + 1); } res = res == amount + 1 ? -1 : res; memoMap.put(amount, res); return res;}...
打家劫舍问题
9月13日 · 2020年

打家劫舍问题

853 2
本文整理于自己的学习笔记.. 一、打家劫舍 I 自顶向下、使用备忘录的递归解法 自顶向下:递归一般是自顶向下,依赖于子问题优化函数的结果,只有子问题完全求出,也就是子问题的递归返回结果,原问题才能求解。...
股票买卖问题
9月6日 · 2020年

股票买卖问题

476 0
葵花宝典 状态转移框架dp[i][k][1]:表示今天是第 i 天,手上持有股票,至今最多允许交易 k 次dp[i][k][0]:表示今天是第 i 天,手上没有持有股票,至今最多允许交易 k 次 /** * 解释:今天我没有持有股票,有两种可能: * 1、要么是我昨天就没有持有,然后今天选择 rest,所以我今天还是没有持有; * 2、要么是我昨天持有股票,但是我今天 sell 了,所以我今天没有持有股票了。 * max( 选择 rest, 选择 sell ) */ ...
12月29日 · 2019年

数据结构:跳表

1644 0
本文主要总结下自己学习跳表时的一些笔记,主要包含跳表的由来、时空复杂度、增删改查和具体应用四个方面。二分查找的数据结构是数组,利用数组随机访问查找的时间复杂度是 O(logn)。如果数据结构是链表,可以达到这样的速度吗?答案是可以的,只是需要对链表进行改造,改造之后的结构就是跳表(又名跳跃表),是一种动态数据结构,可以支持快速的插入、删除、查找、按范围查找,功能类似于红黑树,Redis 中的有序集合使用的就是跳表(后文会说)。...