java算法day28

java算法day28

• 300 最长递增子序列
• 136 只出现一次的数字
• 169 多数元素
• 234 回文链表
• 53 最大子数组和

---

300 最长递增子序列

这个是记忆化搜索的代码。是从递归改过来的。
这题显然是要用dp做比较合适。因为很容易看到原问题与子问题之间的关系。

还是从后往前看。
然后可以利用选与不选，或者选哪个。这两种方式来进行拆分，然后进行递归。

class Solution {int[] memo;public int lengthOfLIS(int[] nums) {if(nums==null||nums.length==0){return 0;}int n = nums.length;memo = new int[n];int maxLen = 0;for(int i = n-1;i>=0;i--){maxLen = Math.max(maxLen,dfs(nums,i));}return maxLen;}int dfs(int[] nums,int index){if(index == 0){return 1;}if(memo[index]!=0){return memo[index];}int maxLen = 1;for(int i = index-1;i>=0;i--){if(nums[i]<nums[index]){maxLen = Math.max(maxLen,dfs(nums,i)+1);}}memo[index] = maxLen;return maxLen;}}

---

如果你熟悉了递归转记忆化搜索转动态规划这个模式。那么可以直接来看动态规划怎么写了。
如果你懂这个过程，那么完全可以看懂递归模板这样做的原因。以及找到这些相关因素到底能有什么用。详细的总结我写在最后面那个题了。我们来看这题dp怎么做

状态定义：
dp[i]的值代表nums以nums[i]结尾的最长子序列的长度。
状态转移方程。

---

136 只出现一次的数字

思路：
拿到题目首先看到题目的含义，就想到了统计数字出现次数，那么就想到了Hash。但是题目不让用额外的空间，那么哈希没用了。
那么往不用空间复杂度想，我又想到了排序，但是排序最快也要o(nlogn)，题目又要用o(n)时间复杂度，于是排序也没有了。

然后去看题解了。
这个解法完全是因为题目的含义才能解出来：
除了某个元素只出现一次之外，其余元素均出现2次。

这非常符合位运算的性质。你要是知道这个性质，你也可以做：
既满足时间复杂度又满足空间复杂度，就要提到位运算中的异或运算 XOR，主要因为异或运算有以下几个特点：
一个数和 0 做 XOR 运算等于本身：a⊕0 = a
一个数和其本身做 XOR 运算等于 0：a⊕a = 0
XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

由于满足交换律和结合律，那么按顺序遍历一遍进行异或运算，那么最后出现两次的肯定异或得到0了。
最后的情况肯定是这个单独的出现的元素异或0得到他本身，返回这个结果就结束了。

class Solution {public int singleNumber(int[] nums) {if(nums.length == 1){return nums[0];}int length = nums.length;//取第一个元素就开始遍历，然后返回最后的结果。int ans = nums[0];for(int i = 1;i<length;i++){ans^=nums[i];}return ans;}
}

---

169 多数元素

那道题想到两个想法：
1、哈希，2、排序。

class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();int length = nums.length;for(int i = 0;i<length;i++){if(map.containsKey(nums[i])){int value = map.get(nums[i]);map.put(nums[i],value+1);}else{map.put(nums[i],1);}}int target = length/2;for(Map.Entry<Integer,Integer> entry : map.entrySet()){int value = entry.getValue();if(value > target){return entry.getKey();}}return 0;}
}

---

最优解
摩尔投票

思路：
候选人candNum初始化为nums[0]，票数count初始化为1。
当遇到与candNum相同的数，则票数count=count+1。
否则票数-1。

一旦count为0时，更换候选人。
遍历完数组之后，candNum即为最终答案。

原理解释：
该方法属于投票法
投票法是遇到相同的则票数+1，不同的票数-1。且众数元素的个数大于总元数的一半，其余元素的个数肯定小于一般。

因此多数元素的个数-其余元素的个数总和的结果肯定>=1。这就相当于按照这种抵消策略。最后肯定会剩余至少1个多数元素。

之前我脑子里一直有那种类似这样的例子：
1 2 1 3 1 4 1 5 。这个纯粹就是我少想了，一定是大于半数。注意是大于。所以这个思路完全行得通。

class Solution {public int majorityElement(int[] nums) {if(nums.length==1){return nums[0];}int length = nums.length;int candNum = nums[0];int count = 1;for(int i = 1;i<length;i++){if(count==0){candNum = nums[i];}if(nums[i]==candNum){count++;}else{count--;}}return candNum;}
}

---

234 回文链表

主要思路：
先找到中间节点：通过快慢指针，fast一次两步，slow一次一步。然后将后半段链表逆置。然后进行回文的逻辑判断即可。

关键点。其实不用考虑中间若是多一个节点的情况，多出来的那个节点完全不会比较到，因为没有比这个元素的机会，当少1个元素的链表遍历完的时候，我循环比较的逻辑就停止了。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head.next==null){return true;}ListNode fast = head;ListNode slow = head;while(fast!=null && fast.next!=null ){slow = slow.next;fast = fast.next.next;}//此时slow已经在中。然后将后面的链表逆置了ListNode pre = null;ListNode cur = slow;while(cur!=null){//存后一个节点ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//现在来进行回文的判断ListNode l1 = head;ListNode l2 = pre;while(l1!=null && l2!=null){if(l1.val!=l2.val){return false;}l1 = l1.next;l2 = l2.next;}return true;}
}

---

53 最大子数组和

有了前面的积累，我终于能直接看懂动态规划的题解了。也终于知道状态转移方程怎么用了。

这里可以总结一下心路历程：
看懂动态规划之前有这样的历程：首先动态规划不是上来就有的。首先应该是暴力递归解法。将递归树画出来后，我们可以发现可以优化的点，那就是递归的过程存在很多的重复计算，那这个时候就需要“备忘录”来存储重复的计算。那么这个时候我们对这颗树做优化，你会发现这个递归树突然就变成了o(n)的量级。从递归树来看，那直接就是一路归并，值指最优值。
而这个归并正是状态转移方程。所以为什么很多题解给个初始状态，给个状态转移方程就说这个题就做完了。所以说，有时感觉这个题有很多种走法，但偏偏为什么动态规划是最优走法，就是这个原因。

本题动态规划思路：
dp[i]表示以nums[i]结尾的最大子数组和。然后一般我们从后往前思考。

分类讨论：
我把这种推导过程称之为拼与不拼。不拼那么就重起一个子数组了。

情况1：nums[i] 单独组成一个子数组，那么dp[i] = nums[i]。这种情况是纯在的，比如-1,-2,-5,7,-2,-3。那么以7这个位置为结尾的最长子数组和应该只有7本身。
情况2：将nums[i]和前面的子数组拼起来，也就是以nums[i-1]结尾的最大子数组和之和添加nums[i]。那么此时dp[i] = f[i-1]+nums[i]。
那么这个原问题和子问题的关系就很明确了。
由于每个元素都有可能是最长子数组和的结尾元素。那么可写出这个递推公式
f[i] = max(f[i-1],0) + nums[i]。
自己理解一下这个公式，这个状态转移方程的意思就是上面的两种情况。
如果f[i-1]比0还小，那说明把前面的子数组加起来是没有收益的，那么就要重起一个子数组了，此时前面这个式子值为0。此时f[i] = nums[i]。

如果你是非常清楚dp的套路。那么我告诉你一个结论，然后一个公式你应该就做完了。
1、dp[i]表示以nums[i]结尾的最长子数组的和。
2、状态转移方程：
初始状态那么就是dp[0]，那么就是以nums[0]结尾的最长子数组，那么dp[0]= nums[0]。
3、循环迭代计算dp数组，然后找出以哪个为值为结尾的子数组和最大。然后返回这个最大值。

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int ans = dp[0];for(int i = 1;i<nums.length;i++){dp[i] = Math.max(dp[i-1],0) + nums[i];ans = Math.max(ans,dp[i]);}return ans;}
}