打家劫舍

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 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 。

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 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 。

public class Onehundred_ninetyEight {
    //dp[i]表示0-i所取得的最大值
    public int rob(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return len == 0 ? 0 : nums[0];
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; ++i)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        return dp[len - 1];
    }
}

public class Onehundred_ninetyEight {

//dp[i]表示0-i所取得的最大值

public int rob(int[] nums) {

int len = nums.length;

if (len <= 1)

return len == 0 ? 0 : nums[0];

int[] dp = new int[len];

dp[0] = nums[0];

dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < len; ++i)

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

return dp[len - 1];

}

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]

输出: 3

解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]

输出: 4

解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。

偷窃到的最高金额 = 1 + 3 = 4 。

public class Twohundred_thirteen {
    /**
     * 分为：偷第一家[0,n-2] 和 不偷第一家[1,n-1]
     **/
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];
        int len = nums.length;
        int max = Math.max(helper(Arrays.copyOfRange(nums, 0, len - 1)), helper(Arrays.copyOfRange(nums, 1, len)));
        return max;
    }

    public int helper(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return len == 0 ? 0 : nums[0];
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; ++i)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        return dp[len - 1];
    }
}

public class Twohundred_thirteen {

/**

* 分为：偷第一家[0,n-2] 和不偷第一家[1,n-1]

**/

public int rob(int[] nums) {

if (nums == null || nums.length == 0)

return 0;

if (nums.length == 1)

return nums[0];

int len = nums.length;

int max = Math.max(helper(Arrays.copyOfRange(nums, 0, len - 1)), helper(Arrays.copyOfRange(nums, 1, len)));

return max;

}

public int helper(int[] nums) {

int len = nums.length;

if (len <= 1)

return len == 0 ? 0 : nums[0];

int[] dp = new int[len];

dp[0] = nums[0];

dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < len; ++i)

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

return dp[len - 1];

}

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

/ \

2 3

\ \

3 1

输出: 7

解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

/ \

4 5

/ \ \

1 3 1

输出: 9

解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class Threehundred_thirtySeven {
    /**
     * 总述：
     * 能盗取的最高金额为：max(抢劫该节点+抢劫该节点的左孩子的左右子树+抢劫该节点的右孩子的左右子树, 抢劫该节点的左子树+抢劫该节点的右子树)
     * <p>
     * 具体：
     * 方法helper(r)意为：在以r为根节点的树中,返回抢劫根节点与不抢劫根节点可获得的最大值的数组(res)
     * 数组res,长度为2,res[0]表示不抢该节点可获得最大值,res[1]表示抢劫该节点可获得最大值
     **/
    public int rob(TreeNode root) {
        int[] ans = helper(root);
        return ans[0] > ans[1] ? ans[0] : ans[1];
    }

    public int[] helper(TreeNode root) {
        int[] res = new int[2];
        if (root == null)
            return res;
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        //res[0]表示不抢root节点，所以左右子树随便抢(只需要抢与不抢根节点的最大值)。
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //res[1]表示抢root节点，但是左右子树的根节点(root.left, root.right)不能抢，所以要left[0]和right[0]
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

public class Threehundred_thirtySeven {

/**

* 总述：

* 能盗取的最高金额为：max(抢劫该节点+抢劫该节点的左孩子的左右子树+抢劫该节点的右孩子的左右子树, 抢劫该节点的左子树+抢劫该节点的右子树)

* <p>

* 具体：

* 方法helper(r)意为：在以r为根节点的树中,返回抢劫根节点与不抢劫根节点可获得的最大值的数组(res)

* 数组res,长度为2,res[0]表示不抢该节点可获得最大值,res[1]表示抢劫该节点可获得最大值

**/

public int rob(TreeNode root) {

int[] ans = helper(root);

return ans[0] > ans[1] ? ans[0] : ans[1];

}

public int[] helper(TreeNode root) {

int[] res = new int[2];

if (root == null)

return res;

int[] left = helper(root.left);

int[] right = helper(root.right);

//res[0]表示不抢root节点，所以左右子树随便抢(只需要抢与不抢根节点的最大值)。

res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

//res[1]表示抢root节点，但是左右子树的根节点(root.left, root.right)不能抢，所以要left[0]和right[0]

res[1] = root.val + left[0] + right[0];

return res;

}

单词拆分

1.单词拆分I LeetCode139

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true

解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。

注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

public class Onehundred_thirtyNine {
    public boolean wordBreak(String s, List<String> wordDict) {
        /**
         * dp[i]表示s中以i-1结尾的字符串是否可以被worddict拆分
         * **/
        if (s == null || s.length() == 0)
            return false;
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

public class Onehundred_thirtyNine {

public boolean wordBreak(String s, List<String> wordDict) {

/**

* dp[i]表示s中以i-1结尾的字符串是否可以被worddict拆分

* **/

if (s == null || s.length() == 0)

return false;

int len = s.length();

boolean[] dp = new boolean[len + 1];

dp[0] = true;

for (int i = 1; i <= len; i++) {

for (int j = 0; j < i; j++) {

if (dp[j] && wordDict.contains(s.substring(j, i))) {

dp[i] = true;

break;

}

return dp[len];

}

2.单词拆分II LeetCode140

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

输入:

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

输出:

[

"cats and dog",

"cat sand dog"

]

示例 2：

输入:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

输出:

[

"pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"

]

解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出:

[]

package gongel_second;

import java.util.ArrayList;
import java.util.List;

public class Onehundred_forty {
    /**
     * 先用139题的方法检测能否拆分，然后用dfs方法回溯
     */
    public List<String> ans = new ArrayList<>();

    public boolean judge(String s, List<String> wordDict) {
        if (s == null || s.length() == 0)
            return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public void dfs(String s, List<String> wordDict, List<String> temp) {
        if (s == null)
            return;
        for (String str : wordDict) {
            if (s.startsWith(str)) {
                if (s.length() == str.length()) {//最后一个词，说明拆分成功
                    temp.add(str);
                    String tem = String.join(" ", temp);
                    ans.add(tem);
                    temp.remove(temp.size() - 1);
//                    return;//这里不能直接return，否则会导致str不能被重复利用
                } else {
                    temp.add(str);
                    dfs(s.substring(str.length()), wordDict, temp);
                    temp.remove(temp.size() - 1);
                }

            }
        }
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (judge(s, wordDict))
            dfs(s, wordDict, new ArrayList<>());
        return ans;
    }
}

package gongel_second;

import java.util.ArrayList;

import java.util.List;

public class Onehundred_forty {

/**

* 先用139题的方法检测能否拆分，然后用dfs方法回溯

public List<String> ans = new ArrayList<>();

public boolean judge(String s, List<String> wordDict) {

if (s == null || s.length() == 0)

return false;

boolean[] dp = new boolean[s.length() + 1];

dp[0] = true;

for (int i = 1; i <= s.length(); i++) {

for (int j = 0; j < i; j++) {

if (dp[j] == true && wordDict.contains(s.substring(j, i))) {

dp[i] = true;

break;

}

return dp[s.length()];

}

public void dfs(String s, List<String> wordDict, List<String> temp) {

if (s == null)

return;

for (String str : wordDict) {

if (s.startsWith(str)) {

if (s.length() == str.length()) {//最后一个词，说明拆分成功

temp.add(str);

String tem = String.join(" ", temp);

ans.add(tem);

temp.remove(temp.size() - 1);

// return;//这里不能直接return，否则会导致str不能被重复利用

} else {

temp.add(str);

dfs(s.substring(str.length()), wordDict, temp);

temp.remove(temp.size() - 1);

}

public List<String> wordBreak(String s, List<String> wordDict) {

if (judge(s, wordDict))

dfs(s, wordDict, new ArrayList<>());

return ans;

}

股票买卖问题

1.买卖股票的最佳时机I LeetCode121

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

public class Onehundred_twentyOne {
    //前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
    //不用dp，直接用变量代替也行，因为每次之和前一个dp比较，并且最后只需要返回最后的dp数组的最后一个值
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0)
            return 0;
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            min = Math.min(min, prices[i]);
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
        }
        return dp[dp.length - 1];
    }
}

public class Onehundred_twentyOne {

//前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

//不用dp，直接用变量代替也行，因为每次之和前一个dp比较，并且最后只需要返回最后的dp数组的最后一个值

public int maxProfit(int[] prices) {

if(prices==null||prices.length==0)

return 0;

int[] dp = new int[prices.length];

dp[0] = 0;

int min = prices[0];

for (int i = 1; i < prices.length; ++i) {

min = Math.min(min, prices[i]);

dp[i] = Math.max(dp[i - 1], prices[i] - min);

}

return dp[dp.length - 1];

}

2.买卖股票的最佳时机II LeetCode122

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]

输出: 4

解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。

因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

//题解：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/
/**
*对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - *c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。
*/
public class Onehundred_twentyTwo {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; ++i) {
            if (prices[i + 1] > prices[i])
                profit += prices[i + 1] - prices[i];//第二天比第一天大就卖出获得收益
        }
        return profit;
    }
}

//题解：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/

/**

*对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - *c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。

public class Onehundred_twentyTwo {

public int maxProfit(int[] prices) {

int profit = 0;

for (int i = 0; i < prices.length - 1; ++i) {

if (prices[i + 1] > prices[i])

profit += prices[i + 1] - prices[i];//第二天比第一天大就卖出获得收益

}

return profit;

}

3.买卖股票的最佳时机III LeetCode123

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]

输出: 6

解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。

随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]

输出: 4

解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。

因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]

输出: 0

解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

public class Onehundred_twentyThree {
    public int maxProfit(int[] prices) {
        /**
         对于任意一天考虑四个变量:
         fstBuy: 在该天第一次买入股票可获得的最大收益
         fstSell: 在该天第一次卖出股票可获得的最大收益
         secBuy: 在该天第二次买入股票可获得的最大收益
         secSell: 在该天第二次卖出股票可获得的最大收益
         分别对四个变量进行相应的更新, 最后secSell就是最大
         收益值(secSell >= fstSell)
         **/
        int fstbuy = Integer.MIN_VALUE;//让初始化必须为0 - p
        int fstsell = 0;
        int secbuy = Integer.MIN_VALUE;//让初始化必须为fstsell - p
        int secsell = 0;
        for (int p : prices) {
            fstbuy = Math.max(fstbuy, 0 - p);//买入今天的股票p，则损失p；又因之前并没有收益，所以收益为0
            fstsell = Math.max(fstsell, fstbuy + p);//卖出今天的股票p，则收益增加p
            secbuy = Math.max(secbuy, fstsell - p);
            secsell = Math.max(secsell, secbuy + p);
        }
        return secsell;
    }
}

public class Onehundred_twentyThree {

public int maxProfit(int[] prices) {

/**

对于任意一天考虑四个变量:

fstBuy: 在该天第一次买入股票可获得的最大收益

fstSell: 在该天第一次卖出股票可获得的最大收益

secBuy: 在该天第二次买入股票可获得的最大收益

secSell: 在该天第二次卖出股票可获得的最大收益

分别对四个变量进行相应的更新, 最后secSell就是最大

收益值(secSell >= fstSell)

**/

int fstbuy = Integer.MIN_VALUE;//让初始化必须为0 - p

int fstsell = 0;

int secbuy = Integer.MIN_VALUE;//让初始化必须为fstsell - p

int secsell = 0;

for (int p : prices) {

fstbuy = Math.max(fstbuy, 0 - p);//买入今天的股票p，则损失p；又因之前并没有收益，所以收益为0

fstsell = Math.max(fstsell, fstbuy + p);//卖出今天的股票p，则收益增加p

secbuy = Math.max(secbuy, fstsell - p);

secsell = Math.max(secsell, secbuy + p);

}

return secsell;

}

4.买卖股票的最佳时机IV LeetCode188

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2

输出: 2

解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2

输出: 7

解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。

随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

public class Onehundred_eightyEight {
    public int maxProfit(int k, int[] prices) {
        /**
         1. 当k大于等于数组长度一半时, 问题退化为贪心问题此时采用 买卖股票的最佳时机 II;
         2. 对于其他的k, 可以采用 买卖股票的最佳时机 III;
         3. t[i][0]和t[i][1]分别表示第i比交易买入和卖出时各自的最大收益
         **/
        if (k < 1)
            return 0;

        //买卖股票的最佳时机 II
        if (k >= prices.length / 2) {
            int profit = 0;
            for (int i = 1; i < prices.length; ++i) {
                if (prices[i] > prices[i - 1])
                    profit += prices[i] - prices[i - 1];
            }
            return profit;
        }

        // 买卖股票的最佳时机 III
        int[][] t = new int[k][2];
        //初始化每次买入时的收益；每次卖出时的收益值自动化初始为0
        for (int i = 0; i < k; ++i) {
            t[i][0] = Integer.MIN_VALUE;//使得初始化每次买入时都为上次的卖出值减去p
        }
        for (int p : prices) {
            t[0][0] = Math.max(t[0][0], -p);
            t[0][1] = Math.max(t[0][1], t[0][0] + p);
            for (int i = 1; i < k; ++i) {
                t[i][0] = Math.max(t[i][0], t[i - 1][1] - p);
                t[i][1] = Math.max(t[i][1], t[i][0] + p);

            }
        }
        return t[k - 1][1];
    }
}

public class Onehundred_eightyEight {

public int maxProfit(int k, int[] prices) {

/**

1. 当k大于等于数组长度一半时, 问题退化为贪心问题此时采用买卖股票的最佳时机 II;

2. 对于其他的k, 可以采用买卖股票的最佳时机 III;

3. t[i][0]和t[i][1]分别表示第i比交易买入和卖出时各自的最大收益

**/

if (k < 1)

return 0;

//买卖股票的最佳时机 II

if (k >= prices.length / 2) {

int profit = 0;

for (int i = 1; i < prices.length; ++i) {

if (prices[i] > prices[i - 1])

profit += prices[i] - prices[i - 1];

}

return profit;

}

// 买卖股票的最佳时机 III

int[][] t = new int[k][2];

//初始化每次买入时的收益；每次卖出时的收益值自动化初始为0

for (int i = 0; i < k; ++i) {

t[i][0] = Integer.MIN_VALUE;//使得初始化每次买入时都为上次的卖出值减去p

}

for (int p : prices) {

t[0][0] = Math.max(t[0][0], -p);

t[0][1] = Math.max(t[0][1], t[0][0] + p);

for (int i = 1; i < k; ++i) {

t[i][0] = Math.max(t[i][0], t[i - 1][1] - p);

t[i][1] = Math.max(t[i][1], t[i][0] + p);

}

return t[k - 1][1];

}

5.最佳买卖股票时机含冷冻期 LeetCode309

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]

输出: 3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

public class Threehundred_nine {
    /**
     * buy[i]表示第i天买入时的最大利润（最后一个操作是买）
     * sell[i]表示第i天卖出时的最大利润（最后一个操作是卖）
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0)
            return 0;
        int[] buy = new int[n];
        int[] sell = new int[n];
        buy[0] = -prices[0];
        sell[0] = 0;
        if (n > 1) {
            buy[1] = Math.max(buy[0], 0 - prices[1]);//因为冷冻期，所以前一天只能为买，所以比较的是buy[0]=-prices[0],而大前天无买卖，所以利润为0，则得到0-prices[1]
            sell[1] = Math.max(sell[0], buy[0] + prices[1]);
        }
        for (int i = 2; i < n; ++i) {
            buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);//因为冷冻期，所以前一天只能为买，所以比较的是buy[i - 1]
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);//比较的是前一天卖出的最大利润和前一天买入的最大利润+今天卖出的价格
        }
        return sell[n - 1];
    }
}

public class Threehundred_nine {

/**

* buy[i]表示第i天买入时的最大利润（最后一个操作是买）

* sell[i]表示第i天卖出时的最大利润（最后一个操作是卖）

public int maxProfit(int[] prices) {

int n = prices.length;

if (n == 0)

return 0;

int[] buy = new int[n];

int[] sell = new int[n];

buy[0] = -prices[0];

sell[0] = 0;

if (n > 1) {

buy[1] = Math.max(buy[0], 0 - prices[1]);//因为冷冻期，所以前一天只能为买，所以比较的是buy[0]=-prices[0],而大前天无买卖，所以利润为0，则得到0-prices[1]

sell[1] = Math.max(sell[0], buy[0] + prices[1]);

}

for (int i = 2; i < n; ++i) {

buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);//因为冷冻期，所以前一天只能为买，所以比较的是buy[i - 1]

sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);//比较的是前一天卖出的最大利润和前一天买入的最大利润+今天卖出的价格

}

return sell[n - 1];

}

查询python第三方包的版本

>>> import nltk
>>> nltk.__version__
'3.3'

>>> import nltk

>>> nltk.__version__

'3.3'

关键字提取

# -*- coding: utf-8 -*-

import math

import jieba
import jieba.posseg as psg
from gensim import corpora, models
from jieba import analyse
import functools


# 停用词表加载方法
def get_stopword_list():
    # 停用词表存储路径，每一行为一个词，按行读取进行加载
    # 进行编码转换确保匹配准确率
    stopword_list = []
    stop_word_path = './data/stopword.txt'
    with open(stop_word_path, 'r', encoding="utf-8") as f:
        for line in f.readlines():
            stopword_list.append(line.replace("\n", ""))
    return stopword_list


# 分词方法，调用结巴接口
def seg_to_list(sentence, pos=False):
    if not pos:
        # 不进行词性标注的分词方法
        seg_list = jieba.cut(sentence)
    else:
        # 进行词性标注的分词方法
        seg_list = psg.cut(sentence)

    return seg_list


# 去除干扰词
def word_filter(seg_list, pos=False):
    stopword_list = get_stopword_list()
    filter_list = []
    # 根据POS参数选择是否词性过滤
    ## 不进行词性过滤，则将词性都标记为n，表示全部保留
    for seg in seg_list:
        if not pos:
            word = seg
            flag = 'n'
        else:
            word = seg.word
            flag = seg.flag
        if not flag.startswith('n'):
            continue
        # 过滤停用词表中的词，以及长度为<2的词
        if not word in stopword_list and len(word) > 1:
            filter_list.append(word)

    return filter_list


# 数据加载，pos为是否词性标注的参数，corpus_path为数据集路径
def load_data(pos=False, corpus_path='./data/corpus.txt'):
    # 调用上面方式对数据集进行处理，处理后的每条数据仅保留非干扰词
    doc_list = []
    for line in open(corpus_path, 'r', encoding="utf-8"):
        content = line.strip()
        # print("content:",content)
        seg_list = seg_to_list(content, pos)
        filter_list = word_filter(seg_list, pos)
        doc_list.append(filter_list)
    return doc_list


# idf值统计方法
def train_idf(doc_list):
    idf_dic = {}
    # 总文档数
    tt_count = len(doc_list)

    # 每个词出现的文档数
    for doc in doc_list:
        for word in set(doc):
            idf_dic[word] = idf_dic.get(word, 0.0) + 1.0

    # 按公式转换为idf值，分母加1进行平滑处理
    for k, v in idf_dic.items():
        idf_dic[k] = math.log(tt_count / (1.0 + v))

    # 对于没有在字典中的词，默认其仅在一个文档出现，得到默认idf值
    default_idf = math.log(tt_count / (1.0))
    return idf_dic, default_idf


#  排序函数，用于topK关键词的按值排序
def cmp(e1, e2):
    import numpy as np
    res = np.sign(e1[1] - e2[1])
    if res != 0:
        return res
    else:
        a = e1[0] + e2[0]
        b = e2[0] + e1[0]
        if a > b:
            return 1
        elif a == b:
            return 0
        else:
            return -1


# TF-IDF类
class TfIdf(object):
    # 四个参数分别是：训练好的idf字典，默认idf值，处理后的待提取文本，关键词数量
    def __init__(self, idf_dic, default_idf, word_list, keyword_num):
        self.word_list = word_list
        self.idf_dic, self.default_idf = idf_dic, default_idf
        self.tf_dic = self.get_tf_dic()
        self.keyword_num = keyword_num

    # 统计tf值
    def get_tf_dic(self):
        tf_dic = {}
        for word in self.word_list:
            tf_dic[word] = tf_dic.get(word, 0.0) + 1.0  # 该word不存在的话返回0

        tt_count = len(self.word_list)
        for k, v in tf_dic.items():
            tf_dic[k] = float(v) / tt_count

        return tf_dic

    # 按公式计算tf-idf
    def get_tfidf(self):
        tfidf_dic = {}
        for word in self.word_list:
            idf = self.idf_dic.get(word, self.default_idf)
            tf = self.tf_dic.get(word, 0)

            tfidf = tf * idf
            tfidf_dic[word] = tfidf

        tfidf_dic.items()
        # 根据tf-idf排序，去排名前keyword_num的词作为关键词
        for k, v in sorted(tfidf_dic.items(), key=functools.cmp_to_key(cmp), reverse=True)[:self.keyword_num]:
            print(k + "/ ", end='')
        print()


# 主题模型
class TopicModel(object):
    # 三个传入参数：处理后的数据集，关键词数量，具体模型（LSI、LDA），主题数量
    def __init__(self, doc_list, keyword_num, model='LSI', num_topics=4):
        # 使用gensim的接口，将文本转为向量化表示
        # 先构建词空间
        self.dictionary = corpora.Dictionary(doc_list)
        # 使用BOW模型向量化
        corpus = [self.dictionary.doc2bow(doc) for doc in doc_list]
        # 对每个词，根据tf-idf进行加权，得到加权后的向量表示
        self.tfidf_model = models.TfidfModel(corpus)
        self.corpus_tfidf = self.tfidf_model[corpus]

        self.keyword_num = keyword_num
        self.num_topics = num_topics
        # 选择加载的模型
        if model == 'LSI':
            self.model = self.train_lsi()
        else:
            self.model = self.train_lda()
        # 得到数据集的主题-词分布
        word_dic = self.word_dictionary(doc_list)
        self.wordtopic_dic = self.get_wordtopic(word_dic)

    def train_lsi(self):
        lsi = models.LsiModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)
        return lsi

    def train_lda(self):
        lda = models.LdaModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)
        return lda

    def get_wordtopic(self, word_dic):
        wordtopic_dic = {}
        for word in word_dic:
            single_list = [word]
            wordcorpus = self.tfidf_model[self.dictionary.doc2bow(single_list)]
            wordtopic = self.model[wordcorpus]
            wordtopic_dic[word] = wordtopic
        return wordtopic_dic

    # 词空间构建方法和向量化方法，在没有gensim接口时的一般处理方法
    def word_dictionary(self, doc_list):
        dictionary = []
        # print("doc_list:\n",doc_list)
        for doc in doc_list:
            dictionary.extend(doc)
            # print(dictionary)
        dictionary = list(set(dictionary))

        return dictionary

    def doc2bowvec(self, word_list):
        vec_list = [1 if word in word_list else 0 for word in self.dictionary]
        return vec_list


    # 计算词的分布和文档的分布的相似度，取相似度最高的keyword_num个词作为关键词
    def get_simword(self, word_list):
        sentcorpus = self.tfidf_model[self.dictionary.doc2bow(word_list)]
        senttopic = self.model[sentcorpus]

        # 余弦相似度计算
        def calsim(l1, l2):
            a, b, c = 0.0, 0.0, 0.0
            for t1, t2 in zip(l1, l2):
                x1 = t1[1]
                x2 = t2[1]
                a += x1 * x1
                b += x1 * x1
                c += x2 * x2
            sim = a / math.sqrt(b * c) if not (b * c) == 0.0 else 0.0
            return sim

        # 计算输入文本和每个词的主题分布相似度
        sim_dic = {}
        for k, v in self.wordtopic_dic.items():
            if k not in word_list:
                continue
            sim = calsim(v, senttopic)
            sim_dic[k] = sim

        for k, v in sorted(sim_dic.items(), key=functools.cmp_to_key(cmp), reverse=True)[:self.keyword_num]:
            print(k + "/ ", end='')
        print()


def tfidf_extract(word_list, pos=False, keyword_num=10):
    doc_list = load_data(pos)
    # print(doc_list)
    idf_dic, default_idf = train_idf(doc_list)
    tfidf_model = TfIdf(idf_dic, default_idf, word_list, keyword_num)
    tfidf_model.get_tfidf()  # 返回tf-idf排名前keyword_num的word


def textrank_extract(text, pos=False, keyword_num=10):
    textrank = analyse.textrank
    keywords = textrank(text, keyword_num)
    # 输出抽取出的关键词
    for keyword in keywords:
        print(keyword + "/ ", end='')
    print()


def topic_extract(word_list, model, pos=False, keyword_num=10):
    doc_list = load_data(pos)
    topic_model = TopicModel(doc_list, keyword_num, model=model)
    topic_model.get_simword(word_list)


if __name__ == '__main__':
    text = '6月19日,《2012年度“中国爱心城市”公益活动新闻发布会》在京举行。' + \
           '中华社会救助基金会理事长许嘉璐到会讲话。基金会高级顾问朱发忠,全国老龄' + \
           '办副主任朱勇,民政部社会救助司助理巡视员周萍,中华社会救助基金会副理事长耿志远,' + \
           '重庆市民政局巡视员谭明政。晋江市人大常委会主任陈健倩,以及10余个省、市、自治区民政局' + \
           '领导及四十多家媒体参加了发布会。中华社会救助基金会秘书长时正新介绍本年度“中国爱心城' + \
           '市”公益活动将以“爱心城市宣传、孤老关爱救助项目及第二届中国爱心城市大会”为主要内容,重庆市' + \
           '、呼和浩特市、长沙市、太原市、蚌埠市、南昌市、汕头市、沧州市、晋江市及遵化市将会积极参加' + \
           '这一公益活动。中国雅虎副总编张银生和凤凰网城市频道总监赵耀分别以各自媒体优势介绍了活动' + \
           '的宣传方案。会上,中华社会救助基金会与“第二届中国爱心城市大会”承办方晋江市签约,许嘉璐理' + \
           '事长接受晋江市参与“百万孤老关爱行动”向国家重点扶贫地区捐赠的价值400万元的款物。晋江市人大' + \
           '常委会主任陈健倩介绍了大会的筹备情况。'

    pos = True
    seg_list = seg_to_list(text, pos)
    # print("seg_list:", "/".join(["{}/{}".format(k, v) for k, v in seg_list]))
    filter_list = word_filter(seg_list, pos)
    # print("filter_list:\n", "/".join(filter_list))

    print('TF-IDF模型结果：')
    tfidf_extract(filter_list)
    print('TextRank模型结果：')
    textrank_extract(text)
    print('LSI模型结果：')
    topic_extract(filter_list, 'LSI', pos)
    print('LDA模型结果：')
    topic_extract(filter_list, 'LDA', pos)

'''
总结：

doc_list得到的是list的嵌套，因为每次按一行处理

TF-IDF模型:
对训练的语料库进行分词并且停用词过滤得到doc_list，然后对提取关键字的文本也进行分词并且停用词过滤得到filter_list，最后计算filter_list的tf-idf并返回排名前keyword_num的word
TextRank模型：
直接对提取关键字的文本（模型输入值为文本）直接进行提取
LSI/LDA模型:
对训练的语料库进行分词并且停用词过滤得到doc_list，然后对提取关键字的文本也进行分词并且停用词过滤得到filter_list，
'''

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

# -*- coding: utf-8 -*-

import math

import jieba

import jieba.posseg as psg

from gensim import corpora, models

from jieba import analyse

import functools

# 停用词表加载方法

def get_stopword_list():

# 停用词表存储路径，每一行为一个词，按行读取进行加载

# 进行编码转换确保匹配准确率

stopword_list = []

stop_word_path = './data/stopword.txt'

with open(stop_word_path, 'r', encoding="utf-8") as f:

for line in f.readlines():

stopword_list.append(line.replace("\n", ""))

return stopword_list

# 分词方法，调用结巴接口

def seg_to_list(sentence, pos=False):

if not pos:

# 不进行词性标注的分词方法

seg_list = jieba.cut(sentence)

else:

# 进行词性标注的分词方法

seg_list = psg.cut(sentence)

return seg_list

# 去除干扰词

def word_filter(seg_list, pos=False):

stopword_list = get_stopword_list()

filter_list = []

# 根据POS参数选择是否词性过滤

## 不进行词性过滤，则将词性都标记为n，表示全部保留

for seg in seg_list:

if not pos:

word = seg

flag = 'n'

else:

word = seg.word

flag = seg.flag

if not flag.startswith('n'):

continue

# 过滤停用词表中的词，以及长度为<2的词

if not word in stopword_list and len(word) > 1:

filter_list.append(word)

return filter_list

# 数据加载，pos为是否词性标注的参数，corpus_path为数据集路径

def load_data(pos=False, corpus_path='./data/corpus.txt'):

# 调用上面方式对数据集进行处理，处理后的每条数据仅保留非干扰词

doc_list = []

for line in open(corpus_path, 'r', encoding="utf-8"):

content = line.strip()

# print("content:",content)

seg_list = seg_to_list(content, pos)

filter_list = word_filter(seg_list, pos)

doc_list.append(filter_list)

return doc_list

# idf值统计方法

def train_idf(doc_list):

idf_dic = {}

# 总文档数

tt_count = len(doc_list)

# 每个词出现的文档数

for doc in doc_list:

for word in set(doc):

idf_dic[word] = idf_dic.get(word, 0.0) + 1.0

# 按公式转换为idf值，分母加1进行平滑处理

for k, v in idf_dic.items():

idf_dic[k] = math.log(tt_count / (1.0 + v))

# 对于没有在字典中的词，默认其仅在一个文档出现，得到默认idf值

default_idf = math.log(tt_count / (1.0))

return idf_dic, default_idf

# 排序函数，用于topK关键词的按值排序

def cmp(e1, e2):

import numpy as np

res = np.sign(e1[1] - e2[1])

if res != 0:

return res

else:

a = e1[0] + e2[0]

b = e2[0] + e1[0]

if a > b:

return 1

elif a == b:

return 0

else:

return -1

# TF-IDF类

class TfIdf(object):

# 四个参数分别是：训练好的idf字典，默认idf值，处理后的待提取文本，关键词数量

def __init__(self, idf_dic, default_idf, word_list, keyword_num):

self.word_list = word_list

self.idf_dic, self.default_idf = idf_dic, default_idf

self.tf_dic = self.get_tf_dic()

self.keyword_num = keyword_num

# 统计tf值

def get_tf_dic(self):

tf_dic = {}

for word in self.word_list:

tf_dic[word] = tf_dic.get(word, 0.0) + 1.0 # 该word不存在的话返回0

tt_count = len(self.word_list)

for k, v in tf_dic.items():

tf_dic[k] = float(v) / tt_count

return tf_dic

# 按公式计算tf-idf

def get_tfidf(self):

tfidf_dic = {}

for word in self.word_list:

idf = self.idf_dic.get(word, self.default_idf)

tf = self.tf_dic.get(word, 0)

tfidf = tf * idf

tfidf_dic[word] = tfidf

tfidf_dic.items()

# 根据tf-idf排序，去排名前keyword_num的词作为关键词

for k, v in sorted(tfidf_dic.items(), key=functools.cmp_to_key(cmp), reverse=True)[:self.keyword_num]:

print(k + "/ ", end='')

print()

# 主题模型

class TopicModel(object):

# 三个传入参数：处理后的数据集，关键词数量，具体模型（LSI、LDA），主题数量

def __init__(self, doc_list, keyword_num, model='LSI', num_topics=4):

# 使用gensim的接口，将文本转为向量化表示

# 先构建词空间

self.dictionary = corpora.Dictionary(doc_list)

# 使用BOW模型向量化

corpus = [self.dictionary.doc2bow(doc) for doc in doc_list]

# 对每个词，根据tf-idf进行加权，得到加权后的向量表示

self.tfidf_model = models.TfidfModel(corpus)

self.corpus_tfidf = self.tfidf_model[corpus]

self.keyword_num = keyword_num

self.num_topics = num_topics

# 选择加载的模型

if model == 'LSI':

self.model = self.train_lsi()

else:

self.model = self.train_lda()

# 得到数据集的主题-词分布

word_dic = self.word_dictionary(doc_list)

self.wordtopic_dic = self.get_wordtopic(word_dic)

def train_lsi(self):

lsi = models.LsiModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)

return lsi

def train_lda(self):

lda = models.LdaModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)

return lda

def get_wordtopic(self, word_dic):

wordtopic_dic = {}

for word in word_dic:

single_list = [word]

wordcorpus = self.tfidf_model[self.dictionary.doc2bow(single_list)]

wordtopic = self.model[wordcorpus]

wordtopic_dic[word] = wordtopic

return wordtopic_dic

# 词空间构建方法和向量化方法，在没有gensim接口时的一般处理方法

def word_dictionary(self, doc_list):

dictionary = []

# print("doc_list:\n",doc_list)

for doc in doc_list:

dictionary.extend(doc)

# print(dictionary)

dictionary = list(set(dictionary))

return dictionary

def doc2bowvec(self, word_list):

vec_list = [1 if word in word_list else 0 for word in self.dictionary]

return vec_list

# 计算词的分布和文档的分布的相似度，取相似度最高的keyword_num个词作为关键词

def get_simword(self, word_list):

sentcorpus = self.tfidf_model[self.dictionary.doc2bow(word_list)]

senttopic = self.model[sentcorpus]

# 余弦相似度计算

def calsim(l1, l2):

a, b, c = 0.0, 0.0, 0.0

for t1, t2 in zip(l1, l2):

x1 = t1[1]

x2 = t2[1]

a += x1 * x1

b += x1 * x1

c += x2 * x2

sim = a / math.sqrt(b * c) if not (b * c) == 0.0 else 0.0

return sim

# 计算输入文本和每个词的主题分布相似度

sim_dic = {}

for k, v in self.wordtopic_dic.items():

if k not in word_list:

continue

sim = calsim(v, senttopic)

sim_dic[k] = sim

for k, v in sorted(sim_dic.items(), key=functools.cmp_to_key(cmp), reverse=True)[:self.keyword_num]:

print(k + "/ ", end='')

print()

def tfidf_extract(word_list, pos=False, keyword_num=10):

doc_list = load_data(pos)

# print(doc_list)

idf_dic, default_idf = train_idf(doc_list)

tfidf_model = TfIdf(idf_dic, default_idf, word_list, keyword_num)

tfidf_model.get_tfidf() # 返回tf-idf排名前keyword_num的word

def textrank_extract(text, pos=False, keyword_num=10):

textrank = analyse.textrank

keywords = textrank(text, keyword_num)

# 输出抽取出的关键词

for keyword in keywords:

print(keyword + "/ ", end='')

print()

def topic_extract(word_list, model, pos=False, keyword_num=10):

doc_list = load_data(pos)

topic_model = TopicModel(doc_list, keyword_num, model=model)

topic_model.get_simword(word_list)

if __name__ == '__main__':

text = '6月19日,《2012年度“中国爱心城市”公益活动新闻发布会》在京举行。' + \

'中华社会救助基金会理事长许嘉璐到会讲话。基金会高级顾问朱发忠,全国老龄' + \

'办副主任朱勇,民政部社会救助司助理巡视员周萍,中华社会救助基金会副理事长耿志远,' + \

'重庆市民政局巡视员谭明政。晋江市人大常委会主任陈健倩,以及10余个省、市、自治区民政局' + \

'领导及四十多家媒体参加了发布会。中华社会救助基金会秘书长时正新介绍本年度“中国爱心城' + \

'市”公益活动将以“爱心城市宣传、孤老关爱救助项目及第二届中国爱心城市大会”为主要内容,重庆市' + \

'、呼和浩特市、长沙市、太原市、蚌埠市、南昌市、汕头市、沧州市、晋江市及遵化市将会积极参加' + \

'这一公益活动。中国雅虎副总编张银生和凤凰网城市频道总监赵耀分别以各自媒体优势介绍了活动' + \

'的宣传方案。会上,中华社会救助基金会与“第二届中国爱心城市大会”承办方晋江市签约,许嘉璐理' + \

'事长接受晋江市参与“百万孤老关爱行动”向国家重点扶贫地区捐赠的价值400万元的款物。晋江市人大' + \

'常委会主任陈健倩介绍了大会的筹备情况。'

pos = True

seg_list = seg_to_list(text, pos)

# print("seg_list:", "/".join(["{}/{}".format(k, v) for k, v in seg_list]))

filter_list = word_filter(seg_list, pos)

# print("filter_list:\n", "/".join(filter_list))

print('TF-IDF模型结果：')

tfidf_extract(filter_list)

print('TextRank模型结果：')

textrank_extract(text)

print('LSI模型结果：')

topic_extract(filter_list, 'LSI', pos)

print('LDA模型结果：')

topic_extract(filter_list, 'LDA', pos)

'''

总结：

doc_list得到的是list的嵌套，因为每次按一行处理

TF-IDF模型:

对训练的语料库进行分词并且停用词过滤得到doc_list，然后对提取关键字的文本也进行分词并且停用词过滤得到filter_list，最后计算filter_list的tf-idf并返回排名前keyword_num的word

TextRank模型：

直接对提取关键字的文本（模型输入值为文本）直接进行提取

LSI/LDA模型:

对训练的语料库进行分词并且停用词过滤得到doc_list，然后对提取关键字的文本也进行分词并且停用词过滤得到filter_list，

'''

月份：2019年4月

打家劫舍

198. 打家劫舍

213. 打家劫舍 II

337. 打家劫舍 III

单词拆分

1.单词拆分I LeetCode139

2.单词拆分II LeetCode140

股票买卖问题

1.买卖股票的最佳时机I LeetCode121

2.买卖股票的最佳时机II LeetCode122

3.买卖股票的最佳时机III LeetCode123

4.买卖股票的最佳时机IV LeetCode188

5.最佳买卖股票时机含冷冻期 LeetCode309

查询python第三方包的版本

关键字提取

文本主题模型之潜在语义索引(LSI)

2019年四月
一	二	三	四	五	六	日
« 3月				5月 »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30