leetcode--バイトジャンプシリーズのテーマを探る
今日leetcodeに上陸して探索区がバイトの鼓動を多くしたコラムを発見し、わざわざ午後にブラシをかけたが、前にブラシをかけたものもあった.しかし、問題はいいですね.復習したつもりで、ここに私ができることと自分がいいと思っている問題を記録してください.
原題リンクはタイトルをクリックしてください
一:チャレンジ文字列
3.重複文字のない長男列
解析:この問題は連続的に繰り返さない最長男シーケンスの長さを要求し、ここでは連続が必要であることに注意してください.この特性を利用して、ウィンドウを維持することができます.ウィンドウには重複のない文字列が入っていて、最初はウィンドウの左側が起点(つまり、下に0と表示されます)にあります.iで文字列を巡回し、現在の文字が現れなかったり、現在の文字が現れたが現在のウィンドウにない場合は、ウィンドウを右に拡張します.現在の文字がウィンドウに表示されると、ウィンドウの左側が現在の文字の前に表示される位置に縮小されます.詳細はコードを参照
14.最大共通接頭辞
簡単な問題は、最初の文字列をテンプレートとして、テンプレートの各文字を1つずつ出して、残りの文字列も対応する位置の文字を1つずつ出して同じかどうかを比較します.文字列の長さの問題に注意すればいいです.
567.文字列の配置
分析:s 2全列をs 1と比較すると必ずタイムアウトします.したがって、2つのウィンドウを維持することができます.1つのウィンドウはs 1をインストールし、もう1つのウィンドウはs 2をインストールします.s 1の長さがlen 1,s 2の長さがlen 2であると仮定する.最初にs 1とs 2の前のlne 1文字をそれぞれのウィンドウに入れます.このとき2つのウィンドウが等しい場合はtrueを直接返し、等しくない場合はlen 1からs 2の文字をロードし、ウィンドウの左側に2つのウィンドウがサイズを維持するため、ウィンドウが等しい場合はtrueを返します.
43.文字列乗算
解析:ここでは主に3つの配列を開き、1つの配列には最初の文字列が保存され、もう1つの配列には2番目の文字列が保存され、最後の配列には結果が保存されます.2つの文字列を保存するときは逆の順序で保存します.私たちは普段乗算をするときも数字の最後の方から前に乗るので、実はこの問題は主に普段紙でやっている乗算をシミュレートしています.
151.文字列内の単語を反転
分析:主な方法は、まず文字列全体を反転してから、文字列を巡回し始め、1つの単語(文字ではないことに注意)を巡回するたびに、この単語を反転します.
93.IPアドレスの復元
分析:一般的な問題は文字列に何種類の可能な配列があるかを聞いて、十中八九はすべて再帰で作ったのです.まず、関数を書いて、1つの文字列がipのノードの1つに合致するかどうかを判断する必要があります.一致する基準:1、1から3ビットの長さの文字列です.2、長さが1より大きいとトップは0にならない.3、整数の大きさは0~255の範囲である.
それから正式な仕事を再帰することができます.ここでは文字列に対して1ビット、2ビット、3ビットを切り取ります..のIPの1つのノードを構成できるかどうかを判断し、できればこの部分を遮断し、残りの部分を再帰して判断を続けます.
コードを具体的に見る
二、配列と並べ替え
15.三数の和
674.最長連続増分シーケンス
三、チェーンテーブルとツリー
2.両数加算
148.チェーンテーブルのソート
142.リングチェーンテーブルII
236.二叉木の最近の公共祖先
四、動的または貪欲
121.株を売買する最良のタイミング
122.株の売買に最適なタイミングII
221.最大正方形
原題リンクはタイトルをクリックしてください
一:チャレンジ文字列
3.重複文字のない長男列
解析:この問題は連続的に繰り返さない最長男シーケンスの長さを要求し、ここでは連続が必要であることに注意してください.この特性を利用して、ウィンドウを維持することができます.ウィンドウには重複のない文字列が入っていて、最初はウィンドウの左側が起点(つまり、下に0と表示されます)にあります.iで文字列を巡回し、現在の文字が現れなかったり、現在の文字が現れたが現在のウィンドウにない場合は、ウィンドウを右に拡張します.現在の文字がウィンドウに表示されると、ウィンドウの左側が現在の文字の前に表示される位置に縮小されます.詳細はコードを参照
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// ，
int hash[128] = {0};
int left = 0,res = 0;
for(int i = 0;i14.最大共通接頭辞
簡単な問題は、最初の文字列をテンプレートとして、テンプレートの各文字を1つずつ出して、残りの文字列も対応する位置の文字を1つずつ出して同じかどうかを比較します.文字列の長さの問題に注意すればいいです.
class Solution {
public:
string longestCommonPrefix(vector& strs) {
if(strs.empty()) return "";
string res = "";
for(int i = 0;i=strs[j].size()||strs[j][i]!=c) // i
return res;
}
res+=c;
}
return res;
}
}; 567.文字列の配置
分析:s 2全列をs 1と比較すると必ずタイムアウトします.したがって、2つのウィンドウを維持することができます.1つのウィンドウはs 1をインストールし、もう1つのウィンドウはs 2をインストールします.s 1の長さがlen 1,s 2の長さがlen 2であると仮定する.最初にs 1とs 2の前のlne 1文字をそれぞれのウィンドウに入れます.このとき2つのウィンドウが等しい場合はtrueを直接返し、等しくない場合はlen 1からs 2の文字をロードし、ウィンドウの左側に2つのウィンドウがサイズを維持するため、ウィンドウが等しい場合はtrueを返します.
class Solution {
public:
bool checkInclusion(string s1, string s2) {
//v1、v2 ， len1 ， TURE， v2 ， ，
int len1 = s1.size(),len2 = s2.size();
vector v1(128,0),v2(128,0);
for(int i = 0;i 43.文字列乗算
解析:ここでは主に3つの配列を開き、1つの配列には最初の文字列が保存され、もう1つの配列には2番目の文字列が保存され、最後の配列には結果が保存されます.2つの文字列を保存するときは逆の順序で保存します.私たちは普段乗算をするときも数字の最後の方から前に乗るので、実はこの問題は主に普段紙でやっている乗算をシミュレートしています.
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;i9)
{
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.文字列内の単語を反転
分析:主な方法は、まず文字列全体を反転してから、文字列を巡回し始め、1つの単語(文字ではないことに注意)を巡回するたびに、この単語を反転します.
class Solution {
public:
void reverseWords(string &s) {
int index = 0,n = s.size();
reverse(s.begin(),s.end()); //
for(int i = 0;i93.IPアドレスの復元
分析:一般的な問題は文字列に何種類の可能な配列があるかを聞いて、十中八九はすべて再帰で作ったのです.まず、関数を書いて、1つの文字列がipのノードの1つに合致するかどうかを判断する必要があります.一致する基準:1、1から3ビットの長さの文字列です.2、長さが1より大きいとトップは0にならない.3、整数の大きさは0~255の範囲である.
それから正式な仕事を再帰することができます.ここでは文字列に対して1ビット、2ビット、3ビットを切り取ります..のIPの1つのノードを構成できるかどうかを判断し、できればこの部分を遮断し、残りの部分を再帰して判断を続けます.
コードを具体的に見る
class Solution {
public:
vector restoreIpAddresses(string s) {
vector res;
// string out = "";
helper(res,s,"",4);
return res;
}
void helper(vector& res,string s,string out,int k)
{
if(k==0)
{
if(s.empty()) // ， s
res.push_back(out);
}
else
{
for(int i = 1;i<=3;i++)
{
// ，
if(s.size()>=i&&isValid(s.substr(0,i))) // ，
{
if(k==1) //k==1 ip
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;
}
}; 二、配列と並べ替え
15.三数の和
class Solution {
public:
//
// ， ( 0)
//
vector> threeSum(vector& nums) {
vector> res;
sort(nums.begin(),nums.end());
for(int i = 0;i0) 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 674.最長連続増分シーケンス
class Solution {
public:
int findLengthOfLCIS(vector& 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.両数加算
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
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.チェーンテーブルのソート
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// ， 。merge
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->valval)
{
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.リングチェーンテーブルII
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
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.二叉木の最近の公共祖先
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
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) //p q
return root;
return left?left:right;
}
};四、動的または貪欲
121.株を売買する最良のタイミング
class Solution {
public:
int maxProfit(vector& prices) {
int res = 0,buy = INT_MAX;
for(auto c:prices)
{
buy = min(buy,c);
res = max(res,c-buy);
}
return res;
}
}; 122.株の売買に最適なタイミングII
class Solution {
public:
int maxProfit(vector& prices) {
int len = prices.size();
if(len<=1)
return 0;
vector have(len);
vector unhave(len);
have[0] = -prices[0];
int res = 0;
for(int i = 1;i 221.最大正方形
class Solution {
public:
int maximalSquare(vector>& matrix) {
if(matrix.empty()||matrix[0].empty()) return 0;
int m = matrix.size(),n = matrix[0].size();
vector> dp(m,vector(n,0));
int res = 0;
for(int i = 0;i