2017-09-27

犒劳一下自己

心情不好的时候，可能这时候真的已经很疲惫了。

不要继续沮丧让自己的心情更糟糕，或许这个时候应该犒劳一下自己，让自己的心情放松，晴朗起来或许一切看起来回事那么情切舒服！

2017-09-27

HouseRobberIII

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

所以说纯粹是怎么多怎么来，那么这种问题是很典型的递归问题，我们可以利用回溯法来做，因为当前的计算需要依赖之前的结果，那么我们对于某一个节点，如果其左子节点存在，我们通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可：

//直接使用递归
public int rob(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int var = 0;
    if (root.left != null) {
        var += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        var += rob(root.right.left) + rob(root.right.right);
    }
    return Math.max(root.val + var, rob(root.right) + rob(root.left));
}

由于上面的方法超时了，所以我们必须优化上面的方法，上面的方法重复计算了很多地方，比如要完成一个节点的计算，就得一直找左右子节点计算，我们可以把已经算过的节点用哈希表保存起来，以后递归调用的时候，现在哈希表里找，如果存在直接返回，如果不存在，等计算出来后，保存到哈希表中再返回，这样方便以后再调用，参见代码如下：

//使用hash 表对多余的递归进行优化
public int rob_1(TreeNode root) {
    HashMap<TreeNode, Integer> map = new HashMap<>();
    return dfs(root, map);
}

private int dfs(TreeNode root, HashMap<TreeNode, Integer> map) {
    if (root == null) {
        return 0;
    }
    if (map.containsKey(root)) {
        return map.get(root);
    }
    int var = 0;
    if (root.left != null) {
        var += dfs(root.left.right, map) + dfs(root.left.left, map);
    }
    if (root.right != null) {
        var += dfs(root.right.left, map) + dfs(root.right.right, map);
    }
    int max = Math.max(var + root.val, dfs(root.left, map) + dfs(root.right, map));
    map.put(root, max);
    return max;
}

下面再来看一种方法，这种方法的递归函数返回一个大小为2的一维数组res，其中res[0]表示不包含当前节点值的最大值，res[1]表示包含当前值的最大值，那么我们在遍历某个节点时，首先对其左右子节点调用递归函数，分别得到包含与不包含左子节点值的最大值，和包含于不包含右子节点值的最大值，那么当前节点的res[0]就是左子节点两种情况的较大值加上右子节点两种情况的较大值，res[1]就是不包含左子节点值的最大值加上不包含右子节点值的最大值，和当前节点值之和，返回即可，参见代码如下：

public int rob_2(TreeNode root) {
        int[] result = dfs_1(root);
        return Math.max(result[0], result[1]);
    }

    private int[] dfs_1(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = dfs_1(root.left);
        int[] right = dfs_1(root.right);
        return new int[]{ Math.max(left[0], left[1]) + Math.max(right[0], right[1]),root.val + left[0] + right[0]};
    }

整理于：http://www.cnblogs.com/grandyang/p/5275096.html

2017-09-27

Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

这题主要就是给一个算式，然后让我们填符号，要是最后的算式的结果等于一个特定的数，现在发现这种阶梯方法比较好就使用了动态规划，里面具体的东西就是递归求解了。

与此类似的体还有很多就是台阶问题等等，都可以使用类似的方法求解！

package LeetCode;

public class TargetSum {
    int count = 0;

    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }

    private void calculate(int[] nums,int i,int sum,int S){
        if (i == nums.length) {
            if (sum == S) {
                count++;
            }
        }else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

2017-09-27

QueueReconstructionbyHeight

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

这道题给了我们一个队列，队列中的每个元素是一个pair，分别为身高和前面身高不低于当前身高的人的个数，让我们重新排列队列，使得每个pair的第二个参数都满足题意。

基本思路：
首先按照高度排序，如果两个人的高度一样的话我们就就按照第二个数字排序
最后把他们插入到一个新的数组里面，就按照他们的第二个数字的下标，插入到对应的下标

package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;



public class QueueReconstructionbyHeight {
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0) {
            return people;
        }
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] p1, int[] p2) {
                return p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0];
            }
        });
        List<int[]> temp = new ArrayList<>();
        for (int[] aPeople : people) {
            if (people.length == aPeople[1]) {
                temp.add(aPeople);
            } else {
                temp.add(aPeople[1], aPeople);
            }
        }
        int ans[][] = new int[people.length][2];
        for (int i = 0; i < temp.size(); i++) {
            ans[i] = temp.get(i);
        }
        return ans;
    }
}

2017-09-27

Dp经典问题LongestIncreasingSubsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

思路：
这道题主要考察的就是动态规划
如果使用暴力破解的方式要么就是超时要么就是空间超出限制
然后动态规划的方法就是：使用一个 dp 数组然后在这个 dp 数组记录的内容就是党目前为止的最长的子序列



package LeetCode;

import org.junit.jupiter.api.Test;

import java.util.Arrays;



public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp,0);
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        System.out.println(LeetcodeUtils.integerArrayToString(dp));;
        return maxans;
    }

    @Test
    public void fun(){
        lengthOfLIS(new int[]{4,10,4,3,8,9});
    }
}