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

Leetcode 刷题打卡记录 包括Solution

刷题 leetcode
🔗
 楼主| wglacier 2019-1-31 18:58:03 | 只看该作者
全局：
0011. Container With Most Water
  1. class Solution {
  2. public:
  3.     int maxArea(vector<int>& height) {
  4.         int i = 0, j = height.size() - 1;
  5.         int r = 0;
  6.         while(i < j) {
  7.             int a = height[i];
  8.             int b = height[j];
  9.             r = max(r, (j-i)*min(a, b));
  10.             // search from the lower end,
  11.             // because if searching from the higher end, even find a higher one, it still use the lower end to calc area
  12.             if (height[i] <= height[j]) {
  13.                 while(i < j && height[i] <= a) i++;
  14.             } else {
  15.                 while(i < j && height[j] <= b) j--;
  16.             }
  17.         }
  18.         return r;
  19.     }
  20. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 18:58:37 | 只看该作者
全局：
0012. Integer to Roman
  1. class Solution:
  2.     def intToRoman(self, num):
  3.         """
  4.         :type num: int
  5.         :rtype: str
  6.         """
  7.         m = [    (1000, {1: 'M', 5: 'Z', 10: 'Z'}),
  8.             (100, {1: 'C', 5: 'D', 10: 'M'}),
  9.             (10, {1: 'X', 5: 'L', 10: 'C'}),
  10.             (1,  {1: 'I', 5: 'V', 10: 'X'})]
  11.             
  12.         out = ''
  13.         for x in m:
  14.             v = x[0]
  15.             p = x[1]
  16.             n = num // v
  17.             if n < 1: continue
  18.             if n == 9: out += p[1] + p[10]
  19.             else:
  20.                 if n >= 5:
  21.                     out += p[5]
  22.                     n -= 5
  23.                 if n == 4:
  24.                     out += p[1] + p[5]
  25.                 else:
  26.                     out += p[1]*n
  27.             num = num % v
  28.         return out
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 18:59:12 | 只看该作者
全局：
0013. Roman to Integer
  1. class Solution:
  2.     def romanToInt(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         m = {
  8.             'I':             1,
  9.             'V':             5,
  10.             'X':             10,
  11.             'L':             50,
  12.             'C':             100,
  13.             'D':             500,
  14.             'M':             1000
  15.         }
  16.         m2 = {
  17.             'I':             'VX',
  18.             'X':             'LC',
  19.             'C':             'DM'
  20.         }
  21.         num = 0
  22.         i = 0
  23.         while i < len(s):
  24.             c = s[i]
  25.             if c in 'IXC':
  26.                 if i < len(s) - 1 and s[i+1] in m2[c]:
  27.                     d = s[i+1]
  28.                     num += m[d] - m[c]
  29.                     i += 2
  30.                     continue
  31.             num += m[c]
  32.             i += 1
  33.         return num
复制代码
Coderust: Hacking the Coding Interview
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 18:59:38 | 只看该作者
全局：
0014. Longest Common Prefix
  1. class Solution {
  2. public:
  3.     string longestCommonPrefix(vector<string>& strs) {
  4.         if (strs.size() < 1) return "";
  5.         if (strs[0].size() < 1) return "";
  6.         string ret = "";
  7.         for (auto i = 0; i < strs[0].size(); i++) {
  8.             auto c = strs[0][i];
  9.             bool ok = true;
  10.             for(auto j = 1; j < strs.size(); j++) {
  11.                 if (strs[j][i] != c) { ok = false; break;}
  12.             }
  13.             if (!ok) break;
  14.             ret += c;
  15.         }
  16.         return ret;
  17.     }
  18. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:00:07 | 只看该作者
全局：
0015. 3Sum
  1. class Solution {
  2. public:   
  3.     struct Node {
  4.         int a, b, c;
  5.         Node(int _a, int _b, int _c): a(_a), b(_b), c(_c) {}
  6.         bool operator < (const auto& o) const {
  7.             return (a < o.a) ||
  8.                 (a == o.a && b < o.b) ||
  9.                 (a == o.a && b == o.b && c < o.c);
  10.         }
  11.     };
  12.     vector<vector<int>> threeSum(vector<int>& nums) {
  13.         if (nums.empty())
  14.             return vector<vector<int>>();

  16.         sort(nums.begin(), nums.end());
  17.         set<Node> r;
  18.         for (auto i = 0; i < nums.size()-2; i++) {
  19.             auto j = i + 1;
  20.             auto v = nums[i] + nums[j];
  21.             if (v > 0) break;
  22.             auto z = lower_bound(nums.begin()+j+1, nums.end(), v*-2);
  23.             auto k = z == nums.end()? nums.size()-1 : z - nums.begin();
  24.             while (j < k) {
  25.                 v = nums[i] + nums[j] + nums[k];
  26.                 if (v == 0) {
  27.                     r.insert(Node(nums[i], nums[j], nums[k]));
  28.                     j++, k--;
  29.                 } else if (v < 0)
  30.                     j++;
  31.                 else
  32.                     k--;
  33.             }
  34.         }
  35.         vector<vector<int>> ret;
  36.         for(auto a : r)
  37.             ret.push_back({a.a, a.b, a.c});
  38.         return ret;
  39.     }
  40. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:00:34 | 只看该作者
全局：
0016. 3Sum Closest
  1. int threeSumClosest(vector<int>& nums, int target) {
  2.     if (nums.size() < 3) return 0;
  3.     sort(nums.begin(), nums.end());
  4.     int ret = accumulate(nums.begin(), nums.begin()+3, 0);
  5.     for (auto i = 0; i < nums.size()-2; i++) {
  6.         auto j = i + 1;
  7.         auto k = nums.size()-1;
  8.         while(j < k) {
  9.             auto a = nums[i] + nums[j] + nums[k];
  10.             if (abs(target -a) < abs(target - ret))
  11.                 ret = a;
  12.             if (a == target)
  13.                 return a;
  14.             else if (a > target)
  15.                 k--;
  16.             else
  17.                 j++;
  18.         }
  19.     }
  20.     return ret;
  21. }
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:01:02 | 只看该作者
全局：
0017. Letter Combinations of a Phone Number
  1. class Solution {
  2. private:
  3.     void calc(const string& digits, int pos, const map<char, string>& sMap, string& str, vector<string>& ret) {
  4.         if (pos >= digits.size()) {
  5.             ret.push_back(str);
  6.             return;
  7.         }
  8.         char c = digits[pos];
  9.         for (const char& a : sMap.at(c)) {
  10.             str[pos] = a;
  11.             calc(digits, pos + 1, sMap, str, ret);
  12.         }
  13.     }
  14. public:
  15.     vector<string> letterCombinations(string digits) {
  16.         vector<string> ret;
  17.         if (digits.empty()) return ret;
  18.         
  19.         string str(digits.size(), ' ');
  20.         map<char, string> sMap = {
  21.             {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
  22.         };
  23.         calc(digits, 0, sMap, str, ret);
  24.         return ret;
  25.     }
  26. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:01:29 | 只看该作者
全局：
0018. 4Sum
  1. class Solution {
  2. public:
  3.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
  4.         vector<vector<int>> ret;
  5.         if (nums.size() < 4) return ret;
  6.         sort(nums.begin(), nums.end());
  7.         
  8.         for (int i = 0; i < nums.size()-3;) {
  9.             for (int j = i+1; j < nums.size()-2;) {
  10.                 int k = j+1;
  11.                 int m = nums.size()-1;
  12.                 while (k < m) {
  13.                     int a = nums[i] + nums[j] + nums[k] + nums[m];
  14.                     if (a == target) {
  15.                         ret.push_back(vector<int>{nums[i],nums[j],nums[k],nums[m]});
  16.                         k++; while(k < m && nums[k] == nums[k-1]) k++;
  17.                         m--; while(m > k && nums[m] == nums[m+1]) m--;
  18.                     } else if (a > target) {
  19.                         m--; while(m > k && nums[m] == nums[m+1]) m--;
  20.                     } else {
  21.                         k++; while(k < m && nums[k] == nums[k-1]) k++;
  22.                     }
  23.                 }
  24.                 // note not to be dup the result
  25.                 j++; while(j < nums.size()-2 && nums[j] == nums[j-1]) j++;
  26.             }
  27.             // note not to be dup the result
  28.             i++; while(i < nums.size()-3 && nums[i] == nums[i-1]) i++;
  29.         }
  30.         return ret;
  31.     }
  32. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:01:52 | 只看该作者
全局：
0019. Remove Nth Node From End of List
  1. class Solution {
  2. public:
  3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  4.         auto t = head;
  5.         while(n > 0) {
  6.             if (!t) return nullptr;
  7.             t = t->next;
  8.             n--;
  9.         }
  10.         if (!t) return head->next;
  11.         auto p = head;
  12.         while (t->next) {
  13.             t = t->next;
  14.             p = p->next;
  15.         }
  16.         p->next = p->next->next;
  17.         return head;
  18.     }
  19. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:02:19 | 只看该作者
全局：
0020. Valid Parentheses
  1. class Solution {
  2. public:
  3.     bool isValid(string s) {
  4.         stack<char> st;
  5.         for (auto& c : s) {
  6.             if (c == '(' || c == '[' || c == '{')
  7.                 st.push(c);
  8.             else {
  9.                 if (st.empty()) return false;
  10.                 auto d = st.top(); st.pop();
  11.                 if (d == '(' && c == ')' ||
  12.                     (d == '[' && c == ']') ||
  13.                     (d == '{' && c == '}'))
  14.                     continue;
  15.                 else
  16.                     return false;
  17.             }
  18.         }
  19.         return st.empty();
  20.     }
  21. };
复制代码
回复

使用道具 举报

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

本版积分规则

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