## 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

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数)，我们也可以直接根据命名规则得到相应的数据型别。

## 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:

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:

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)

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