搜索
体验新版
<
一亩三分地»论坛 › 专业技术 › 转码 › 学习圈 › Leetcode 刷题打卡记录 包括Solution
1 ...234567891011... 12下一页
返回列表 发新帖
楼主: wglacier
跳转到指定楼层
上一主题 下一主题
收起左侧

Leetcode 刷题打卡记录 包括Solution

刷题 leetcode
🔗
 楼主| wglacier 2019-2-4 18:13:13 | 只看该作者
全局：
0077 Combinations
  1. class Solution {
  2. private:
  3.      void comb(int n, int k, int start, vector<vector<int>>& res, vector<int>& v) {
  4.         if (k == 0) {
  5.             res.push_back(v);
  6.             return;
  7.         }
  8.         for (int i = start; i <= n - k + 1; i++) {
  9.             v.push_back(i);
  10.             comb(n, k-1, i+1, res, v);
  11.             v.pop_back();
  12.         }
  13.     }
  14. public:
  15.     vector<vector<int>> combine(int n, int k) {
  16.         vector<vector<int>> res;
  17.         vector<int> v;
  18.         comb(n, k, 1, res, v);
  19.         return res;
  20.     }
  21. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-4 18:38:01 | 只看该作者
全局：
0078 Subsets
  1. class Solution {
  2. private:
  3.     void getAllK(vector<vector<int>>& res, int start, int k, const vector<int>& nums, vector<int>& v) {
  4.         if (k == 0) {
  5.             res.push_back(v);
  6.             return;
  7.         }
  8.         
  9.         for (int i = start; i < nums.size()-k+1; i++) {
  10.             v.push_back(nums[i]);
  11.             getAllK(res, i+1, k-1, nums, v);
  12.             v.pop_back();
  13.         }
  14.     }
  15. public:
  16.     vector<vector<int>> subsets(vector<int>& nums) {
  17.         vector<vector<int>> res;
  18.         res.push_back(vector<int>());
  19.         for (int k = 1; k <= nums.size(); k++) {
  20.             vector<int> v;
  21.             getAllK(res, 0, k, nums, v);
  22.         }
  23.         return res;
  24.     }
  25. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-4 18:42:57 | 只看该作者
全局：
0078 Subsets Solution 2
  1. class Solution {
  2. public:
  3.     vector<vector<int>> subsets(vector<int>& nums) {
  4.         vector<vector<int>> res(1, vector<int>());
  5.         for (int i = 1; i < pow(2,nums.size()); i++) {
  6.             vector<int> v;
  7.             for (int j = 0; j < 32; j++) {
  8.                 int bitMask = 1 << j;
  9.                 if (i < bitMask) break;

  11.                 if (i & bitMask) {
  12.                     v.push_back(nums[j]);
  13.                 }
  14.             }
  15.             res.push_back(v);
  16.         }
  17.         return res;
  18.     }
  19. };
复制代码
Coderust: Hacking the Coding Interview
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-4 19:33:35 | 只看该作者
全局：
0079 Word Search
  1. class Solution {
  2. private:
  3.     // validate pos (i,j) and try next
  4.     bool isValid(vector<vector<char>>& board, string word, int wordIdx,
  5.                  vector<vector<bool>>& flags, int i, int j) {
  6.         char c = word[wordIdx];
  7.         bool ok = (i >=0 && i < board.size() &&
  8.            j >= 0 && j < board[0].size() &&
  9.            !flags[i][j] &&
  10.            board[i][j] == c);
  11.         if (ok) {
  12.             flags[i][j] = true;
  13.             bool r = tryWords(board, word, wordIdx+1, flags, i, j);
  14.             flags[i][j] = false;
  15.             return r;
  16.         }
  17.         return false;
  18.     }
  19.     // board[i][j] is already checked ok
  20.     bool tryWords(vector<vector<char>>& board, string word, int wordIdx,
  21.                  vector<vector<bool>>& flags, int i, int j) {
  22.         if (wordIdx == word.size()) return true;
  23.         
  24.         // left
  25.         if (isValid(board, word, wordIdx, flags, i-1, j))
  26.             return true;
  27.         // right
  28.         if (isValid(board, word, wordIdx, flags, i+1, j))
  29.             return true;
  30.         // top
  31.         if (isValid(board, word, wordIdx, flags, i, j-1))
  32.             return true;
  33.         // right
  34.         if (isValid(board, word, wordIdx, flags, i, j+1))
  35.             return true;
  36.         return false;
  37.     }
  38. public:
  39.     bool exist(vector<vector<char>>& board, string word) {
  40.         vector<vector<bool>> flags(board.size(), vector<bool>(board[0].size(), false));
  41.         for (int i = 0; i < board.size(); i++) {
  42.             for (int j = 0; j < board[0].size(); j++) {
  43.                 if (board[i][j] == word[0]) {
  44.                     flags[i][j] = true;
  45.                     if (tryWords(board, word, 1, flags, i, j))
  46.                         return true;
  47.                     flags[i][j] = false;
  48.                 }
  49.             }
  50.         }
  51.         return false;
  52.     }
  53. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-6 14:09:05 | 只看该作者
全局：
0080 Remove Duplicates from Sorted Array II
  1. // 16 ms
  2. class Solution {
  3. public:
  4.     int removeDuplicates(vector<int>& nums) {
  5.         if (nums.size() < 3) return nums.size();

  7.         int cnt = 1;
  8.         int d = 1;
  9.         for (int i = 1; i < nums.size(); i++) {
  10.             if (nums[i] == nums[i-1]) {
  11.                 ++cnt;
  12.                 if (cnt > 2) continue;
  13.             } else {
  14.                 cnt = 1;
  15.             }
  16.             nums[d++] = nums[i];
  17.         }
  18.         return d;
  19.     }
  20. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-6 14:09:29 | 只看该作者
全局：
0080 Remove Duplicates from Sorted Array II Solution 2
  1. // 8 ms
  2. class Solution {
  3. public:
  4.     int removeDuplicates(vector<int>& nums) {
  5.         if (nums.size() < 3) return nums.size();

  7.         int d = 2;
  8.         for (int i = 2; i < nums.size(); i++) {
  9.             if (nums[i] != nums[d-2]) {
  10.                 nums[d++] = nums[i];
  11.             }
  12.         }   
  13.         return d;
  14.     }
  15. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-6 14:15:17 | 只看该作者
全局：
0081 Search in Rotated Sorted Array II
  1. class Solution {
  2. private:
  3.     bool searchHelper(vector<int>& nums, int target, int low, int high) {
  4.         if (low <= high) {
  5.             int m = low + (high-low)/2;
  6.             if (target == nums[m])
  7.                 return true;
  8.             
  9.             // left is sorted
  10.             if (nums[low] < nums[m]) {
  11.                 if (target < nums[m] && target >= nums[low]) {
  12.                     return searchHelper(nums, target, low, m-1);
  13.                 } else {
  14.                     return searchHelper(nums, target, m+1, high);
  15.                 }
  16.                 // right is sorted
  17.             } else if (nums[m] < nums[high]) {
  18.                 if (nums[m] < target && target <= nums[high]) {
  19.                     return searchHelper(nums, target, m+1, high);
  20.                 } else {
  21.                     return searchHelper(nums, target, low, m-1);
  22.                 }
  23.             } else {
  24.                 return searchHelper(nums, target, low, m-1) ||
  25.                     searchHelper(nums, target, m+1, high);
  26.             }
  27.         }
  28.         return false;
  29.     }
  30. public:
  31.     bool search(vector<int>& nums, int target) {
  32.         int low = 0, high = nums.size() - 1;
  33.         return searchHelper(nums, target, low, high);
  34.     }
  35. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-6 18:06:33 | 只看该作者
全局：
128. Longest Consecutive Sequence
  1. // 12 ms, 26%, sort, n*log(n)
  2. class Solution {
  3. public:
  4.     int longestConsecutive(vector<int>& nums) {
  5.         if (nums.empty()) return 0;

  7.         sort(nums.begin(), nums.end());

  9.         int res = 1;
  10.         int k = 1;
  11.         for (int i = 1; i < nums.size(); i++) {
  12.             if (nums[i] == nums[i-1])
  13.                 continue;
  14.             if (nums[i] - nums[i-1] == 1) {
  15.                 k++;
  16.                 res = max(res, k);
  17.             }
  18.             else
  19.                 k = 1;
  20.         }
  21.         return res;
  22.     }
  23. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-6 18:07:10 | 只看该作者
全局：
128. Longest Consecutive Sequence Solution 2
  1. // 16 ms, min heap
  2. class Solution {
  3. public:
  4.     int longestConsecutive(vector<int>& nums) {
  5.         if (nums.empty()) return 0;

  7.         // build a min heap, in log(n)
  8.         priority_queue<int, vector<int>, greater<int>> queue(nums.begin(), nums.end());
  9.         int last = queue.top();
  10.         queue.pop();
  11.         int res = 1, k = 1;
  12.         while (!queue.empty()) {
  13.             int v = queue.top();
  14.             queue.pop();
  15.             if (v != last) {
  16.                 if (v - last == 1) {
  17.                     k++;
  18.                     res = max(res, k);
  19.                 } else {
  20.                     k = 1;
  21.                 }
  22.             }
  23.             last = v;
  24.         }
  25.         return res;
  26.     }
  27. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-2-7 05:11:59 | 只看该作者
全局：
139 Word Break

  2. // 8ms
  3. class Solution {
  4. private:
  5.     bool breakWord(const string& s, int idx, const vector<set<string>>& wordMap,
  6.                   vector<int>& dp, const int maxLen) {
  7.         if (idx >= s.size()) return true;

  9.         if (dp[idx] >= 0) {
  10.             return dp[idx];
  11.         }
  12.         for (int i = idx; i < s.size();i++) {
  13.             int len = i-idx+1;
  14.             if (len > maxLen) break;
  15.             string w = s.substr(idx, len);
  16.             if (wordMap[w[0]-'a'].count(w) > 0) {
  17.                 if (breakWord(s, i+1, wordMap, dp, maxLen)) {
  18.                     dp[idx] = 1;
  19.                     return true;
  20.                 }
  21.             }
  22.         }
  23.         dp[idx] = 0;
  24.         return false;
  25.     }
  26. public:
  27.     bool wordBreak(string s, vector<string>& wordDict) {
  28.         vector<set<string>> wordMap(26);
  29.         int maxLen = 0;
  30.         for(auto w : wordDict) {
  31.             int idx = tolower(w[0]) - 'a';
  32.             wordMap[idx].insert(w);
  33.             maxLen = max(maxLen, (int)w.size());
  34.         }
  35.         vector<int> dp(s.size(), -1);
  36.         return breakWord(s, 0, wordMap, dp, maxLen);
  37.     }
  38. };
复制代码
回复

使用道具 举报

下一页 »
1 ...234567891011... 12下一页
返回列表 发新帖
B Color Link Quote Code
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒：
  • ☑ 禁止发布广告，拉群，贴个人联系方式：找人请去🔗同学同事飞友，拉群请去🔗拉群结伴，广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑，过后则不能删帖。为防止被骚扰甚至人肉，不要公开留微信等联系方式，如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名：面经（美国面经、中国面经、数科面经、PM面经），抖包袱（美国、中国）和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表