發表文章

目前顯示的是 12月, 2017的文章

https://leetcode.com/contest/weekly-contest-65/problems/reach-a-number/

class Solution { public: int reachNumber(int target) { if (target == 0) return 0; if (target < 0) target *= -1; int remain = target; int step = 0; bool odd = (target & 1); while(remain > 0) { step++; remain -= step; } int pattern = step % 4; int pattern2 = pattern % 2; printf("%d %d %d\n", step, pattern, pattern2); if (odd) { if ((pattern == 1) || (pattern == 2)) return step; else { if (pattern == 0) return (step + 1); if (pattern == 3) return (step + 2); } } else { if ((pattern == 0) || (pattern == 3)) return step; else { if (pattern == 1) return (step + 2); if (pattern == 2) re...

https://leetcode.com/contest/weekly-contest-64/problems/open-the-lock/

class Solution { public: int openLock(vector<string>& deadends, string target) { map<string, int> m; map<string, int>::iterator mit; for (int i = 0; i < deadends.size(); i++) { m.insert(make_pair(deadends[i], -1)); } queue<pair<string, int> > q; string s("0000"); if (m.find(s) != m.end()) { return -1; } q.push(make_pair(s, 0)); m.insert(make_pair(s, 0)); while(!q.empty()) { string now = q.front().first; int length = q.front().second; //printf("%s %d\n", now.c_str(), length); q.pop(); for (int i = 0; i < 4; i++) { string up(now); char c = up.at(i); if (c < '9') { c = c + 1; } else { c = '0'; } ...

https://leetcode.com/problems/cracking-the-safe/

#include <iostream> #include <limits.h> #include <vector> #include <string> #include <iterator> #include <map> #include <queue> #include <list> #include <algorithm> #include <stdio.h> #include <set> using namespace std; class Solution { int total; string start; int digit; int numbers; bool DFS(set<string> &used, string &now, string &ans) { if(used.size() == total) { now.erase(0, 1); now.push_back('0'); if (now == start) { return true; } } for (int i = 0; i < numbers; i++) { string tmp(now); tmp.erase(0, 1); tmp.push_back('0' + i); if (used.find(tmp) == used.end()) { ans.push_back('0' + i); used.insert(tmp); bool done = DFS(used, tmp, ans); if (d...

String Util

链接:https://www.zhihu.com/question/35967887/answer/125238385 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 std::vector<std::string> split(const std::string &s, const std::string &d) { std::vector<std::string> v; char *str = new char[s.size()+1]; strcpy(str, s.c_str()); while (char *t = strsep(&str, d.c_str())) v.push_back(t); delete[] str; return v; } std::string &ltrim(std::string &s) { if (s.empty()) return s; std::string::const_iterator iter = s.begin(); while (iter != s.end() && isspace(*iter++)); s.erase(s.begin(), --iter); return s; } std::string &rtrim(std::string &s) { if (s.empty()) return s; std::string::const_iterator iter = s.end(); while (iter != s.begin() && isspace(*--iter)); s.erase(++iter, s.end()); return s; } std::string &trim(std::string &s) { ltrim(s); rtrim(s); return s; } bool startsWith(const std::string &str, co...

Complexity

圖片
http://bigocheatsheet.com/

https://leetcode.com/problems/range-sum-query-2d-immutable

class NumMatrix { public: NumMatrix(vector<vector<int>> matrix) { if (matrix.size() == 0 || matrix[0].size() == 0) return; sumArray = matrix; for (int i = 0; i < matrix.size(); i++) { int sum = 0; for (int j = 0; j < matrix[0].size(); j++) { sum += matrix[i][j]; sumArray[i][j] = sum; } } for (int j = 0; j < matrix[0].size(); j++) { int sum = 0; for (int i = 0; i < matrix.size(); i++) { sum += sumArray[i][j]; sumArray[i][j] = sum; } } } int sumRegion(int row1, int col1, int row2, int col2) { if (sumArray.size() == 0 || sumArray[0].size() == 0) return 0; int r1 = 0; int r2 = 0; int r3 = 0; if (row1 > 0) { r1 = sumArray[row1 -1][col2]; } if (col1 > 0) {...

https://leetcode.com/contest/weekly-contest-60/problems/flood-fill/

class Solution { private: int h; int w; inline bool top(int sr, int sc, pair<int, int> &result) { if (sr > 0) { result = make_pair((sr - 1), sc); return true; } return false; } inline bool down(int sr, int sc, pair<int, int> &result) { if (sr < (h - 1)) { result = make_pair((sr + 1), sc); return true; } return false; } inline bool left(int sr, int sc, pair<int, int> &result) { if (sc > 0) { result = make_pair(sr, (sc - 1)); return true; } return false; } inline bool right(int sr, int sc, pair<int, int> &result) { if (sc < (w - 1)) { result = make_pair(sr, sc + 1); return true; } return false; ...

https://leetcode.com/contest/weekly-contest-60/problems/asteroid-collision/

#include <deque> #include <vector> #include <stdio.h> #include <stdlib.h> using namespace std; class Solution { public: vector<int> asteroidCollision(vector<int>& asteroids) { std::deque<int> s; vector<int> ans; for (int i = 0; i < asteroids.size(); i++) { if (asteroids[i] > 0) { s.push_back(asteroids[i]); } else { int now = -1 * asteroids[i]; while (1) { if (s.empty()) { ans.push_back(asteroids[i]); break; } int other = s.back(); if (other <= now) { s.pop_back(); if (other == now) { break; } } else { break; } } ...

https://leetcode.com/contest/weekly-contest-61/problems/delete-and-earn/

class Solution { public: int deleteAndEarn(vector<int>& nums) { if (nums.size() == 0) return 0; std::sort(nums.begin(), nums.end()); int count = 1; int now = nums[0]; vector<pair<int,int>> v; for (int i = 1; i < nums.size(); i++) { if (now != nums[i]) { v.push_back(make_pair(now, count)); now = nums[i]; count = 1; } else { count++; } } v.push_back(make_pair(now, count)); vector<int> answer(v.size(), 0); answer[0] = (v[0].first * v[0].second); int score_with; for (int i = 1; i < v.size(); i++) { if (v[i].first == (v[i - 1].first + 1)) { score_with = (v[i].first * v[i].second) + ((i > 1) ? (answer[i - 2]) : (0)); } else { score_with = (v[i].first * v[i].second) + (answer[i - 1]); } ...

https://leetcode.com/contest/weekly-contest-61/problems/monotone-increasing-digits/

Paste your text here.class Solution { public: int monotoneIncreasingDigits(int N) { std::string s = std::to_string(N); std::string result; int max = 0; int i, j; int last = -1; for (i = 0; i < s.length(); ++i) { if (s.at(i) > max){ max = s.at(i); last = i; } else if (s.at(i) == max) { continue; } else { break; } } if (i != s.length()) { for (j = 0; j < last; j++) { result += s.at(j); } if ((s.at(j) - 1) != '0') result += (s.at(j) - 1); for (int j = last + 1; j < s.length(); j++) { result += '9'; } } else { result = s; } return std::stoi(result, nullptr, 10); }; };

https://leetcode.com/problems/daily-temperatures/

class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { std::list<pair<int, int>>::iterator it; vector<int> ans(temperatures.size(), 0); list<pair<int/*value*/, int/*index*/>> l; for (int i = 0; i < temperatures.size(); i++) { pair<int,int> now = make_pair(temperatures[i], i); for (it = l.begin(); it != l.end(); ) { if (it->first < temperatures[i]) { ans[it->second] = i - it->second; it = l.erase(it); } else { break; } } l.push_front(now); } return ans; } };