tag:blogger.com,1999:blog-20848367371438702362024-03-27T16:53:17.039-07:00喜刷刷Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.comBlogger130125tag:blogger.com,1999:blog-2084836737143870236.post-75357334192726467452014-11-30T21:01:00.000-08:002014-11-30T21:07:45.991-08:00C++ Specific Questions - Overloading VS OverridingRef: <a href="http://stackoverflow.com/questions/429125/override-and-overload-in-c">http://stackoverflow.com/questions/429125/override-and-overload-in-c</a><br />
<br />
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
<em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Overloading</em> generally means that you have two or more functions in the same scope having the same name. The function that better matches the arguments when a call is made wins and is called. Important to note, as opposed to calling a virtual function, is that the function that's called is selected at compile time. It all depends on the static type of the argument. If you have an overload for <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">B</code> and one for <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">D</code>, and the argument is a reference to <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">B</code>, but it really points to a <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">D</code> object, then the overload for <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">B</code> is chosen in C++. That's called <em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">static dispatch</em> as opposed to <em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">dynamic dispatch</em>. You overload if you want to do the same as another function having the same name, but you want to do that for another argument type. Example:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Foo</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">const</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> f</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// print a foo</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Bar</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">const</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> bar</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// print a bar</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span></code></pre>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
they both print their argument, so they are overloaded. But the first prints a foo, and the second prints a bar. If you have two functions that do different things, it's considered bad style when they have the same name, because that can lead to confusion about what will happen actually when calling the functions. Another usecase for overloading is when you have additional parameters for functions, but they just forward control to other functions:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Foo</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> f</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">PrintAttributes</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> b</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">/* ... */</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Foo</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> f</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">string </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">const</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> header</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">bool</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> printBold</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">f</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">PrintAttributes</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">header</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> printBold</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">));</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span></code></pre>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
That can be convenient for the caller, if the options that the overloads take are often used.</div>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
<em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Overriding</em> is something completely different. It doesn't compete with overloading. It means that if you have a virtual function in a base class, you can write a function with the same signature in the derived class. The function in the derived class <em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">overrides</em> the function of the base. Sample:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">struct</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> base </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">virtual</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">()</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> cout </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"><<</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="str" style="background: transparent; border: 0px; color: maroon; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">"base!"</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">;</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">struct</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> derived</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">:</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> base </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">virtual</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">()</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> cout </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"><<</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="str" style="background: transparent; border: 0px; color: maroon; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">"derived!"</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">;</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span></code></pre>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
Now, if you have an object and call the <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">print</code> member function, the print function of the derived is always called, because it overrides the one of the base. If the function <code style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 1px 5px; vertical-align: baseline; white-space: pre-wrap;">print</code> wasn't virtual, then the function in the derived wouldn't override the base function, but would merely <em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">hide</em> it. Overriding can be useful if you have a function that accepts a base class, and every one that's derived from it:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> doit</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">base </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">&</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">b</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">{</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// and sometimes, we want to print it</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
b</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">print</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">();</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">}</span></code></pre>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
Now, even though at compile time the compiler only knows that b is at least base, print of the derived class will be called. That's the point of virtual functions. Without them, the print function of the base would be called, and the one in the derived class wouldn't override it.<br />
<br />
<br />
<br />
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
You over<em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">load</em> functions for three reasons:</div>
<ol style="background: rgb(255, 255, 255); border: 0px; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; list-style-image: initial; list-style-position: initial; margin: 0px 0px 1em 30px; padding: 0px; vertical-align: baseline;">
<li style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"><div style="background: transparent; border: 0px; clear: both; font-size: 13.600000381469727px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
To provide two (or more) functions that perform similar, closely related things, differentiated by the types and/or number of arguments it accepts. Contrived example:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Log</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">string msg</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// logs a message to standard out</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Log</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">string msg</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">ofstream</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// logs a message to a file</span></code></pre>
</li>
<li style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"><div style="background: transparent; border: 0px; clear: both; font-size: 13.600000381469727px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
To provide two (or more) ways to perform the same action. Contrived example:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Plot</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Point</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> pt</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// plots a point at (pt.x, pt.y)</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">void</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">Plot</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> x</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> y</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="com" style="background: transparent; border: 0px; color: grey; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">// plots a point at (x, y)</span></code></pre>
</li>
<li style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"><div style="background: transparent; border: 0px; clear: both; font-size: 13.600000381469727px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
To provide the ability to perform an equivalent action given two (or more) different input types. Contrived example:</div>
<pre class="lang-cpp prettyprint prettyprinted" style="background: rgb(238, 238, 238); border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;"><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">wchar_t</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">ToUnicode</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="kwd" style="background: transparent; border: 0px; color: darkblue; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">char</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;"> c</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">
std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">wstring </span><span class="typ" style="background: transparent; border: 0px; color: #2b91af; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">ToUnicode</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">std</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">::</span><span class="pln" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">string s</span><span class="pun" style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span></code></pre>
</li>
</ol>
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
In <em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">some</em> cases it's worth arguing that a function of a different name is a better choice than an overloaded function. In the case of constructors, overloading is the only choice.</div>
<hr style="background-color: #dddddd; border: 0px; color: #dddddd; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; height: 1px; line-height: 17.804800033569336px; margin-bottom: 20px;" />
<div style="background: rgb(255, 255, 255); border: 0px; clear: both; font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 13.600000381469727px; line-height: 17.804800033569336px; margin-bottom: 1em; padding: 0px; vertical-align: baseline;">
Over<em style="background: transparent; border: 0px; font-size: 13.600000381469727px; margin: 0px; padding: 0px; vertical-align: baseline;">riding</em> a function is entirely different, and serves an entirely different purpose. Function overriding is how polymorphism works in C++. You override a function to change the behavior of that function in a derived class. In this way, a base class provides interface, and the derived class provides implementation.</div>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-74516666087205400772014-11-30T18:40:00.000-08:002014-11-30T18:40:26.049-08:00Microsoft Onsite Interview Checklist1. Resume preparation<br />
<br />
2. Basic data structure/algorithm<br />
<br />
3. Design question<br />
<br />
4. Behavior question<br />
<br />
5. C++ language specific question<br />
<br />
6. Knowledge about ASP.NET<br />
<br />Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2tag:blogger.com,1999:blog-2084836737143870236.post-36045350022127484102014-11-30T07:56:00.000-08:002014-11-30T19:50:02.067-08:00基础data structure/algorithm列表<span style="color: blue;"><b>1. Implementation of stack/queue (array and linked list)</b></span><br />
Implement queue using array: circular array - when meet end, wrap around to the beginning.<br />
An array with size n can implement an queue with size n-1 (related to the queue full condition)<br />
Queue empty: head == tail<br />
Queue full: head == tail+1 or head == tail wrap around<br />
Enqueue: tail++ or wrap around<br />
Dequeue: head++ or wrap around<br />
<br />
<b><span style="color: blue;">2. Binary search tree: insertion, deletion, </span></b><b><span style="color: blue;">successor, traversal, </span></b><b><span style="color: blue;">balance.</span></b><br />
(1) Insertion: always insert to leaf; need to find the parent of the insertion position, O(h).<br />
(2) Deletion: assume delete z.<br />
z has not child: just delete.<br />
z has only one child: replace z by its child.<br />
z has both left/right child: find leftmost node in z's right subtree y. If y==z.right, replace z by y. Otherwise replace y by y's right child, and then replace z by y.<br />
<a href="http://geeksquiz.com/binary-search-tree-set-2-delete/">http://geeksquiz.com/binary-search-tree-set-2-delete/</a><br />
(3) Successor: <a href="http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/">http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/</a><br />
(4) Preorder, in-order, and post-order traversal using iterative methods.<br />
<br />
<span style="color: blue;"><b>3. Heap: creation, insertion.</b></span><br />
(1) Concept: nearly complete binary tree, implemented using array<br />
Parent-child relation: for 0-based array (A[0:n-1])<br />
parent(i) = (i-1)/2<br />
left(i) = 2*i+1<br />
right(i) = 2*i+2<br />
(2) Properties:<br />
Max heap: A[parent(i)] >= A[i] - heap sort<br />
Min heap: A[parent(i)] <= A[i] - priority queue<br />
(3) Heapify: find the largest among y = {A[i], A[left(i)], A[ right(i)]}.<br />
If y = A[i], done; else, swap A[i] with y, and heapify y<br />
(4) Build max heap: for each i from heap.size/2 to 0, heapify(i).<br />
<br />
<span style="color: blue;"><b>4. Hash table: array + linked list implementation, collision</b></span><br />
<br />
<span style="color: blue;"><b>5. Sorting: (1) merge sort, (2) quick sort, (3) counting sort</b></span><br />
Merge sort:<br />
<a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort">http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort</a><br />
<a href="http://www.sanfoundry.com/cpp-program-implement-merge-sort/">http://www.sanfoundry.com/cpp-program-implement-merge-sort/</a><br />
Quick sort:<br />
<a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort">http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort</a><br />
<a href="https://gsamaras.wordpress.com/code/quicksort-c/">https://gsamaras.wordpress.com/code/quicksort-c/</a><br />
<br />
<span style="color: blue;"><b>6. Master theorem</b></span><br />
Key: compare logb(a) and c: <a href="http://en.wikipedia.org/wiki/Master_theorem">http://en.wikipedia.org/wiki/Master_theorem</a><br />
<br />
<span style="color: blue;"><b>1. Stack implementation using array in C++:</b></span><br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #557799;">#include <string></span>
<span style="color: #008800; font-weight: bold;">using</span> <span style="color: #008800; font-weight: bold;">namespace</span> std;
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Stack</span> {
<span style="color: #997700; font-weight: bold;">private:</span>
<span style="color: #333399; font-weight: bold;">int</span> top;
<span style="color: #333399; font-weight: bold;">int</span> capacity;
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #333333;">*</span>storage;
<span style="color: #997700; font-weight: bold;">public:</span>
Stack(<span style="color: #333399; font-weight: bold;">int</span> capacity) {
<span style="color: #008800; font-weight: bold;">if</span> (capacity <span style="color: #333333;"><=</span> <span style="color: #0000dd; font-weight: bold;">0</span>)
<span style="color: #008800; font-weight: bold;">throw</span> string(<span style="background-color: #fff0f0;">"Stack's capacity must be positive"</span>);
storage <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[capacity];
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">-></span>capacity <span style="color: #333333;">=</span> capacity;
top <span style="color: #333333;">=</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
}
<span style="color: #333399; font-weight: bold;">void</span> push(<span style="color: #333399; font-weight: bold;">int</span> value) {
<span style="color: #008800; font-weight: bold;">if</span> (top <span style="color: #333333;">==</span> capacity)
<span style="color: #008800; font-weight: bold;">throw</span> string(<span style="background-color: #fff0f0;">"Stack's underlying storage is overflow"</span>);
top<span style="color: #333333;">++</span>;
storage[top] <span style="color: #333333;">=</span> value;
}
<span style="color: #333399; font-weight: bold;">int</span> peek() {
<span style="color: #008800; font-weight: bold;">if</span> (top <span style="color: #333333;">==</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>)
<span style="color: #008800; font-weight: bold;">throw</span> string(<span style="background-color: #fff0f0;">"Stack is empty"</span>);
<span style="color: #008800; font-weight: bold;">return</span> storage[top];
}
<span style="color: #333399; font-weight: bold;">void</span> pop() {
<span style="color: #008800; font-weight: bold;">if</span> (top <span style="color: #333333;">==</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>)
<span style="color: #008800; font-weight: bold;">throw</span> string(<span style="background-color: #fff0f0;">"Stack is empty"</span>);
top<span style="color: #333333;">--</span>;
}
<span style="color: #333399; font-weight: bold;">bool</span> isEmpty() {
<span style="color: #008800; font-weight: bold;">return</span> (top <span style="color: #333333;">==</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
}
<span style="color: #333333;">~</span>Stack() {
<span style="color: #008800; font-weight: bold;">delete</span>[] storage;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<b><span style="color: blue;">2. Min Binary Heap Implementation in C++:</span></b><br />
<br />
<a href="http://www.codeproject.com/Tips/816934/Min-Binary-Heap-Implementation-in-Cplusplus">http://www.codeproject.com/Tips/816934/Min-Binary-Heap-Implementation-in-Cplusplus</a>Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-31395756120057396062014-11-30T07:44:00.000-08:002014-11-30T08:37:40.600-08:00面试中的clarifying questions面试题经常有意无意字面上很含糊,这个时候一定需要和面世官交流搞清楚确切的意思。总结一下每个topic需要澄清的地方:<br />
<div>
<br /></div>
<div>
1. Array:</div>
<div>
(1) Sorted or not?</div>
<div>
(2) How many elements?</div>
<div>
(3) Element type? Int, float, double?</div>
<div>
(4) What's the range of those numbers? Positive or negative?</div>
<div>
(5) Contain duplicates or not?</div>
<div>
(6) Subsequence: adjacent or not?</div>
<div>
<br /></div>
<div>
2. Binary tree:</div>
<div>
(1) Binary search tree or normal binary tree?</div>
<div>
(2) Balanced or not?</div>
<div>
(3) Complete or not?</div>
<div>
(4) Has parent pointer or not?</div>
<div>
<br /></div>
<div>
3. Linked list:</div>
<div>
(1) Singly or doubly linked list?</div>
<div>
(2) Has duplicated nodal value or not?</div>
<div>
<br /></div>
<div>
4. String:</div>
<div>
(1) Need to remove white spaces? Tab and newline?</div>
<div>
(2) Only has digits? English letters? Upper or lower case?</div>
<div>
<br /></div>
<div>
5. Graph:</div>
<div>
(1) How many nodes and edges?</div>
<div>
(2) Directed or undirected?</div>
<div>
(3) Edges have weights? If so, what's the range?</div>
<div>
(4) Has loops? Negative sum loops?<br />
<br />
6. Return value:<br />
(1) What should my method return?<br />
(2) If there are multiple solutions to the problem, which one should be returned?<br />
(3) If it should return multiple values, do you have any preference on what to return?<br />
(4) What should I do/return if the input is invalid / does not match the constraints?</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-38797026866614445972014-11-29T13:02:00.000-08:002014-11-29T14:38:59.273-08:00[LeetCode] Wildcard Matching<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Implement wildcard pattern matching with support for <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'?'</code> and <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'*'</code>.</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the <span style="box-sizing: border-box; font-weight: 700;">entire</span> input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false</pre>
<div>
<br /></div>
<span style="color: blue;"><b></b></span><br />
<div>
<span style="color: blue;"><b><span style="color: blue;"><b><br /></b></span></b></span></div>
<span style="color: blue;"><b>
思路1:DP</b></span><br />
<div>
<br /></div>
<div>
和Regular Expression Matching很像,这里的'?'相当于Regular Expression中的'.',但'*'的用法不一样。这里'*'与前一个字符没有联系,并且无法消去前一个字符,但可以表示任意一串字符。递推公式的推导和Regular Expression Matching也基本类似。</div>
<div>
<br /></div>
<div>
<span style="color: red;"><b>p[j-1] == s[i-1] || p[j-1] == '?':dp[i][j] = dp[i-1][j-1]</b></span></div>
<div>
<span style="color: red;"><b>p[j-1] == '*':</b></span></div>
<div>
<span style="color: red;"><b>1. 匹配0个字符:dp[i][j] = dp[i][j-1]</b></span></div>
<div>
<span style="color: red;"><b>2. 匹配1个字符:dp[i][j] = dp[i-1][j-1]</b></span></div>
<div>
<span style="color: red;"><b>3. 匹配多个字符:dp[i][j] = dp[i-1][j]</b></span></div>
<div>
<br /></div>
<div>
先用二维数组写,发现会Memory Limit Exceeded</div>
<div>
<br /></div>
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">bool</span> isMatch(<span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>s, <span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>p) {
<span style="color: #333399; font-weight: bold;">int</span> m <span style="color: #333333;">=</span> strlen(s), n <span style="color: #333333;">=</span> strlen(p);
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">>></span> dp(m<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">></span>(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,<span style="color: #007020;">false</span>));
dp[<span style="color: #0000dd; font-weight: bold;">0</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>m; i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span>s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'?'</span>)
dp[i][j] <span style="color: #333333;">=</span> i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #0066bb; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'*'</span>)
dp[i][j] <span style="color: #333333;">=</span> dp[i][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> (i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> (dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j]));
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[m][n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<br />
<br />
然后用一维滚动数组改写,发现会Time Limit Exceeded<br />
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">bool</span> isMatch(<span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>s, <span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>p) {
<span style="color: #333399; font-weight: bold;">int</span> m <span style="color: #333333;">=</span> strlen(s), n <span style="color: #333333;">=</span> strlen(p);
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">></span> dp(m<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #007020;">false</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>m; i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">bool</span> diag <span style="color: #333333;">=</span> dp[<span style="color: #0000dd; font-weight: bold;">0</span>];
dp[<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> i<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">?</span> <span style="color: #007020;">true</span> <span style="color: #333333;">:</span> <span style="color: #007020;">false</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> temp <span style="color: #333333;">=</span> dp[j];
<span style="color: #008800; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span>s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'?'</span>)
dp[j] <span style="color: #333333;">=</span> i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> diag;
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #0066bb; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'*'</span>)
dp[j] <span style="color: #333333;">=</span> dp[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> (i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> (diag <span style="color: #333333;">||</span> dp[j]));
diag <span style="color: #333333;">=</span> temp;
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>思路2:双指针扫描</b></span><div>
<br /></div>
<div>
用DP会TLE,那么一定有其他好的方法。</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com3tag:blogger.com,1999:blog-2084836737143870236.post-23669526111056038042014-11-29T10:50:00.000-08:002014-11-29T13:54:03.194-08:00[LeetCode] Regular Expression Matching<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Implement regular expression matching with support for <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'.'</code> and <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'*'</code>.</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the <span style="box-sizing: border-box; font-weight: 700;">entire</span> input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true</pre>
<br />
<br />
<span style="color: blue;"><b>思路1: DP</b></span><br />
<div>
<br /></div>
<div>
关键在于如何处理这个'*'号。</div>
<div>
<br /></div>
<div>
状态:和Mininum Edit Distance这类题目一样。</div>
<div>
dp[i][j]表示s[0:i-1]是否能和p[0:j-1]匹配。</div>
<div>
<br /></div>
<div>
递推公式:由于只有p中会含有regular expression,所以以p[j-1]来进行分类。</div>
<div>
p[j-1] != '.' && p[j-1] != '*':dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])</div>
<div>
p[j-1] == '.':dp[i][j] = dp[i-1][j-1]</div>
<div>
<br /></div>
<div>
而关键的难点在于 p[j-1] = '*'。由于星号可以匹配0,1,乃至多个p[j-2]。</div>
<div>
1. 匹配0个元素,即消去p[j-2],此时p[0: j-1] = p[0: j-3]</div>
<div>
dp[i][j] = dp[i][j-2]</div>
<div>
<br /></div>
<div>
2. 匹配1个元素,此时p[0: j-1] = p[0: j-2]</div>
<div>
dp[i][j] = dp[i][j-1]</div>
<div>
<br /></div>
<div>
3. 匹配多个元素,此时p[0: j-1] = { p[0: j-2], p[j-2], ... , p[j-2] }</div>
<div>
dp[i][j] = dp[i-1][j] && (p[j-2]=='.' || s[i-2]==p[j-2])</div>
<div>
<br /></div>
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">bool</span> isMatch(<span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>s, <span style="color: #008800; font-weight: bold;">const</span> <span style="color: #333399; font-weight: bold;">char</span> <span style="color: #333333;">*</span>p) {
<span style="color: #333399; font-weight: bold;">int</span> m <span style="color: #333333;">=</span> strlen(s), n <span style="color: #333333;">=</span> strlen(p);
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">>></span> dp(m<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">></span>(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,<span style="color: #007020;">false</span>));
dp[<span style="color: #0000dd; font-weight: bold;">0</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><=</span>m; i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><=</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">!=</span><span style="color: #0044dd;">'.'</span> <span style="color: #333333;">&&</span> p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">!=</span><span style="color: #0044dd;">'*'</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span>p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">&&</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>])
dp[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
}
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'.'</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>])
dp[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
}
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(j<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">1</span>) { <span style="color: #888888;">//'*' cannot be the 1st element</span>
<span style="color: #008800; font-weight: bold;">if</span>(dp[i][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> dp[i][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span>]) <span style="color: #888888;">// match 0 or 1 preceding element</span>
dp[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(i<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> (p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span>]<span style="color: #333333;">==</span>s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">||</span> p[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'.'</span>) <span style="color: #333333;">&&</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j]) <span style="color: #888888;">// match multiple preceding elements</span>
dp[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
}
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[m][n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
<br /></div>
<b><span style="color: blue;">思路2: 双指针扫描</span></b><br />
<div>
<br /></div>
<div>
LeetCode作者给的解法,非常巧妙:<br />
<br />
http://leetcode.com/2011/09/regular-expression-matching.html</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com8tag:blogger.com,1999:blog-2084836737143870236.post-77188513560173641172014-11-27T21:37:00.003-08:002014-11-27T21:37:57.082-08:00[LeetCode] Max Points on a Line<span style="background-color: white; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;">Given </span><i style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;">n</i><span style="background-color: white; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;"> points on a 2D plane, find the maximum number of points that lie on the same straight line.</span><br />
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
解这个平面几何题有3个要点:</div>
<div>
<br /></div>
<div>
1. 如何判断共线?</div>
<div>
两点成一直线,所以两点没有共线不共线之说。对于点p1(x1, y1),p2(x2, y2),p3(x3, y3)来说,共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同,即</div>
<div>
(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)</div>
<div>
所以对共线的n点,其中任意两点连线的斜率相同。</div>
<div>
<br /></div>
<div>
2. 如何判断最多的共线点?</div>
<div>
对于每个点p出发,计算该点到所有其他点qi的斜率,对每个斜率统计有多少个点符合。其中最多的个数加1(出发点本身)即为最多的共线点。</div>
<div>
<br /></div>
<div>
3. 特殊情况</div>
<div>
当x1 = x2,y1!=y2时,为垂直连线。计算斜率时分母为0会出错。</div>
<div>
当x1 = x2,y1 = y2时,两点重合。则(x2, y2)和所有(x1, y1)的连线共线。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> maxPoints(vector<span style="color: #333333;"><</span>Point<span style="color: #333333;">></span> <span style="color: #333333;">&</span>points) {
<span style="color: #333399; font-weight: bold;">int</span> maxPts <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>points.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> nMax <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>, nSame <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>, nInf <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
unordered_map<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">float</span>,<span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> comSlopes;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span>i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><</span>points.size(); j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(points[j].x<span style="color: #333333;">==</span>points[i].x) {
<span style="color: #008800; font-weight: bold;">if</span>(points[j].y<span style="color: #333333;">==</span>points[i].y)
nSame<span style="color: #333333;">++</span>;
<span style="color: #008800; font-weight: bold;">else</span>
nInf<span style="color: #333333;">++</span>;
<span style="color: #008800; font-weight: bold;">continue</span>;
}
<span style="color: #333399; font-weight: bold;">float</span> slope <span style="color: #333333;">=</span> <span style="color: red;"><b>(float)</b></span>(points[j].y<span style="color: #333333;">-</span>points[i].y)<span style="color: #333333;">/</span><span style="color: red;"><b>(float)</b></span>(points[j].x<span style="color: #333333;">-</span>points[i].x);
comSlopes[slope]<span style="color: #333333;">++</span>;
nMax <span style="color: #333333;">=</span> max(nMax, comSlopes[slope]);
}
<span style="color: red;"><b>nMax = max(nMax, nInf)+nSame+1;</b></span>
maxPts <span style="color: #333333;">=</span> max(maxPts,nMax);
}
<span style="color: #008800; font-weight: bold;">return</span> maxPts;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com1tag:blogger.com,1999:blog-2084836737143870236.post-26009567140023645152014-11-27T20:09:00.000-08:002014-11-27T20:48:15.692-08:00[LeetCode] Word Ladder I, II<span style="color: blue;"><b>Word Ladder I</b></span><br />
<br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given two words (<i style="box-sizing: border-box;">start</i> and <i style="box-sizing: border-box;">end</i>), and a dictionary, find the length of shortest transformation sequence from <i style="box-sizing: border-box;">start</i> to <i style="box-sizing: border-box;">end</i>, such that:</div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">Only one letter can be changed at a time</li>
<li style="box-sizing: border-box;">Each intermediate word must exist in the dictionary</li>
</ol>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given:<br />
<i style="box-sizing: border-box;">start</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"hit"</code><br />
<i style="box-sizing: border-box;">end</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"cog"</code><br />
<i style="box-sizing: border-box;">dict</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">["hot","dot","dog","lot","log"]</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
As one shortest transformation is <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"hit" -> "hot" -> "dot" -> "dog" -> "cog"</code>,<br />
return its length <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">5</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">Return 0 if there is no such transformation sequence.</li>
<li style="box-sizing: border-box;">All words have the same length.</li>
<li style="box-sizing: border-box;">All words contain only lowercase alphabetic characters.</li>
</ul>
<br />
<br />
<span style="color: blue;"><b>Word Ladder II</b></span><br />
<br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given two words (<i style="box-sizing: border-box;">start</i> and <i style="box-sizing: border-box;">end</i>), and a dictionary, find all shortest transformation sequence(s) from <i style="box-sizing: border-box;">start</i> to <i style="box-sizing: border-box;">end</i>, such that:</div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">Only one letter can be changed at a time</li>
<li style="box-sizing: border-box;">Each intermediate word must exist in the dictionary</li>
</ol>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given:<br />
<i style="box-sizing: border-box;">start</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"hit"</code><br />
<i style="box-sizing: border-box;">end</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"cog"</code><br />
<i style="box-sizing: border-box;">dict</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">["hot","dot","dog","lot","log"]</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Return</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">All words have the same length.</li>
<li style="box-sizing: border-box;">All words contain only lowercase alphabetic characters.</li>
</ul>
<br />
<br />
<span style="color: blue;"><b>思路:
</b></span><br />
<br />
LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题,但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化?<br />
<br />
1. 将每个单词看成图的一个节点。<br />
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时,则s1与s2之间有连接。<br />
3. 给定s1和s2,问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。<br />
<br />
无论是求最短路径长度还是求所有最短路径,都是用BFS。在BFS中有三个关键步骤需要实现:<br />
<br />
1. 如何找到与当前节点相邻的所有节点。<br />
这里可以有两个策略:<br />
(1) 遍历整个字典,将其中每个单词与当前单词比较,判断是否只差一个字符。复杂度为:n*w,n为字典中的单词数量,w为单词长度。<br />
(2) 遍历当前单词的每个字符x,将其改变成a~z中除x外的任意一个,形成一个新的单词,在字典中判断是否存在。复杂度为:26*w,w为单词长度。<br />
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说,长度大多小于100,而字典中的单词数则往往是成千上万,所以策略2相对较优。<br />
<br />
2. 如何标记一个节点已经被访问过,以避免重复访问。<br />
可以将访问过的单词从字典中删除。<br />
<br />
3. 一旦BFS找到目标单词,如何backtracking找回路径?<br />
<br />
<br />
<br />
<span style="color: blue;"><b>Word Ladder I</b></span><br />
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> ladderLength(string start, string end, unordered_set<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> <span style="color: #333333;">&</span>dict) {
dict.insert(end);
queue<span style="color: #333333;"><</span>pair<span style="color: #333333;"><</span>string,<span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">>></span> q;
q.push(make_pair(start,<span style="color: #0000dd; font-weight: bold;">1</span>));
<span style="color: #008800; font-weight: bold;">while</span>(<span style="color: #333333;">!</span>q.empty()) {
string s <span style="color: #333333;">=</span> q.front().first;
<span style="color: #333399; font-weight: bold;">int</span> len <span style="color: #333333;">=</span> q.front().second;
<span style="color: #008800; font-weight: bold;">if</span>(s<span style="color: #333333;">==</span>end) <span style="color: #008800; font-weight: bold;">return</span> len;
q.pop();
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> neighbors <span style="color: #333333;">=</span> findNeighbors(s, dict);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>neighbors.size(); i<span style="color: #333333;">++</span>)
q.push(make_pair(neighbors[i],len<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>));
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> findNeighbors(string s, unordered_set<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> <span style="color: #333333;">&</span>dict) {
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> ret;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>s.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">char</span> c <span style="color: #333333;">=</span> s[i];
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; j<span style="color: #333333;"><</span><span style="color: #0000dd; font-weight: bold;">26</span>; j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(c<span style="color: #333333;">==</span><span style="color: #0044dd;">'a'</span><span style="color: #333333;">+</span>j) <span style="color: #008800; font-weight: bold;">continue</span>;
s[i] <span style="color: #333333;">=</span> <span style="color: #0044dd;">'a'</span><span style="color: #333333;">+</span>j;
<span style="color: #008800; font-weight: bold;">if</span>(dict.count(s)) {
ret.push_back(s);
dict.erase(s);
}
}
s[i] <span style="color: #333333;">=</span> c;
}
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>Word Ladder II</b></span><br />
<div>
<br /></div>
<div>
<br /></div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com3tag:blogger.com,1999:blog-2084836737143870236.post-1471566595048014912014-11-27T17:04:00.001-08:002014-11-27T17:04:19.607-08:00[LeetCode新题] Intersection of Two Linked Lists<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Write a program to find the node at which the intersection of two singly linked lists begins.</div>
<br style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;" />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example, the following two linked lists:</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
begin to intersect at node c1.</div>
<br style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;" />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Notes:</span></div>
<ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">If the two linked lists have no intersection at all, return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">null</code>.</li>
<li style="box-sizing: border-box;">The linked lists must retain their original structure after the function returns.</li>
<li style="box-sizing: border-box;">You may assume there are no cycles anywhere in the entire linked structure.</li>
<li style="box-sizing: border-box;">Your code should preferably run in O(n) time and use only O(1) memory.</li>
</ul>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
找链表交界,很类似Linked List Cycle II那题,方法也是类似的双指针相遇法。分两步走:</div>
<div>
<br /></div>
<div>
1. 如何判断两链表是否相交?</div>
<div>
两链表相交则他们必然有共同的尾节点。所以遍历两两链表,找到各自的尾节点,如果tailA!=tailB则一定不相交,反之则相交。</div>
<div>
<br /></div>
<div>
2. 如何判断两链表相交的起始节点?</div>
<div>
在第1步判断相交时可以顺带计算两链表的长度lenA和lenB。让长的链表的head先走abs(lenA-lenB)步,然后和短链表的head一起走,直到两者相遇,即为要找的节点。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
ListNode <span style="color: #333333;">*</span>getIntersectionNode(ListNode <span style="color: #333333;">*</span>headA, ListNode <span style="color: #333333;">*</span>headB) {
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>headA <span style="color: #333333;">||</span> <span style="color: #333333;">!</span>headB) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #007020;">NULL</span>;
<span style="color: #333399; font-weight: bold;">int</span> lenA <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>, lenB <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
ListNode <span style="color: #333333;">*</span>tailA <span style="color: #333333;">=</span> headA, <span style="color: #333333;">*</span>tailB <span style="color: #333333;">=</span> headB;
<span style="color: #008800; font-weight: bold;">while</span>(tailA<span style="color: #333333;">-></span>next) {
tailA <span style="color: #333333;">=</span> tailA<span style="color: #333333;">-></span>next;
lenA<span style="color: #333333;">++</span>;
}
<span style="color: #008800; font-weight: bold;">while</span>(tailB<span style="color: #333333;">-></span>next) {
tailB <span style="color: #333333;">=</span> tailB<span style="color: #333333;">-></span>next;
lenB<span style="color: #333333;">++</span>;
}
<span style="color: #008800; font-weight: bold;">if</span>(tailA<span style="color: #333333;">!=</span>tailB) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #007020;">NULL</span>;
<span style="color: #008800; font-weight: bold;">if</span>(lenA<span style="color: #333333;">></span>lenB) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>lenA<span style="color: #333333;">-</span>lenB; i<span style="color: #333333;">++</span>)
headA <span style="color: #333333;">=</span> headA<span style="color: #333333;">-></span>next;
}
<span style="color: #008800; font-weight: bold;">else</span> {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>lenB<span style="color: #333333;">-</span>lenA; i<span style="color: #333333;">++</span>)
headB <span style="color: #333333;">=</span> headB<span style="color: #333333;">-></span>next;
}
<span style="color: #008800; font-weight: bold;">while</span>(headA<span style="color: #333333;">!=</span>headB) {
headA <span style="color: #333333;">=</span> headA<span style="color: #333333;">-></span>next;
headB <span style="color: #333333;">=</span> headB<span style="color: #333333;">-></span>next;
}
<span style="color: #008800; font-weight: bold;">return</span> headA;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-6655586197529768332014-11-27T15:59:00.000-08:002014-11-27T16:43:44.038-08:00[LeetCode] First Missing Positive <div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given an unsorted integer array, find the first missing positive integer.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,2,0]</code> return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">3</code>,<br />
and <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[3,4,-1,1]</code> return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">2</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Your algorithm should run in <i style="box-sizing: border-box;">O</i>(<i style="box-sizing: border-box;">n</i>) time and uses constant space.</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
无序数组的题目如果要O(n)解法往往要用到hash table,但这题要求constant space。所以可以用数组本身作为一个"hash table":A[0] = 1, A[1] = 2, .... A[n-1] = n。目标是尽可能将数字i放到数组第i-1个位置。<br />
<br />
扫描数组中每个数:<br />
1. 如果A[i]<1或者A[i]>n。说明A[i]一定不是first missing positive。跳过<br />
2. 如果A[i] = i+1,说明A[i]已经在正确的位置,跳过<br />
3. 如果A[i]!=i+1,且0<A[i]<=n,应当将A[i]放到A[A[i]-1]的位置,所以可以交换两数。<br />
这里注意,当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过。</div>
<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> firstMissingPositive(<span style="color: #333399; font-weight: bold;">int</span> A[], <span style="color: #333399; font-weight: bold;">int</span> n) {
<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">while</span>(i<span style="color: #333333;"><</span>n) {
<span style="color: #008800; font-weight: bold;">if</span>(A[i]<span style="color: #333333;">!=</span>i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">&&</span> A[i]<span style="color: #333333;">></span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> A[i]<span style="color: #333333;"><=</span>n <span style="color: #333333;">&&</span> <span style="color: red;"><b>A[i]!=A[A[i]-1]</b></span>)
swap(A[i],A[A[i]<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]);
<span style="color: #008800; font-weight: bold;">else</span>
i<span style="color: #333333;">++</span>;
}
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>n; i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(A[i]<span style="color: #333333;">!=</span>i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>) <span style="color: #008800; font-weight: bold;">return</span> i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: red;"><b>n+1</b></span>;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2tag:blogger.com,1999:blog-2084836737143870236.post-44586764175485211912014-11-27T13:33:00.000-08:002014-11-27T13:34:09.698-08:00[LeetCode] Simplify Path<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given an absolute path for a file (Unix-style), simplify it.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
<span style="box-sizing: border-box; font-weight: 700;">path</span> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/home/"</code>, => <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/home"</code><br />
<span style="box-sizing: border-box; font-weight: 700;">path</span> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/a/./b/../../c/"</code>, => <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/c"</code></div>
<div class="showspoilers" style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<a href="https://oj.leetcode.com/problems/simplify-path/#" style="background: 0px 0px; box-sizing: border-box; color: #0088cc; text-decoration: none;">click to show corner cases.</a></div>
<div class="spoilers" style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;">
<span style="box-sizing: border-box; font-weight: 700;">Corner Cases:</span><br />
<div style="box-sizing: border-box; margin-bottom: 10px;">
</div>
<ul style="box-sizing: border-box; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">Did you consider the case where <span style="box-sizing: border-box; font-weight: 700;">path</span> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/../"</code>?<br style="box-sizing: border-box;" />In this case, you should return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/"</code>.</li>
<li style="box-sizing: border-box;">Another corner case is the path might contain multiple slashes <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'/'</code> together, such as <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/home//foo/"</code>.<br style="box-sizing: border-box;" />In this case, you should ignore redundant slashes and return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"/home/foo"</code>.</li>
</ul>
</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
Unix的path规则可以在这里了解:</div>
<div>
http://en.wikipedia.org/wiki/Path_(computing)</div>
<div>
<br /></div>
<div>
归下类的话,有四种字符串:</div>
<div>
1. "/":为目录分隔符,用来分隔两个目录。</div>
<div>
2. ".":当前目录</div>
<div>
3. "..":上层目录</div>
<div>
4. 其他字符串:目录名</div>
<div>
<br /></div>
<div>
简化的核心是要找出所有的目录,并且如果遇到"..",需要删除上一个目录。</div>
<div>
<br /></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
string simplifyPath(string path) {
string ret, curDir;
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> allDir;
<span style="color: red;"><b>path.push_back('/');</b></span>
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>path.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(path[i]<span style="color: #333333;">==</span><span style="color: #0044dd;">'/'</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(curDir.empty()) {
<span style="color: #008800; font-weight: bold;">continue</span>;
}
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(curDir<span style="color: #333333;">==</span><span style="background-color: #fff0f0;">"."</span>) {
curDir.clear();
}
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(curDir<span style="color: #333333;">==</span><span style="background-color: #fff0f0;">".."</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>allDir.empty())
allDir.pop_back();
curDir.clear();
}
<span style="color: #008800; font-weight: bold;">else</span> {
allDir.push_back(curDir);
curDir.clear();
}
}
<span style="color: #008800; font-weight: bold;">else</span> {
curDir.push_back(path[i]);
}
}
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>allDir.size(); i<span style="color: #333333;">++</span>)
ret.append(<span style="background-color: #fff0f0;">"/"</span><span style="color: #333333;">+</span>allDir[i]);
<span style="color: red;"><b>if(ret.empty()) ret = <span style="background-color: #fff0f0;">"/"</span>;</b></span>
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-10739205705603167012014-11-26T23:36:00.001-08:002014-11-26T23:36:12.923-08:00[LeetCode] LRU Cache<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">get</code> and <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">set</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">get(key)</code> - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.<br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">set(key, value)</code> - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
LRU cache数据结构的核心就是当存储空间满了,而有新的item要插入时,要先丢弃最早更新的item。这里的数据结构需要符合以下条件:<br />
<br />
1. 要能快速找到最早更新的item。这里需要将item以更新时间顺序排序。<br />
可选的有:queue,heap,linked list<br />
<br />
2. 要能快速访问指定item,并且访问以后要更新它的时间顺序。<br />
对于更新时间顺序这个操作,queue和heap要做到就很困难了。所以这点最佳的是linked list。但linked list中查找指定item需要遍历,这里可以用一个hash table来记录key与节点之间的对应。并且由于要随时更新节点位置,doubly linked list更为适用。<br />
<br />
根据以上两点,有了以下解法。注意由于代码较长,面试时尽可能将一些基本操作写成函数。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">LRUCache</span>{
<span style="color: #008800; font-weight: bold;">struct</span> Node {
<span style="color: #333399; font-weight: bold;">int</span> val;
<span style="color: #333399; font-weight: bold;">int</span> key;
Node <span style="color: #333333;">*</span>next;
Node <span style="color: #333333;">*</span>prev;
Node(<span style="color: #333399; font-weight: bold;">int</span> k, <span style="color: #333399; font-weight: bold;">int</span> v)<span style="color: #333333;">:</span>key(k),val(v) {}
};
<span style="color: #333399; font-weight: bold;">int</span> maxSize;
Node<span style="color: #333333;">*</span> head;
Node<span style="color: #333333;">*</span> tail;
unordered_map<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span>,Node<span style="color: #333333;">*></span> keyToNode;
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">insertToEnd</span>(<span style="color: #333399; font-weight: bold;">int</span> key, <span style="color: #333399; font-weight: bold;">int</span> value) {
<span style="color: #008800; font-weight: bold;">if</span>(isFull() <span style="color: #333333;">||</span> keyToNode.count(key)<span style="color: #333333;">!=</span><span style="color: #0000dd; font-weight: bold;">0</span>) <span style="color: #008800; font-weight: bold;">return</span>;
Node <span style="color: #333333;">*</span>nd <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> Node(key, value);
keyToNode[key] <span style="color: #333333;">=</span> nd;
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>head) {
head <span style="color: #333333;">=</span> tail <span style="color: #333333;">=</span> nd;
}
<span style="color: #008800; font-weight: bold;">else</span> {
tail<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> nd;
nd<span style="color: #333333;">-></span>prev <span style="color: #333333;">=</span> tail;
tail <span style="color: #333333;">=</span> tail<span style="color: #333333;">-></span>next;
}
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">removeHead</span>() {
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>head) <span style="color: #008800; font-weight: bold;">return</span>;
keyToNode.erase(head<span style="color: #333333;">-></span>key);
Node <span style="color: #333333;">*</span>temp <span style="color: #333333;">=</span> head;
<span style="color: #008800; font-weight: bold;">if</span>(head<span style="color: #333333;">==</span>tail) <span style="color: #888888;">// only one node remain</span>
head <span style="color: #333333;">=</span> tail <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
<span style="color: #008800; font-weight: bold;">else</span> {
head <span style="color: #333333;">=</span> head<span style="color: #333333;">-></span>next;
head<span style="color: #333333;">-></span>prev <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
}
<span style="color: #008800; font-weight: bold;">delete</span> temp;
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">moveToEnd</span>(<span style="color: #333399; font-weight: bold;">int</span> key) {
<span style="color: #888888;">// key not exist, or already at the end</span>
<span style="color: #008800; font-weight: bold;">if</span>(keyToNode.count(key)<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">||</span> keyToNode[key]<span style="color: #333333;">==</span>tail) <span style="color: #008800; font-weight: bold;">return</span>;
Node <span style="color: #333333;">*</span>nd <span style="color: #333333;">=</span> keyToNode[key];
<span style="color: #008800; font-weight: bold;">if</span>(nd<span style="color: #333333;">==</span>head) {
head <span style="color: #333333;">=</span> head<span style="color: #333333;">-></span>next;
head<span style="color: #333333;">-></span>prev <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
}
<span style="color: #008800; font-weight: bold;">else</span> { <span style="color: #888888;">// not head, not tail</span>
nd<span style="color: #333333;">-></span>prev<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> nd<span style="color: #333333;">-></span>next;
nd<span style="color: #333333;">-></span>next<span style="color: #333333;">-></span>prev <span style="color: #333333;">=</span> nd<span style="color: #333333;">-></span>prev;
}
tail<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> nd;
nd<span style="color: #333333;">-></span>prev <span style="color: #333333;">=</span> tail;
nd<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
tail <span style="color: #333333;">=</span> tail<span style="color: #333333;">-></span>next;
}
<span style="color: #997700; font-weight: bold;">public:</span>
LRUCache(<span style="color: #333399; font-weight: bold;">int</span> capacity) {
maxSize <span style="color: #333333;">=</span> capacity;
head <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
tail <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
keyToNode.clear();
}
<span style="color: #333399; font-weight: bold;">int</span> get(<span style="color: #333399; font-weight: bold;">int</span> key) {
<span style="color: #008800; font-weight: bold;">if</span>(keyToNode.count(key)<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">0</span>) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
moveToEnd(key);
<span style="color: #008800; font-weight: bold;">return</span> keyToNode[key]<span style="color: #333333;">-></span>val;
}
<span style="color: #333399; font-weight: bold;">void</span> set(<span style="color: #333399; font-weight: bold;">int</span> key, <span style="color: #333399; font-weight: bold;">int</span> value) {
<span style="color: #888888;">// key already exists</span>
<span style="color: #008800; font-weight: bold;">if</span>(get(key)<span style="color: #333333;">!=-</span><span style="color: #0000dd; font-weight: bold;">1</span>) {
keyToNode[key]<span style="color: #333333;">-></span>val <span style="color: #333333;">=</span> value;
<span style="color: #008800; font-weight: bold;">return</span>;
}
<span style="color: #888888;">// key not exist, insert new node</span>
<span style="color: #008800; font-weight: bold;">if</span>(isFull()) removeHead();
insertToEnd(key, value);
}
<span style="color: #333399; font-weight: bold;">bool</span> isFull() {
<span style="color: #008800; font-weight: bold;">return</span> keyToNode.size()<span style="color: #333333;">>=</span>maxSize;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-9402924938746122032014-11-26T20:28:00.000-08:002014-11-26T20:33:00.301-08:00[LeetCode] Merge Intervals<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a collection of intervals, merge all overlapping intervals.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,3],[2,6],[8,10],[15,18]</code>,<br />
return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,6],[8,10],[15,18]</code>.</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
从Insert Interval那题的解法,我们知道了如何判断两个interval是否重合,如果不重合,如何判断先后顺序。那么这题就很简单了,首先按照start的大小来给所有interval排序,start小的在前。然后扫描逐个插入结果。如果发现当前interval a和结果中最后一个插入的interval b不重合,则插入a到b的后面;反之如果重合,则将a合并到b中。注意要给object排序需要定义一个compare structure作为sort函数的额外参数。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: red;"> <span style="font-weight: bold;">struct</span> compInterval {
<span style="font-weight: bold;">bool</span> <span style="font-weight: bold;">operator</span>()(<span style="font-weight: bold;">const</span> Interval &a, <span style="font-weight: bold;">const</span> Interval &b) <span style="font-weight: bold;">const</span> {
<span style="font-weight: bold;">return</span> a.start<b.start;
}
};</span>
vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> merge(vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> <span style="color: #333333;">&</span>intervals) {
sort(intervals.begin(),intervals.end(),compInterval());
vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> ret;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>intervals.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(ret.empty() <span style="color: #333333;">||</span> ret.back().end <span style="color: #333333;"><</span> intervals[i].start) <span style="color: #888888;">// no overlap</span>
ret.push_back(intervals[i]);
<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #888888;">// overlap</span>
ret.back().end <span style="color: #333333;">=</span> max(ret.back().end, intervals[i].end);
}
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com0tag:blogger.com,1999:blog-2084836737143870236.post-54919694145563847312014-11-26T19:49:00.004-08:002014-11-26T19:50:15.654-08:00[LeetCode] Insert Interval<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a set of <i style="box-sizing: border-box;">non-overlapping</i> intervals, insert a new interval into the intervals (merge if necessary).</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
You may assume that the intervals were initially sorted according to their start times.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span><br />
Given intervals <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,3],[6,9]</code>, insert and merge <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[2,5]</code> in as <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,5],[6,9]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span><br />
Given <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,2],[3,5],[6,7],[8,10],[12,16]</code>, insert and merge <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[4,9]</code> in as <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,2],[3,10],[12,16]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
This is because the new interval <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[4,9]</code> overlaps with <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[3,5],[6,7],[8,10]</code>.</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
题目涉及两个问题:</div>
<div>
1. 如何判断两个interval有重合。</div>
<div>
2. 如果重合,如何合并。</div>
<div>
3. 如何判断[s1, e1]是否在[s2, e2]前面</div>
<div>
<br /></div>
<div>
A1. 两个interval有重合有很多种可能性,但判断它们不重合则比较简单直观。无非两种情况:</div>
<div>
<br /></div>
<div>
(1) [s1, e1] [s2, e2]:即s2>e1 </div>
<div>
(2) [s2, e2] [s1, e1]:即s1>e2</div>
<div>
<br /></div>
<div>
<span style="color: red;"><b>不重合的条件为:s2>e1 || s1>e2,反之则重合。</b></span></div>
<div>
<br /></div>
<div>
A2. <span style="color: red;"><b>对于两个有重合的interval: [s1, e1],[s2, e2]。合并后变为[min(s1,s2), max(e1,e2)]。</b></span></div>
<div>
<br /></div>
<div>
A3. <span style="color: red;"><b>[s1, e1]在[s2, e2]前面的条件:e1<s2</b></span></div>
<div>
<br /></div>
<div>
所以插入interval a的算法为:扫描队列中每个interval I[i]:<br />
如果a已经被插入了,则只要插入I(i)就行。<br />
如果a在I(i)前,则先插入a再插入I(i)到结果。</div>
<div>
如果a和I(i)有重合,则将I(i)合并入a,但并不插入结果。</div>
<div>
如果a在I(i)后,则插入I(i)到结果。</div>
<div>
<br /></div>
<div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> insert(vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> <span style="color: #333333;">&</span>intervals, Interval newInterval) {
vector<span style="color: #333333;"><</span>Interval<span style="color: #333333;">></span> ret;
<span style="color: #333399; font-weight: bold;">bool</span> isInsert <span style="color: #333333;">=</span> <span style="color: #007020;">false</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>intervals.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #888888;">// already insert newInterval</span>
<span style="color: #008800; font-weight: bold;">if</span>(isInsert) {
ret.push_back(intervals[i]);
<span style="color: #008800; font-weight: bold;">continue</span>;
}
<span style="color: #888888;">// insert newInterval before current interval</span>
<span style="color: #008800; font-weight: bold;">if</span>(newInterval.end <span style="color: #333333;"><</span> intervals[i].start) {
ret.push_back(newInterval);
ret.push_back(intervals[i]);
isInsert <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
<span style="color: #008800; font-weight: bold;">continue</span>;
}
<span style="color: #888888;">// combine newInterval with current interval</span>
<span style="color: #008800; font-weight: bold;">if</span>(newInterval.start<span style="color: #333333;"><=</span>intervals[i].end <span style="color: #333333;">&&</span> intervals[i].start<span style="color: #333333;"><=</span>newInterval.end) {
newInterval.start <span style="color: #333333;">=</span> min(newInterval.start, intervals[i].start);
newInterval.end <span style="color: #333333;">=</span> max(newInterval.end, intervals[i].end);
<span style="color: #008800; font-weight: bold;">continue</span>;
}
<span style="color: #888888;">// newInterval after current interval</span>
ret.push_back(intervals[i]);
}
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>isInsert) ret.push_back(newInterval);
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2tag:blogger.com,1999:blog-2084836737143870236.post-75515582255677248312014-11-26T18:50:00.000-08:002014-11-27T10:35:41.453-08:00[LeetCode] Longest Valid Parentheses <div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a string containing just the characters <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">'('</code> and <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">')'</code>, find the length of the longest valid (well-formed) parentheses substring.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"(()"</code>, the longest valid parentheses substring is <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"()"</code>, which has length = 2.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Another example is <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">")()())"</code>, where the longest valid parentheses substring is <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"()()"</code>, which has length = 4.</div>
<br />
<span style="color: blue;"><b>思路1:DP</b></span><br />
<div>
<br /></div>
<div>
求极值问题一般想到DP或Greedy,显然Greedy在这里不太适用,只有用DP了。<br />
<div>
<br />
1. 状态:<br />
<span style="color: red;"><b>DP[i]:以s[i-1]为结尾的longest valid parentheses substring的长度。</b></span><br />
<br />
2. 通项公式:<br />
s[i] = '(':<br />
DP[i] = 0<br />
<br />
s[i] = ')':找i前一个字符的最长括号串DP[i]的前一个字符<span style="color: red;"><b>j = i-2-DP[i-1]</b></span><br />
<span style="color: red;"><b>DP[i] = DP[i-1] + 2 + DP[j],如果j >=0,且s[j] = '('</b></span><br />
<span style="color: red;"><b>DP[i] = 0,如果j<0,或s[j] = ')'</b></span><br />
<br />
......... ( x x x x )<br />
j i-2 i-1<br />
<br />
证明:不存在j' < j,且s[j' : i]为valid parentheses substring。<br />
假如存在这样的j',则s[j'+1 : i-1]也valid。那么对于i-1来说:<br />
( x x x x x<br />
j' j'+1 i-1<br />
这种情况下,i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。<br />
<br />
3. 计算方向<br />
显然<span style="color: red;"><b>自左向右,且DP[0] = 0</b></span><br />
<br /></div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> longestValidParentheses(string s) {
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> s.size(), maxLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> dp(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,<span style="color: #0000dd; font-weight: bold;">0</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>n; i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> j <span style="color: #333333;">=</span> i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span><span style="color: #333333;">-</span>dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">if</span>(s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0044dd;">'('</span> <span style="color: #333333;">||</span> j<span style="color: #333333;"><</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">||</span> s[j]<span style="color: #333333;">==</span><span style="color: #0044dd;">')'</span>)
dp[i] <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">else</span> {
dp[i] <span style="color: #333333;">=</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">2</span><span style="color: #333333;">+</span>dp[j];
maxLen <span style="color: #333333;">=</span> max(maxLen, dp[i]);
}
}
<span style="color: #008800; font-weight: bold;">return</span> maxLen;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<br />
<br />
<div>
<span style="color: blue;"><b>思路2:stack</b></span></div>
<div>
<br /></div>
<div>
括号题自然又想到了stack。仔细想下,这题目其实是Valid Parentheses的升级版。一个valid parentheses substring必然以'('开头以')'结尾,并且中间一定也是一个valid parentheses substring。这也意味着依照Valid Parentheses解法那样,用stack来存储没有配对的'('和')',并用相应的')'来消去stack top的'(',最长substring的首尾必然会在这个过程中相消。<br />
<br />
1. 由于我们需要知道它们之间的长度,所以stack里可以存储各个'('的坐标。<br />
2. 为了能正确计算类似“ ) ( ) ( ) ”这种valid substring连接而组成的valid substring。我们必须也插入')'进stack,作为边界来计算长度。<br />
3. 为了能在stack中区分左右括号,每个插入item定义为pair<int,int>。first为坐标,second表示左还是右括号。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> longestValidParentheses(string s) {
stack<span style="color: #333333;"><</span>pair<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span>,<span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">>></span> stk; <span style="color: #888888;">// first: index, second: 0:'(', 1:')'</span>
<span style="color: #333399; font-weight: bold;">int</span> maxLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>, curLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>s.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(s[i]<span style="color: #333333;">==</span><span style="color: #0044dd;">'('</span>) <span style="color: #888888;">// left parenthesis</span>
stk.push(make_pair(i,<span style="color: #0000dd; font-weight: bold;">0</span>));
<span style="color: #008800; font-weight: bold;">else</span> { <span style="color: #888888;">// right parenthesis</span>
<span style="color: #008800; font-weight: bold;">if</span>(stk.empty() <span style="color: #333333;">||</span> stk.top().second<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">1</span>)
stk.push(make_pair(i,<span style="color: #0000dd; font-weight: bold;">1</span>));
<span style="color: #008800; font-weight: bold;">else</span> {
stk.pop();
<span style="color: #008800; font-weight: bold;">if</span>(stk.empty())
curLen <span style="color: #333333;">=</span> i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">else</span>
curLen <span style="color: #333333;">=</span> i<span style="color: #333333;">-</span>stk.top().first;
maxLen <span style="color: #333333;">=</span> max(maxLen, curLen);
}
}
}
<span style="color: #008800; font-weight: bold;">return</span> maxLen;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com1tag:blogger.com,1999:blog-2084836737143870236.post-51998881660870868062014-11-26T13:19:00.000-08:002014-11-26T14:45:34.524-08:00[LeetCode] Largest Rectangle in Histogram<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <i style="box-sizing: border-box;">n</i> non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<img src="http://www.leetcode.com/wp-content/uploads/2012/04/histogram.png" style="border: 0px; box-sizing: border-box; vertical-align: middle;" /></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 11px; line-height: 30px; margin-bottom: 10px;">
Above is a histogram where width of each bar is 1, given height = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 10px; padding: 2px 4px;">[2,1,5,6,2,3]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<img src="http://www.leetcode.com/wp-content/uploads/2012/04/histogram_area.png" style="border: 0px; box-sizing: border-box; vertical-align: middle;" /></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 11px; line-height: 30px; margin-bottom: 10px;">
The largest rectangle is shown in the shaded area, which has area = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 10px; padding: 2px 4px;">10</code> unit.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given height = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[2,1,5,6,2,3]</code>,<br />
return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">10</code>.</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路1:Brute Force</b></span><br />
<div>
<div>
<br /></div>
<div>
对每个bar i,求它能构成的最大面积。用左右指针向两边扫,直到遇到比bar i矮的或遇到边界则停止,然后根据左右指针距离得到宽度和面积。但是这个解法过不了大集合,因为最坏情况:当整个histogram是递增或递减时,算法复杂度是O(n^2)。</div>
<div>
<br /></div>
<div>
<br /></div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> largestRectangleArea(vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> <span style="color: #333333;">&</span>height) {
<span style="color: #333399; font-weight: bold;">int</span> maxArea <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>height.size(); i<span style="color: #333333;">++</span>)
maxArea <span style="color: #333333;">=</span> max(maxArea, calRecArea(height,i));
<span style="color: #008800; font-weight: bold;">return</span> maxArea;
}
<span style="color: #333399; font-weight: bold;">int</span> calRecArea(vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> <span style="color: #333333;">&</span>height, <span style="color: #333399; font-weight: bold;">int</span> index) {
<span style="color: #333399; font-weight: bold;">int</span> left <span style="color: #333333;">=</span> index<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>, right <span style="color: #333333;">=</span> index<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">while</span>(left<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> height[left]<span style="color: #333333;">>=</span>height[index])
left<span style="color: #333333;">--</span>;
<span style="color: #008800; font-weight: bold;">while</span>(right<span style="color: #333333;"><</span>height.size() <span style="color: #333333;">&&</span> height[right]<span style="color: #333333;">>=</span>height[index])
right<span style="color: #333333;">++</span>;
<span style="color: #008800; font-weight: bold;">return</span> (right<span style="color: #333333;">-</span>left<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>)<span style="color: #333333;">*</span>height[index];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>思路2:Stack</b></span><br />
<div>
<br /></div>
<div>
仔细考察Brute Force算法,发现问题在于指针重复扫描。以递增序列为例:<br />
<br />
0 1 2 3 4 5 6<br />
<br />
在计算s[0]的时候扫描了右边6个数,计算s[1]时继续扫描右边5个数,依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时,bar i~j的面积一定都能扩展到j。而一旦在j+1递减了,那么表示bar i~j中的部分bar k无法继续扩展,条件是h[k]>h[j+1]。<br />
<br />
1. 利用这个性质,可以将递增序列cache在一个stack中,一旦遇到递减,则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k,并计算面积。<br />
<br />
2. 由于面积的计算需要同时知道高度和宽度,所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度,而反之则不行。<br />
<br />
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> largestRectangleArea(vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> <span style="color: #333333;">&</span>height) {
<span style="color: #008800; font-weight: bold;">if</span>(height.empty()) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
height.push_back(<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
height.insert(height.begin(),<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
stack<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> s;
<span style="color: #333399; font-weight: bold;">int</span> maxArea <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>height.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">while</span>(<span style="color: #333333;">!</span>s.empty() <span style="color: #333333;">&&</span> height[i]<span style="color: #333333;"><=</span>height[s.top()]) {
<span style="color: #333399; font-weight: bold;">int</span> h <span style="color: #333333;">=</span> height[s.top()];
s.pop();
<span style="color: #008800; font-weight: bold;">if</span>(height[i]<span style="color: #333333;"><</span>h) maxArea <span style="color: #333333;">=</span> max(maxArea, (i<span style="color: #333333;">-</span>s.top()<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>)<span style="color: #333333;">*</span>h);
}
s.push(i);
}
<span style="color: #888888;">// reset height</span>
height.erase(height.begin());
height.pop_back();
<span style="color: #008800; font-weight: bold;">return</span> maxArea;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com1tag:blogger.com,1999:blog-2084836737143870236.post-26562028846830216512014-11-26T11:53:00.001-08:002014-11-26T12:29:16.853-08:00[LeetCode] Unique Binary Search Trees I, II<span style="color: blue;"><b>Unique Binary Search Trees I</b></span><br />
<br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <i style="box-sizing: border-box;">n</i>, how many structurally unique <span style="box-sizing: border-box; font-weight: 700;">BST's</span> (binary search trees) that store values 1...<i style="box-sizing: border-box;">n</i>?</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given <i style="box-sizing: border-box;">n</i> = 3, there are a total of 5 unique BST's.</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3</pre>
<br />
<div>
<br /></div>
<b><span style="color: blue;">Unique Binary Search Trees II</span></b><br />
<div>
<br /></div>
<div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <i style="box-sizing: border-box;">n</i>, generate all structurally unique <span style="box-sizing: border-box; font-weight: 700;">BST's</span> (binary search trees) that store values 1...<i style="box-sizing: border-box;">n</i>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given <i style="box-sizing: border-box;">n</i> = 3, your program should return all 5 unique BST's shown below.</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div class="showspoilers" style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
confused what <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"{1,#,2,3}"</code> means? <a href="https://oj.leetcode.com/problems/unique-binary-search-trees-ii/#" style="background: 0px 0px; box-sizing: border-box; color: #0088cc; text-decoration: none;">> read more on how binary tree is serialized on OJ.</a></div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>思路: </b></span><b style="color: blue;">Unique Binary Search Trees I</b><br />
<div>
<br /></div>
<div>
首先注意这里是BST而不是普通的Binary Tree,所以数字会对插入的位置有影响。这类找combination/permutation的题都需要找找规律。</div>
<div>
<br /></div>
<div>
n = 0</div>
<div>
<br /></div>
<div>
n = 1</div>
<div>
1</div>
<div>
<br /></div>
<div>
n = 2</div>
<div>
1 2</div>
<div>
\ /</div>
<div>
2 1</div>
<div>
<br /></div>
<div>
n = 3</div>
<div>
<div>
1 3 3 2 1</div>
<div>
\ / / / \ \</div>
<div>
3 2 1 1 3 2</div>
<div>
/ / \ \</div>
<div>
2 1 2 3</div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
定义f(n)为unique BST的数量,以n = 3为例:</div>
<div>
<br /></div>
<div>
构造的BST的根节点可以取{1, 2, 3}中的任一数字。</div>
<div>
<br /></div>
<div>
如以1为节点,则left subtree只能有0个节点,而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为:f(0) * f(2) = 2</div>
<div>
<br /></div>
<div>
以2为节点,则left subtree只能为1,right subtree只能为2:f(1) * f(1) = 1</div>
<div>
<br /></div>
<div>
以3为节点,则left subtree有1, 2两个节点,right subtree有0个节点:f(2)*f(0) = 2</div>
<div>
<br /></div>
<div>
总结规律:</div>
<div>
<span style="color: red;"><b>f(0) = 1</b></span></div>
<div>
<span style="color: red;"><b>f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)</b></span></div>
<div>
<br /></div>
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> numTrees(<span style="color: #333399; font-weight: bold;">int</span> n) {
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> numBST(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,<span style="color: #0000dd; font-weight: bold;">0</span>);
numBST[<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>n; i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; j<span style="color: #333333;"><</span>i; j<span style="color: #333333;">++</span>) {
numBST[i] <span style="color: #333333;">+=</span> numBST[j]<span style="color: #333333;">*</span>numBST[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">-</span>j];
}
}
<span style="color: #008800; font-weight: bold;">return</span> numBST[n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
<br /></div>
<b><span style="color: blue;">思路: Unique Binary Search Trees II</span></b><br />
<div>
<br /></div>
<div>
要求生成所有的unique BST,类似combination/permutation的题目,可以递归构造。</div>
<div>
<br /></div>
<div>
<span style="color: red;"><b>1. 根节点可以任取min ~ max (例如min = 1, max = n),假如取定为i。</b></span></div>
<div>
<span style="color: red;"><b>2. 则left subtree由min ~ i-1组成,假设可以有L种可能。right subtree由i+1 ~ max组成,假设有R种可能。生成所有可能的left/right subtree。</b></span></div>
<div>
<span style="color: red;"><b>3 对于每个生成的left subtree/right subtree组合<T_left(p), T_right(q)>,p = 1...L,q = 1...R,添加上根节点i而组成一颗新树。</b></span></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
vector<span style="color: #333333;"><</span>TreeNode <span style="color: #333333;">*></span> generateTrees(<span style="color: #333399; font-weight: bold;">int</span> n) {
<span style="color: #008800; font-weight: bold;">return</span> genBST(<span style="color: #0000dd; font-weight: bold;">1</span>, n);
}
vector<span style="color: #333333;"><</span>TreeNode <span style="color: #333333;">*></span> genBST(<span style="color: #333399; font-weight: bold;">int</span> min, <span style="color: #333399; font-weight: bold;">int</span> max) {
vector<span style="color: #333333;"><</span>TreeNode <span style="color: #333333;">*></span> ret;
<span style="color: #008800; font-weight: bold;">if</span>(min<span style="color: #333333;">></span>max) {
ret.push_back(<span style="color: #007020;">NULL</span>);
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>min; i<span style="color: #333333;"><=</span>max; i<span style="color: #333333;">++</span>) {
vector<span style="color: #333333;"><</span>TreeNode<span style="color: #333333;">*></span> leftSubTree <span style="color: #333333;">=</span> genBST(min,i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
vector<span style="color: #333333;"><</span>TreeNode<span style="color: #333333;">*></span> rightSubTree <span style="color: #333333;">=</span> genBST(i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,max);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; j<span style="color: #333333;"><</span>leftSubTree.size(); j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> k<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; k<span style="color: #333333;"><</span>rightSubTree.size(); k<span style="color: #333333;">++</span>) {
TreeNode <span style="color: #333333;">*</span>root <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> TreeNode(i);
root<span style="color: #333333;">-></span>left <span style="color: #333333;">=</span> leftSubTree[j];
root<span style="color: #333333;">-></span>right <span style="color: #333333;">=</span> rightSubTree[k];
ret.push_back(root);
}
}
}
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com1tag:blogger.com,1999:blog-2084836737143870236.post-88816152684011507682014-11-26T00:34:00.001-08:002014-11-26T09:48:39.886-08:00[LeetCode] Distinct Subsequences<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a string <span style="box-sizing: border-box; font-weight: 700;">S</span> and a string <span style="box-sizing: border-box; font-weight: 700;">T</span>, count the number of distinct subsequences of <span style="box-sizing: border-box; font-weight: 700;">T</span> in <span style="box-sizing: border-box; font-weight: 700;">S</span>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"ACE"</code> is a subsequence of <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"ABCDE"</code> while <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"AEC"</code> is not).</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Here is an example:<br />
<span style="box-sizing: border-box; font-weight: 700;">S</span> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"rabbbit"</code>, <span style="box-sizing: border-box; font-weight: 700;">T</span> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"rabbit"</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">3</code>.</div>
<br />
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
一看要求解的个数,然后又是string匹配,而且形式上和Minimum Edit Distance那题很像,基本就是DP题跑不了了。DP题惯例的三步走:定义状态,推导递推公式,确定状态计算方向和起始状态。</div>
<div>
<br /></div>
<div>
<span style="color: blue;"><b>1. 状态</b></span><b><span style="color: blue;">:</span></b>i, j分别表示T中长度为i的prefix:T[0:i-1],和S中长度为j的prefix:S[0:j-1]。</div>
<div>
<span style="color: red;"><b>DP[i][j]:S[0:j-1]中存在T[0:i-1]作为distinct subsequence的个数</b></span>。显然如果j<i,DP[i][j] = 0。</div>
<div>
<br /></div>
<div>
<span style="color: blue;"><b>2. 递推公式:</b></span></div>
<div>
(a) T[i]!=s[j]:<br />
<br /></div>
<div>
T = r a b</div>
<div>
<div>
S = <span style="color: red;">r</span> c <span style="color: red;">a</span> c <span style="color: red;">b</span> <span style="color: blue;">c</span></div>
</div>
<div>
<br /></div>
<div>
DP[i+1][j+1] = DP[i+1][j]</div>
<div>
<br /></div>
<div>
(b) T[i] = s[j]: </div>
<div>
<br /></div>
<div>
T = r a b b</div>
<div>
S = <span style="color: red;">r a b b</span> b - DP[i+1][j] = 1</div>
<div>
S = <span style="color: red;">r a b</span> b <span style="color: blue;">b</span> - DP[i][j] = 2</div>
<div>
S = <span style="color: red;">r a </span>b <span style="color: red;">b</span> <span style="color: blue;">b</span><span style="color: red;"> </span>/</div>
<div>
<br /></div>
<div>
DP[i+1][j+1] = DP[i][j] + DP[i+1][j]</div>
<div>
<br />
<span style="color: red;"><b>公式总结:</b></span><br />
<b style="color: red;">S[j-1]!= T[i-1]:DP[i][j] = DP[i][j-1]</b><br />
<span style="color: red;"><b>S[j-1]==T[i-1]:DP[i][j] = DP[i-1][j-1] + DP[i][j-1]</b></span><br />
<br />
<br /></div>
<div>
<span style="color: blue;"><b>3. 计算方向和起始状态:</b></span></div>
<div>
DP[i][j]</div>
<div>
DP[i+1][j] DP[i+1][j+1]</div>
<div>
<br /></div>
<div>
所以<span style="color: red;"><b>从上向下,从左到右</b></span>的顺序可以计算。</div>
<div>
<br /></div>
<div>
根据计算顺序,需要先设置第0行、0列的值。<br />
<span style="color: red;"><b>第0列:DP[i][0] = 0</b></span>,i>0。因为T的长度大于S的长度,不可能成为S的subsequence。<br />
<span style="color: red;"><b>第0行:DP[0][j] = 1</b></span>,j>=0。这是为了保证第1行的计算正确:<br />
<br />
T = r<br />
S = r a r b r c<br />
<br />
<span style="color: blue;">r a r b r c </span><br />
1 1 1 1 1 1 1<br />
<span style="color: blue;">r</span> 0 <span style="color: red;">1</span> 1 <span style="color: red;">2</span> 2 <span style="color: red;">3</span> 3</div>
<div>
<br />
<br />
<b><span style="color: blue;">4. 计算优化:用滚动数组减少内存消耗。</span></b></div>
<div>
<br />
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> numDistinct(string S, string T) {
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> S.size(), m <span style="color: #333333;">=</span> T.size();
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> dp(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">1</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>m; i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> upLeft <span style="color: #333333;">=</span> dp[<span style="color: #0000dd; font-weight: bold;">0</span>];
dp[<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><=</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> temp <span style="color: #333333;">=</span> dp[j];
dp[j] <span style="color: #333333;">=</span> dp[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">if</span>(S[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span>T[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]) dp[j] <span style="color: #333333;">+=</span> upLeft;
upLeft <span style="color: #333333;">=</span> temp;
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2tag:blogger.com,1999:blog-2084836737143870236.post-82506510670286733922014-11-25T22:38:00.002-08:002014-11-25T22:38:52.824-08:00[LeetCode] Longest Consecutive Sequence<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[100, 4, 200, 1, 3, 2]</code>,<br />
The longest consecutive elements sequence is <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1, 2, 3, 4]</code>. Return its length: <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">4</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Your algorithm should run in O(<i style="box-sizing: border-box;">n</i>) complexity.</div>
<br />
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
既然要O(n)算法,排序显然不行,所以自然想到用hash table。将序列中的所有数存到一个unordered_set中。对于序列里任意一个数A[i],我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在,继续找A[i]+2和A[i]-2,以此类推,直到将整个连续序列找到。为了避免在扫描到A[i]-1时再次重复搜索该序列,在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时,所有连续序列搜索结束。</div>
<div>
<br /></div>
<div>
复杂度:由于每个数字只被插入set一次,并删除一次,所以算法是O(n)的。</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> longestConsecutive(vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> <span style="color: #333333;">&</span>num) {
<span style="color: #008800; font-weight: bold;">if</span>(num.empty()) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
unordered_set<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> ht;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>num.size(); i<span style="color: #333333;">++</span>)
ht.insert(num[i]);
<span style="color: #333399; font-weight: bold;">int</span> maxLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>num.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(ht.empty()) <span style="color: #008800; font-weight: bold;">break</span>;
<span style="color: #333399; font-weight: bold;">int</span> curLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">int</span> curNum <span style="color: #333333;">=</span> num[i];
<span style="color: #008800; font-weight: bold;">while</span>(ht.count(curNum)) {
ht.erase(curNum);
curLen<span style="color: #333333;">++</span>;
curNum<span style="color: #333333;">++</span>;
}
curNum <span style="color: #333333;">=</span> num[i]<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">while</span>(ht.count(curNum)) {
ht.erase(curNum);
curLen<span style="color: #333333;">++</span>;
curNum<span style="color: #333333;">--</span>;
}
maxLen <span style="color: #333333;">=</span> max(maxLen, curLen);
}
<span style="color: #008800; font-weight: bold;">return</span> maxLen;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com5tag:blogger.com,1999:blog-2084836737143870236.post-30268624170052126852014-11-25T21:01:00.001-08:002014-11-25T21:01:57.955-08:00[LeetCode] Permutation Sequence<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
The set <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[1,2,3,…,<i style="box-sizing: border-box;">n</i>]</code> contains a total of <i style="box-sizing: border-box;">n</i>! unique permutations.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
By listing and labeling all of the permutations in order,<br />
We get the following sequence (ie, for <i style="box-sizing: border-box;">n</i> = 3):</div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"123"</code></li>
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"132"</code></li>
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"213"</code></li>
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"231"</code></li>
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"312"</code></li>
<li style="box-sizing: border-box;"><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"321"</code></li>
</ol>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <i style="box-sizing: border-box;">n</i> and <i style="box-sizing: border-box;">k</i>, return the <i style="box-sizing: border-box;">k</i><span style="box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; top: -0.5em; vertical-align: baseline;">th</span> permutation sequence.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span> Given <i style="box-sizing: border-box;">n</i> will be between 1 and 9 inclusive.</div>
<div>
<br /></div>
思路:<br />
<div>
<br /></div>
<div>
同样先通过举例来获得更好的理解。以n = 4,k = 9为例:</div>
<div>
<div>
<br /></div>
<div>
<span style="color: red;">1</span><span style="color: #38761d;">2</span>34</div>
<div>
<span style="color: red;">1</span><span style="color: #38761d;">2</span>43</div>
<div>
<span style="color: red;">1</span><span style="color: #e69138;">3</span>24</div>
<div>
<span style="color: red;">1</span><span style="color: #e69138;">3</span>42</div>
<div>
<span style="color: red;">1</span><span style="color: #38761d;">4</span>23</div>
<div>
<span style="color: red;">1</span><span style="color: #38761d;">4</span>32</div>
<div>
<span style="color: blue;">2</span>134</div>
<div>
<span style="color: blue;">2</span>143</div>
<div>
<span style="color: blue;">2</span>314 <= k = 9</div>
<div>
<span style="color: blue;">2</span>341</div>
<div>
<span style="color: blue;">2</span>413</div>
<div>
<span style="color: blue;">2</span>431</div>
<div>
<span style="color: red;">3</span>124</div>
<div>
<span style="color: red;">3</span>142</div>
<div>
<span style="color: red;">3</span>214</div>
<div>
<span style="color: red;">3</span>241</div>
<div>
<span style="color: red;">3</span>412</div>
<div>
<span style="color: red;">3</span>421</div>
<div>
<span style="color: blue;">4</span>123</div>
<div>
<span style="color: blue;">4</span>132</div>
<div>
<span style="color: blue;">4</span>213</div>
<div>
<span style="color: blue;">4</span>231</div>
<div>
<span style="color: blue;">4</span>312</div>
<div>
<span style="color: blue;">4</span>321</div>
</div>
<div>
<br /></div>
<div>
最高位可以取{1, 2, 3, 4},而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。</div>
<div>
<br /></div>
<div>
而对于以2开头的6个数字而言,k = 9是其中的第k' = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s[1]为{1, 3, 4}中的第k'/(2!)+1 = 2个,即s[1] = 3。</div>
<div>
<br /></div>
<div>
对于以23开头的2个数字而言,k = 9是其中的第k'' = k'%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.</div>
<div>
<br /></div>
<div>
对于以231开头的一个数字而言,k = 9是其中的第k''' = k''/(1!)+1 = 1个。s[3] = 4</div>
<div>
<br /></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
string getPermutation(<span style="color: #333399; font-weight: bold;">int</span> n, <span style="color: #333399; font-weight: bold;">int</span> k) {
string ret;
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> factorial(n,<span style="color: #0000dd; font-weight: bold;">1</span>);
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">char</span><span style="color: #333333;">></span> num(n,<span style="color: #0000dd; font-weight: bold;">1</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><</span>n; i<span style="color: #333333;">++</span>)
factorial[i] <span style="color: #333333;">=</span> factorial[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">*</span>i;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;"><</span>n; i<span style="color: #333333;">++</span>)
num[i] <span style="color: #333333;">=</span> (i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>)<span style="color: #333333;">+</span><span style="color: #0044dd;">'0'</span>;
k<span style="color: #333333;">--</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>n; i<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;">--</span>) {
<span style="color: #333399; font-weight: bold;">int</span> j <span style="color: #333333;">=</span> k<span style="color: #333333;">/</span>factorial[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
k <span style="color: #333333;">%=</span> factorial[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
ret.push_back(num[j]);
num.erase(num.begin()<span style="color: #333333;">+</span>j);
}
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com24tag:blogger.com,1999:blog-2084836737143870236.post-72504299531156060522014-11-25T20:01:00.000-08:002014-11-25T20:01:03.078-08:00[LeetCode] Next Permutation<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
The replacement must be in-place, do not allocate extra memory.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.<br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1,2,3</code> → <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1,3,2</code><br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">3,2,1</code> → <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1,2,3</code><br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1,1,5</code> → <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1,5,1</code></div>
<br />
思路:<br />
<div>
<br /></div>
<div>
遇到这类概念比较抽象的题目,写几个例子通常会帮助理解问题的规律:</div>
<div>
<br /></div>
<div>
7 2 5 <span style="color: red;">2</span> 3 1</div>
<div>
7 2 5 3 <span style="color: red;">1</span> 2</div>
<div>
7 <span style="color: red;">2</span> 5 3 2 1</div>
<div>
7 3 1 2 <span style="color: red;">2</span> 5</div>
<div>
<br /></div>
<div>
其中红色的数字表示next permutation改变原数字的最高位。比如对于725321来说,由于5321由于从最低位到最高位是升序排列,已经达到该四位数字permutation的最大值。这时不得不改变第5位的2来增加数值。如何改变?为了使增量最小,在前4位中比第5位大的数(5, 3)中找一个最小的数,即数字3。用3替换2,而剩下5, 2, 2, 1四个数字要组成最低4位。由于第5位已经从2增加到3,同样为了使增量最小,我们希望剩下的4位数尽可能小。所以将他们从低到高位降序排列即可。总结上面的思考:</div>
<div>
<br /></div>
<div>
<span style="color: red;"><b>1. 从低位向高位(从右向左)找第一个递减的数:s[i]<s[i+1]。如果不存在,则表明该permutation已经最大,next permutation为当前序列的逆序。</b></span></div>
<div>
<span style="color: red;"><b>2. 在s[i+1:n-1]中找一个j,使s[j]>s[i]>=s[j+1],swap(s[i], s[j])</b></span></div>
<div>
<span style="color: red;"><b>3. 将s[i+1:n-1]排序,从低位到高位单调递减。</b></span></div>
<div>
<br /></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">void</span> nextPermutation(vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> <span style="color: #333333;">&</span>num) {
<span style="color: #008800; font-weight: bold;">if</span>(num.size()<span style="color: #333333;"><</span><span style="color: #0000dd; font-weight: bold;">2</span>) <span style="color: #008800; font-weight: bold;">return</span>;
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> num.size(), j <span style="color: #333333;">=</span> n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span>;
<span style="color: #008800; font-weight: bold;">while</span>(j<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> num[j]<span style="color: #333333;">>=</span>num[j<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>]) j<span style="color: #333333;">--</span>;
<span style="color: #008800; font-weight: bold;">if</span>(j<span style="color: #333333;"><</span><span style="color: #0000dd; font-weight: bold;">0</span>) {
sort(num.begin(),num.end());
<span style="color: #008800; font-weight: bold;">return</span>;
}
<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>j<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">while</span>(i<span style="color: #333333;"><</span>n <span style="color: #333333;">&&</span> num[i]<span style="color: #333333;">></span>num[j]) i<span style="color: #333333;">++</span>;
i<span style="color: #333333;">--</span>;
swap(num[i],num[j]);
sort(num.begin()<span style="color: #333333;">+</span>j<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, num.end());
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com5tag:blogger.com,1999:blog-2084836737143870236.post-61602480377658194132014-11-25T15:22:00.000-08:002014-11-25T18:07:45.867-08:00[LeetCode] Palindrome Partitioning I, II<span style="color: blue;"><b>Palindrome Partitioning I</b></span><br />
<br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a string <i style="box-sizing: border-box;">s</i>, partition <i style="box-sizing: border-box;">s</i> such that every substring of the partition is a palindrome.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Return all possible palindrome partitioning of <i style="box-sizing: border-box;">s</i>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example, given <i style="box-sizing: border-box;">s</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"aab"</code>,<br />
Return</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> [
["aa","b"],
["a","a","b"]
]</pre>
<br />
<br />
<span style="color: blue;"><b>Palindrome Partitioning II</b></span><br />
<br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given a string <i style="box-sizing: border-box;">s</i>, partition <i style="box-sizing: border-box;">s</i> such that every substring of the partition is a palindrome.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Return the minimum cuts needed for a palindrome partitioning of <i style="box-sizing: border-box;">s</i>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example, given <i style="box-sizing: border-box;">s</i> = <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"aab"</code>,<br />
Return <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">1</code> since the palindrome partitioning <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">["aa","b"]</code> could be produced using 1 cut.</div>
<div>
<br /></div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:Palindrome Partitioning I</b></span><br />
<div>
<br /></div>
<div>
遇到要求所有组合、可能、排列等解集的题目,一般都是用DFS + backtracking来做。要分割回文的前提是能够判断回文。在做DFS的时候,如果每次从start出发查找s[start:end]是否是回文,会使算法复杂度大大增加。而在Longest Palindromic Substring这题中已经知道如何用DP来计算任意s[i:j]是否是回文。因此可以先计算该判断矩阵,在DFS的时候用来剪枝,大大提高效率。</div>
<div>
<br /></div>
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span>string<span style="color: #333333;">>></span> partition(string s) {
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> s.size();
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span>string<span style="color: #333333;">>></span> ret;
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> sol;
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">>></span> isPal(n, vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">></span>(n,<span style="color: #007020;">false</span>));
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;">--</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span>i; j<span style="color: #333333;"><</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>((i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">>=</span>j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">||</span> isPal[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]) <span style="color: #333333;">&&</span> s[i]<span style="color: #333333;">==</span>s[j])
isPal[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
}
}
findPartitions(s, <span style="color: #0000dd; font-weight: bold;">0</span>, isPal, sol, ret);
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
<span style="color: #333399; font-weight: bold;">void</span> findPartitions(string <span style="color: #333333;">&</span>s, <span style="color: #333399; font-weight: bold;">int</span> start, vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">>></span> <span style="color: #333333;">&</span>isPal, vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> <span style="color: #333333;">&</span>sol, vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span>string<span style="color: #333333;">>></span> <span style="color: #333333;">&</span>ret) {
<span style="color: #008800; font-weight: bold;">if</span>(start<span style="color: #333333;">==</span>s.size()) {
ret.push_back(sol);
<span style="color: #008800; font-weight: bold;">return</span>;
}
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>start; i<span style="color: #333333;"><</span>s.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(isPal[start][i]) {
<span style="color: #333399; font-weight: bold;">int</span> len <span style="color: #333333;">=</span> i<span style="color: #333333;">-</span>start<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
sol.push_back(s.substr(start, len));
findPartitions(s, i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, isPal, sol, ret);
sol.pop_back();
}
}
}
};
</pre>
</td></tr>
</tbody></table>
</div>
<br />
<br />
<span style="color: blue;"><b>思路:Palindrome Partitioning II</b></span><br />
<div>
<br /></div>
<div>
整体的思路是一维DP。DP[i]表示长度为i的prefix:s[0: i-1]的min cut数量。<br />
DP[i] = min (DP[j] + 1) ,对所有 0<=j<i,且s[j: i-1]为palindrome。<br />
和I同样的技巧,用DP先计算存储一个palindrome判断矩阵isPal[i][j],便于后面一维DP计算中能迅速判断s[j: i-1]是否为palindrome。<br />
<br />
有一个更优的解法参考:<br />
<a href="https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space">https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space</a></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> minCut(string s) {
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> s.size();
<span style="color: #008800; font-weight: bold;">if</span>(n<span style="color: #333333;"><=</span><span style="color: #0000dd; font-weight: bold;">1</span>) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">>></span> isPal(n, vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">bool</span><span style="color: #333333;">></span>(n, <span style="color: #007020;">false</span>));
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span>; i<span style="color: #333333;">--</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span>i; j<span style="color: #333333;"><</span>n; j<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>((i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">></span>j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">||</span> isPal[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]) <span style="color: #333333;">&&</span> s[i]<span style="color: #333333;">==</span>s[j])
isPal[i][j] <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>;
}
}
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> dp(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,INT_MAX);
dp[<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>n; i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span>i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span>; j<span style="color: #333333;">--</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(isPal[j][i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]) {
dp[i] <span style="color: #333333;">=</span> min(dp[i], dp[j]<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>);
}
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com3tag:blogger.com,1999:blog-2084836737143870236.post-2538097477363663532014-11-25T14:21:00.001-08:002014-11-25T14:23:54.080-08:00[LeetCode] Text Justification<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given an array of words and a length <i style="box-sizing: border-box;">L</i>, format the text such that each line has exactly <i style="box-sizing: border-box;">L</i> characters and is fully (left and right) justified.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">' '</code> when necessary so that each line has exactly<i style="box-sizing: border-box;">L</i> characters.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For the last line of text, it should be left justified and no extra space is inserted between words.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
<span style="box-sizing: border-box; font-weight: 700;">words</span>: <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">["This", "is", "an", "example", "of", "text", "justification."]</code><br />
<span style="box-sizing: border-box; font-weight: 700;">L</span>: <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">16</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Return the formatted lines as:</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">[
"This is an",
"example of text",
"justification. "
]
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span> Each word is guaranteed not to exceed <i style="box-sizing: border-box;">L</i> in length.</div>
<div class="showspoilers" style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<a href="https://oj.leetcode.com/problems/text-justification/#" style="background: 0px 0px; box-sizing: border-box; color: #0088cc; text-decoration: none;">click to show corner cases.</a></div>
<div class="spoilers" style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px;">
<span style="box-sizing: border-box; font-weight: 700;">Corner Cases:</span><br />
<div style="box-sizing: border-box; margin-bottom: 10px;">
</div>
<ul style="box-sizing: border-box; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">A line other than the last line might contain only one word. What should you do in this case?<br style="box-sizing: border-box;" />In this case, that line should be left-justified.</li>
</ul>
</div>
<div>
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
比较麻烦的字符串细节实现题。需要解决以下几个问题:</div>
<div>
<br /></div>
<div>
1. 首先要能判断多少个word组成一行:</div>
<div>
这里统计读入的所有words的总长curLen,并需要计算空格的长度。假如已经读入words[0:i]。当curLen + i <=L 且加curLen + 1 + word[i+1].size() > L时,一行结束。</div>
<div>
<br /></div>
<div>
2. 知道一行的所有n个words,以及总长curLen之后要决定空格分配:</div>
<div>
平均空格数:k = (L - curLen) / (n-1)</div>
<div>
前m组每组有空格数k+1:m = (L - curLen) % (n-1)</div>
<div>
<br /></div>
<div>
例子:L = 21,curLen = 14,n = 4</div>
<div>
k = (21 - 14) / (4-1) = 2</div>
<div>
m = (21 - 14) % (4-1) = 1</div>
<div>
A---B--C--D</div>
<div>
<br /></div>
<div>
3. 特殊情况:</div>
<div>
(a) 最后一行:当读入到第i = words.size()-1 个word时为最后一行。该行k = 1,m = 0</div>
<div>
(b) 一行只有一个word:此时n-1 = 0,计算(L - curLen)/(n-1)会出错。该行k = L-curLen, m = 0</div>
<div>
(c) 当word[i].size() == L时。<br />
<br /></div>
<string><string><string><words .size="" i="" if="" size="" words=""><string><!--0--></string></words></string></string></string>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> fullJustify(vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> <span style="color: #333333;">&</span>words, <span style="color: #333399; font-weight: bold;">int</span> L) {
<span style="color: #333399; font-weight: bold;">int</span> start <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>, end <span style="color: #333333;">=</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>, totLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">bool</span> isLast <span style="color: #333333;">=</span> <span style="color: #007020;">false</span>;
vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> ret;
<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">while</span>(i<span style="color: #333333;"><</span>words.size()) {
<span style="color: #008800; font-weight: bold;">if</span>(words[i].size()<span style="color: #333333;">></span>L) <span style="color: #008800; font-weight: bold;">return</span> ret;
<span style="color: #333399; font-weight: bold;">int</span> newLen <span style="color: #333333;">=</span> totLen <span style="color: #333333;">+</span> (end<span style="color: #333333;">-</span>start<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>) <span style="color: #333333;">+</span> words[i].size();
<span style="color: #008800; font-weight: bold;">if</span>(newLen<span style="color: #333333;"><=</span>L) { <span style="color: #888888;">// words[i] can be in current line</span>
end <span style="color: #333333;">=</span> i;
totLen <span style="color: #333333;">+=</span> words[i].size();
i<span style="color: #333333;">++</span>;
}
<span style="color: #008800; font-weight: bold;">else</span> { <span style="color: #888888;">// word[i-1] is the end of a line</span>
string line <span style="color: #333333;">=</span> createLine(words, L, start, end, totLen, <span style="color: #007020;">false</span>);
ret.push_back(line);
start <span style="color: #333333;">=</span> i;
end <span style="color: #333333;">=</span> i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
totLen <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
}
string lastLine <span style="color: #333333;">=</span> createLine(words, L, start, end, totLen, <span style="color: #007020;">true</span>);
ret.push_back(lastLine);
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
string createLine(vector<span style="color: #333333;"><</span>string<span style="color: #333333;">></span> <span style="color: #333333;">&</span>words, <span style="color: #333399; font-weight: bold;">int</span> L, <span style="color: #333399; font-weight: bold;">int</span> start, <span style="color: #333399; font-weight: bold;">int</span> end, <span style="color: #333399; font-weight: bold;">int</span> totLen, <span style="color: #333399; font-weight: bold;">bool</span> isLast) {
string ret;
<span style="color: #008800; font-weight: bold;">if</span>(start<span style="color: #333333;"><</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">||</span> end<span style="color: #333333;">>=</span>words.size() <span style="color: #333333;">||</span> start<span style="color: #333333;">></span>end) <span style="color: #008800; font-weight: bold;">return</span> ret;
ret.append(words[start]);
<span style="color: #333399; font-weight: bold;">int</span> n <span style="color: #333333;">=</span> end<span style="color: #333333;">-</span>start<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #888888;">// special case: one word or last line - left justified</span>
<span style="color: #008800; font-weight: bold;">if</span>(n<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">||</span> isLast) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>start<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>end; i<span style="color: #333333;">++</span>)
ret.append(<span style="background-color: #fff0f0;">" "</span> <span style="color: #333333;">+</span> words[i]);
<span style="color: #333399; font-weight: bold;">int</span> j <span style="color: #333333;">=</span> L<span style="color: #333333;">-</span>totLen<span style="color: #333333;">-</span>(n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
ret.append(j, <span style="color: #0044dd;">' '</span>);
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
<span style="color: #888888;">// normal case: fully justified</span>
<span style="color: #333399; font-weight: bold;">int</span> k <span style="color: #333333;">=</span> (L<span style="color: #333333;">-</span>totLen)<span style="color: #333333;">/</span>(n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>), m <span style="color: #333333;">=</span> (L<span style="color: #333333;">-</span>totLen)<span style="color: #333333;">%</span>(n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span>start<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>end; i<span style="color: #333333;">++</span>) {
<span style="color: #333399; font-weight: bold;">int</span> nspace <span style="color: #333333;">=</span> i<span style="color: #333333;">-</span>start<span style="color: #333333;"><=</span>m <span style="color: #333333;">?</span> k<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">:</span> k;
ret.append(nspace,<span style="color: #0044dd;">' '</span>);
ret.append(words[i]);
}
<span style="color: #008800; font-weight: bold;">return</span> ret;
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com3tag:blogger.com,1999:blog-2084836737143870236.post-39961998964501262992014-11-25T12:30:00.001-08:002014-11-25T12:41:54.503-08:00[LeetCode] Edit Distance<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given two words <i style="box-sizing: border-box;">word1</i> and <i style="box-sizing: border-box;">word2</i>, find the minimum number of steps required to convert <i style="box-sizing: border-box;">word1</i> to <i style="box-sizing: border-box;">word2</i>. (each operation is counted as 1 step.)</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
You have the following 3 operations permitted on a word:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: #333333; font-family: Helvetica Neue, Helvetica, Arial, sans-serif;"><span style="background-color: white; font-size: 14px; line-height: 30px;">a) Insert a character</span></span><br />
<span style="color: #333333; font-family: Helvetica Neue, Helvetica, Arial, sans-serif;"><span style="background-color: white; font-size: 14px; line-height: 30px;">b) Delete a character</span></span><br />
<span style="color: #333333; font-family: Helvetica Neue, Helvetica, Arial, sans-serif;"><span style="background-color: white; font-size: 14px; line-height: 30px;">c) Replace a character</span></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<br /></div>
<span style="color: blue;"><b>思路:</b></span><br />
<div>
<br /></div>
<div>
很多算法教科书上都有的经典二维DP问题。</div>
<div>
<br /></div>
<div>
1. 状态:</div>
<div>
<span style="color: red;"><b>DP[i+1][j+1]:word1[0:i] -> word2[0:j]的edit distance。</b></span></div>
<div>
<br /></div>
<div>
2. 通项公式:</div>
<div>
考虑word1[0:i] -> word2[0:j]的最后一次edit。无非题目中给出的三种方式:</div>
<div>
<br /></div>
<div>
a) 插入一个字符:word1[0:i] -> word2[0:j-1],然后在word1[0:i]后插入word2[j]</div>
<div>
DP[i+1][j+1] = DP[i+1][j]+1</div>
<div>
<br /></div>
<div>
b) 删除一个字符:word1[0:i-1] -> word2[0:j],然后删除word1[i]</div>
<div>
DP[i+1][j+1] = DP[i][j+1]+1</div>
<div>
<br /></div>
<div>
c) 替换一个字符:word1[0:i-1] -> word2[0:j-1]</div>
<div>
word1[i] != word2[j]时,word1[i] -> word2[j]:DP[i+1][j+1] = DP[i][j] + 1</div>
<div>
word1[i] == word2[j]时:DP[i+1][j+1] = DP[i][j] </div>
<div>
<br /></div>
<div>
所以min editor distance应该为:</div>
<div>
<span style="color: red;"><b>DP[i+1][j+1] = min(DP[i][j] + k, DP[i+1][j]+1, DP[i][j+1]+1) </b></span></div>
<div>
<span style="color: red;"><b>word1[i]==word2[j] -> k = 0, 否则k = 1</b></span></div>
<div>
<br /></div>
<div>
3. 计算方向:</div>
<div>
<span style="color: blue;">replace (i, j) delete (i, j+1)</span></div>
<div>
<span style="color: blue;">insert (i+1, j)</span> <span style="color: red;">(i+1, j+1)</span></div>
<div>
<br /></div>
<div>
可见要求DP[i+1][j+1],必须要知道二维矩阵中左上,上方和下方的3个值。所以当我们确定第0行和第0列的值后,就可以<span style="color: red;"><b>从上到下、从左到右</b></span>的计算了。</div>
<div>
<br /></div>
<div>
4. 起始、边界值</div>
<div>
<span style="color: red;"><b>DP[0][i] = i</b></span>: word1为空,要转化到word2[0:i-1],需要添加i个字符。</div>
<div>
<span style="color: red;"><b>DP[i][0] = i</b></span>: word2为空,要从word1转化到空字符串,需要删除i个字符。</div>
<div>
<br /></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> minDistance(string word1, string word2) {
<span style="color: #333399; font-weight: bold;">int</span> m <span style="color: #333333;">=</span> word1.size(), n <span style="color: #333333;">=</span> word2.size();
vector<span style="color: #333333;"><</span>vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">>></span> dp(m<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span>(n<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">0</span>));
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><=</span>n; j<span style="color: #333333;">++</span>)
dp[<span style="color: #0000dd; font-weight: bold;">0</span>][j] <span style="color: #333333;">=</span> j;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><=</span>m; i<span style="color: #333333;">++</span>) {
dp[i][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> i;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; j<span style="color: #333333;"><=</span>n; j<span style="color: #333333;">++</span>) {
dp[i][j] <span style="color: #333333;">=</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">if</span>(word1[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">!=</span>word2[j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]) dp[i][j]<span style="color: #333333;">++</span>;
dp[i][j] <span style="color: #333333;">=</span> min(min(dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][j]<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>, dp[i][j<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>), dp[i][j]);
}
}
<span style="color: #008800; font-weight: bold;">return</span> dp[m][n];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2tag:blogger.com,1999:blog-2084836737143870236.post-39011570923810392162014-11-25T10:34:00.003-08:002014-11-25T10:34:51.899-08:00[LeetCode] Decode Ways<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
A message containing letters from <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">A-Z</code> is being encoded to numbers using the following mapping:</div>
<pre style="background-color: whitesmoke; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">'A' -> 1
'B' -> 2
...
'Z' -> 26
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given an encoded message containing digits, determine the total number of ways to decode it.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example,<br />
Given encoded message <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"12"</code>, it could be decoded as <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"AB"</code> (1 2) or <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">"L"</code> (12).</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: #333333; font-family: Helvetica Neue, Helvetica, Arial, sans-serif;"><span style="background-color: white; font-size: 14px; line-height: 30px;">The number of ways decoding </span></span><code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 30px; padding: 2px 4px;">"12"</code><span style="color: #333333; font-family: Helvetica Neue, Helvetica, Arial, sans-serif;"><span style="background-color: white; font-size: 14px; line-height: 30px;"> is 2.</span></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<br /></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: blue;"><b>思路:</b></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
假设解码函数为h。对于一位数X,只能解码成h[X]。而对于一个两位数XY:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
1. 如果XY<=26,那么能解码成h[X], h[Y], h[XY]</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
2. 否则,只能解码成h[X], h[Y]</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
由于只要求计算最多的解码方法而并不要求每种解码的结果,所以用DP做更为合适高效。</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<br /></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
定义dp[i+1]为能解码长度为i+1的string s[0:i]的方法数:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
1. dp[0] = 1,dp[1] = 0</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
2. v = s[i-1]*10+s[i]:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
v<=26: dp[i+1] = dp[i] + dp[i-1]</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
v>26:dp[i+1] = dp[i]</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<br /></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: blue;">corner case:有0的情况</span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: blue;">Y = 0:显然无法解码成h[Y],此时只能看h[XY]是否valid:dp[i+1] = dp[i-1]</span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: blue;">X = 0:显然无法解码成h[XY],此时dp[i+1] = dp[i]</span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: blue;"><br /></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: red;"><b>整理总结corner case:</b></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<b style="color: red;">XY可以解码的条件是:</b><span style="color: red;"><b>9<XY<=26</b></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<span style="color: red;"><b>Y可以单独解码的条件是:Y != '0'</b></span></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #997700; font-weight: bold;">public:</span>
<span style="color: #333399; font-weight: bold;">int</span> numDecodings(string s) {
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: red;"><b>s.empty() || s[0]<'1' || s[0]>'9'</b></span>) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
vector<span style="color: #333333;"><</span><span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">></span> dp(s.size()<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>,<span style="color: red; font-weight: bold;">0</span>);
<span style="color: red;"><b>dp[0] = dp[1] = 1;</b></span>
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>; i<span style="color: #333333;"><</span>s.size(); i<span style="color: #333333;">++</span>) {
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>isdigit(s[i])) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">int</span> v <span style="color: #333333;">=</span> (s[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">-</span><span style="color: #0044dd;">'0'</span>)<span style="color: #333333;">*</span><span style="color: #0000dd; font-weight: bold;">10</span> <span style="color: #333333;">+</span> (s[i]<span style="color: #333333;">-</span><span style="color: #0044dd;">'0'</span>);
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: red;"><b>v<=26 && v>9</b></span>) dp[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">+=</span> dp[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: red;"><b>s[i]!='0'</b></span>) dp[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>] <span style="color: #333333;">+=</span> dp[i];
<span style="color: #008800; font-weight: bold;">if</span>(dp[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">0</span>) <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
<span style="color: #008800; font-weight: bold;">return</span> dp[s.size()];
}
};
</pre>
</td></tr>
</tbody></table>
</div>
Yanbing Shihttp://www.blogger.com/profile/16541941455216571610noreply@blogger.com2