刷leetCode算法题+解析（十七）

打家劫舍

题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路：其实这道题就题目好玩点，剩下思路还是老思路。不就是数组中非连续数最大的和么，这就是一道典型的动态规划的题

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

说到动态规划我其实是拒绝的，毕竟学渣惯了，听到一个这么深奥又费解的词还是很虚的，但是等真正做题不断在一次次碰壁中用到了这种思维方式，觉得也不过就是那样。所谓动态规划我个人理解就是在运算的过程中不断选优的做法。上一道典型动态规划的题就是爬楼梯那个。这两道题的统一点就是在走到n步的时候不知道n之前是怎么走的，怎么算的。所以几乎都是要从最开始就要选优。或者说动态规划就是每一步都要择优而选，而这一步步应该也可以看成的一个不那么纯粹的递归。
还是回归于这个题：由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值。
举例来说：1 号房间可盗窃最大值为 333 即为 dp[1]=3，2 号房间可盗窃最大值为 444 即为 dp[2]=4，3 号房间自身的值为 222 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 555
接着上代码：

class Solution {
    public int rob(int[] nums) {
        int [] result = new int[nums.length+2];
        //第一天前面没有初始值，所以设置为0
        result[0] = 0;
        result[1] = 0;
        for(int i=0;i<nums.length;i++){
            result[i+2] = Math.max(result[i]+nums[i],result[i+1]);
        }
        return result[result.length-1];
    }
}

再多说两句，动态规划这块真的很抽象，反正我一开始看这个题是往递归上考虑的，后来发现递归很难实现，也正好想起了当时的爬楼梯（因为这两道题都卡了我好久，印象深刻）。才试图用动态规划的思路来做的。我自己也是半桶水的水平，如果大佬有分辨什么时候递归什么时候动态规划的好方法也请不吝赐教啊。

快乐数

编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路：这个名字，突如其来的骚啊~怎么寻思取的呢？好了不吐槽名字说题目，反正我第一反应是递归，先去撸代码，回来再好好说。回来了，不出所料的递归。思路比较清晰明了，所以直接上代码：

class Solution {
    public boolean isHappy(int n) {
        //这个是实际测试的，如果想要形成循环，其中循环结果有4.
        //换言之当n等于4以后则意味着进入了死循环
        if(n==4){
            return false;
        }
        int result = 0;
        while(n>0){
            result += Math.pow(n%10,2);
            n = n/10;
        }
        //如果结果不是1则递归。
        return result==1?true:isHappy(result);
    }
}

这里也没啥坑，就是第一版本（没有第一个n==4的判断）写完直接提交了，有死循环起码能知道死循环节点是什么。然后发现如果出现死循环则4是其中一个节点，所以这里又判断了下，如果是4则直接返回false。其实这个名字不错，这么简单的题有助于增加信心，是挺快乐的。下一题

移出链表元素

题目：删除链表中等于给定值 val 的所有节点。

示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

这个题简直良心，上午的动态规划怀疑人生，下午两道送分题增加信心。反正这道题只要知道链表的原理就很简单了。挨个挂节点就行了。直接上代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //给定链表为空直接返回
        if(head==null ){
            return null;
        }
        //随便设置一个头结点，省的最后找不到头
        ListNode result = new ListNode(head.val);
        ListNode cur = result;
        while(head!=null){                    
            //不是给定值才挂链表上     
            if(head.val!=val){
                cur.next = new ListNode(head.val) ;
                cur = cur.next;               
            }   
            head = head.next;        
        }
        return result.next;
    }
}

今天就整理到这里，如果稍微帮到你了记得点个喜欢点个关注呦~也祝大家工作顺顺利利！