网站分为那几个模块,电子商务网站建设人才调研,Wordpress也,黄页88推广多少钱java算法day28
300 最长递增子序列136 只出现一次的数字169 多数元素234 回文链表53 最大子数组和 300 最长递增子序列
这个是记忆化搜索的代码。是从递归改过来的。 这题显然是要用dp做比较合适。因为很容易看到原问题与子问题之间的关系。
还是从后往前看。 然后可以利用选…java算法day28
300 最长递增子序列136 只出现一次的数字169 多数元素234 回文链表53 最大子数组和 300 最长递增子序列
这个是记忆化搜索的代码。是从递归改过来的。 这题显然是要用dp做比较合适。因为很容易看到原问题与子问题之间的关系。
还是从后往前看。 然后可以利用选与不选或者选哪个。这两种方式来进行拆分然后进行递归。
class Solution {int[] memo;public int lengthOfLIS(int[] nums) {if(numsnull||nums.length0){return 0;}int n nums.length;memo new int[n];int maxLen 0;for(int i n-1;i0;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;i0;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 运算等于 0a⊕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;ilength;i){ans^nums[i];}return ans;}
}169 多数元素
那道题想到两个想法 1、哈希2、排序。
class Solution {public int majorityElement(int[] nums) {MapInteger,Integer map new HashMap();int length nums.length;for(int i 0;ilength;i){if(map.containsKey(nums[i])){int value map.get(nums[i]);map.put(nums[i],value1);}else{map.put(nums[i],1);}}int target length/2;for(Map.EntryInteger,Integer entry : map.entrySet()){int value entry.getValue();if(value target){return entry.getKey();}}return 0;}
}最优解 摩尔投票
思路 候选人candNum初始化为nums[0]票数count初始化为1。 当遇到与candNum相同的数则票数countcount1。 否则票数-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.length1){return nums[0];}int length nums.length;int candNum nums[0];int count 1;for(int i 1;ilength;i){if(count0){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.nextnull){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]结尾的最大子数组和。然后一般我们从后往前思考。
分类讨论 我把这种推导过程称之为拼与不拼。不拼那么就重起一个子数组了。
情况1nums[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;inums.length;i){dp[i] Math.max(dp[i-1],0) nums[i];ans Math.max(ans,dp[i]);}return ans;}
}
