题目链接 题意： 在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。 思路： 训练的时候一眼二分，但是求圆并的时候gg了。。毫无思路。 搞定了多个圆面积并。。这题就很easy了。。 需要注意，每次二分的时候，记得初始化圆的d... /* *********************************************** Author :111qqz File Name :H.cpp …

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array …

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. 思路：找规律。。。二分。。。 0 1 2 3 4 …

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 思 …

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Write a function to determine if a given target is in the array. The array may contain duplicates. 好像阿里一面的时候问过。。。 思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。 总的思路是。。。当发现重复元素。。并且该重复元素不 …

题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 思路：二分。。。注意有重复元素。。。 class Solution { public: int minNumberInRotateArray(vector<int> a) { int siz = a.size(); int l = 0 ; int r = siz-1; while (r-l>1) { int mid = (l+r)>>1; if (a[mid]>a[r]) l …

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。 /* *********************************************** Author :111qqz Created Time :2017年03月09日 星期四 19时03分07秒 File Name :74.cpp ************************************************ */ class Solution { public: bool …

题目链接 题意：求一个BST中某两个节点LCA.... 思路：卧槽。。。竟然求LCA...直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。 两个节点的LCA的值一定在这两个节点之间。 可以根据这个条件做二分。。。 这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; …

题目链接 d:题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。 思路：先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333. upd:和lca没有什么关系，因为一个点能控制另一个点这两个点一定在一条通向根的链上，因此距离直接减一下就好了。 机智的做法：dfs的时候维护一个栈，对于栈中序列，后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u，现在我们固定u，考虑能控制他的v。这些v在树上的形态 …

题目链接 题意：n只青蛙，第i只位于x[i],舌头长度为t[i]。m只蚊子，第i只蚊子所在位置为p[i],蚊子的大小为b[i]。 蚊子按照出现顺序输入。 一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。 当多只青蛙可以吃到同一只蚊子的时候，最左边的那只青蛙来吃。 当一只青蛙吃掉一只蚊子以后，青蛙的舌头增加蚊子的大小。 当一只青蛙吃掉一只蚊子后，因为舌头边长而又能吃到其他蚊子的时候，这只青蛙会继续吃，只到当前没有蚊子可以被任何一只青蛙吃到，在这个过程之后才会飞来下一只蚊子。 思路：问题的关键在于，对于某只蚊子，我们如何找到能吃到该蚊子的青蛙中最左边的那只。 可以抽象成寻找区 …