Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
找到第一個缺失的正整數(shù)，每個正整數(shù)放在n-1的下標上。
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size();) {
if (nums[i] != nums[nums[i] - 1] && nums[i] - 1 >= 0 && nums[i] - 1 < nums.size()) {
swap(nums[i], nums[nums[i]-1]);
} else {
i++;
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != i + 1) return i+1;
}
return nums.size()+1;
}
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Subscribe to see which companies asked this question.
將矩陣中出現(xiàn)0的行和列全部設(shè)置為0。主要是空間復(fù)雜度上O(m+n) => O(1)不好想，不遍歷第一列，使用col0記錄第一列是否出現(xiàn)0.
void setZeroes(vector<vector<int> > &matrix) {
int col0 = 1, m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; ++i) {
if (!matrix[i][0]) col0 = 0;
for (int j = 1; j < n; ++j) {
if (!matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 1; --j) {
if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
}
if (!col0) matrix[i][0] = 0;
}
}
解析: 找出0,1數(shù)組中 連續(xù)1出現(xiàn)的最長個數(shù)。
邊界：為空
思路：可以使用left、right指針，很好寫。更簡單易懂的方式是使用計數(shù)器len，遍歷數(shù)組在數(shù)組元素為1時，len++，數(shù)組元素為0時，len=0
時間復(fù)雜度：O(n)
int findMaxConsecutiveOnes(vector<int>& nums) {
int max_cnt = 0, cnt = 0;
for (auto n : nums) {
if (n == 1) max_cnt = max(++cnt, max_cnt);
else cnt = 0;
}
return max_cnt;
}
解析: 找出數(shù)組中未出現(xiàn)的數(shù)字(1<= nums[i] <= n)
邊界：
思路：可以使用笨方法，空間復(fù)雜度O(n)。也可以使用trick，將出現(xiàn)的下標的元素+= n。
時間復(fù)雜度：O(n)
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (auto n:nums) {
nums[(n-1)%nums.size()] += nums.size();
}
vector<int> ret;
for (int i = 0; i< nums.size(); ++i) {
if (nums[i] <= nums.size()) {
ret.push_back(i+1);
}
}
return ret;
}
解析: 求數(shù)組中其他元素的乘積，不允許除法，要求O(n) 時間，O(1)空間
邊界：數(shù)組為空
思路：這道題不好想，因為不允許除法。使用左右乘積，left每次記錄乘到上一個的積，right每次記錄從后往前乘積。當left和right有交叉時，便形成了所有左邊的乘積乘以右邊的乘積。關(guān)鍵點：left、right累積乘積，res數(shù)組初始化為1，從而res[i]leftright的結(jié)果為去除該元素外的乘積。
時間復(fù)雜度：O(n)
vector<int> productExceptSelf(vector<int>& nums) {
int left = 1, right = 1;
vector<int> res(nums.size(),1);
for (int i = 0; i < nums.size(); ++i) {
res[i] *= left;
left *= nums[i];
res[nums.size() - 1 -i] *= right;
right *= nums[nums.size() -1 - i];
}
return res;
}
531. Lonely Pixel I
解析: 求行列中只有B的點的個數(shù)
邊界：數(shù)組為空
思路：分別記錄行、列的B出現(xiàn)次數(shù)，再進行一次循環(huán)元素為'B'且行、列出現(xiàn)次數(shù)都為1時，為不重復(fù)點。
時間復(fù)雜度：O(nm)
int findLonelyPixel(vector<vector<char>>& picture) {
vector<int> rows(picture.size(),0);
vector<int> columns(picture[0].size(),0);
for (int i = 0; i < picture.size(); ++i) {
for (int j = 0; j < picture[i].size(); ++j) {
if (picture[i][j] == 'B') {
rows[i]++;
columns[j]++;
}
}
}
int res = 0;
for (int i = 0; i < picture.size(); ++i) {
for (int j = 0; j < picture[i].size(); ++j) {
if (picture[i][j] == 'B' && rows[i] == 1 && columns[j] == 1) {
res++;
}
}
}
return res;
}
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
解析: 矩陣每個點附近8個位置
live -> live 2/3
dead -> live 3
其他情況都為dead。
思路：1. 遍歷全部位置的附近位置，判斷滿足下一階段為live的情況，board[i][j] |= 2。 2. 遍歷全部位置board[i][j] 右移一位
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = m?board[0].size():0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int count = 0;
for (int I = max(i - 1, 0); I < min (i + 2, m); ++I) {
for (int J = max(j - 1, 0); J < min(j + 2, n); ++J) {
count += board[I][J] & 1;
}
}
if (count == 3 || count - board[i][j] == 3) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
board[i][j] >>= 1;
}
}
}
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
解析: 插入間隔到不重疊的間隔數(shù)組中
邊界：數(shù)組為空，不重疊
思路：題目挺簡單，但是思路要清楚簡潔。1. 插入前面不重疊的部分。 2. 找出重疊部分最小的起始位置和最大的結(jié)束位置，插入新的間隔。 3. 插入后面不重疊的部分
時間復(fù)雜度：O(n)
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> res;
auto it = intervals.begin();
for (; it != intervals.end(); ++it) {
if (newInterval.start > it->end) res.push_back(*it);
else if (newInterval.end < it->start) break;
else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it -> end);
}
}
res.push_back(Interval(newInterval.start, newInterval.end));
res.insert(res.end(), it, intervals.end());
return res;
}
解析: 起始詞到達終止詞最短距離
邊界：數(shù)組為空
思路：BFS。此處使用的技巧是雙向BFS，2頭都可以找能到達且存在于給定詞典中的，每次使用短的那個進行遍歷。startWords為某一段能到達的集合，比endWords短。
時間復(fù)雜度：O(n!)
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end()) return 0;
unordered_set<string> startWords({beginWord});
unordered_set<string> endWords({ endWord });
return ladderHelper(startWords, endWords, dict, 1);
}
int ladderHelper(unordered_set<string> startWords, unordered_set<string> endWords, unordered_set<string> dict, int level) {
if (startWords.empty()) return 0;
if (startWords.size() > endWords.size()) return ladderHelper(endWords, startWords, dict, level);
for (auto word : startWords) dict.erase(word);
for (auto word : endWords) dict.erase(word);
unordered_set<string> middleWords;
for (auto word : startWords) {
string newWord = word;
for (int i = 0; i < word.size(); ++i) {
word = newWord;
for (int j = 0; j < 26; j++) {
word[i] = 'a' + j;
if (endWords.find(word) != endWords.end()) return level + 1;
else if (dict.find(word) != dict.end()) {
middleWords.insert(word);
}
}
}
}
return ladderHelper(middleWords, endWords, dict, level + 1);
}
