Month: July 2017

79. Word Search

Description:

https://leetcode.com/problems/word-search/#/description

Algorithm:

main:

for each element in 2D vector

{

if (board[i][j] == word[0])

{

mark the element;

dfs(board, pos_x, pos_y, height, width, wordIdx, word);

unmark the element;

}

}

dfs:

if (wordIdx == word.size())if (wordIdx == word.size()) return true;

check the four surrounding letters

 

if (board[i][j] == word[0])

{

mark the element;

if  dfs(board, pos_x, pos_y, height, width, wordIdx + 1, word)

return true;

unmark the element;

}

Code:

Actually my algorithm is TOTALLY the same with the fastest one. However, mine takes 76ms while the fastest only takes 6ms. I optimized my code again and again and finally get the fastest. Here are all my codes and i will show the improvements.

Code1 (76ms, beats 17.34%):

Code2 (16ms, beats 64.74%):

Main change from Code1 to Code2 is the usage of newPos_x and newPos_y

Code3 (6ms, beats 99.61%):

Main change from Code2 to Code3 is to use string &word instead of string word.

Store array to Mat

From: http://blog.csdn.net/u010417185/article/details/53114452

 

当采用这种方法取元素值得时候，type成为一个麻烦的问题，因为一般我们生成Mat的时候，都是这样的：

 

而取元素值时不能写成”a.at(x,y)”或者”a.at<a.type()>(x,y)”。

所以这里列出OpenCV中定义的型别和C++中型别的对应关系，

 

CV_8SC1 -> char

CV_8UC1 -> unsigned char

CV_16SC1 -> short

CV_16UC1 -> unsigned short

CV_32SC1 -> int

CV_32FC1 -> float

CV_64FC1 -> double

OpenCv中的数据型别命名规则为：CV_(比特数)+(数据类型)+(Channel数)，我们也可以直接根据命名规则得到相应的数据型别。

 

下面举例：

 
若不知道所属的属性，则可以通过转变数据类型进行获取值。本人一般喜欢转为double型，代码如下：

 

 

对于保存图片的Mat来说，下面给出读取Mat中数据的例子：

 

 

220. Contains Duplicate III

Description:

https://leetcode.com/problems/contains-duplicate-iii/#/description

Algorithm:

  • Use vector<pair<int, int>> to solve this problem.
  • Learn how to define comparison rules for std::sort()
    • sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; });

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

comp:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.

The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Why there is a green []?????

Code:

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
const int n = nums.size();
vector<pair<int, int>> pairs; // a vector of (value, index) pairs
pairs.reserve(n);
for (int i = 0; i < n; ++i)
pairs.emplace_back(nums[i], i);
sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; });
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j)
if ((long long)pairs[j].first - pairs[i].first <= t)
{
if (abs(pairs[j].second - pairs[i].second) <= k)
return true;
}
else
break;
return false;
}
};

Time & Space:

 

219. Contains Duplicate II

Description:

https://leetcode.com/problems/contains-duplicate-ii/#/description
Algorithm:

Easy

Code:

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.size() < 2) return false;
unordered_map <int, int> record;
for (int i = 0; i < nums.size();i++)
{
if (record.find(nums[i]) != record.end() && i - record[nums[i]] <= k)
return true;
else
record[nums[i]] = i;
}
return false;
}
};

Time & Space:

O(nlogn) & O(n)

map底层是红黑树实现的，因此它的find函数时间复杂度：O(logn)

217. Contains Duplicate

Description:

https://leetcode.com/problems/contains-duplicate/#/description

Algorithm:

  1. Use sort, very easy
  2. Don’t use sort, use a array to record the appearance of words. If a word appears for more than 1 times, return true.

Code1:

class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if (nums.size() < 2) return false;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1;i++)
{
if (nums[i] == nums[i+1])
return true;
}
return false;
}
};

Code2:

class Solution {
public:
bool containsDuplicate(vector& nums) {
int min = INT_MAX;
int max = INT_MIN;
for (int i = 0; i < nums.size(); ++i) { if (nums[i] > max) {
max = nums[i];
}

if (nums[i] < min) { min = nums[i]; } } vector exists(max - min + 1, false);
for (int i = 0; i < nums.size(); ++i) { if (exists[nums[i] - min]) { return true; } else { exists[nums[i] - min] = true; } } return false; } };

Time & Space:

Code1:

Time: O(nlogn) Space O(1)

Code2:

Time: O(n), Space O(n)

300. Longest Increasing Subsequence

Description:

https://leetcode.com/problems/longest-increasing-subsequence/#/description

Algorithm:

About explanation of Code1, 3, please refer to:

https://leetcode.com/articles/longest-increasing-subsequence/

For Code2:

There are two steps:

  • Step1:
    • Use array to record the index of number which is larger than num[i], priority: position
    • Use another array to record the index of number which is larger than num[i], priority: value
  • Step2
    • from end to start, find the max length of array
      • length = max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1;

Code1:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
vector<int> dp = vector<int>(nums.size(), 0);
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.size(); i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = max(maxans, dp[i]);
}
return maxans;
}
};

Code2:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> lengths = vector<int>(n, 1);
vector<int> posLarger = vector<int>(n, INT_MIN);
vector<int> valLarger = vector<int>(n, -1);
posLarger[n-1] = -1;
for (int i = 0; i < nums.size() - 1;i++)
{
for (int j = i + 1; j < nums.size();j++)
{
if (nums[j] > nums[i])
{
if (posLarger[i] == INT_MIN)
posLarger[i] = j;
if (valLarger[i] == -1)
valLarger[i] = j;
else if (nums[j] < nums[valLarger[i]])
valLarger[i] = j;
}
}
if (posLarger[i] == INT_MIN)
{
posLarger[i] = -1;
valLarger[i] = -1;
}
}
for (int i = nums.size() - 1; i >= 0;i--)
{
if (posLarger[i] >= 0)
lengths[i] = max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1;
}
int result = 1;
for (int i = 0;i < nums.size();i++)
{
if (lengths[i] > result)
result = lengths[i];
}
return result;
}
};

Code3:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for (int i = 0; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if (it == res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
};

Time & Space:

Code1:

// Simple DP solution, beats 10.42%
// Time: O(n2), Space: O(n)

Code2:

// My solution, beats 49.5%
// Time: O(n2), Space: O(n)

Code3:

Time: O(nlogn), Space: O(n)

Read Paper: Adaptive Image Space Sampling for Gaze-Contingent Real-time Rendering

Pipeline:

Implemented after geometry pass and before actual shading

Build visual perception model:

Derive per-pixel sample probability map P that assigns a single perceptual importance value in [0,1] for each feature.

Features

  • Acuity
    • Build a eccentricity fall-off model which is valid for more than 30degree.
    • Revise the model based on eye motion (the fovea becomes a line)
    • Should read Dropbox\OPENGL\papers\VISUAL SENSORY UNITS AND THE MINIMUM ANGLE OF RESOLUTION
  • Attention
    • Texture adaption:
      • just use mipmap: remove high frequency to avoid aliasing
    • 3 perceptual filters:
      • Object Saliency Detection: Fo
      • Silhouette Detection: Fs
      • Highlight Detection: Fh
  • Brightness adaption