6.5号刷题

第一题 392. Is Subsequence

算法

利用两个指针不断的指示位置，向前推进

public class Solution {
    public boolean isSubsequence(String t, String s) {
        if (s.length() == 0 && t.length() != 0) return false;
        if (t.length() == 0) return true;
        int lows = 0, lowt = 0, highs = s.length() - 1, hight = t.length() - 1;
        boolean tag = true;
        while (lows <= highs) {
            if (tag) {
                char target = t.charAt(lowt);
                if (s.charAt(lows) == target) {
                    lowt++;
                    tag = false;
                }
                lows++;
            } else {
                char target = t.charAt(hight);
                if (s.charAt(highs) ==  target) {
                    hight--;
                    tag = true;
                }
                highs--;
            }
        }
        return lowt - hight > 0;       
    }
}

第二题 494. Target Sum

题目描述

给定一组非负整数a1, a2, …, an，以及一个目标数S。给定两种符号+和-，对于每一个整数，选择一个运算符。

计算有多少种运算符的组合方式，可以使整数的和为目标数S。

注意：

给定数组长度为正数并且不会超过20。
元素之和不会超过1000。
输出答案确保在32位整数范围内。

算法

回溯 O(2^n)

相当于对二叉树进行深度遍历，当我们画出所有的可能性的时候，我们发现可以利用回溯的方法对所有的可能性进行遍历.当访问到最后一个的时候，如果当前的和等于总数的话，就返回找到了，值为1。最后累加所有的可能性

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        return helper(0, nums, S, 0);
    }
    
    public int helper(int p, int[] nums, int target, int sum) {
        if (p == nums.length) return sum == target ? 1 : 0;
        return helper(p + 1, nums,target ,sum + nums[p]) + helper(p + 1, nums, target, sum - nums[p]);
    }
    
}

DP

首先将问题进行转化，对于此题，我们可以看错寻找两个subarray p和n，使得sum(P) - sum(N)为target。经过公示的推导，我们得到了最终目的是找到一个subarray使得其和为(targe + sumall) / 2。

                  sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                       2 * sum(P) = target + sum(nums)

这样问题被巧妙的转化为了416. Partition Equal Subset Sum,求是否存在subarray使得其为部分和。

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (S > sum || (S + sum) % 2 == 1) return 0;
        else sum = (S + sum) / 2;
        
        int[] dp = new int[sum + 1];
        dp[0] = 1;
        
        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = sum; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]]; 
            }
        }
        
        return dp[sum];     
    }
}

第三题 416. Partition Equal Subset Sum

题目描述

给定一个只包含正整数的非空数组，判断数组是否可以分成两个和相等的子数组。

算法

二维数组

利用二维数组对所有可能的状态进行表示，dp[i][j]表示对于一个总数j，前0-i个数是否存在一个subarray使得其恰好等于总数j。如果满足j - num[i-1]刚好等于0或之前已经存在的总和，则置为true。

public class canPartition416 {
    public static boolean canPartition(int[] nums) {
        if (nums.length <= 0) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 == 1) return false;
        else sum = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][sum + 1];
        for (int i = 0; i < nums.length + 1; i++) {
            Arrays.fill(dp[i], false);
        }
        for (int i = 0; i < nums.length + 1; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = 1; j < sum + 1; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[nums.length][sum];
    }
}

一维数组

将二维数组简化为一维进行表示。但是注意，j的值必须从后往前推进，否则会出现问题，思路与二维数组是相似的

public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length <= 0) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 == 1) return false;
        else sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = sum; j >= nums[i - 1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[sum];      
    }
}

第四题 198. House Robber

题目描述

你是一名专业强盗，计划沿着一条街打家劫舍。每间房屋都储存有一定数量的金钱，唯一能阻止你打劫的约束条件就是：由于房屋之间有安全系统相连，如果同一个晚上有两间相邻的房屋被闯入，它们就会自动联络警察，因此不可以打劫相邻的房屋。

给定一列非负整数，代表每间房屋的金钱数，计算出在不惊动警察的前提下一晚上最多可以打劫到的金钱数。

算法

自己的

利用一个array存储到目前为止的最大值，不断向后推进。beat40%多，比后面两个方法快一点

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] max = new int[nums.length];
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        max[0] = nums[0];
        max[1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            max[i] = Math.max(max[i-2] + nums[i], max[i-1]);
            if (i >= 3) max[i] = Math.max(max[i], max[i-3] + nums[i]);
        }
        return max[nums.length-1];      
    }
}

别人的方法

利用一个二维矩阵进行存储，dp[i][0 or 1]0代表不抢，1代表强，然后不断向后推进，计算出结果。

还有一个空间复杂度为O(1)的算法

public class rob198 {
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[][] dp = new int[nums.length + 1][2];
        for (int i = 1; i < nums.length + 1; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = nums[i - 1] + dp[i - 1][0];
        }
        return Math.max(dp[nums.length][0], dp[nums.length][1]);
    }
    public int rob3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int preNo = 0, preYes = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = preNo;
            preNo = Math.max(preNo, preYes);
            preYes = nums[i] + temp;
        }
        return Math.max(preNo, preYes);
    }
}

第五题 213. House Robber II

题目描述

注意：这道题是题目House Robber（入室盗贼）的扩展。

抢完上一条街的房屋之后，小偷又给自己找了一个不太引人注意的新作案场所。这一次，所有的房屋围成一个环形。也就是说第一个房屋和最后一个房屋相邻。与此同时，这些房屋的安保系统与上一条街的相同。

给定一组非负整数代表每一件房屋的金钱数，求解在不惊动警察的情况下一晚上最多可以抢到的钱数。

算法

利用之前的方法继续进行改进，我们发现，这个题目可以合并为从(0, nums.length - 2) 和 (1, nums.length - 1)两种情况。

我们分别对两种情况进行计算，然后求出最大值。

public class rob213 {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robSub(nums, 0, nums.length - 2), robSub(nums, 1, nums.length - 1));
    }
    public int robSub(int[] nums, int low, int high) {
        int preNot = 0, preYes = 0;
        for (int i = low; i <= high; i++) {
            int temp = preNot;
            preNot = Math.max(preNot, preYes);
            preYes = nums[i] + temp;
        }
        return Math.max(preNot, preYes);
    }
}

第六题 202. Happy Number

题目描述

编写一个算法判断某个数字是否是“快乐数”。

快乐数的定义过程如下：从任意一个正整数开始，将原数替换为其每一位的平方和，重复此过程直到数字=1（此时其值将不再变化），或者进入一个不包含1的无限循环。那些以1为过程终止的数字即为“快乐数”。

例如：19是一个快乐数，演算过程见题目描述。

算法

比较简单，就不多说了，两份代码，后面的是重构过的。

public class isHappy202 {
    public boolean isHappy1(int n) {
        if (n <= 0) return false;
        Set<Integer> past = new HashSet<>();
        past.add(n);
        int num = n;
        while (true) {
            int tmpSum = 0;
            while (true) {
                int digit = num % 10;
                tmpSum += digit * digit; // Math.pow(digit, 2)
                num = num / 10;
                if (num == 0) break;
            }
            if (tmpSum == 1) return true;
            if (past.contains(tmpSum)) return false;
            past.add(tmpSum);
            num = tmpSum;
        }
    }
    public boolean isHappy2(int n) {
        if (n <= 0) return false;
        Set<Integer> past = new HashSet<>();
        past.add(n);
        int num = n;
        while (past.add(num)) {
            int tmpSum = 0;
            while (num > 0) {
                int digit = num % 10;
                tmpSum += digit * digit;
                num = num / 10;
            }
            if (tmpSum == 1) return true;
            num = tmpSum;
        }
        return false;
    }
}

第七题 242. Valid Anagram

题目描述

给定字符串s和t，编写函数判断t是否为s的anagram（字谜游戏，由颠倒字母顺序而构成的字[短语]）。

测试用例见题目描述。

注意：

你可以假设字符串只包含小写字母。

算法

利用hashmap

public class isAnagram242 {
    public boolean isAnagram(String s, String t) {
        if (s.equals(t)) return true;
        if (s.length() != t.length()) return false;
        Map<Character, Integer> chars = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (chars.containsKey(temp)) {
                int value = chars.get(temp) + 1;
                chars.put(temp, value);
            } else {
                chars.put(temp, 1);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            char temp = t.charAt(i);
            if (chars.containsKey(temp)) {
                int value = chars.get(temp) - 1;
                if (value == 0) chars.remove(temp);
                else chars.put(temp, value);
            } else {
                return false;
            }
        }
        return chars.isEmpty();
    }
}

利用Array

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.equals(t)) return true;
        if (s.length() != t.length()) return false;
        int[] chars = new int['z' - 'a' + 1];
        for (char temp : s.toCharArray()) {
            chars[temp - 'a'] += 1;
        }
        for (char temp : t.toCharArray()) {
            chars[temp - 'a'] -= 1;
        }
        
        for (int num : chars) {
            if (num != 0) return false;
        }
        return true;        
    }
}

学到的东西

String 可以通过String.toCharArray变成一个Char的数组