Leetcode 刷题打卡记录包括Solution

wglacier

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

已经刷了几十道了，从今天开始争取每天打卡，同时把之前的也逐渐贴上来。
0060 Permutation Sequence

// 自己的解法，效率不高
// 484ms, 12.9%, 2019.1.26
class Solution {
private:
string buf;
int idx;
vector<bool> flags;
public:
bool getPerm(int n, int k, int start) {
if (start == n) {
idx++;
return idx == k;
}
for (int i = 0; i < n; i++) {
if (flags) continue;
flags = true;
char c = buf[start];
buf[start] = '0' + i + 1;
if (getPerm(n, k, start + 1))
return true;
flags = false;
buf[start] = c;
}
return false;
}
string getPermutation(int n, int k) {
string s(n, ' ');
flags.resize(n);
for (int i = 0; i < n; i++) {
s = '0' + i + 1;
flags = false;
}
buf = s;
idx = 0;
getPerm(n, k, 0);
return buf;
}
};
// 参考了这个帖子的讲解
// [url]https://leetcode.com/problems/permutation-sequence/discuss/22507/%22Explain-like-I'm-five%22-Java-Solution-in-O[/url](n)
// 0ms ,100%
/*
say n = 4, you have {1, 2, 3, 4}
If you were to list out all the permutations you have
1 + (permutations of 2, 3, 4)
2 + (permutations of 1, 3, 4)
3 + (permutations of 1, 2, 4)
4 + (permutations of 1, 2, 3)
*/
class Solution {
public:
string getPermutation(int n, int k) {
// calc facts
vector<int> facs(n + 1);
facs[0] = 1;
for (int i = 1; i <= n; i++) {
facs = i * facs[i-1];
}
string nums = "123456789";
string res;
for (int i = 1; i <= n; i++) {
int idx = (k-1) / facs[n-i];
res += nums[idx];
nums.erase(nums.begin() + idx);
k -= idx * facs[n-i];
}
return res;
}
};

复制代码

wglacier

0037. Sudoku Solver

class Solution {
private:
vector<vector<bool>> bufRows = vector<vector<bool>>(9, vector<bool>(256, false));
vector<vector<bool>> bufCols = vector<vector<bool>>(9, vector<bool>(256, false));
vector<vector<bool>> bufDias = vector<vector<bool>>(9, vector<bool>(256, false));
public:
bool isValid(vector<vector<char>>& board, int i, int j, char c) {
return !bufRows[i][c]
&& !bufCols[j][c]
&& !bufDias[i/3*3 + j/3][c];
}
void setFlag(vector<vector<char>>& board, int i, int j, char c, bool value) {
bufRows[i][c] = value;
bufCols[j][c] = value;
bufDias[i/3*3 + j/3][c] = value;
}
bool solve(vector<vector<char>>& board, int i, int j) {
if (i == 9) return true;
if (j == 9) return solve(board, i+1, 0);
char c = board[i][j];
if (c != '.') return solve(board, i, j+1);
for (char d = '1'; d <= '9'; d++) {
if (!isValid(board,i, j, d))
continue;
setFlag(board, i, j, d, true);
board[i][j] = d;
if (solve(board, i, j+1))
return true;
board[i][j] = '.';
setFlag(board, i, j, d, false);
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.')
continue;
bufRows[i][c] = true;
bufCols[j][c] = true;
bufDias[i/3*3 + j/3][c] = true;
}
}
solve(board, 0, 0);
}
};
```
```c++
class Solution {
public:
bool validatePos(const vector<vector<char>>& board, int i, int j) {
// vertical
vector<bool> vcols(9, false);
for (int m = 0; m < 9; m++) {
// cols
if (board[m][j] == '.') continue;
int num = board[m][j] - '1';
if (vcols[num]) {
return false;
}
vcols[num] = true;
}
// 3x3
vector<bool> vsqrs(9, false);
int basei = i/3*3;
int basej = j/3*3;
for (int m = 0; m < 9; m++) {
char c = board[basei+m/3][basej+m%3];
if (c == '.') continue;
int num = c - '1';
if (vsqrs[num]) return false;
vsqrs[num] = true;
}
return true;
}
bool tryNext(vector<vector<char>>& board, vector<vector<bool>>& cache) {
bool started = false;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') continue;
// try every possible values
for (int m = 0; m < 9; m++) {
if (!cache[i][m]) continue;
board[i][j] = m + '1';
cache[i][m] = false;
if (validatePos(board, i, j)
&& tryNext(board, cache)) {
return true;
}
board[i][j] = '.';
cache[i][m] = true;
}
// tried every possible ways still no luck, must have made a wrong attempt
return false;
}
}
// nothing left to guess
return true;
}
void solveSudoku(vector<vector<char>>& board) {
// pre-calc per row
vector<vector<bool>> cache(9, vector<bool>(9, true));
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
cache[i][c - '1'] = false;
}
}
}
tryNext(board, cache);
}
};

复制代码

wglacier

30. Substring with Concatenation of All Words
Solution 2 using Trie, 44ms

class Trie {
Trie *cc[26];
int pos;
public:
Trie() {
pos = -1;
fill_n(cc, 26, nullptr);
}
void insert(const string &s, int position) {
Trie* p = this;
for (auto &c : s) {
int idx = c - 'a';
if (!p->cc[idx]) {
p->cc[idx] = new Trie();
}
p = p->cc[idx];
}
p->pos = position;
}
int search(const string &s, int start, int sz) {
Trie* p = this;
for (int i = start; i < start + sz; i++) {
int idx = s[i] - 'a';
if (!p->cc[idx]) return -1;
p = p->cc[idx];
}
return p->pos;
}
};
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (words.empty() || s.empty())
return res;
unordered_map<string,int> mm;
for (auto &w : words) {
mm[w]++;
}
vector<int> flagTmpl(mm.size(), 0);
Trie trie;
int i = 0;
for (auto itt : mm) {
flagTmpl[i] = itt.second;
trie.insert(itt.first, i);
i++;
}
vector<int> dp(s.size(), -2);
const int WD_LEN = words[0].size();
for (int i = 0; i <= (int)s.size()-(int)(WD_LEN*words.size()); i++) {
if (dp[i] == -1) continue;
vector<int> flags(flagTmpl);
int flagCount = 0;
int start = i;
while (flagCount < words.size() && start <= s.size() - WD_LEN) {
int pos = dp[start];
if (pos == -1) break;
if (pos == -2) {
pos = trie.search(s, start, WD_LEN);
}
if (pos < 0) {
dp[start] = -1;
break;
}
if (flags[pos] < 1) {
break;
}
flags[pos]--;
dp[start] = pos;
start += WD_LEN;
++flagCount;
}
if (flagCount == words.size()) {
res.push_back(i);
}
}
return res;
}
};

复制代码

wglacier

0068 Text Justification, hard

// 0ms
class Solution {
private:
string outputOneJustify(vector<string> wbuf, int maxWidth, int len) {
// `len` is the total length of all words and one space between words
// words length without any spaces
int wlen = len - (wbuf.size() - 1);
int spacesLeft = maxWidth - wlen;
string res;
for (string& ws : wbuf) {
if (!res.empty()) {
res += string(spacesLeft/(wbuf.size()-1), ' ');
int extraSpaces = spacesLeft % (wbuf.size()-1);
if (extraSpaces > 0) {
res += string(1, ' ');
spacesLeft--;
}
}
res += ws;
}
if (res.size() < maxWidth) {
res += string(maxWidth - res.size(), ' ');
}
return res;
}
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int len = 0;
vector<string> wbuf;
vector<string> resStrs;
for (string& s : words) {
// every word needs a space before it except the first one
if (len > 0) ++len;
if (len + s.size() <= maxWidth) {
wbuf.push_back(s);
len += s.size();
} else {
len--;
string res = outputOneJustify(wbuf, maxWidth, len);
resStrs.push_back(res);
len = s.size();
wbuf.clear();
wbuf.push_back(s);
}
}
// last line
if (len > 0) {
string res;
for (string& s : wbuf) {
if (!res.empty()) {
res += string(1, ' ');
}
res += s;
}
if (res.size() < maxWidth) {
res += string(maxWidth - res.size(), ' ');
}
resStrs.push_back(res);
}
return resStrs;
}
};
int main(int argc, char* argv[]) {
vector<string> v = {
"This", "is", "an", "example", "of", "text", "justification."
};
for (string a : Solution().fullJustify(v, 16))
cout << "'" << a << "'" << endl;
return 0;
}

复制代码

wglacier

0061 Rotate List

// 4ms, 100%
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr)
return head;
// get the length
int len = 0;
ListNode *p = head;
while (p != nullptr) {
len++;
p = p->next;
}
k = k % len;
if (k == 0) return head;
// make p k steps ahead of q
p = head;
ListNode *q = head;
while (k > 0) {
k--;
q = q->next;
}
// move to the end
while(q->next != nullptr) {
p = p->next;
q = q->next;
}
q->next = head;
head = p->next;
p->next = nullptr;
return head;
}
};

复制代码

wglacier

0062 Unique Paths

// 0ms, 100%
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> v(m, vector<int>(n, 0));
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
if (i == m-1 || j == n-1) {
v[i][j] = 1;
} else {
v[i][j] = v[i+1][j] + v[i][j+1];
}
}
}
return v[0][0];
}
};

复制代码

wglacier

0063 Unique Paths II

// 0ms
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty())
return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> v(obstacleGrid.size(),
vector<int>(obstacleGrid[0].size(), 0));
if (obstacleGrid[m-1][n-1] == 0)
v[m-1][n-1] = 1;
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
if (obstacleGrid[i][j] == 1) {
continue;
}
if (i < m-1)
v[i][j] += v[i+1][j];
if (j < n-1)
v[i][j] += v[i][j+1];
}
}
return v[0][0];
}
};

复制代码

wglacier

0064 Minimum Path Sum

// 4ms, 100%
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty())
return 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> v(m, vector<int>(n, 0));
v[m-1][n-1] = grid[m-1][n-1];
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
if (i == m-1 && j == n-1)
continue;
if (i == m-1)
v[i][j] = v[i][j+1] + grid[i][j];
else if (j == n-1)
v[i][j] = v[i+1][j] + grid[i][j];
else {
v[i][j] = min(v[i][j+1], v[i+1][j]) + grid[i][j];
}
}
}
return v[0][0];
}
};
int main(int argc, char* argv[]) {
vector<vector<int>> v = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
cout << Solution().minPathSum(v) << endl;
}

复制代码

wglacier

0069 Sqrt(x)

// 8ms
class Solution {
public:
int mySqrt(int x) {
if (x < 1) return x;
long a = 1, b = x;
while (a <= b) {
long m = a + (b-a)/2;
long r = m*m;
if (r == x) return m;
if (r > x)
b = m-1;
else
a = m+1;
}
return b;
}
};

复制代码

wglacier

0070 Climbing Stairs

// 0ms
class Solution {
public:
int climbStairs(int n) {
if (n < 2) return 1;
vector<int> v(n+1, 0);
v[n] = 1;
v[n-1] = 1;
for (int i = n-2; i >= 0; i--) {
v[i] = v[i+1] + v[i+2];
}
return v[0];
}
};

复制代码

wglacier

0071 Simplify Path

// 4ms
class Solution {
public:
string simplifyPath(string path) {
if (path.empty()) return "/";
// prev state:
// empty
// .
// ..
// any name, like '.a', '..b', 'abc', etc
vector<string> vec;
int i = 0;
string buf;
while (i < path.size()) {
char c = path[i];
if (c == '/') {
if (buf.empty()) {
// do nothing
} else {
if (buf == ".") {
}
else if(buf == "..") {
if (!vec.empty())
vec.pop_back();
} else {
vec.push_back(buf);
}
buf.clear();
}
} else {
buf += string(1, c);
}
i++;
}
if (!buf.empty()) {
if (buf == "..") {
if (!vec.empty())
vec.pop_back();
}
else if (buf != ".")
vec.push_back(buf);
}
string res;
for (auto& a : vec) {
res += string("/") + a;
}
if (res.empty()) res = "/";
return res;
}
};

复制代码

wglacier

0001 Two Sum

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
using node = std::pair<int,int> ;
vector<node> v;
for (int i = 0; i < nums.size(); i++) {
v.push_back(std::make_pair(nums[i], i));
}
sort(v.begin(), v.end());
int i = 0, j = nums.size()-1;
while (i < j) {
int d = target - (v[i].first + v[j].first);
if (d == 0) {
vector<int> r = {v[i].second, v[j].second};
sort(r.begin(), r.end());
return r;
} else if (d > 0) {
i++;
} else {
j--;
}
}
}
};

复制代码

Leetcode 刷题打卡记录包括Solution

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块

Leetcode 刷题打卡记录 包括Solution

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块

Leetcode 刷题打卡记录包括Solution