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

Leetcode 刷题打卡记录 包括Solution

刷题 leetcode
🔗
 楼主| wglacier 2019-1-31 19:02:58 | 只看该作者
全局：
0021. Merge Two Sorted Lists
  1. class Solution {
  2. public:
  3.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  4.         ListNode dummy(0);
  5.         ListNode* r = &dummy;
  6.         while (l1 != nullptr && l2 != nullptr) {
  7.             if (l1->val < l2->val) {
  8.                 r->next = l1;
  9.                 r = l1;
  10.                 l1 = l1->next;
  11.             } else {
  12.                 r->next = l2;
  13.                 r = l2;
  14.                 l2 = l2->next;
  15.             }
  16.         }
  17.         if (l1) r->next = l1;
  18.         else r->next = l2;
  19.         return dummy.next;
  20.     }
  21. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:03:28 | 只看该作者
全局：
0022. Generate Parentheses
  1. class Solution {
  2. public:
  3.     void genPair(int i, int nl, int nr, string& str, vector<string>& vs) {
  4.         if( nl == 0 && nr == 0) {
  5.             vs.push_back(str);
  6.             return;
  7.         }
  8.         if (nl > 0) {
  9.             str[i] = '(';
  10.             genPair(i+1, nl-1, nr, str, vs);
  11.         }
  12.         if (nr > nl) {
  13.             str[i] = ')';
  14.             genPair(i+1, nl, nr-1, str, vs);
  15.         }
  16.     }
  17.     vector<string> generateParenthesis(int n) {
  18.         string s(n*2, ' ');
  19.         vector<string> vs;
  20.         genPair(0, n, n, s, vs);
  21.         return vs;
  22.     }
  23. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:03:51 | 只看该作者
全局：
0023. Merge k Sorted Lists
  1. class Solution {
  2. public:
  3.     ListNode* mergeTwo(ListNode* l, ListNode* r) {
  4.         ListNode dummy(0);
  5.         ListNode* p = &dummy;
  6.         while( l != nullptr && r != nullptr) {
  7.             if (l->val < r->val) {
  8.                 p->next = l;
  9.                 p = l;
  10.                 l = l->next;
  11.             } else {
  12.                 p->next = r;
  13.                 p = r;
  14.                 r = r->next;
  15.             }
  16.         }
  17.         if (l) p->next = l;
  18.         else if (r) p->next = r;
  19.         return dummy.next;
  20.     }
  21.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  22.         if (lists.empty()) return nullptr;

  24.         while (lists.size() > 1) {
  25.             ListNode* l = lists.back(); lists.pop_back();
  26.             ListNode* r = lists.back(); lists.pop_back();
  27.             ListNode* p = mergeTwo(l, r);
  28.             lists.push_back(p);
  29.         }
  30.         return lists.back();
  31.     }
  32. };
复制代码
Coderust: Hacking the Coding Interview
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:04:26 | 只看该作者
全局：
0024. Swap Nodes in Pairs
  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         ListNode dummy(0);
  5.         ListNode* t = &dummy;
  6.         t->next = head;
  7.         while (t) {
  8.             ListNode* p = t->next;
  9.             if (!p || !p->next) break;
  10.             
  11.             ListNode* q = p->next;
  12.             ListNode* r = q->next;
  13.             
  14.             t->next = q;
  15.             q->next = p;
  16.             p->next = r;
  17.             t = p;
  18.         }
  19.         return dummy.next;
  20.     }
  21. };

  23. // recursive way
  24. ListNode* swapPairs(ListNode* head) {
  25.     if (!head || !head->next) return head;
  26.    
  27.     ListNode* p = head->next;
  28.     ListNode* q = p->next;
  29.     p->next = head;
  30.     head->next = swapPairs(q);
  31.     return p;
  32. }
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:04:46 | 只看该作者
全局：
0025. Reverse Nodes in k-Group
  1. class Solution {
  2. public:
  3.     ListNode* reverseK(ListNode* head) {
  4.         ListNode* p = nullptr;
  5.         ListNode* cur = head;
  6.         while(cur) {
  7.             ListNode* n = cur->next;
  8.             cur->next = p;
  9.             p = cur;
  10.             cur = n;
  11.         }
  12.         return p;
  13.     }
  14.     ListNode* reverseKGroup(ListNode* head, int k) {
  15.         ListNode dummy(0);
  16.         ListNode* p = &dummy;
  17.         p->next = head;
  18.         while (p) {
  19.             int n = k;
  20.             ListNode* t = p;
  21.             while (n--) {
  22.                 t = t->next;
  23.                 if (!t) return dummy.next;
  24.             }
  25.             ListNode* next = t->next;
  26.             t->next = nullptr;
  27.             ListNode* newh = reverseK(p->next);
  28.             ListNode* newt = p->next;
  29.             p->next = newh;
  30.             newt->next = next;
  31.             p = newt;
  32.         }
  33.         return dummy.next;
  34.     }
  35. };

  37. // recursive
  38. class Solution {
  39. public:
  40.     ListNode* reverseKGroup(ListNode* head, int k) {
  41.         if(head == NULL || k < 2) return head;
  42.         
  43.         ListNode *p1 = head, *p2 = head;
  44.         int kk = k-1;
  45.         while(kk-- > 0) {
  46.             p2 = p2->next;
  47.             if(p2 == NULL) return head;
  48.         }
  49.         
  50.         ListNode *nextNode = reverseKGroup(p2->next, k);
  51.         kk = k-1;
  52.         while(kk-- > 0) {
  53.             auto t = p1->next;
  54.             p1->next = nextNode;
  55.             nextNode = p1;
  56.             p1 = t;
  57.         }
  58.         p1->next = nextNode;
  59.         return p1;
  60.     }
  61. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:05:10 | 只看该作者
全局：
0026. Remove Duplicates from Sorted Array
  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         if (nums.empty()) return 0;
  5.         int j = 1;
  6.         
  7.         for (int i = 1; i < nums.size(); i++) {
  8.             if (nums[i] == nums[i-1]) continue;
  9.             if (i != j) {
  10.                 nums[j] = nums[i];
  11.             }
  12.             j++;
  13.         }
  14.         return j;
  15.     }
  16. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:05:36 | 只看该作者
全局：
0027. Remove Element
  1. class Solution {
  2. public:
  3.     int removeElement(vector<int>& nums, int val) {
  4.         if (nums.empty()) return 0;
  5.         int j = 0;
  6.         for (int i = 0; i < nums.size(); i++) {
  7.             if (nums[i] == val) continue;
  8.             if (i != j)
  9.                 nums[j] = nums[i];
  10.             j++;
  11.         }
  12.         return j;
  13.     }
  14. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:06:26 | 只看该作者
全局：
0028. strStr
  1. class Solution {
  2. public:
  3.     int strStr(string haystack, string needle) {
  4.         if (needle.empty()) return 0;
  5.         if (haystack.size() < needle.size()) return -1;

  7.         for (int i = 0; i <= haystack.size() - needle.size(); i++) {
  8.             bool ok = true;
  9.             for (int j = 0; j < needle.size(); j++) {
  10.                 if (needle[j] != haystack[i+j]) {
  11.                     ok = false;
  12.                     break;
  13.                 }
  14.             }
  15.             if (ok) return i;
  16.         }
  17.         return -1;
  18.     }
  19. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:06:51 | 只看该作者
全局：
0029. Divide Two Integers
  1. class Solution {
  2. public:
  3.     int get_sign(int a) { return (a >> 31) & 0x1; }
  4.    
  5.     int divide(int dividend, int divisor) {
  6.         if (divisor == 0) return 0;
  7.         if (divisor == INT_MIN) {
  8.             return dividend == INT_MIN;
  9.         }
  10.         // result sign, 0 for positive and 1 for negative
  11.         int sign = get_sign(dividend) ^ get_sign(divisor);
  12.         if (dividend == INT_MIN) {
  13.             if (sign == 0) { // result is positive
  14.                 int r = divide(dividend - divisor, divisor);
  15.                 if (r == INT_MAX) return r;
  16.                 return r + 1;
  17.             } else {
  18.                 int r = divide(dividend + divisor, divisor);
  19.                 return r - 1;
  20.             }
  21.         }
  22.         int a = abs(dividend);
  23.         int b = abs(divisor);
  24.         int ret = 0;
  25.         while (a >= b) {
  26.             int base = b;
  27.             int count = 1;
  28.             while (base < (a >> 1)) {
  29.                 base = base << 1;
  30.                 count = count << 1;
  31.             }
  32.             a -= base;
  33.             ret += count;
  34.         }
  35.         if (sign == 1) ret = (ret ^ 0xFFFFFFFF) + 1;
  36.         return ret;
  37.     }
  38. };
复制代码
回复

使用道具 举报

🔗
 楼主| wglacier 2019-1-31 19:07:15 | 只看该作者
全局：
0030. Substring with Concatenation of All Words
  1. class Solution {
  2. public:
  3.     bool checkAtIndex(const string& s, int& from, const vector<string>& words, const vector<vector<int>>& wdMap) {
  4.         
  5.         vector<int> usedFlag(words.size(), 0);
  6.         int usedCount = 0;
  7.         for (; from + words[0].size() <= s.size(); ) {
  8.             char c = s[from];
  9.             auto& wds = wdMap[c];
  10.             if (wds.empty()) return false;
  11.             bool foundone = false;
  12.             for (int idx : wds) {
  13.                 if (usedFlag[idx] == 1) continue;
  14.                 const string& s2 = words[idx];
  15.                 if (strncmp(s.data() + from, s2.data(), s2.size()) != 0)
  16.                     continue;
  17.                 foundone = true;
  18.                 from += s2.size();
  19.                 usedFlag[idx] = 1;
  20.                 usedCount += 1;
  21.                 if (usedCount == words.size()) {
  22.                     return true;
  23.                 }
  24.                 break;
  25.             }
  26.             if (!foundone) return false;
  27.         }
  28.         return false;
  29.     }

  31.     vector<int> findSubstring(string s, vector<string>& words) {
  32.         vector<int> ret;
  33.         if (s.empty() || words.empty() ||
  34.                 (s.size() < words.size()*words[0].size())
  35.                 ) return ret;
  36.         int WD_SIZE = words[0].size();
  37.         
  38.         vector<vector<int>> wdMap(256);
  39.         for (int i = 0; i < words.size(); i++) {
  40.             wdMap[words[i][0]].push_back(i);
  41.         }
  42.         for (int i = 0; i + WD_SIZE*words.size() <= s.size(); ) {
  43.             int from = i;
  44.             if (checkAtIndex(s, from, words, wdMap)) {
  45.                 ret.push_back(i);
  46.             }
  47.             i++;
  48.         }
  49.         return ret;
  50.     }
  51. };

  53. int main()
  54. {
  55.     //string s1(5000, 'a');
  56.     //vector<string> ar(5001, 'a');
  57.     //string s1 = "barfoofoobarthefoobarman";
  58.     //vector<string> ar = {"bar","foo","the"};
  59.     //string s1 = "";
  60.     //vector<string> ar = {};
  61.     string s1 = "aaaaaaaa";
  62.     vector<string> ar = {"aa","aa","aa"};

  64.     auto r = Solution().findSubstring(s1, ar);
  65.     for (auto a : r)
  66.         cout << a << " ,";
  67.     cout << endl;
  68. }
复制代码
回复

使用道具 举报

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

本版积分规则

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