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

Leetcode 刷题打卡记录 包括Solution

刷题 leetcode
🔗
 楼主| wglacier 2019-1-31 16:30:39 | 只看该作者
全局：
0002 Add Two Numbers
  1. class Solution {
  2. private:
  3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry) {
  4.         if (l1 == NULL && l2 == NULL && carry == 0) {
  5.             return NULL;
  6.         }
  7.         int r = carry;
  8.         if (l1 != NULL) r += l1->val;
  9.         if (l2 != NULL) r += l2->val;
  10.         ListNode* node = new ListNode(r % 10);
  11.         node->next = addTwoNumbers(l1?l1->next:NULL, l2? l2->next:NULL, r / 10);
  12.         return node;
  13.     }
  14. public:
  15.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  16.         return addTwoNumbers(l1, l2, 0);
  17.     }
  18. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:31:19 | 只看该作者
全局：
0003 Longest Substring Without Repeating Characters
  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         int ret = 0;
  5.         int max_t = 0;
  6.         vector<int> buf(256, -1);
  7.         for (int i = 0; i < s.size(); i++) {
  8.             char c = s[i];
  9.             if (buf[c] < 0) {
  10.                 max_t++;
  11.             } else {
  12.                 max_t = min(max_t + 1, i - buf[c]);
  13.             }
  14.             buf[c] = i;
  15.             ret = max(ret, max_t);
  16.         }
  17.         return ret;
  18.     }
  19. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:33:05 | 只看该作者
全局：
0004 Median of Two Sorted Arrays
  1. class Solution {
  2. public:
  3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  4.         int z = nums1.size() + nums2.size();
  5.         int m = (z -1) / 2;
  6.         int i = 0, j = 0;
  7.         int k = 0;
  8.         int v1 = 0, v2 = 0;
  9.         while (i < nums1.size() || j < nums2.size()) {
  10.             int v = 0;
  11.             if (j >= nums2.size() || ( i < nums1.size() && nums1[i] < nums2[j])) {
  12.                 v = nums1[i];
  13.                 i += 1;
  14.             } else {
  15.                 v = nums2[j];
  16.                 j += 1;
  17.             }
  18.             if (k == m) {
  19.                 v1 = v;
  20.             } else if (k == m+1) {
  21.                 v2 = v;
  22.                 break;
  23.             }
  24.             k += 1;
  25.         }
  26.         if (z % 2 != 0) {
  27.             return v1;
  28.         } else {
  29.             return (v1 + v2) / 2.0;
  30.         }
  31.     }
  32. };
复制代码
Coderust: Hacking the Coding Interview
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:33:53 | 只看该作者
全局：
0005. Longest Palindromic Substring
  1. class Solution {
  2. public:
  3.     string longestPalindrome(string s) {
  4.         vector<vector<int>> v(s.size(), vector<int>(s.size(), 0));
  5.         for(int i = 0; i < s.size(); i++) {
  6.             v[i][i] = 1;
  7.         }
  8.         
  9.         int r1 = 0, r2 = 0, r_len = 1;
  10.         for(int j = 1; j < s.size(); j++) {
  11.             for(int i = 0; i < s.size(); i++) {            
  12.                 if (i + j >= s.size()) continue;
  13.                 int a = i, b = i + j;
  14.                 if (s[a] != s[b]) continue;
  15.                
  16.                 if (b - a <= 2 || v[a+1][b-1] > 0) {
  17.                     if (b - a <= 2) {
  18.                         v[a][b] = b - a + 1;
  19.                     } else {
  20.                         v[a][b] = v[a+1][b-1] + 2;
  21.                     }
  22.                     if (v[a][b] > r_len) {
  23.                         r_len = v[a][b];
  24.                         r1 = a, r2 = b;
  25.                     }
  26.                 }
  27.             }
  28.         }
  29.         return s.substr(r1, r2 - r1 + 1);
  30.     }
  31. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:34:48 | 只看该作者
全局：
Another solution for 0005
//Expand around centers

  2. ```C++
  3. class Solution {
  4. private:
  5.     int findStr(const string& s, int& a, int& b) {
  6.         while(a >= 0 && b < s.size() && s[a] == s[b]) {
  7.             a--, b++;
  8.         }
  9.         a++, b--;
  10.         if (a > b) return 0;
  11.         return b-a+1;
  12.     }
  13. public:
  14.     string longestPalindrome(string s) {
  15.         int s0 = 0, e0 = 0;
  16.         for(int i = 1; i < s.size(); i++) {
  17.             int a = i-1, b = i+1;
  18.             int r = findStr(s, a, b);
  19.             if (r > (e0-s0+1)) {
  20.                 s0 = a;
  21.                 e0 = b;
  22.             }
  23.             a = i-1;
  24.             b = i;
  25.             r = findStr(s, a, b);
  26.             if (r > (e0-s0+1)) {
  27.                 s0 = a;
  28.                 e0 = b;
  29.             }
  30.         }
  31.         return s.substr(s0, e0-s0+1);
  32.     }
  33. };
复制代码

回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:35:54 | 只看该作者
全局：
0006 Zigzag Conversion
  1. class Solution {
  2. public:
  3.     string convert(string s, int numRows) {
  4.         if (numRows < 2 || s.size() < 2) return s;
  5.         
  6.         vector<string> ret = vector<string>(numRows, "");
  7.         int step = -1;
  8.         int r = 0;
  9.         for(auto c : s) {
  10.             ret[r] += c;
  11.             if (r == 0 || (r == numRows - 1)) step *= -1;
  12.             r += step;
  13.         }
  14.         return std::accumulate(ret.begin(), ret.end(), string(""));
  15.     }
  16. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:36:55 | 只看该作者
全局：
0007. Reverse Integer
  1. class Solution {
  2. public:
  3.     int reverse(int x) {
  4.         int x0 = x;
  5.         if (x < 0) x *= -1;
  6.         
  7.         int r = 0;
  8.         while (x > 0) {
  9.             int t = x % 10;
  10.             if (r*10/10 != r) return 0;
  11.             r = r * 10 + t;
  12.             if (r & 0x80000000) return 0;
  13.             x /= 10;
  14.         }
  15.         if (x0 < 0) r *= -1;
  16.         return r;
  17.     }
  18. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:37:40 | 只看该作者
全局：
0008. String to Integer (atoi)
  1. #include <climits>

  3. class Solution {
  4. private:
  5.     int overFlow(int sign) {
  6.         if (sign > 0) return INT_MAX;
  7.         else return INT_MIN;
  8.     }
  9. public:
  10.     int myAtoi(string str) {
  11.         int r = 0;
  12.         int sign = 1;
  13.         auto i = str.find_first_not_of(' ');
  14.         if (i == string::npos) return 0;
  15.         if (str[i] == '-') {
  16.             sign = -1;
  17.             i++;
  18.         } else if (str[i] == '+')
  19.             i++;

  21.         for (; i < str.size(); i++) {
  22.             char c = str[i];
  23.             if (!isdigit(c)) break;
  24.             
  25.             if (r * 10 / 10 != r)
  26.                 return overFlow(sign);
  27.             r = r * 10;
  28.             int v = (c - '0') * sign;
  29.             if( sign > 0 && (r + v < r))
  30.                 return overFlow(sign);
  31.             else if (sign < 0 && (r + v > r))
  32.                 return overFlow(sign);
  33.             r = r + v;
  34.         }
  35.         return r;
  36.     }
  37. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:39:13 | 只看该作者
全局：
0009. Palindrome Number
  1. // Construct another integer
  2. class Solution {
  3. public:
  4.     bool isPalindrome(int x) {
  5.         int r = 0;
  6.         int x0 = x;
  7.         while(x > 0) {
  8.             r = r*10 + x % 10;
  9.             x = x / 10;
  10.         }
  11.         return x0 == r;
  12.     }
  13. };
复制代码


Compare bit by bit from the two ends
  1. class Solution {
  2. public:
  3.     bool isPalindrome(int x) {
  4.         if (x < 0) return false;
  5.         
  6.         const int max_u = 1000000000;
  7.         int upbase = max_u;
  8.         int dobase = 10;

  10.         while(upbase > 0 && (x / upbase == 0))
  11.             upbase /= 10;
  12.         if (upbase < 10) return true;
  13.         
  14.         while(upbase >= dobase) {
  15.             int a = 0;
  16.             if (upbase == max_u) a = x / upbase;
  17.             else a = x % (upbase*10) / upbase;
  18.             
  19.             int b = x % dobase / (dobase/10);
  20.             if (a != b) return false;
  21.             upbase /= 10;
  22.             dobase *= 10;
  23.         }
  24.         return true;
  25.     }
  26. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 16:39:51 | 只看该作者
全局：
0010. Regular Expression Matching
  1. class Solution {
  2. public:
  3.     bool isMatch(string s, string p) {
  4.         if (p.empty())
  5.             return s.empty();

  7.         vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, false));
  8.         dp[0][0] = true;
  9.         if (!s.empty())
  10.             dp[1][1] = p[0] == '.' || p[0] == s[0];

  12.         for (int j = 2; j <= p.size(); j++) {
  13.             // special cases, second char in p is '*', like 'a*b*c*' can match ''
  14.             dp[0][j] = p[j-1] == '*' && dp[0][j-2];

  16.             for (int i = 1; i <= s.size(); i++) {
  17.                 if (p[j-1] != '*') {
  18.                     dp[i][j] = dp[i-1][j-1]
  19.                         && (p[j-1] == '.' || s[i-1] == p[j-1]);
  20.                 } else {
  21.                     dp[i][j] = dp[i][j-2]   // match 0 time
  22.                         // || dp[i][j-1]
  23.                         || (dp[i-1][j]
  24.                              && (p[j-2] == '.' || s[i-1] == p[j-2]));
  25.                 }
  26.             }
  27.         }
  28.         return dp[s.size()][p.size()];
  29.     }
  30. };

  32. int main(int argc, char* argv[]) {
  33. vector<tuple<string,string,bool>> v = {
  34.     {"aa", "a", false},
  35.     {"a", "a", true},
  36.     {"", "a*", true},
  37.     {"", "ABC", false},
  38.     {"abc", "abcd", false},
  39.     {"abc", "babc", false},
  40.     {"abc", ".*abc", true},
  41.     {"abc", ".*bc", true},
  42.     {"abc", ".*c", true},
  43.     {"abc", ".*", true},
  44.     {"abc", "a*b*c*", true},
  45.     {"abc", "a*b*c", true}
  46. };
  47.     for (auto a : v) {
  48.         bool r = Solution().isMatch(get<0>(a), get<1>(a));
  49.         if (r != get<2>(a)) {
  50.             cout << "error: " << get<0>(a) << ' '  << get<1>(a) << ' ' << r << ", expected: " << get<2>(a) << endl;
  51.         }
  52.     }
  53.     return 0;
  54. }
复制代码
回复

使用道具 举报

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

本版积分规则

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