头像

我爱大雪菜

HKUST


访客:10185

离线:4小时前



能被整除的数

import java.util.Scanner;

public class Main {
    static int N = 20;
    static int p[] = new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for(int i = 0 ; i < m ; i ++) p[i] = scanner.nextInt();
        int res = 0;
        for(int i = 1; i < 1<<m; i ++) {//枚举每一种方案
            long t = 1,s = 0;//s用来记录这种方案,选择的数的个数,从而判断应该加还是减;t存累乘的结果
            for(int j = 0; j < m ; j ++) {
                if((i>>j&1)==1) {
                    if(t*p[j]>n) {//这里要加long 否则会溢出
                        t = -1;
                        break;
                    }
                    t *= p[j];
                    s++;
                }//为这种方案求出一个总乘积t
            }
            if(t!=-1) {
                if(s%2==1) res += n/t;//奇数个数,说明要加
                else res -= n/t;//偶数个数,说明要减
            }
        }
        System.out.println(res);
    }
}


活动打卡代码 LeetCode 139. Word Break

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {

        const int N = s.size();
        unordered_set<string> dict;
        bool dp[N + 1];

        memset(dp, false, sizeof dp);

        for (auto x : wordDict) {
            dict.insert(x);    
        }

        dp[0] = true;

        for (int i = 1; i <= N; i ++ ) {
            for (int j = 0; j < i; j ++ ) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[N];
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, vector<int> &res) {
        if (!root) return;
        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }


    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        dfs(root, res);
        return res[k - 1];
    }
};



题目描述

约数个数

C++ 代码

import java.io.*;
import java.util.*;

class Main{

    // int  mod = 1e9 + 7;
    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        //用来存所有 primes 里的约数个数. 
        Map<Integer, Integer> primes = new HashMap<>();

        while(n-->0){

            //当前需要求约数的数
            int cur = Integer.parseInt(in.readLine());

            for(int i = 2; i<= cur/i; i++){
                int cnt = 0;
                while(cur % i == 0){
                    cnt ++ ; //当前 i的约数个数++
                    cur/=i; //更新当前数
                }
                // 当前 约数i的个数. + cnt.
                primes.put(i, primes.getOrDefault(i,0)+ cnt);
            }
            // 当前数为被除尽. 那么最后一个约数则等于 当前数
            if(cur > 1) primes.put(cur, primes.getOrDefault(cur,0)+1);
        }

        long res = 1l;
        //每一个 alpha + 1 相乘 % 1e9 + 7. 
        for(Integer prime : primes.keySet()) res = res*(primes.get(prime)+1)%1000000007;
        System.out.println(res);
    }
}



题目描述

试除法求约数 -

时间复杂度

O(sqrt(n))

JAVA 代码

import java.io.*;
import java.util.*;

class Main{
    static void get_divisor(int x){
        //TreeSet 是二差树实现的,Treeset中的数据是自动排好序的,不允许放入null值
        Set<Integer> s = new TreeSet<Integer>();

        for(int i=1; i<=x/i; i++){
            //如果是约数.
            if(x%i==0){
                s.add(i);
                //得到另一个约数
                if(x/i!=i) s.add(x/i);//如果x/i = i 那么只放一次. 
            }
        }
        for(Integer cur: s){
            System.out.print(cur+" ");
        }
        System.out.println();
    }

    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        while(n-->0){
            int num = Integer.parseInt(in.readLine());
            get_divisor(num);
        }
    }
}



题目描述

kmp

参考的 巨鹿同学的代码.
灰常详细.
https://www.acwing.com/activity/content/code/content/230785/

java 代码

import java.util.Scanner;
public class Main{
    static int N = 10010;
    static int ne[] = new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        char[] a1 = (" "+scanner.nextLine()).toCharArray();
        int m = scanner.nextInt();
        scanner.nextLine();
        char[] a2 = (" "+scanner.nextLine()).toCharArray();
        /**
         * ne[]:存储一个字符串以每个位置为结尾的‘可匹配最长前后缀’的长度。
         * 构建ne[]数组:
         *              1,初始化ne[1] = 0,i从2开始。
         *              2,若匹配,s[i]=s[j+1]说明1~j+1是i的可匹配最长前缀,ne[i] = ++j;
         *              3,若不匹配,则从j的最长前缀位置+1的位置继续与i比较
         *              (因为i-1和j拥有相同的最长前后缀,我们拿j的前缀去对齐i-1的后缀),
         *              即令j = ne[j],继续比较j+1与i,若匹配转->>2
         *              4,若一直得不到匹配j最终会降到0,也就是i的‘可匹配最长前后缀’的长度
         *              要从零开始重新计算
         */
        for(int i = 2,j = 0;i <= n ;i++) {
            while(j!=0&&a1[i]!=a1[j+1]) j = ne[j]; 
            if(a1[i]==a1[j+1]) j++;
            ne[i] = j;
        }
        /**
         * 匹配两个字符串:
         *      1,从i=1的位置开始逐个匹配,利用ne[]数组减少比较次数
         *      2,若i与j+1的位置不匹配(已知1~j匹配i-j~i-1),
         *      j跳回ne[j]继续比较(因为1~j匹配i-j~i-1,所以1~ne[j]也能匹配到i-ne[j]~i-1)
         *      3,若匹配则j++,直到j==n能确定匹配成功
         *      4,成功后依然j = ne[j],就是把这次成功当成失败,继续匹配下一个位置
         */
        for(int i = 1,j = 0; i <= m;i++) {
            while(j!=0&&a2[i]!=a1[j+1]) j = ne[j];
            if(a2[i]==a1[j+1]) j++;
            if(j==n) {
                j = ne[j];
                System.out.print(i-n+" ");
            }
        }
        /**
         * 时间复杂度:
         *      因为:j最多加m次,再加之前j每次都会减少且最少减一,j>0
         *      所以:while循环最多执行m次,若大于m次,j<0矛盾
         *      最终答案:O(2m)
         */
    }
}



活动打卡代码 LeetCode 542. 01 Matrix

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> dis(n, vector<int>(m, -1));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0) {
                    dis[i][j] = 0;
                    q.push({i, j});
                }

        while (!q.empty()) {
            pair<int, int> sta = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = sta.first + dx[i], y = sta.second + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || dis[x][y] != -1)
                    continue;

                dis[x][y] = dis[sta.first][sta.second] + 1;
                q.push(make_pair(x, y));
            }
        }

        return dis;
    }
};



class Solution {
public:
    vector<vector<bool>> st;
    int n, m;

    void solve(vector<vector<char>>& board) {
        if (board.empty()) return;
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i ++ )
        {
            vector<bool> temp;
            for (int j = 0; j < m; j ++ )
                temp.push_back(false);
            st.push_back(temp);
        }

        for (int i = 0; i < n; i ++ )
        {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (board[i][m - 1] == 'O') dfs(i, m - 1, board);
        }
        for (int i = 0; i < m; i ++ )
        {
            if (board[0][i] == 'O') dfs(0, i, board);
            if (board[n - 1][i] == 'O') dfs(n - 1, i, board);
        }

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (!st[i][j])
                    board[i][j] = 'X';
    }

    void dfs(int x, int y, vector<vector<char>>&board)
    {
        st[x][y] = true;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && board[a][b] == 'O')
                dfs(a, b, board);
        }
    }
};




class Solution {
public:
    int minCut(string s) {

        int n = s.size();
        vector<vector<int>> c(n + 1, vector<int> (n + 1, false));

        for (int i = 1; i <= n; i ++ ) {
            for (int j = 0; j + i - 1 < n; j ++ ) {
                int l = j, r = j + i - 1;
                c[l][r] = s[l] == s[r] && (l + 1 > r - 1 || c[l + 1][r - 1]);
            }
        }


        vector<int> f(n + 1, 0);

        for (int i = 1; i <= n; i ++ ) {
            f[i] = INT_MAX;
            for (int j = 1; j <= i; j ++ ) {
                if (c[j - 1][i - 1]) {
                    f[i] = min(f[j - 1] + 1, f[i]);
                }
            }
        }

        return f[n] - 1;
    }
};




class Solution {
public:
    int numDistinct(string s, string t) {

        int n = s.size(), m = t.size();

        vector<vector<long long>> f(n + 1, vector<long long> (m + 1, 0));

        for (int i = 0; i <= n; i ++ ) f[i][0] = 1;

        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1]) f[i][j] += f[i - 1][j - 1];
            }
        }

        return f[n][m];

    }
};