s****n
发帖数: 199 | 1 两道leetcode原题
1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
外的空间。
没刷到这两道题，第二道题磕磕碰碰没做完
脸家前辈来说说是不是这样就没戏了？
谢谢 |
i*****d
发帖数: 962 | |
S**I
发帖数: 15689 | 3 第二题磕磕碰碰不应该啊；LC上的原题是从sorted linked list转BST，算是有一点难
度；反过来一个in-order traversal就解决了。
【在 s****n 的大作中提到】
: 两道leetcode原题
: 1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
: false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
: 2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
: 外的空间。
: 没刷到这两道题，第二道题磕磕碰碰没做完
: 脸家前辈来说说是不是这样就没戏了？
: 谢谢
|
c*******a
发帖数: 1879 | 4 什么叫 “判断一个array of integer是不是单调”？
单调增， 单调减？
O(N)?
【在 s****n 的大作中提到】
: 两道leetcode原题
: 1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
: false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
: 2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
: 外的空间。
: 没刷到这两道题，第二道题磕磕碰碰没做完
: 脸家前辈来说说是不是这样就没戏了？
: 谢谢
|
W***o
发帖数: 6519 | 5 左右各扫一遍即可，复杂度没变化
: 什么叫 “判断一个array of integer是不是单调”？
: 单调增， 单调减？
: O(N)?
【在 c*******a 的大作中提到】
: 什么叫 “判断一个array of integer是不是单调”？
: 单调增， 单调减？
: O(N)?
|
c*******a
发帖数: 1879 | 6 解释一下题目的意思吧
【在 W***o 的大作中提到】
: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增， 单调减？
:
: O(N)?
:
|
W***o
发帖数: 6519 | 7 楼猪的例子已经不能再清楚了
: 解释一下题目的意思吧
【在 c*******a 的大作中提到】
: 解释一下题目的意思吧
|
t****b
发帖数: 2484 | 8 牛 我还想着用个flag标一下增减
这样写个helper 然后扫两遍就够了 又快又好
【在 W***o 的大作中提到】
: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增， 单调减？
:
: O(N)?
:
|
y******x
发帖数: 31 | 9 扫一遍看最大最小值是不是在两端也行吧。
: 牛 我还想着用个flag标一下增减
: 这样写个helper 然后扫两遍就够了 又快又好
【在 t****b 的大作中提到】
: 牛 我还想着用个flag标一下增减
: 这样写个helper 然后扫两遍就够了 又快又好
|
t****b
发帖数: 2484 | 10 1 2 4 3 5
就不行啊
【在 y******x 的大作中提到】
: 扫一遍看最大最小值是不是在两端也行吧。
:
:
: 牛 我还想着用个flag标一下增减
:
: 这样写个helper 然后扫两遍就够了 又快又好
:
|
|
|
x***r
发帖数: 11 | 11 楼主运气真好，碰到这么简单的题
楼主运气真背，这么简单的题竟然没有刷到 |
s****a
发帖数: 794 | |
t**********n
发帖数: 1718 | 13 刷了poj 这些题就如同小儿科 40W大包送上门 |
o****p
发帖数: 9785 | 14 小苑城边猎骑回
手中已有新春桂
一方狱市获来苏
伸舒轶出元气外
包含万象藏心里
子若得之慎勿失
来时歌舞助欢娱 |
s******b
发帖数: 185 | 15 不懂啊。左右扫一遍然后呢？
【在 W***o 的大作中提到】
: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增， 单调减？
:
: O(N)?
:
|
s******b
发帖数: 185 | 16 不许用额外空间怎么办？
【在 S**I 的大作中提到】
: 第二题磕磕碰碰不应该啊；LC上的原题是从sorted linked list转BST，算是有一点难
: 度；反过来一个in-order traversal就解决了。
|
l**8
发帖数: 44 | 17 第一题我也不太会，在网上搜的一个答案， 不知道大牛具体是怎么做的。
public boolean isIncreasingOrDecreasing(int[] arr) {
boolean increasing = true, decreasing = true;
if (arr.length <= 2) {
return true;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i-1]) {
increasing = false;
}
if (arr[i] > arr[i-1]) {
decreasing = false;
}
if (!increasing && !decreasing) {
return false;
}
}
return true;
} |
u***n
发帖数: 21026 | 18 对的，扫一遍就可以了，一个判断增，一个判断减，只要有一个判断全过就是单调
【在 l**8 的大作中提到】
: 第一题我也不太会，在网上搜的一个答案， 不知道大牛具体是怎么做的。
: public boolean isIncreasingOrDecreasing(int[] arr) {
: boolean increasing = true, decreasing = true;
: if (arr.length <= 2) {
: return true;
: }
: for (int i = 1; i < arr.length; i++) {
: if (arr[i] < arr[i-1]) {
: increasing = false;
: }
|
u***n
发帖数: 21026 | 19 不需要额外空间，linkedlist value就是Treenode
【在 s******b 的大作中提到】
: 不许用额外空间怎么办？
|
t****b
发帖数: 2484 | 20 这个太长 而且引入了变量 不够优雅 我来抛个砖
private bool isInc (int[] array) {
for(int i=0;i
if(array[i]>array[i+1]) return false;
}
return true;
}
public bool isMono (int[] array) {
return isInc(array) || isInc(array.reverse());
}
【在 l**8 的大作中提到】
: 第一题我也不太会，在网上搜的一个答案， 不知道大牛具体是怎么做的。
: public boolean isIncreasingOrDecreasing(int[] arr) {
: boolean increasing = true, decreasing = true;
: if (arr.length <= 2) {
: return true;
: }
: for (int i = 1; i < arr.length; i++) {
: if (arr[i] < arr[i-1]) {
: increasing = false;
: }
|
|
|
W***o
发帖数: 6519 | 21 几个月之前写的代码
public static boolean isMonotonic(int[] A) {
int n = A.length, start = 1;
while (start < n && A[start] == A[start-1]) { start++; }
if (start == n) return true; // NOTE: critical
boolean isIncreasing = A[start] > A[start-1];
for (int i = start + 1; i < n; i++) {
if (isIncreasing && A[i] < A[i-1]) return false;
if (!isIncreasing && A[i] > A[i-1]) return false;
}
return true;
}
// 单调栈的思路
public static boolean isMonotonic2(int[] A) {
int n = A.length, start = 1;
while (start < n && A[start] == A[start-1]) { start++; }
if (start == n) return true; // NOTE: critical
boolean isIncreasing = A[start] > A[start-1];
int prev = A[start];
for (int i = start + 1; i < n; i++) {
if (isIncreasing && A[i] < prev || !isIncreasing && A[i] > prev)
return false;
prev = A[i]; // update prev -- this is simpler than monotonic
stack!
}
/*
Stack stack = new Stack<>();
for (int i = start; i < n; i++) {
// 单调栈存储的是数值,不是INDEX
while (stack.size() > 0 && ((isIncreasing && A[i] < stack.peek()
) || (!isIncreasing && A[i] > stack.peek()))) {
if (isIncreasing && A[i] < stack.peek()) return false;
else if (!isIncreasing && A[i] > stack.peek()) return false;
}
stack.push(A[i]);
}
*/
return true;
} |
s******b
发帖数: 185 | 22 dfs所需要的空间不算？
【在 u***n 的大作中提到】
: 不需要额外空间，linkedlist value就是Treenode
|
s******b
发帖数: 185 | 23 没有贴完。
【在 W***o 的大作中提到】
: 几个月之前写的代码
: public static boolean isMonotonic(int[] A) {
: int n = A.length, start = 1;
: while (start < n && A[start] == A[start-1]) { start++; }
: if (start == n) return true; // NOTE: critical
: boolean isIncreasing = A[start] > A[start-1];
: for (int i = start + 1; i < n; i++) {
: if (isIncreasing && A[i] < A[i-1]) return false;
: if (!isIncreasing && A[i] > A[i-1]) return false;
: }
|
D**********7
发帖数: 28 | 24 上周salesforce也考过这题，思路就是上面回复的，扫一遍就可以了。 |
l**8
发帖数: 44 | 25 第二道题是用inorder traversal, 但是有些tricky.
如果只是把元素值打印出来或者放入到list的话，就是个简单的inorder traversal.
但是这里是要把BST变成linked list。在遍历的时候要把tree node的left child变成
null, right child变为 next node of an in-order traversal.
刚开始我也写不出来，后来去看LC 114. Flatten Binary Tree to Linked List.
把那道题的最优解法改动了一下：
public class Solution {
private TreeNode pre = null;
private void flatten(TreeNode root){
if(root==null) return;
flatten(root.right);
root.right=pre;
pre=root;
TreeNode leftchild=root.left;
root.left=null;
flatten(leftchild);
}
}
这里pre记录的是上一个访问的node，也是linked list中的next child. 思路是build
the linked list from the tail. 这里，先访问right child， 然后是current root,
最后是left child。
代码不长，但是我自己也想不出来... |
m******e
发帖数: 82 | 26 比较头尾数字，可以得出增或减或相等，定义3个bool predictor，循环的时候用指定
predictor即可，楼主以为如何 |
f*****n
发帖数: 2126 | 27 第一题报个题号吧， 我怎么没搜出来这题。 今天开始刷了。首先是sort colors。 |
B*******O
发帖数: 543 | 28 Omg 现在真是什么人都敢去脸书面试啦
【在 t****b 的大作中提到】
: 这个太长 而且引入了变量 不够优雅 我来抛个砖
: private bool isInc (int[] array) {
: for(int i=0;i: if(array[i]>array[i+1]) return false;
: }
: return true;
: }
: public bool isMono (int[] array) {
: return isInc(array) || isInc(array.reverse());
: }
|
X******g
发帖数: 10 | 29 第二题用Morris Inorder遍历就行。
vector inorderTraversal(TreeNode* root)
{
vector res;
TreeNode* curr=root;
while(curr)
{
if(!curr->left)
{
res.push_back(curr->val);
curr=curr->right;
}
else
{
TreeNode* lrMost=curr->left;
while(lrMost->right&&lrMost->right!=curr)
lrMost=lrMost->right;
if(!lrMost->right)
lrMost->right=curr,curr=curr->left;
else //if lrMost->right==curr
{
lrMost->right=NULL;
res.push_back(curr->val);
curr=curr->right;
}
}
}
return res;
}
【在 s****n 的大作中提到】
: 两道leetcode原题
: 1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
: false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
: 2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
: 外的空间。
: 没刷到这两道题，第二道题磕磕碰碰没做完
: 脸家前辈来说说是不是这样就没戏了？
: 谢谢
|
p*********g
发帖数: 2998 | 30 这2题简单到爆了， 第一题左扫一遍，又扫一遍，
第二题，pre-order, middle -> left -> right |
|
|
u**u
发帖数: 668 | 31 单调题
class Solution {
public:
bool isMono(vector &nums) {
int n = nums.size();
if (n < 2) return true;
bool inc = false, dec = false;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) inc = true;
else if (nums[i] < nums[i - 1]) dec = true;
if (inc && dec) return false;
}
return true;
}
}; |
u**u
发帖数: 668 | 32 狗家题最近能把你们虐哭，烦的要死，各种自己遍的题 |
t****b
发帖数: 2484 | 33 太长 要是狗家的题 一定问你怎么能不考虑具体增减
【在 u**u 的大作中提到】
: 单调题
: class Solution {
: public:
: bool isMono(vector &nums) {
: int n = nums.size();
: if (n < 2) return true;
: bool inc = false, dec = false;
: for (int i = 1; i < n; i++) {
: if (nums[i] > nums[i - 1]) inc = true;
: else if (nums[i] < nums[i - 1]) dec = true;
|
s******b
发帖数: 185 | 34 第二题：
List* flattenToLL(Node* root) {
List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
root->left=NULL
root->right=list2
// The "middle" list3 cannot be NULL; append list2 to list3
if (!list1) return root; // Nothing to prepend
List *last = list1;
while (last->right) last=last->right; // Go to the end of list1
last->right = root; // Append list3+list2 to the end of list1
return list1;
} |
M***6
发帖数: 895 | 35 我也这么想的。这题太直接了，不考任何数据结构和算法。
【在 W***o 的大作中提到】
: 几个月之前写的代码
: public static boolean isMonotonic(int[] A) {
: int n = A.length, start = 1;
: while (start < n && A[start] == A[start-1]) { start++; }
: if (start == n) return true; // NOTE: critical
: boolean isIncreasing = A[start] > A[start-1];
: for (int i = start + 1; i < n; i++) {
: if (isIncreasing && A[i] < A[i-1]) return false;
: if (!isIncreasing && A[i] > A[i-1]) return false;
: }
|
p**k
发帖数: 8 | 36
你这个i++就优雅了？
【在 t****b 的大作中提到】
: 这个太长 而且引入了变量 不够优雅 我来抛个砖
: private bool isInc (int[] array) {
: for(int i=0;i: if(array[i]>array[i+1]) return false;
: }
: return true;
: }
: public bool isMono (int[] array) {
: return isInc(array) || isInc(array.reverse());
: }
|
s**********g
发帖数: 14942 | 37 recursion的空间当然要算
所以要用morris traversal
其实不算特简单
【在 s******b 的大作中提到】
: dfs所需要的空间不算？
|
s**********g
发帖数: 14942 | 38 morris traversal不是谁都会的
直接dfs有额外空间（recursion stack）
【在 p*********g 的大作中提到】
: 这2题简单到爆了， 第一题左扫一遍，又扫一遍，
: 第二题，pre-order, middle -> left -> right
|
s**********g
发帖数: 14942 | 39 啥叫最近
难道不一直都这样吗
【在 u**u 的大作中提到】
: 狗家题最近能把你们虐哭，烦的要死，各种自己遍的题
|
y****3
发帖数: 131 | 40
public class Monotonic {
enum type {
increasing, decreasing, undefined
}
public boolean isMonotonic(int[] input) {
if (input == null || input.length <= 1)
return true;
type mono_type = type.undefined;
for (int i = 0; i < input.length - 1; i++) {
if (input[i] > input[i+1]) {
if (mono_type == type.increasing) return false;
mono_type = type.decreasing;
}
else if (input[i] < input[i+1]) {
if (mono_type == type.decreasing) return false;
mono_type = type.increasing;
}
}
return true;
}
}
【在 s****n 的大作中提到】
: 两道leetcode原题
: 1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
: false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
: 2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
: 外的空间。
: 没刷到这两道题，第二道题磕磕碰碰没做完
: 脸家前辈来说说是不是这样就没戏了？
: 谢谢
|
