Tag: ACM 题解

这题比较有意思, 拿来分享一下: 在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y. 当且仅当对应于值x和y的节点是同类时, 才返回true. 例如: 1 2 3 2和3的父母是同一个, 所以不是表兄弟(妹) 1 2 3 4 5 4和5是, 因为来自不同的父母, 并且所以树的高度是一样的. 深度优先+递归 二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, …

一只袋鼠要从河这边跳到河对岸, 河很宽, 但是河中间打了很多桩子, 每隔一米就有一个, 每个桩子上都有一个弹簧, 袋鼠跳到弹簧上就可以跳的更远. 每个弹簧力量不同, 用一个数字代表它的力量, 如果弹簧力量为5, 就代表袋鼠下一跳最多能够跳5米, 如果为0, 就会陷进去无法继续跳跃. 河流一共N米宽, 袋鼠初始位置就在第一个弹簧上面, 要跳到最后一个弹簧之后就算过河了, 给定每个弹簧的力量, 求袋鼠最少需要多少跳能够到达对岸. 如果无法到达输出-1 输入描述: 输入分两行, 第一行是数组长度N (1 ≤ N ≤ 10000), 第二行是每一项的值, 用空格分隔. 输出描述: …

最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷 能力立马下降许多) 题意就是 不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是. 很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下: typedef unsigned long long …