狗狗家昂赛

第2题， 可以暴力dfs吗

reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...

followup 空出任意一格，怎么做呢？

reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...

这个思路是对的，divide and conquer，用小L拼成大L，L型块是可以旋转的。用递归来解决。可惜我当时花了很久才想到这个思路也没写出完整的代码

reliveinfire 发表于 2017-11-14 10:54
请问第一题怎么做呢?

用stack, O(N) 是否可行?

第一题有几种解法，题目要求三个数不一定是连续的

1. 暴力O(n^3)
2. 从前往后遍历，用数组pre[n]存储在i位时 0到i-1的最小值；
    从后往前遍历，用数组after[n]存储在i位时 i+1到n-1的最大值；
    再遍历一遍数组看是否存在pre[i] < array[i] < after[i]
    O(n)time O(n) space
3. 遍历时存储前面元素的最小值min1，和第二小值min2, 和canidata_min， min1和min2要满足index递增,
    当前元素大于min1 小于min2时更新min2；当前元素小于min1时更新candidate_min; 当前元素大于
    candidate_min小于min2时更新min1，min2；当前元素大于min2返回true
    O(n)time O(1) space
   

the first problem is 334. Increasing Triplet Subsequence?
sorry, no chinese input right now.

Benbenbird 发表于 2017-11-17 05:27
the first problem is 334. Increasing Triplet Subsequence?
sorry, no chinese input right now.

没错，难怪当时看的觉得眼熟

reliveinfire 发表于 2017-11-15 10:16
第二题, 可以先考虑 2*2, 会发现如果, 有一格被占用, 剩下的可以L补满

再考虑4*4, 可以切成 4个2*2, ( ...

厉害厉害！膜拜