hot100之数组
<h3 id="最大子数组和053">最大子数组和(053)</h3><p>先看代码</p>
<pre><code class="language-java">class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int subSum = 0;
int res = nums;
for (int i = 0; i < n; i++){
subSum = Math.max(nums, subSum+nums);
res = Math.max(res, subSum);
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>贪心+动态规划</p>
<p>判断<strong>前子数组</strong>是否对 subSum 产生负影响, 产生影响则放弃前子数组, 重新开始新的子数组</p>
<p>动态规划体现在计算当前的子数组和时，需要考虑前面的子数组和是否对当前有贡献。贪心体现在如果前面的子数组和为负数，就直接舍弃重新开始计算。这道题的关键在于理解subSum代表以当前元素结尾的最大子数组和。</p>
<ul>
<li>感悟</li>
</ul>
<p>因为前值会对后值产生影响 , 让人自然想到动态规划</p>
<p>由于后值只需要前一个状态的值 我们可以用 subSum作滚动计算,优化空间复杂度</p>
<h3 id="合并区间056">合并区间(056)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (p, q)-> p - q);
List<int []> res = new ArrayList<>();
for(int[] p : intervals){
int m = res.size();
if (m > 0 && p <= res.get(m-1)){
res.get(m-1) = Math.max(res.get(m-1), p);
}else res.add(p);
}
return res.toArray(new int[]);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>利用左端点进行排序, 再组合</p>
<ul>
<li>感悟</li>
</ul>
<p>左端点排序可以不破坏p与 p一致, 递增</p>
<h3 id="轮转数组189">轮转数组(189)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n-1);
reverse(nums, 0, k-1);
reverse(nums, k, n-1);
}
private void reverse(int[] nums, int lef, int rig){
while (lef < rig){
int temp = nums;
nums = nums;
nums = temp;
}
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>先对整体数组翻转, 在以k为节点 左右各自翻转</p>
<ul>
<li>感悟</li>
</ul>
<p>数学 真神奇吧</p>
<h3 id="除自身以外数的乘积238">除自身以外数的乘积(238)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] preSum = new int;
preSum = 1;
int[] sufSum = new int;
sufSum = 1;
for(int i = 1; i < n ; i++){
preSum = preSum * nums;
}
for(int i = n-2; i >= 0; i--){
sufSum = sufSum * nums;
}
int[] res = new int;
for(int i = 0; i < n; i++){
res = preSum * sufSum;
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>分别计算数组的前缀积与后缀积</p>
<p>用 i之前的前缀积 *i之和的后缀积</p>
<blockquote>
<p><code>res = preSum * sufSum</code><br>
preSum = 1 sufSum = 1<br>
可知 preSum 为 num * …. * num<br>
同理 sufSum 为 num * …. * num<br>
可知<code>preSum * sufSum</code> 不包含 num</p>
</blockquote>
<ul>
<li>感悟</li>
</ul>
<p>分解数据的前后缀再求解</p>
<h3 id="缺失的第一个正数041">缺失的第一个正数(041)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++){
while(0 < nums && nums <= n && nums != nums - 1]){
int j = nums - 1;
int temp = nums;
nums = nums;
nums = temp;
}
}
for (int i = 0; i < n; i++){
if (nums != i+1){
return i+1;
}
}
return n+1;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>还是分座位, 如果i号座位上坐的人不是i , 让出座位给i</p>
<ul>
<li>感悟</li>
</ul>
<p>将理论问题生活化. 生活中的一个直觉, 背后可能有丰富的理论</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18916608
頁:
[1]