-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLeetCode-46-Permutations.html
More file actions
287 lines (219 loc) · 17.5 KB
/
LeetCode-46-Permutations.html
File metadata and controls
287 lines (219 loc) · 17.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
<!DOCTYPE html>
<html>
<head>
<!-- [[! Document Settings ]] -->
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<!-- [[! Page Meta ]] -->
<title>LeetCode 46 : Permutations</title>
<meta name="description" content="Make Today Better Than Yesterday - Code, Food, Photo and some Geek stuff ..." />
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="shortcut icon" href="/assets/images/favicon.ico" >
<!-- [[! Styles'n'Scripts ]] -->
<link rel="stylesheet" type="text/css" href="/assets/css/screen.css" />
<link rel="stylesheet" type="text/css"
href="//fonts.googleapis.com/css?family=Merriweather:300,700,700italic,300italic|Open+Sans:700,400" />
<link rel="stylesheet" type="text/css" href="/assets/css/syntax.css" />
<!-- [[! Ghost outputs important style and meta data with this tag ]] -->
<link rel="canonical" href="/" />
<meta name="referrer" content="origin" />
<link rel="next" href="/page2/" />
<meta property="og:site_name" content="Make Today Better Than Yesterday" />
<meta property="og:type" content="website" />
<meta property="og:title" content="Make Today Better Than Yesterday" />
<meta property="og:description" content="Code, Food, Photo and some Geek stuff ..." />
<meta property="og:url" content="/" />
<meta property="og:image" content="/assets/images/cover1.jpg" />
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:title" content="Make Today Better Than Yesterday" />
<meta name="twitter:description" content="Code, Food, Photo and some Geek stuff ..." />
<meta name="twitter:url" content="/" />
<meta name="twitter:image:src" content="/assets/images/cover1.jpg" />
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "Website",
"publisher": "Finding The Way Home",
"url": "/",
"image": "/assets/images/cover1.jpg",
"description": "Code, Food, Photo and some Geek stuff ..."
}
</script>
<meta name="generator" content="Jekyll 3.0.0" />
<link rel="alternate" type="application/rss+xml" title="Make Today Better Than Yesterday" href="/rss.xml" />
</head>
<body class="home-template nav-closed">
<div class="nav">
<h3 class="nav-title">Menu</h3>
<a href="#" class="nav-close">
<span class="hidden">Close</span>
</a>
<ul>
<li class="nav-home " role="presentation"><a href="/">Home</a></li>
<li class="nav-about " role="presentation"><a href="/about">About</a></li>
<li class="nav-photo " role="presentation"><a href="/tag/photo">Photo</a></li>
<li class="nav-food " role="presentation"><a href="/tag/food">Food</a></li>
<li class="nav-geek " role="presentation"><a href="/tag/geek">Geek</a></li>
<li class="nav-code " role="presentation"><a href="/tag/code">Code</a></li>
<li class="nav-author " role="presentation"><a href="/author/CT">Author</a></li>
</ul>
<a class="subscribe-button icon-feed" href="/rss.xml">Subscribe</a>
</div>
<span class="nav-cover"></span>
<div class="site-wrapper">
<!-- [[! Everything else gets inserted here ]] -->
<!-- < default -->
<!-- The comment above "< default" means - insert everything in this file into -->
<!-- the [body] of the default.hbs template, which contains our header/footer. -->
<!-- Everything inside the #post tags pulls data from the post -->
<!-- #post -->
<header class="main-header post-head " style="background-image: url(/assets/images/cover_2.jpg) ">
<nav class="main-nav overlay clearfix">
<a class="blog-logo" href="/"><img src="/assets/images/ghost.png" alt="Blog Logo" /></a>
<a class="menu-button icon-menu" href="#"><span class="word">Menu</span></a>
</nav>
</header>
<main class="content" role="main">
<article class="post tag-code">
<header class="post-header">
<h1 class="post-title">LeetCode 46 : Permutations</h1>
<section class="post-meta">
<!-- <a href='/'>Ching Tsai</a> -->
<time class="post-date" datetime="2016-03-07">07 Mar 2016</time>
<!-- [[tags prefix=" on "]] -->
on
<a href='/tag/code'>Code</a>
</section>
</header>
<section class="post-content">
<blockquote>
<p>Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].</p>
</blockquote>
<h3>Initial Though</h3>
<p>基本上的概念就是對一個 input integer array 做隨機排序，使個 Backtracking 的經典題目。</p>
<h3>Guide</h3>
<p>這裡可以想像就是在對一個 N-ary Tree 用 DFS 來遍歷， 而 N 就是總共所有的 integer array。所以可以想像每下一層就是要從剩下的數字中挑一個放到 <code>sub</code>，所以這裡我用一個 <code>HashSet</code> 來記錄已經取出的數字。如此做到所有的數字都被拿完，也就是 <code>sub</code> 和 input array 一樣長，此時就把 <code>sub</code> clone 一份到 <code>result</code> 裡。並且回傳的時候要把自己放到 <code>sub</code> 尾端的數字 pop 掉，另外也要移除 <code>HashSet</code> 裡的同一個數字。這樣從底部回去的時候，之前選的字才能被之後 sub array 選到。</p>
<h3>Code</h3>
<div class="highlight"><pre><code class="language-java" data-lang="java"><span class="kd">public</span> <span class="kd">class</span> <span class="nc">Solution</span> <span class="o">{</span>
<span class="kd">public</span> <span class="n">List</span><span class="o"><</span><span class="n">List</span><span class="o"><</span><span class="n">Integer</span><span class="o">>></span> <span class="nf">permute</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">)</span> <span class="o">{</span>
<span class="n">List</span><span class="o"><</span><span class="n">List</span><span class="o"><</span><span class="n">Integer</span><span class="o">>></span> <span class="n">result</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o"><</span><span class="n">List</span><span class="o"><</span><span class="n">Integer</span><span class="o">>>();</span>
<span class="n">HashSet</span><span class="o"><</span><span class="n">Integer</span><span class="o">></span> <span class="n">h</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashSet</span><span class="o"><</span><span class="n">Integer</span><span class="o">>();</span>
<span class="n">LinkedList</span><span class="o"><</span><span class="n">Integer</span><span class="o">></span> <span class="n">sub</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o"><</span><span class="n">Integer</span><span class="o">>();</span>
<span class="n">DFS</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="mi">0</span><span class="o">,</span><span class="n">result</span><span class="o">,</span><span class="n">h</span><span class="o">,</span><span class="n">sub</span><span class="o">);</span>
<span class="k">return</span> <span class="n">result</span><span class="o">;</span>
<span class="o">}</span>
<span class="kd">public</span> <span class="kt">void</span> <span class="nf">DFS</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span> <span class="kt">int</span> <span class="n">k</span> <span class="o">,</span> <span class="n">List</span><span class="o"><</span><span class="n">List</span><span class="o"><</span><span class="n">Integer</span><span class="o">>></span> <span class="n">result</span><span class="o">,</span> <span class="n">HashSet</span><span class="o"><</span><span class="n">Integer</span><span class="o">></span> <span class="n">h</span> <span class="o">,</span> <span class="n">LinkedList</span><span class="o"><</span><span class="n">Integer</span><span class="o">></span> <span class="n">sub</span><span class="o">){</span>
<span class="k">if</span><span class="o">(</span><span class="n">k</span><span class="o">==</span><span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">){</span>
<span class="n">result</span><span class="o">.</span><span class="na">add</span><span class="o">((</span><span class="n">List</span><span class="o"><</span><span class="n">Integer</span><span class="o">>)</span><span class="n">sub</span><span class="o">.</span><span class="na">clone</span><span class="o">());</span>
<span class="k">return</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span><span class="mi">0</span> <span class="o">;</span><span class="n">i</span><span class="o"><</span><span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">;</span><span class="n">i</span><span class="o">++){</span>
<span class="k">if</span><span class="o">(!</span><span class="n">h</span><span class="o">.</span><span class="na">contains</span><span class="o">(</span><span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">])){</span>
<span class="n">sub</span><span class="o">.</span><span class="na">addLast</span><span class="o">(</span><span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>
<span class="n">h</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>
<span class="n">DFS</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="o">,</span><span class="n">result</span><span class="o">,</span><span class="n">h</span><span class="o">,</span><span class="n">sub</span><span class="o">);</span>
<span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="na">removeLast</span><span class="o">();</span>
<span class="n">h</span><span class="o">.</span><span class="na">remove</span><span class="o">(</span><span class="n">a</span><span class="o">);</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="o">}</span>
</code></pre></div>
</section>
<footer class="post-footer">
<!-- Everything inside the #author tags pulls data from the author -->
<!-- #author-->
<figure class="author-image">
<a class="img" href="/author/CT" style="background-image: url(/assets/images/ct.png)"><span class="hidden">'s Picture</span></a>
</figure>
<section class="author">
<h4><a href="/author/CT">Ching Tsai</a></h4>
<p> 每天努力學習的研究攻城獅，略懂平行運算，分散式系統及機器學習，平時偶爾攝影，興趣是看 YouTube 學煮菜。</p>
<div class="author-meta">
<span class="author-location icon-location"> Hsinchu, Taiwan</span>
<span class="author-link icon-link"><a href="http://ChingTsai.github.io/chingtsai.github.io/"> ChingTsai.github.io/chingtsai.github.io/</a></span>
</div>
</section>
<!-- /author -->
<section class="share">
<h4>Share this post</h4>
<a class="icon-twitter" href="http://twitter.com/share?text=LeetCode 46 : Permutations&url=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-46-Permutations"
onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
<span class="hidden">Twitter</span>
</a>
<a class="icon-facebook" href="https://www.facebook.com/sharer/sharer.php?u=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-46-Permutations"
onclick="window.open(this.href, 'facebook-share','width=580,height=296');return false;">
<span class="hidden">Facebook</span>
</a>
<a class="icon-google-plus" href="https://plus.google.com/share?url=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-46-Permutations"
onclick="window.open(this.href, 'google-plus-share', 'width=490,height=530');return false;">
<span class="hidden">Google+</span>
</a>
</section>
<!-- Add Disqus Comments -->
<div id="disqus_thread"></div>
<script type="text/javascript">
//var disqus_developer = 1;
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'maketodaybetterthanyesterday'; // required: replace example with your forum shortname
var disqus_identifier = '/LeetCode-46-Permutations';
var disqus_url = 'http://ChingTsai.github.io/chingtsai.github.io//LeetCode-46-Permutations';
//console.log(disqus_shortname+" "+disqus_identifier+" "+disqus_url);
/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">blog comments powered by <span class="logo-disqus">Disqus</span></a>
</div>
</footer>
</article>
</main>
<aside class="read-next">
<!-- [[! next_post ]] -->
<a class="read-next-story " style="background-image: url(/assets/images/highlight.jpg)" href="/Jekyll-Markdown-Syntax-Highlighting">
<section class="post">
<h2>Jekyll Markdown Syntax Highlighting</h2>
<p>當初會被吸引來用 Jekyll 還來搭建這個 Blog ，其中一個很大的原因，也是因為內建的 Markdown expression 可以很方便的幫一些範例 Code 做美美的 Syntax Highlighting。不過 Highlighting 的 style...</p>
</section>
</a>
<!-- [[! /next_post ]] -->
<!-- [[! prev_post ]] -->
<a class="read-next-story prev " style="background-image: url(/assets/images/post_filter.jpg)" href="/Filter-%E5%88%9D%E9%AB%94%E9%A9%97">
<section class="post">
<h2>Filter 初體驗</h2>
<p>由於本身就有再攝影，所以希望這個 Blog 的圖片儘量都能用自己拍的照片。我對於拍照期望就是能還原最原始當下的情況，所以以往對於濾鏡的使用都嗤之以鼻，認為自己不會用到。不過在客製這個 Blog 的時候，當我把之前 Template 的預設圖換成自己的圖的時候，就總是覺得哪裡怪怪的，挑來挑去都找不到適合的。後來才發現如過要用來裝飾 Blog 用普通色調的圖片就會現得格格不入。如此想想還是嘗試一下濾鏡。 原本打算用 MAC 照片 來調，雖然 照片 裡的工具用來修圖已經足以，不過如果要調色系的話卻太陽春且繁瑣。後來上網找了下發現了Pixlr...</p>
</section>
</a>
<!-- [[! /prev_post ]] -->
</aside>
<!-- /post -->
<footer class="site-footer clearfix">
<section class="copyright"><a href="/">Make Today Better Than Yesterday</a> © 2016</section>
<section class="poweredby">Proudly published with <a href="https://jekyllrb.com/">Jekyll</a> using <a href="https://github.com/biomadeira/jasper">Jasper</a></section>
</footer>
</div>
<!-- [[! Ghost outputs important scripts and data with this tag ]] -->
<script type="text/javascript" src="https://code.jquery.com/jquery-1.11.3.min.js"></script>
<!-- [[! The main JavaScript file for Casper ]] -->
<script type="text/javascript" src="/assets/js/jquery.fitvids.js"></script>
<script type="text/javascript" src="/assets/js/index.js"></script>
<!-- Add Google Analytics -->
<!-- Google Analytics Tracking code -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', '', 'auto');
ga('send', 'pageview');
</script>
</body>
</html>