求问几道面经中的算法题

1.判断一个数组是否是大约排好序的数组，也就是下面两个条件满足一个
1. 交换任意两个数字，得到的是一个排好序的 比如 [1, 5, 3, 4, 2]
2. 数组中的一段子序列旋转后能是一个排好序的数组，比如[1,2, 7,6,5,4,3, 8,9]

2.定义一个点是valid的当覆盖在这个点上的interval数量不超过2（两个及以下）。求问，给一串intervals([0,2],[0,3],[1,3]...)，最少删掉几个interval可以使所有的点都valid

3.设计一个类中的put方法。
实现一个哈希表的结构，要求键值对按键的值升序排列，已经限定了键和值分别存在数组里，另外提供了插入键和插入值的方法，所以要实现的就是基于这两个方法的键值对插入。（提示用二分法？但是我还是有点迷惑）

4.给一个大整数，和几个幸运数字，求比大整数小的全部由幸运数字组成的整数的最大值

5.定义一个点是valid的当覆盖在这个点上的interval数量不超过2（两个及以下）。求问，给一串intervals([0,2],[0,3],[1,3]...)，最少删掉几个interval可以使所有的点都valid

解答加米！多谢朋友们

1. 可以用一个first来记录第一个不符合要求的点，这个时候，first一定大于他下一个。然后我们找second。second一定大于first - 1所对应的值，小于first以及second的后一个，同时从first + 1到second - 1之间一定是单调的，要么单增要么单减，

第一题我的思路是：
1） 拿两个单调栈monotonic stack从左向右和从右向左各扫一遍，把坐标扔一个set里面，可以得到所有不遵守规定的点
2） 然后是判断地狱，如果没有点，如果有 一个点，如果有两个点，如果有超过两个点。
3） 要是超过两个点，就找出最两头的俩点，先看俩点要是掉能不能塞回去，然后把中间的倒排序，要是倒序完了跟原来子串一样，说明之前就是倒序的，那翻转后应该ok

我写了几个test case看着像是对的，不知道对题意理解对不对

1. def is_almost_sorted(arr):
   
2.     stack = []
   
3.     points = set()
   
4.     for i in range(len(arr) - 1, -1, -1):
   
5.         n = arr[i]
   
6.         if len(stack) > 0 and n > arr[stack[-1]]:
   
7.             points.add(stack.pop())
   
8.         stack.append(i)
   
9.     stack = []
   
10.     for i in range(len(arr)):
    
11.         n = arr[i]
    
12.         if len(stack) > 0 and n < arr[stack[-1]]:
    
13.             points.add(stack.pop())
    
14.         stack.append(i)
    
15.     if len(points) == 0:
    
16.         return True
    
17.     if len(points) == 1:
    
18.         return False
    
19.     if len(points) == 2:
    
20.         return True
    
21.     l, r = min(points), max(points)
    
22.     if (l > 0 and arr[r] >= arr[l - 1]) and (r < len(arr) - 1 and arr[l] <= arr[r + 1]) and \
    
23.             sorted(arr[l:r + 1], reverse=True) == arr[l:r + 1]:
    
24.         return True
    
25.     return False
    

复制代码

第一题的第一部分我是暴力解法，两两交换看符不符合要求，Python代码如下：
def is_swappable(self, lst):
        s = sorted(lst)
        for i, j in combinations(range(len(lst)), 2):
            l = lst[:]
            l, l[j] = l[j], l[i]
            if l == s:
                return True
        return False[/i]
第二部分我忘记我写在哪个电脑里了，找到也发上来

2.我感觉可以把所有的endpoint都存下来，sort一下，用sweepline的做法从左往右扫，当count大于2的时候，通过maxHeap删掉最远的。然后记录删了多少个。

3.就是用二分找到需要插入的位置，然后调用那两个方法就好了吧

4. 没太看懂，感觉是贪心吧。然后数位dp的想法也在里面。就是把大整数的每一位存下来，从高到低，如果这一位正好是幸运数字，那就取这个数字，然后继续下一位。否则就取比当前数字小的最大幸运数字，剩下的位数全部取最大幸运数字。当然还有一个conrner case，就是有一位没法取幸运数字，这样的话直接取比原数字小一位，每一位都是幸运数字最大值的数字。

5和2一样吧

不知道小帅 发表于 2020-11-11 07:00
2.我感觉可以把所有的endpoint都存下来，sort一下，用sweepline的做法从左往右扫，当count大于2的时候，通 ...

通过maxHeap删掉最远的是什么意思呀？

不知道小帅 发表于 2020-11-11 06:53
1. 可以用一个first来记录第一个不符合要求的点，这个时候，first一定大于他下一个。然后我们找second。sec ...

赞！那第一个条件要怎么判断呀？（交换任意两个数字，得到的是一个排好序的 比如 [1, 5, 3, 4, 2]）

xhjennyz 发表于 2020-11-11 08:21
通过maxHeap删掉最远的是什么意思呀？

有点类似skyline那个题目，当前超过两个的话，我们贪心地删除右边能扩展到最远的那个，因为这样的话，我们更可能后面少删除。所以我们需要maxHeap来保存右端点。

xhjennyz 发表于 2020-11-11 08:28
赞！那第一个条件要怎么判断呀？（交换任意两个数字，得到的是一个排好序的 比如 [1, 5, 3, 4, 2]）

我感觉是一样的，对于第一种情况，从index first + 1到second - 1是单调递增的话就是第一种情况，单调递减就是第二种