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.
找到第一個(gè)缺失的正整數(shù)仲吏，每個(gè)正整數(shù)放在n-1的下標(biāo)上冈闭。
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)的最長個(gè)數(shù)宋光。
邊界：為空
思路：可以使用left情连、right指針叽粹，很好寫。更簡單易懂的方式是使用計(jì)數(shù)器len，遍歷數(shù)組在數(shù)組元素為1時(shí)虫几，len++锤灿，數(shù)組元素為0時(shí)，len=0
時(shí)間復(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)的下標(biāo)的元素+= n啡氢。
時(shí)間復(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) 時(shí)間倘是，O(1)空間
邊界：數(shù)組為空
思路：這道題不好想亭枷，因?yàn)椴辉试S除法。使用左右乘積搀崭，left每次記錄乘到上一個(gè)的積奶栖，right每次記錄從后往前乘積。當(dāng)left和right有交叉時(shí)门坷，便形成了所有左邊的乘積乘以右邊的乘積宣鄙。關(guān)鍵點(diǎn)：left、right累積乘積默蚌，res數(shù)組初始化為1冻晤，從而res[i]leftright的結(jié)果為去除該元素外的乘積。
時(shí)間復(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的點(diǎn)的個(gè)數(shù)
邊界：數(shù)組為空
思路：分別記錄行绸吸、列的B出現(xiàn)次數(shù)鼻弧，再進(jìn)行一次循環(huán)元素為'B'且行、列出現(xiàn)次數(shù)都為1時(shí)锦茁，為不重復(fù)點(diǎn)攘轩。
時(shí)間復(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?
解析: 矩陣每個(gè)點(diǎn)附近8個(gè)位置
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. 插入后面不重疊的部分
時(shí)間復(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;
}
解析: 起始詞到達(dá)終止詞最短距離
邊界：數(shù)組為空
思路：BFS袖迎。此處使用的技巧是雙向BFS冕臭，2頭都可以找能到達(dá)且存在于給定詞典中的腺晾，每次使用短的那個(gè)進(jìn)行遍歷。startWords為某一段能到達(dá)的集合辜贵，比endWords短丘喻。
時(shí)間復(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);
}
