paul90539/leetcode

leetcode

前言

自己寫過的題目紀錄，不一定會是最佳解，
而且有一部份受個人習慣影響，像是會很想避免使用hashMap，
主要只是想留存一些程式與解題思路，方便以後回憶算法。

ICON來源

https://github.com/ikatyang/emoji-cheat-sheet
裡面的ICON非常便利使用，呼叫API對應的ICON就會出現

Problem List

#	Title	Solutions	Video	Difficulty	Upvote	Tag
2136	Earliest Possible Day of Full Bloom	Solution		Hard	94.74%
2131	Longest Palindrome by Concatenating Two Letter Words	Solution		Medium	98.07%
2095	Delete the Middle Node of a Linked List	Solution		Medium	98.17%	LinkList
1832	Check if the Sentence Is Pangram	Solution		Easy	97.82%
1706	Where Will the Ball Fall	Solution		Medium	94.41%
1662	Check If Two String Arrays are Equivalent	Solution		Easy	91.73%
1544	Make The String Great	Solution		Easy	95.84%
1531	String Compression II	Solution	🎞️	Hard	93.06%	DP
1480	Running Sum of 1d Array	Solution		Easy	95.69%
1448	Count Good Nodes in Binary Tree	Solution		Medium	97.33%	Tree
1335	Minimum Difficulty of a Job Schedule	Solution	🎞️	Hard	91.59%	DP
1323	Maximum 69 Number	Solution		Easy	91.87%
1239	Maximum Length of a Concatenated String with Unique Characters	Solution		Medium	93.40%	DFS
1155	Number of Dice Rolls With Target Sum	Solution		Medium	96.91%	DP
1047	Remove All Adjacent Duplicates In String	Solution		Easy	96.17%	Stack
976	Largest Perimeter Triangle	Solution		Easy	87.93%
954	Array of Doubled Pairs	Solution		Medium	90.73%	HashMap
926	Flip String to Monotone Increasing	Solution		Medium	95.80%	DP
901	Online Stock Span	Solution		Medium	93.81%	Stack
899	Orderly Queue	Solution		Hard	72.28%
877	Stone Game	Solution	🎞️	Medium	50.59%	DP
876	Middle of the Linked List	Solution		Easy	97.31%	LinkList
766	Toeplitz Matrix	Solution		Easy	95.36%
724	Find Pivot Index	Solution		Easy	90.44%	Integral Image
692	Top K Frequent Words	Solution		Medium	95.56%	HashMap
645	Set Mismatch	Solution	🎞️	Easy	81.18%
433	Minimum Genetic Mutation	Solution		Medium	90.41%	BFS
429	N-ary Tree Level Order Traversal	Solution		Medium	96.22%	Tree
415	Add Strings	Solution		Easy	86.57%
303	Range Sum Query - Immutable	Solution		Easy	58.26%	Integral Image
237	Delete Node in a Linked List	Solution		Medium	76.19%	LinkList
132	Palindrome Partitioning II	Solution	🎞️	Hard	97.76%	DP
49	Group Anagrams	Solution		Medium	97.12%
38	Count and Say	Solution		Medium	32.16%
36	Valid Sudoku	Solution		Medium	89.27%
21	Merge Two Sorted Lists	Solution		Easy	91.91%	LinkList
12	Integer to Roman	Solution		Medium	49.84%
11	Container With Most Water	Solution		Medium	95.11%
5	Longest Palindromic Substring	Solution		Medium	94.55%	DP
4	Median of Two Sorted Arrays	Solution	🎞️	Hard	89.82%	Divide and Conquer
3	Longest Substring Without Repeating Characters	Solution	🎞️	Medium	95.91%	HashMap, Sliding Window
2	Add Two Numbers	Solution		Medium	83.76%	LinkList
1	Two Sum	Solution	🎞️	Easy	96.85%	HashMap

與題目無關的加速問題(C++的輸入輸出保護)

簡單來說，C++在IO方面效率低下，是因為他內部為了兼容C而採取的保護措施
而保護措施預設是開啟的，只要關掉IO的執行時間就會飛快提升，leetcode也能進一步加快執行效率
以下就是關閉保護措施的程式碼:

ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);

ios_base::sync_with_stdio
這個函數是一個"是否兼容stdio"的開關，C++為了兼容C，保證程式在使用了std::printf和std::cout的時候不發生混亂，將輸出流綁到了一起

tie
tie是將兩個stream綁定的函數，空參數的話則返回當前的輸出流指標
在默認的情況下cin綁定的是cout，每次執行 << 操作符的時候都要調用flush
這樣會增加IO負擔，可以通過tie(0)(0表示NULL)來解除cin與cout的綁定，進一步加快執行效率

詳細說明(來源)

C++ std::string 字串拼接效率分析

C++中不同方式串接字串效率會有明顯的不同，詳細請看->0038_README

//std::string next, str;
//int same;
// 1. this way spend time: 0, 6, 7 ms
next +='0'+same;
next += str[s];
// 2. this way spend time: 18, 21, 23 ms
next += to_string(same) + str[s];
// 3. this way spend time: 113, 120, 120 ms
next = next + to_string(same) + str[s];