继续过Hard题目.周五

	#	Title	Acceptance	Difficulty
。	65	Valid Number	12.6%	Hard
。	126	Word Ladder II	13.6%	Hard
。	149	Max Points on a Line	15.6%	Hard
。	146	LRU Cache	16.0%	Hard
。	68	Text Justification	18.1%	Hard
。	460	LFU Cache	19.0%	Hard
。	44	Wildcard Matching	19.0%	Hard
。	308	Range Sum Query 2D - Mutable	19.8%	Hard
。	4	Median of Two Sorted Arrays	20.8%	Hard
。	420	Strong Password Checker	21.0%	Hard
。	273	Integer to English Words	21.1%	Hard
。	30	Substring with Concatenation of All Words	21.7%	Hard
。	440	K-th Smallest in Lexicographical Order	22.1%	Hard
。	140	Word Break II	22.2%	Hard
。	212	Word Search II	22.2%	Hard
。	269	Alien Dictionary	22.3%	Hard
。	174	Dungeon Game	22.9%	Hard
。	214	Shortest Palindrome	23.0%	Hard
。	446	Arithmetic Slices II - Subsequence	23.0%	Hard
。	32	Longest Valid Parentheses	23.1%	Hard
。	295	Find Median from Data Stream	23.3%	Hard
。	132	Palindrome Partitioning II	23.4%	Hard
。	10	Regular Expression Matching	23.6%	Hard
。	76	Minimum Window Substring	23.8%	Hard
。	188	Best Time to Buy and Sell Stock IV	23.8%	Hard
。	321	Create Maximum Number	23.9%	Hard
。	135	Candy	23.9%	Hard
。	335	Self Crossing	23.9%	Hard
。	97	Interleaving String	23.9%	Hard
。	391	Perfect Rectangle	24.2%	Hard
。	158	Read N Characters Given Read4 II - Call multiple times	24.4%	Hard
。	466	Count The Repetitions	24.6%	Hard
。	336	Palindrome Pairs	24.7%	Hard
。	41	First Missing Positive	24.9%	Hard
。	124	Binary Tree Maximum Path Sum	25.0%	Hard
。	224	Basic Calculator	25.5%	Hard
。	218	The Skyline Problem	25.5%	Hard
。	84	Largest Rectangle in Histogram	25.6%	Hard
。	23	Merge k Sorted Lists	25.9%	Hard
。	45	Jump Game II	26.0%	Hard
。	85	Maximal Rectangle	26.1%	Hard
。	57	Insert Interval	26.3%	Hard
。	138	Copy List with Random Pointer	26.6%	Hard
。	233	Number of Digit One	27.3%	Hard
。	381	Insert Delete GetRandom O(1) - Duplicates allowed	28.0%	Hard
。	37	Sudoku Solver	28.1%	Hard
。	432	All O`one Data Structure	28.2%	Hard
。	87	Scramble String	28.3%	Hard
。	123	Best Time to Buy and Sell Stock III	28.3%	Hard
。	56	Merge Intervals	28.4%	Hard
。	282	Expression Add Operators	28.5%	Hard
。	316	Remove Duplicate Letters	28.6%	Hard
	164	Maximum Gap	28.6%	Hard
	99	Recover Binary Search Tree	28.7%	Hard
	327	Count of Range Sum	28.9%	Hard
	51	N-Queens	29.0%	Hard
	25	Reverse Nodes in k-Group	29.7%	Hard
	472	Concatenated Words	30.1%	Hard
	465	Optimal Account Balancing	30.1%	Hard
	248	Strobogrammatic Number III	30.5%	Hard
	72	Edit Distance	30.6%	Hard
	115	Distinct Subsequences	30.6%	Hard
	403	Frog Jump	30.9%	Hard
	411	Minimum Unique Word Abbreviation	31.1%	Hard
	239	Sliding Window Maximum	31.4%	Hard
	330	Patching Array	31.5%	Hard
	297	Serialize and Deserialize Binary Tree	31.6%	Hard
	354	Russian Doll Envelopes	31.8%	Hard
	358	Rearrange String k Distance Apart	31.8%	Hard
	33	Search in Rotated Sorted Array	31.9%	Hard
	363	Max Sum of Rectangle No Larger Than K	32.1%	Hard
	410	Split Array Largest Sum	32.2%	Hard
	480	Sliding Window Median	33.1%	Hard
	317	Shortest Distance from All Buildings	33.3%	Hard
	117	Populating Next Right Pointers in Each Node II	33.5%	Hard
	315	Count of Smaller Numbers After Self	33.5%	Hard
	301	Remove Invalid Parentheses	34.5%	Hard
	42	Trapping Rain Water	35.3%	Hard
	128	Longest Consecutive Sequence	35.3%	Hard
	329	Longest Increasing Path in a Matrix	35.4%	Hard
	407	Trapping Rain Water II	35.6%	Hard
	154	Find Minimum in Rotated Sorted Array II	36.2%	Hard
	265	Paint House II	37.1%	Hard
	272	Closest Binary Search Tree Value II	37.6%	Hard
	291	Word Pattern II	37.7%	Hard
	305	Number of Islands II	38.1%	Hard
	380	Insert Delete GetRandom O(1)	38.4%	Hard
	145	Binary Tree Postorder Traversal	38.4%	Hard
	340	Longest Substring with At Most K Distinct Characters	38.6%	Hard
	352	Data Stream as Disjoint Intervals	38.9%	Hard
	159	Longest Substring with At Most Two Distinct Characters	39.7%	Hard
	312	Burst Balloons	41.6%	Hard
	287	Find the Duplicate Number	41.8%	Hard
	425	Word Squares	41.9%	Hard
	52	N-Queens II	42.8%	Hard
	302	Smallest Rectangle Enclosing Black Pixels	44.0%	Hard
	471	Encode String with Shortest Length	44.2%	Hard
	296	Best Meeting Point	50.4%	Hard

。

Jump Game II

26.0%

Hard

很好的题目。

https://discuss.leetcode.com/topic/3191/o-n-bfs-solution/2

Maximal Rectangle

26.1%

Hard

这个解法真的是相当的好。

https://discuss.leetcode.com/topic/6650/share-my-dp-solution/2

233

Number of Digit One

27.3%

Hard

这个解法非常好，也非常有技巧：

https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

通过对某一个位置上面的1的个数累加，来完成。

Insert Interval

26.3%

Hard

解法非常好。

http://www.cnblogs.com/charlesblc/p/6438698.html

Sudoku Solver

28.1%

Hard

很好的解法：

https://discuss.leetcode.com/topic/11327/straight-forward-java-solution-using-backtracking

432

All O`one Data Structure

28.2%

Hard

我也有大致的思路。这个里面的代码写的真是非常的精巧。

https://discuss.leetcode.com/topic/63827/c-solution-with-comments

class AllOne {

public:

    void inc(string key) {

        // If the key doesn't exist, insert it with value 0.

        if (!bucketOfKey.count(key))

            bucketOfKey[key] = buckets.insert(buckets.begin(), {, {key}});

        // Insert the key in next bucket and update the lookup.

        auto next = bucketOfKey[key], bucket = next++;

        if (next == buckets.end() || next->value > bucket->value + )

            next = buckets.insert(next, {bucket->value + , {}});

        next->keys.insert(key);

        bucketOfKey[key] = next;

        // Remove the key from its old bucket.

        bucket->keys.erase(key);

        if (bucket->keys.empty())

            buckets.erase(bucket);

    }

    void dec(string key) {

        // If the key doesn't exist, just leave.

        if (!bucketOfKey.count(key))

            return;

        // Maybe insert the key in previous bucket and update the lookup.

        auto prev = bucketOfKey[key], bucket = prev--;

        bucketOfKey.erase(key);

        if (bucket->value > ) {

            if (bucket == buckets.begin() || prev->value < bucket->value - )

                prev = buckets.insert(bucket, {bucket->value - , {}});

            prev->keys.insert(key);

            bucketOfKey[key] = prev;

        }

        // Remove the key from its old bucket.

        bucket->keys.erase(key);

        if (bucket->keys.empty())

            buckets.erase(bucket);

    }

    string getMaxKey() {

        return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());

    }

    string getMinKey() {

        return buckets.empty() ? "" : *(buckets.begin()->keys.begin());

    }

private:

    struct Bucket { int value; unordered_set<string> keys; };

    list<Bucket> buckets;

    unordered_map<string, list<Bucket>::iterator> bucketOfKey;

};

很不错。用了stl里面的list，然后用了里面的iterator，可以方便的++,--,insert和erase。

巴特西

继续过Hard题目.周五

最新文章

热门文章