J*****v
发帖数: 314 | 1 给你你个数组，要你返回数组的最小值的平方是否小于最大值。题目很简单，需要注意
的就是最小值的平方可能越界。
follow-up：如果这个数组不满足第一题中的条件，然后允许你执行“删除数组的第一
个元素”的操作，让你返回要执行多少次，也就是删除多少个数组前面的元素后才能满
足第一题中的条件。如果删完都不满足，返回-1；这一题小哥反复提示才想出来一个O
（n）的做法，然后今天看还有个小bug，哎。。
接着follow-up：如果可以每次都可以选择删除第一个或者最后一个，问最少要删掉几
次。。 | z*****6
发帖数: 16 | 2 搞一個bst，查lowerKey(min*min), 存在就返回rank，不存在就回-1 | w****e
发帖数: 586 | 3 第一个follow-up, 从后往前找最长的满足要求的序列不就好了吗，O(n)
第二个follow-up，O(nlogn)容易，O(n)要再想想 | M***6
发帖数: 895 | 4 bst里存什么？没看懂
[在 zou2016 (middleboy) 的大作中提到：]
:搞一個bst，查lowerKey(min*min), 存在就返回rank，不存在就回-1 | z*****6
发帖数: 16 | 5 我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
更大，所以無論怎麼刪除，都不能完成第一題的條件，對麼？ | w****e
发帖数: 586 | 6 确实有点怪，不过我认为是lz描述反了
【在 z*****6 的大作中提到】
: 我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
: 更大，所以無論怎麼刪除，都不能完成第一題的條件，對麼？
| J*****L
发帖数: 73 | 7 follow up有大小说错了吧
越删 min^2 | t******3
发帖数: 3 | | J*****v
发帖数: 314 | 9 删除头尾元素可以改变整个数组的最大值和最小值
【在 z*****6 的大作中提到】
: 我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
: 更大，所以無論怎麼刪除，都不能完成第一題的條件，對麼？
| o****d
发帖数: 2835 | 10 你仔细想想 删除元素只可能让最小值变大 以及 最大值变小 这样如果原题不成立 那
么删除后更不会成立
应该是楼主描述反了
★ 发自iPhone App: ChineseWeb 13
【在 J*****v 的大作中提到】
: 删除头尾元素可以改变整个数组的最大值和最小值
| | | c********t
发帖数: 5706 | 11 lz描述应该是正确的。因为最小数可能是负数。
第一个follow-up，从后往前找，不需要都满足，找到满足的最小index
第二个 use min to split to subarrays , 再对每个subarray check， recursion 找
到最长的满足. O(nlogn)
【在 w****e 的大作中提到】
: 第一个follow-up, 从后往前找最长的满足要求的序列不就好了吗，O(n)
: 第二个follow-up，O(nlogn)容易，O(n)要再想想
| J*****v
发帖数: 314 | 12 没错，因为有负数，所以题目是对的。
我们很可能需要把各个数的平方根存在一个数组里，这样比较快很多。
但是两个follow-up还需要其他trick才能解决，你的解法能详细说说吗？
【在 c********t 的大作中提到】
: lz描述应该是正确的。因为最小数可能是负数。
: 第一个follow-up，从后往前找，不需要都满足，找到满足的最小index
: 第二个 use min to split to subarrays , 再对每个subarray check， recursion 找
: 到最长的满足. O(nlogn)
| h**********c
发帖数: 4120 | | J*****v
发帖数: 314 | 14 可以。这是第一个follow-up的O(N)解法，需要预先把非负数全部开根号存下来，还要
把rightMin全部存下来。
但第二个follow-up还没想出来。
public int minDelectionFromFront(int[] nums) {
if(minSquaredSmallerThanMax(nums)) {
return 0;
}
int len = nums.length;
double[] sqrts = new double[len];
for (int i = 0; i < len; i++) {
sqrts[i] = nums[i] >= 0 ? Math.sqrt(nums[i]) : Double.MIN_VALUE;
}
double[] rightMaxSqrt = new double[len];
int[] rightMin = new int[len];
for (int i = len - 1; i >= 0; i--) {
if (i == len - 1) {
rightMaxSqrt[i] = sqrts[len - 1];
rightMin[i] = nums[len - 1];
} else {
rightMaxSqrt[i] = Math.max(rightMaxSqrt[i + 1], sqrts[i]);
rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
}
}
//System.out.println("rightMaxSqrt = " + Arrays.toString(
rightMaxSqrt));
//System.out.println("rightMin = " + Arrays.toString(rightMin));
for (int i = 0; i < len; i++) {
if (nums[i] == rightMin[i] && Math.abs(nums[i]) < rightMaxSqrt[i
]) {
return i;
}
}
return -1;
}
【在 h**********c 的大作中提到】
: 很小心翼翼问，把最大数开根号行吗？
| J*****v
发帖数: 314 | 15 第二个follow-up如果用上面同样的方法可解，时间复杂度O(N^2)，不知道有没有更好
的方法？ | J*****v
发帖数: 314 | 16 终于做出来了，这题用来刷掉三哥效果最好
public class Solution {
public boolean minSquaredSmallerThanMax(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
return (long) min * min < max;
}
public int minDelectionFromFront(int[] nums) {
if(minSquaredSmallerThanMax(nums)) {
return 0;
}
int len = nums.length;
double[] sqrts = new double[len];
for (int i = 0; i < len; i++) {
sqrts[i] = nums[i] >= 0 ? Math.sqrt(nums[i]) : Double.MIN_VALUE;
}
double[] rightMaxSqrt = new double[len];
int[] rightMin = new int[len];
for (int i = len - 1; i >= 0; i--) {
if (i == len - 1) {
rightMaxSqrt[i] = sqrts[len - 1];
rightMin[i] = nums[len - 1];
} else {
rightMaxSqrt[i] = Math.max(rightMaxSqrt[i + 1], sqrts[i]);
rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
}
}
//System.out.println("rightMaxSqrt = " + Arrays.toString(
rightMaxSqrt));
//System.out.println("rightMin = " + Arrays.toString(rightMin));
for (int i = 0; i < len; i++) {
if (nums[i] == rightMin[i] && Math.abs(nums[i]) < rightMaxSqrt[i
]) {
return i;
}
}
return -1;
}
public int minDelectionFromBothEnds(int[] nums) {
if(minSquaredSmallerThanMax(nums)) {
return 0;
}
int len = nums.length;
double[] sqrts = new double[len];
for (int i = 0; i < len; i++) {
sqrts[i] = nums[i] >= 0 ? Math.sqrt(nums[i]) : Double.MIN_VALUE;
}
//j >= i
double[][] maxSqrt = new double[len][len];
//j >= i
int[][] min = new int[len][len];
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if (i == j) {
maxSqrt[i][j] = sqrts[i];
min[i][j] = nums[i];
} else {
maxSqrt[i][j] = Math.max(maxSqrt[i + 1][j], sqrts[i]);
min[i][j] = Math.min(min[i + 1][j], nums[i]);
}
}
}
//print("maxSqrt", maxSqrt);
//print("min", min);
int res = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if(
(nums[j] == min[i][j] && Math.abs(nums[j]) < maxSqrt[i][j])
||
(nums[i] == min[i][j] && Math.abs(nums[i]) < maxSqrt[i][j])
) {
res = Math.min(res, len - (j - i + 1));
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
public static void main(String[] args) {
test(new int[] {-9, -8, -7, 4, 25, -11, -20}, false, -1, 5);
test(new int[] {-9, -8, -7, 4, 25, -11, -2}, false, -1, 5);
test(new int[] {-9, -8, -7, 4, 25, -1, -2}, false, -1, 3);
test(new int[] {-9, -8, -7, 4, 25, -1}, false, -1, 3);
test(new int[] {-7, 4, 25}, false, 1, 1);
test(new int[] {-9, -8, -7, 4, 25}, false, 3, 3);
test(new int[] {-49, 1, 4, -1}, false, -1, 1);
test(new int[] {-7, 1, 2, -1}, false, -1, 1);
test(new int[] {-9, 5, -8, -7, 2}, false, -1, -1);
test(new int[] {-9, 3, 2, -8, -7, 5}, false, -1, -1);
test(new int[] {-9, 2, -8, -7, 5}, false, -1, -1);
test(new int[] {-9, 2, -8, -7, 2, 5}, false, 4, 4);
test(new int[] {-9, -8, -7, 2, 5}, false, 3, 3);
test(new int[] { -7, 2, 5}, false, 1, 1);
test(new int[] { 9, -7, 2, 5}, false, 2, 2);
test(new int[] { 1, 2, 3, 4 }, true, 0, 0);
test(new int[] { 5 }, false, -1, -1);
test(new int[] { 1 }, false, -1, -1);
test(new int[] { 5, 1, 3 }, true, 0, 0);
test(new int[] { 1, 1, 1 }, false, -1, -1);
test(new int[] { 5, 3, 1 }, true, 0, 0);
test(new int[] { 2, 5, 3, 1 }, true, 0, 0);
test(new int[] { -2 }, false, -1, -1);
test(new int[] { 1, 5, 3 }, true, 0, 0);
}
private static void test(int[] nums, boolean expectedRes1, int
expectedMinDelectionFromFront, int expectedTakenEnds) {
System.out.println("when nums = " + Arrays.toString(nums));
boolean actualRes1 = soln.minSquaredSmallerThanMax(nums);
int actualMinDelectionFromFront = soln.minDelectionFromFront(nums);
int actualTakenEnds = soln.minDelectionFromBothEnds(nums);
if(actualRes1 != expectedRes1) {
System.err.println("actualRes1 = " + actualRes1 + ", while
expected result = " + expectedRes1);
} else if(actualMinDelectionFromFront !=
expectedMinDelectionFromFront) {
System.err.println("actualMinDelectionFromFront = " +
actualMinDelectionFromFront + ", while expected result = " +
expectedMinDelectionFromFront);
} else if(actualTakenEnds != expectedTakenEnds) {
System.err.println("Error. actualTakenEnds = " + actualTakenEnds
+ ", while expected result = " + expectedTakenEnds);
} else {
System.out.println("Test case passed");
}
System.out.println("==============");
}
static Solution soln = new Solution();
void print(String s, int[][] matrix) {
System.out.println(s + " = ");
for(int[] row : matrix) {
System.out.println(Arrays.toString(row));
}
}
void print(String s, double[][] matrix) {
System.out.println(s + " = ");
for(double[] row : matrix) {
System.out.println(Arrays.toString(row));
}
}
} | z*****6
发帖数: 16 | 17 你第一个test case，-20的平方是小于25的呀。我怎么觉得这个题可以用stack来做，
复杂度是O（N）
我想法是用一个min stack和max stack，存的下标。如果nums[min.peek()]平方小于
max.peek的，那么就count=Math.min取更优解。然后pop min，否则就pop max。我的疑
问是这么pop min和pop max正确么，可能会漏掉解。因为：min：2，3， max：5，6，
按照上面逻辑会pop min的2而不是pop max的5，但是2和6可能挨的更近。所以需要一种
构建min和max的stack的方法使其不会造成这样的情况，或着可以干脆同样逻辑倒着再
跑一遍（match的时候pop max，不match的时候pop min）
总体无论哪种形式应该都是O（N） | c******e
发帖数: 73 | 18 First follow up as above mentioned by wishee (温顺的野猪) and coldknight (
冷骑士),
Start from the array end , and check forward, until find the first index
doesn't meet the requirement. It should be simpleer than 各个数的平方根存在
一个数组里.
Second follow up, I can think to sort first, and creat the hashmap for (
value, index) , then go one pass to find the first value meet the
requirement and get the index, it will be o(nlogn) . | b******y
发帖数: 168 | 19 要不是in order，删第一个和删最后一个有什么区别？ | r********k
发帖数: 258 | 20 For the first extension, the solution is correct. For the second option,
here is one way to do it:
1. find min and max of the array;
2. check if condition is met; if so, stop.
3. if condition is not met, split array into three:
from min to max, and left over two min_leftover, and max_leftover.
4. repeat step 1 and step 2 for three arrays.
5. emit -1 if all recursions end without meeting the condition. | | | J*****v
发帖数: 314 | 21 -20的平方当然大于25啊！
【在 z*****6 的大作中提到】
: 你第一个test case，-20的平方是小于25的呀。我怎么觉得这个题可以用stack来做，
: 复杂度是O（N）
: 我想法是用一个min stack和max stack，存的下标。如果nums[min.peek()]平方小于
: max.peek的，那么就count=Math.min取更优解。然后pop min，否则就pop max。我的疑
: 问是这么pop min和pop max正确么，可能会漏掉解。因为：min：2，3， max：5，6，
: 按照上面逻辑会pop min的2而不是pop max的5，但是2和6可能挨的更近。所以需要一种
: 构建min和max的stack的方法使其不会造成这样的情况，或着可以干脆同样逻辑倒着再
: 跑一遍（match的时候pop max，不match的时候pop min）
: 总体无论哪种形式应该都是O（N）
| J*****v
发帖数: 314 | 22 值有可能有重复的，用HashMap会把重复的值覆盖掉
(
【在 c******e 的大作中提到】
: First follow up as above mentioned by wishee (温顺的野猪) and coldknight (
: 冷骑士),
: Start from the array end , and check forward, until find the first index
: doesn't meet the requirement. It should be simpleer than 各个数的平方根存在
: 一个数组里.
: Second follow up, I can think to sort first, and creat the hashmap for (
: value, index) , then go one pass to find the first value meet the
: requirement and get the index, it will be o(nlogn) .
| c*******t
发帖数: 1095 | 23 用stack建left/right min/max 数组
follow 1：
原值建rightMax
平方值建rightMin
再 2 pointer
follow 2：
能从两个方向去掉唯一的好处就是去掉最后一个的时候可以选择从前去掉或者从后去掉
，两个取最优
再对称做一遍的，建leftMax和leftMin，2pointer
取最优 O(n) | J*****v
发帖数: 314 | 24 follow 2每删一次元素都会导致一维leftMax和leftMin变动，所以你说的O(N)不可能成
立，只能用二维数组leftMax和leftMin，所以不会是O(N)
这题没这么简单，你们想的太简单了
【在 c*******t 的大作中提到】
: 用stack建left/right min/max 数组
: follow 1：
: 原值建rightMax
: 平方值建rightMin
: 再 2 pointer
: follow 2：
: 能从两个方向去掉唯一的好处就是去掉最后一个的时候可以选择从前去掉或者从后去掉
: ，两个取最优
: 再对称做一遍的，建leftMax和leftMin，2pointer
: 取最优 O(n)
| d********e
发帖数: 1720 | 25 O(N)?
用DP, 从后面往前递归验证，cache results.
O
【在 J*****v 的大作中提到】
: 给你你个数组，要你返回数组的最小值的平方是否小于最大值。题目很简单，需要注意
: 的就是最小值的平方可能越界。
: follow-up：如果这个数组不满足第一题中的条件，然后允许你执行“删除数组的第一
: 个元素”的操作，让你返回要执行多少次，也就是删除多少个数组前面的元素后才能满
: 足第一题中的条件。如果删完都不满足，返回-1；这一题小哥反复提示才想出来一个O
: （n）的做法，然后今天看还有个小bug，哎。。
: 接着follow-up：如果可以每次都可以选择删除第一个或者最后一个，问最少要删掉几
: 次。。
| w****e
发帖数: 586 | 26 不知道你在折腾什么。第一个follow up都和你说了从后往前找符合条件的最长序列，
一个for loop，O(1) space就搞定了的事
第二个follow up，其实就是在问符合条件的连续最长子序列是多长。O(nlogn)时间的
做法恐怕不少，这是一个：
1. 对每个元素，创建一个二元组，（value，index）
2. sort这些二元组based on value。
第1、2步其实就是带着index sort一把。时间O(nlogn)
3. 创建一个与原数组等长的数组bool visited[]，初始化0
4. 按着value从大到小遍历排序好的二元组
4a. 如果visited[index]>0, continue
4b. 否则，按index回到原来数组，从该元素出发向左向右走到不能走（出现负数
并且平方超过该元素）位置。路上经过的所有数全部把相应visited位置改成1。比较此
时序列长度是否超过已发现的最长子序列。如是则记录此时序列长度。
最后输出记录下来的最长子序列。
二元组只遍历一遍，原数组在visited[]的帮助下每个元素也只会被访问一次。所以第3
、4步合起来时间O(n)
最终的时间复杂度O(nlogn)，空间复杂度O(n)
其实很简单，对吧... 但是我不知道有没有更好的。
【在 J*****v 的大作中提到】
: 可以。这是第一个follow-up的O(N)解法，需要预先把非负数全部开根号存下来，还要
: 把rightMin全部存下来。
: 但第二个follow-up还没想出来。
: public int minDelectionFromFront(int[] nums) {
: if(minSquaredSmallerThanMax(nums)) {
: return 0;
: }
: int len = nums.length;
: double[] sqrts = new double[len];
: for (int i = 0; i < len; i++) {
| w****e
发帖数: 586 | 27 靠，写完这么长才想到，其实sort是不必要的，确实有O(n)时间的做法。说破了也不难
。。trick就是用hashmap记住已知的子序列头尾index对应，避免重复检查。
【在 w****e 的大作中提到】
: 不知道你在折腾什么。第一个follow up都和你说了从后往前找符合条件的最长序列，
: 一个for loop，O(1) space就搞定了的事
: 第二个follow up，其实就是在问符合条件的连续最长子序列是多长。O(nlogn)时间的
: 做法恐怕不少，这是一个：
: 1. 对每个元素，创建一个二元组，（value，index）
: 2. sort这些二元组based on value。
: 第1、2步其实就是带着index sort一把。时间O(nlogn)
: 3. 创建一个与原数组等长的数组bool visited[]，初始化0
: 4. 按着value从大到小遍历排序好的二元组
: 4a. 如果visited[index]>0, continue
| b******y
发帖数: 168 | 28 第一问可能就需要递归。如果min max同号，不需要做。如果min max异号，max在min的
前面，直接从min的index生成新数组，递归。如果min在max前面，从min的index到max
找符合要求的vlaue，找到停，找不到从max的index生成新数组，。
第二问主要是找min max中间，没有就两头各生成一个新数组，做两个递归 |
|
