生活随笔
收集整理的這篇文章主要介紹了
LeetCode——字节跳动系列题目
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
轉(zhuǎn)至：https://blog.csdn.net/Uupton/article/details/84640146
今天登陸leetcode發(fā)現(xiàn)探索區(qū)多了字節(jié)跳動(dòng)的專欄，特意用了一下午去刷，有些是之前刷過的。但題目不錯(cuò)，就當(dāng)是復(fù)習(xí)一遍吧，這里記錄一下我會(huì)的以及自己覺得不錯(cuò)的題目。
原題鏈接請(qǐng)點(diǎn)擊題目
一：挑戰(zhàn)字符串
3. 無重復(fù)字符的最長(zhǎng)子串
分析：這題要求連續(xù)的不重復(fù)的最長(zhǎng)子序列的長(zhǎng)度，注意這里是需要連續(xù)，利用這個(gè)特性，我們可以維護(hù)一個(gè)窗口，窗口裝的是無重復(fù)的字符串，一開始窗口的左邊在起點(diǎn)(即下標(biāo)為0處)。我們用 i 遍歷字符串，如果當(dāng)前字符沒有出現(xiàn)過或者當(dāng)前字符雖然出現(xiàn)過但不在當(dāng)前的窗口，則窗口向右擴(kuò)張。而當(dāng)當(dāng)前字符出現(xiàn)在窗口內(nèi)，則窗口的左邊收縮到當(dāng)前字符前一個(gè)出現(xiàn)的位置。詳見代碼
class Solution {public : int lengthOfLongestSubstring (string s) int hash[128 ] = {0 }; int left = 0 ,res = 0 ; for (int i = 0 ;i<s.size();i++) { if (hash[s[i]] == 0 ||hash[s[i]]<left) res = max(res,i-left+1 ); else left = hash[s[i]]; hash[s[i]] = i+1 ; } return res; } };
14. 最長(zhǎng)公共前綴
簡(jiǎn)單題，以第一個(gè)字符串作為模版，逐個(gè)拿出模版的每個(gè)字符，然后其余的字符串也逐個(gè)拿出相對(duì)應(yīng)位置的字符比較是否相同。注意字符串長(zhǎng)度的問題即可。
class Solution {public : string longestCommonPrefix (vector <string >& strs) if (strs.empty()) return "" ; string res = "" ; for (int i = 0 ;i<strs[0 ].size();i++) { char c = strs[0 ][i]; for (int j = 1 ;j<strs.size();j++) { if (i>=strs[j].size()||strs[j][i]!=c) return res; } res+=c; } return res; } };
567. 字符串的排列
分析：對(duì)s2全排再一一跟s1對(duì)比肯定會(huì)超時(shí)。所以我們可以維護(hù)兩個(gè)窗口，一個(gè)窗口裝s1，另一個(gè)窗口裝s2。假設(shè)s1長(zhǎng)度為len1,s2長(zhǎng)度為len2。開始先分別裝s1和s2的前l(fā)ne1個(gè)字符進(jìn)各自的窗口。如果此時(shí)兩個(gè)窗口相等則直接返回true，如果不等則s2的窗口從len1開始裝s2的字符，同時(shí)窗口的左邊要?jiǎng)h除一個(gè)元素，因?yàn)閮蓚€(gè)窗口要保持大小，期間如果兩個(gè)窗口相等則返回true
class Solution {public : bool checkInclusion (string s1, string s2) int len1 = s1.size(),len2 = s2.size(); vector <int > v1(128 ,0 ),v2(128 ,0 ); for (int i = 0 ;i<len1;i++) { v1[s1[i]]++; v2[s2[i]]++; } if (v1==v2) return true ; for (int i = len1;i<len2;i++) { v2[s2[i]]++; v2[s2[i-len1]]--; if (v1 == v2) return true ; } return false ; } };
43. 字符串相乘
分析：這里主要開了三個(gè)數(shù)組來做，一個(gè)數(shù)組存第一個(gè)字符串，另一個(gè)數(shù)組存第二個(gè)字符串，最后一個(gè)數(shù)組存結(jié)果。保存兩個(gè)字符串的時(shí)候要反著順序存，因?yàn)槲覀兤綍r(shí)做乘法的時(shí)候也是從數(shù)字的最后一位向前乘的，所以其實(shí)這道題主要是模擬了平時(shí)在紙上做的乘法。
class Solution {public : string multiply (string num1, string num2) int x[120 ] = {0 },y[120 ] = {0 },z[250 ] = {0 }; int len1 = num1.size(),len2 = num2.size(); for (int i = len1-1 ,k = 0 ;i>=0 ;i--) x[k++] = num1[i]-'0' ; for (int i = len2-1 ,k = 0 ;i>=0 ;i--) y[k++] = num2[i]-'0' ; for (int i = 0 ;i<len1;i++) { for (int j = 0 ;j<len2;j++) z[i+j] += (x[i]*y[j]); } for (int i = 0 ;i<249 ;i++) { if (z[i]>9 ) { z[i+1 ] += z[i]/10 ; z[i]%=10 ; } } int i; for (i = 249 ;i>=0 ;i--) if (z[i] != 0 ) break ; string res = "" ; for (;i>=0 ;i--) res+=(z[i]+'0' ); if (res == "" ) return "0" ; return res; } };
?
151. 翻轉(zhuǎn)字符串里的單詞
分析：主要做法就是先把整個(gè)字符串反轉(zhuǎn)，然后開始遍歷字符串，每遍歷完一個(gè)單詞（注意不是一個(gè)字符）的時(shí)候?qū)⑦@個(gè)單詞再反轉(zhuǎn)。
class Solution {public : void reverseWords (string &s) int index = 0 ,n = s.size(); reverse(s.begin(),s.end()); for (int i = 0 ;i<n;i++) { if (s[i]!=' ' ) { if (index!=0 ) s[index++] = ' ' ; int j = i; while (j<n&&s[j]!=' ' ) s[index++] = s[j++]; reverse(s.begin()+index-(j-i),s.begin()+index); i = j; } } s.resize(index); } };
93. 復(fù)原IP地址
分析：一般題目問字符串有多少種可能的排列，十有八九都是用遞歸做的。我們需要先寫一個(gè)函數(shù)判斷一個(gè)字符串是否符合ip其中一個(gè)結(jié)點(diǎn)，符合的標(biāo)準(zhǔn)：1、1到3位長(zhǎng)度的字符串。2、長(zhǎng)度大于一的話首位不能為0。3、整數(shù)大小要在0~255的范圍內(nèi)。
接著就可以遞歸做正式工作。這里對(duì)字符串分別截取一位、二位、三位。。。判斷是否能構(gòu)成ip的一個(gè)結(jié)點(diǎn)，如果能的話就截?cái)噙@部分，讓剩余的部分遞歸下去繼續(xù)做判斷。
具體看代碼
class Solution {public : vector <string > restoreIpAddresses(string s) { vector <string > res; helper(res,s,"" ,4 ); return res; } void helper (vector <string >& res,string s,string out,int k) { if (k==0 ) { if (s.empty()) res.push_back(out); } else { for (int i = 1 ;i<=3 ;i++) { if (s.size()>=i&&isValid(s.substr(0 ,i))) { if (k==1 ) helper(res,s.substr(i),out+s.substr(0 ,i),k-1 ); else helper(res,s.substr(i),out+s.substr(0 ,i)+'.' ,k-1 ); } } } } bool isValid (string s) { if (s.empty()||s.size()>3 ||(s.size()>1 &&s[0 ]=='0' )) return false ; int num = atoi(s.c_str()); return num>=0 &&num<=255 ; } };
二、數(shù)組與排序
15. 三數(shù)之和
class Solution {public : vector <vector <int >> threeSum(vector <int >& nums) { vector <vector <int >> res; sort(nums.begin(),nums.end()); for (int i = 0 ;i<nums.size();i++) { if (nums[i]>0 ) break ; if (i>0 &&nums[i] == nums[i-1 ]) continue ; int target = 0 -nums[i]; int j = i+1 ,k = nums.size()-1 ; while (j<k) { if (nums[j]+nums[k] == target) { res.push_back({nums[i],nums[j],nums[k]}); while (j<k&&nums[j+1 ] == nums[j]) j++; while (j<k&&nums[k-1 ] == nums[k]) k--; j++;k--; } else if (nums[j]+nums[k]<target) j++; else k--; } } return res; } };
?
674. 最長(zhǎng)連續(xù)遞增序列
class Solution {public : int findLengthOfLCIS (vector <int >& nums) int res = 0 ,cnt = 0 ; int cur = INT_MAX; for (int num:nums) { if (num>cur) cnt++; else cnt = 1 ; res = max(res,cnt); cur = num; } return res; } };
?
三、鏈表與樹
2. 兩數(shù)相加
class Solution {public : ListNode* addTwoNumbers (ListNode* l1, ListNode* l2) { int add = 0 ; ListNode* res = new ListNode(0 ); ListNode* head = res; while (l1||l2||add) { int num = (l1?l1->val:0 )+(l2?l2->val:0 )+add; head->next = new ListNode(num%10 ); head = head->next; add = num/10 ; l1 = l1?l1->next:l1; l2 = l2?l2->next:l2; } return res->next; } };
?
148. 排序鏈表
class Solution {public : ListNode* sortList (ListNode* head) { if (!head||!head->next) return head; ListNode* slow = head,*fast = head,*pre = head; while (fast&&fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL ; return merge(sortList(head),sortList(slow)); } ListNode* merge (ListNode* a,ListNode* b) { ListNode* head = new ListNode(0 ); ListNode* node = head; while (a&&b) { if (a->val<b->val) { node->next = a; a = a->next; } else { node->next = b; b = b->next; } node = node->next; } if (a) node->next = a; if (b) node->next = b; return head->next; } };
?
142. 環(huán)形鏈表 II
class Solution {public : ListNode *detectCycle (ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast&&fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break ; } if (!fast||!fast->next) return NULL ; slow = head; while (fast != slow) { slow = slow->next; fast = fast->next; } return fast; } };
?
236. 二叉樹的最近公共祖先
class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { if (!root||p==root||q==root) return root; TreeNode* left = lowestCommonAncestor(root->left,p,q); TreeNode* right = lowestCommonAncestor(root->right,p,q); if (left&&right) return root; return left?left:right; } };
?
四、動(dòng)態(tài)或貪心
121. 買賣股票的最佳時(shí)機(jī)
class Solution {public : int maxProfit (vector <int >& prices) int res = 0 ,buy = INT_MAX; for (auto c:prices) { buy = min(buy,c); res = max(res,c-buy); } return res; } };
?
122. 買賣股票的最佳時(shí)機(jī) II
class Solution {public : int maxProfit (vector <int >& prices) int len = prices.size(); if (len<=1 ) return 0 ; vector <int > have(len); vector <int > unhave(len); have[0 ] = -prices[0 ]; int res = 0 ; for (int i = 1 ;i<len;i++) { unhave[i] = max(unhave[i-1 ],have[i-1 ]+prices[i]); have[i] = max(have[i-1 ],unhave[i-1 ]-prices[i]); res = max(res,unhave[i]); } return res; } };
?
221. 最大正方形
class Solution {public : int maximalSquare (vector <vector <char >>& matrix) if (matrix.empty()||matrix[0 ].empty()) return 0 ; int m = matrix.size(),n = matrix[0 ].size(); vector <vector <int >> dp(m,vector <int >(n,0 )); int res = 0 ; for (int i = 0 ;i<m;i++) { for (int j = 0 ;j<n;j++) { if (i == 0 ||j == 0 ) dp[i][j] = matrix[i][j]-'0' ; else if (matrix[i][j] == '1' ) dp[i][j] = min(min(dp[i-1 ][j-1 ],dp[i-1 ][j]),dp[i][j-1 ])+1 ; res = max(res,dp[i][j]); } } return res*res; } };
?
?
總結(jié)
以上是生活随笔 為你收集整理的LeetCode——字节跳动系列题目 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
