L
L
Leetcode题解
Search…
README
7.Reverse Integer
9.Palindrome Number
13.Roman to Integer
19.Remove Nth Node from End of List
20.Valid Parentheses
21.Merge Two Sorted Lists
22.Generate Parentheses
26.Remove Duplicates from Sorted Array
27.Remove Element
28.Implement strStr()
35.Search Insert Position
38.Count and Say
46.Permutations
53.Maximum Subarray
58.Length of Last Word
59.Spiral Matrix II
66.Plus One
67.Add Binary
69.Sqrt
70.Climbing Stairs
77.Combinations
78.Subsets
83.Remove Duplicates from Sorted List
88.Merge Sorted Array
104.Maximum Depth of Binary Tree
107.Binary Tree Level Order Traversal II
108.Convert Sorted Array to Binary Search Tree
100.Same Tree
101.Symmetric Tree
105.Construct Binary Tree from Preorder and Inorder Traversal
110.Balanced Binary Tree
111.Minimum Depth of Binary Tree
112.Path Sum
118.Pascals Triangle
119.Pascals Triangle II
121.Best Time to Buy and Sell Stock
125.Valid Palindrome
131.Palindrome Partitioning
139.Word Break
140.Word Break II
141.Linked List Cycle
143.Reorder List
155.Min Stack
167.Two Sum II- Input Array is Sorted
168.Excel Sheet Column Title
169.Majority Element
171.Excel Sheet Column Number
172.Factorial Trailing Zeroes
175.Combine Two Tables
181.Employee Earning More Than Their Managers
182.Duplicate Emails
183.Customers Who Never Order
189.Rotate Array
191.Number of 1 Bits
193.Valid Phone Numbers
195.Tenth Line
196.Delete Duplicate Emails
197.Rising Temperature
198.House Robber
202.Happy Number
203.Remove Linked List Elements
204.Count Primes
205.Isomorphic Strings
206.Reverse Linked List
217.Contains Duplicate
219.Contains Duplicate II
225.Implement Stack Using Queues
226.Invert Binary Tree
231.Power of Two
232.Implement Queue Using Stack
234.Palindrome Linked List
237.Delete Node in a Linked List
240.Search a 2D Matrix II
242.Valid Anagram
257.Binary Tree Paths
258.Add Digits
263.Ugly Numbers
268.Missing Number
278.First Bad Version
284.Peeking Iterator
290.Word Pattern
282.Nim Game
303.Range Sum Query Immutable
338.Counting Bits
342.Power of Four
344.Reverse String
345.Reverse Vowels of a String
349.Intersection of Two Arrays
350.Intersection of Two Arrays II
367.Valid Perfect Square
371.Sum of Two Integers
374.Guess Number Higher or Lower
383.Ransom Note
387.First Unique Character in a String
400.Nth Digit
401.Binary Watch
404.Sum of Left Leaves
405.Convert A Number to Hexadecimal
409.Longest Palindrome
412.Fizz Buzz
414.Third Maximum Number
415.Add Strings
427.Construct Quad Tree
429.N Ary Tree Level Order Traversal
434.Number of Segments in a String
437.Path Sum III
438.Find All Anagrams in a String
441.Arranging Coins
443.String Compression
447.Number of Boomerangs
448.Find All Numbers Disappeared in an Array
453.Minimum Moves to Equal Array Elements
455.Assign Cookies
459.Repeated Substring Pattern
461.Hamming Distance
463.Island Perimeter
475.Heaters
476.Number Complement
482.License Key Formatting
485.Max Consecutive Ones
492.Construct the Rectangle
496.Next Greater Element I
500.Keyboard Row
501.Find Mode in Binary Tree
504.Base 7
506.Relative Ranks
507.Perfect Number
509.Fibonacci Number
520.Detect Capital
521.Longest Uncommon Subsequence I
530.Minimum Absolute Difference in BST
532.K-diff Pairs in an Array
535.Encode and Decode TinyURL
538.Convert BST to Greater Tree
541.Reverse String II
543.Diameter of Binary Tree
551.Student Attendace Record I
557.Reverse Words in a String
558.Quad Tree Intersection
559.Maxmium Depth of N Ary Tree
561.Array Partition I
563.Binary Tree Tilt
566.Reshape the Matrix
572.Subtree of Another Tree
575.Distribute Candies
581.Shortest Unsorted Continuous Subarray
589.N Ary Tree Preorder Traversal
590.N Ary Tree Postorder Traversal
594.Longest Harmonious Subsequence
595.Big Countires
596.Classes More Than 5 Students
598.Range Addition II
599.Minimum Index of Two Lists
605.Can Place Flowers
606.Construct String from Binary Tree
617.Merge Two Binary Trees
620.Not Boring Movies
627.Swap Salary
628.Maximum Product of Three Numbers
633.Sum of Square Numbers
637.Average of Levels in Binary Tree
643.Maximum Average Subarray I
645.Set Mismatch
653.Two Sum IV - Input is a BST
654.Maximum Binary Tree
657.Robot Return to Origin
661.Image Smoother
665.Non-Decreasing Array
669.Trim a Binary Search Tree
671.Second Minimum Node in a Binary Tree
680.Valid Palindrome II
682.Baseball Game
686.Repeated String Match
687.Longest Univalue Path
690.Employee Importance
693.Binary Number with Alternating Bits
696.Count Binary Substring
697.Degree of an Array
700.Search in a Binary Search Tree
701.Insert Into a Binary Search Tree
703.Kth Largest Element in a Stream
704.Binary Search
705.Design Hashset
706.Design Hashmap
707.Design Linked List
709.To Lower Case
713.Subarray Product Less Than K
717.1 Bit and 2 Bit Characters
720.Longest Word in Dictionary
724.Find Pivot Index
728.Self Dividing Numbers
733.Flood Fill
739.每日温度
744.Find Smallest Letter Greater Than Target
746.Min Cost Climbing Stairs
747.Largest Number At Least Twice Of Others
748.Shortest Completing Word
754.Reach A Number
762.Prime Number of Set Bits in Binary Representation
766.Toeplitz Matrix
771.Jewels and Stones
783.Minimum Distance Between BST Nodes
784.Letter Case Permutation
788.Rotated Digits
796.Rotate String
804.Unique Morse Code Words
806.Number of Lines to Write String
807.Max Increase to Keep City Skyline
811.Subdomain Visit Count
812.Largest Triangle Area
814.Binary Tree Pruning
819.Most Common Word
821.Shortest Distance to a Character
824.Goat Latin
829.Consecutive Numbers Sum
830.Position of Large Groups
831.Masking Personal Information
832,Flipping an Image
833.Find And Replace in String
835,Image Overlap
836.Rectangle Overlap
840.Magic Squares In Grid
844.Backspace String Compare
848.Shifting Letters
849.Maximize Distance to Closest Person
852.Peak Index in A Mountain Array
853.Car Fleet
855.Exam Room
859.Buddy Strings
860.Lemonade Change
861.Score After Flipping Matrix
864.Shortest Path to Get All Keys
865.Smallest Subtree with all the Deepest Nodes
866.Prime Palindrome
867.transpose
868.Binary Gap
872.Leaf Similar Trees
874.Walking Robot Simulation
876.Middle of the Linked List
883.Projection Area of 3D Shapes
884.Uncommon Words from Two Sentences
887.Super Egg Drop
888.Fair Candy Swap
892.Surface Area of 3D Shapes
893.Groups of Special Equivalent Strings
894.All Possible Full Binary Trees
896.monotonic array
897.increasing order search tree
900.RLE Iterator
901.Online Stock Span
905.Sort Array by Parity
908.Smallest Range I
910.Smallest Range II
913.Cat and Mouse
914.X of a Kind in a Deck of Cards
915.Partition Array into Disjoint Intervals
916.Word Subsets
917.Reverse Only Letters
922.Sort Array by Parity II
925.Long Pressed Name
929.Unique Email Address
937.Reorder Log Files
938.Range Sum of BST
941.Valid Mountain Array
942.Di String Match
944.Delete Column to Make Sorted
949.Largest Time For Given Digits
950.Reveal Cards in Increasing Order
953.Verifying an Alien Dictionary
961.N Repeated Element in Size 2N Array
965.Univalued Binary Tree
970.Powerful Integers
974.Subarray Sums Divisible By K
976.Largest Perimeter Triangle
977.Squares of a Sorted Array
985.Sum of Even Numbers After Queries
989.Add to Array-Form of Integer
990.Satisfiability of Equality Equations
993.Cousins in Binary Tree
994.Rotting Oranges
997.Find the Town Judge
999.Available Captures for Rook
1002.Find Common Characters
1005.Maximise Sum of Array after K Negations
1008.Construct Binary Search Tree from Preorder Traversal
1021.Remove Outermost Parentheses
1025.Divisor Game
1029.Tow City Scheduling
1030.Matrix Cells in Distance Order
1033.Moving Stones Until Consecutive
1037.Valid Boomerang
1038.Binary Search Tree to Greater Sum Tree
1041.Robot Bounded in Circle
1042.Flower Planting with no Adjacent
1046.Last Stone Weight
1089.Duplicate Zeros
1013.Partition Array Into Three Parts with Equal Sum
1018.Binary Prefix Divisible By 5
1022.Sum of Root To Leaf Binary Numbers
1071.Greatest Common Divisor of Strings
1079.Letter Tile Possibilities
1103.Distribute Candies to People
1114.Print in Order
1115.Print FooBar Alternately
1116.Print Zero Even Odd
1117.Building H2O
1128.Number of Equivalent Domino Pairs
1169.Invalid Transactions
1176.Diet Plan Performance
1282.用户分组
1329.Sort the Matrix Diagonally
1379.Find a Corresponding Node of a Binary Tree in a Clone of That Tree
1395.Count Number of Teams
ByteDance
面试题 64
面试题 16.01
面试题 16.18
面试题 29
面试题 46
Powered By GitBook
1042.Flower Planting with no Adjacent
1042.Flower Planting with no Adjacent
难度:Easy
有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外，没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
示例 1：
​
输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
示例 2：
​
输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：
​
输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
​
提示：
​
1 <= N <= 10000
0 <= paths.size <= 20000
不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。
本质上是四色问题的染色，使用回溯法。
class Solution {
private:
int n,m;
int color[10000];
vector<vector<int>>a;
bool Valid(int t)
{
if(a[t].size()<1) return true;
for(auto i:a[t])
if(color[t]==color[i])
return false;
return true;
}
bool traceback(int t)
{
//cout<<t<<endl;
if(t==n) return true;
for(int i=1;i<=m;i++)
{
color[t]=i;
if(Valid(t))
{
if(traceback(t+1)) return true;
}
}
return false;
}
public:
vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
n=N;
m=4;
vector<int> tmp{-1};
a.resize(10000);
for(int i=0;i<paths.size();i++)
{
a[paths[i][0]-1].push_back(paths[i][1]-1);
a[paths[i][1]-1].push_back(paths[i][0]-1);
}
traceback(0);
vector<int >answer(color,color+N);
return answer;
}
};
著名的NP完全问题，难度分类不应该是EASY，回溯法是暴力解法。
执行用时 : 232 ms, 在Flower Planting With No Adjacent的C++提交中击败了92.48% 的用户 内存消耗 : 49.9 MB, 在Flower Planting With No Adjacent的C++提交中击败了100.00% 的用户
Previous
1041.Robot Bounded in Circle
Next
1046.Last Stone Weight
Last modified 8mo ago
Copy link