刷题半年，也没找到。
面试官为什么出这个题！？梳理梳理面试官就几个维度
写对了但是没有讲到核心考点
这五个维度很重要
伸展核心法：能够回答怎么想到的，follow up比较清楚
闷头写错的
负数题目
We want to find the first bad version and have an API isBadVersion, we want to use least call and we want to know
第一步能不能复述这个题目
0000011111 sequence
深度的建模，有加分，我的笔记
Find first 1
Least operation isBadVersion
第二步：solution
Since we need least call, iteration needs O(N)
binary-search is better than iteration O(logN)
Binary-search to find the first 1.
If the mid == 1 we still continue to (left,mid)
else we continue to (mid, right)
Binary-search的关键是有序数列，为什么能用二叉搜索的关键，考点严谨
From brute force to best solution, 加分项，有了一个完整过程
逻辑性太差
第三步：coding
public int findFirst (int[] input) {
int left = 0;
int right = input.length - 1;
int result = -1;
while (left < right) {
int mid = left + ( right - left) / 2;
if (isBadVersion(mid) == 1) {
result = mid;
right = mid; } else {
left = mid + 1;
}
}
return result;
}
corner case不需要处理
如果写的好的代码是不需要有corner case
第四步：test case
000000000
0001111111
1111111111
1
0
01
两个元素很有可能会有死循环
长度为0，1，2，3这样罗列
{}
1
0
00
01
11
000
001
011
111
一般情况：
00001
11111
000111
超长情况：
0 * 10000000 & 1 * 10
0 * 100000000
如何推出是二叉搜索的
start < end? 怎么证明不会超时？
考点：两点
// interval will reduce either start ++ or end --
// runtime error 1 <= start <= mid <= end <= n
3
版本会被修好的，之后一直就是好的
好与坏的区间怎么找到？
00001111100000
Since, it is not sorted array now, we can not use BS now.
But if we find one, we can use BS on the other side.
Worst Case O(n)
Best Case
we can find the first 1 and the end 1 to get the interval
但是不能两侧用binary search了，不是sorted了
linear to find the last 1 (n2) find the first 1 (n1)
(n1 , n2)
扫地机器人：
题目：
机器人有3种走路方式，（向前，向左，向右）
遇到障碍物会停下啊
机器人有两种操作模式， 向前走或者转弯（转弯包括向左和向右）
目的：设计一条路线，能把整个房间打扫干净
会碰到的三种情况 + . ^
Math :
给定一个起点，遍历一个矩阵，有向前和向左向右转弯模式
思路：
Math modeling
Graph with wall +, a robrt begin in one position
Move
Turn left/right
Clean
Goal: Design a solution to clean all the house
其实就是矩阵遍历
DFS
BFS
可以BFS，效率更高
priority A*
网友评论