头像

熊本熊本熊




离线:2020-10-31 04:32


最近来访(18)
用户头像
998
用户头像
郫县林俊杰
用户头像
rizon
用户头像
summer_409
用户头像
达达_3
用户头像
刷题冲冲冲
用户头像
37_50
用户头像
anji
用户头像
秋_
用户头像
zombotany
用户头像
贝尔
用户头像
JING._6
用户头像
遥か
用户头像
Lakers23
用户头像
小志不言弃
用户头像
CCPC菜狗
用户头像
王开心wkx
用户头像
点点豆豆


熊本熊本熊
2019-06-25 14:07

看这里没有K数之和的模板,这里提供一个,已经把 LeetCode的 4数之和,3数之和 都AC了。

emmm, 讲道理啊,速度不怎么样,嘤嘤嘤,毕竟是递归。

但是胜在方便理解 K数之和 系列问题,而且简单粗暴。代码看起来貌似很长,其实有用的就两块:

  • 一个是最基础的 二数之和 问题,这里用的是双指针法(K_Sum_Recursive_Template 里的 if 部分)
  • 然后就是递归部分,递归直到变成 二数之和 问题(K_Sum_Recursive_Template 里的 else 部分)

这里提供了一个贼简单的接口:kSum(int[] nums, int target, int k),复制上去就可以用。

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class K_Sum_Recursive {
    /**
     * 我是一个接口,在系统提供的他们的方法里面调用我即可
     * 
     * 相当加了一层包装,对外提供了一个系统可以使用的接口
     * @param nums 系统给定的数组
     * @param target 系统要求的目标值
     * @return 系统要求的返回值
     */
    public List<List<Integer>> kSum(int[] nums, int target, int k) {
        // 先排序,这个是必须的。
        Arrays.sort(nums);

        // 根据模板方法的要求,将该方法需要的输入都准备好。
        int[] stack = new int[k];
        Arrays.fill(stack, 0x3f3f3f3f);
        int stack_index = -1;
        int begin = 0;
        // 递归开始
        List<List<Integer>> ans = K_Sum_Recursive_Template(nums, stack, stack_index, k, begin, target);
        // 递归结束,返回解
        return ans;
    }

    /**
     * K数之和问题的模板方法,所有K数问题都可以调用这个方法
     * @param nums 输入的数组
     * @param stack 定义的一个长度为 k_sum 问题中的 k 的数组,初始化为0x3f3f3f3f
     * @param stack_index 栈指针,初始化值为-1
     * @param k 表明当前问题被 分解/递归 成了 k数之和 的问题
     * @param begin 当前问题要固定的值的起点
     * @param target 当前 k数之和 的目标和
     * @return 当前 k数之和 的解集,要在上一层合并到最终解集里去
     */
    private List<List<Integer>> K_Sum_Recursive_Template(int[] nums, int[] stack, int stack_index, int k, int begin, int target){
        List<List<Integer>> ans = new ArrayList<>();

        // 当递归到两数之和的时候,不再进行递归,直接使用左右指针法解决
        if(k == 2){
            List<Integer> temp_ans;

            int left = begin;
            int right = nums.length - 1;

            while(left < right){
                if(nums[left] + nums[right] > target){
                    // 过大,因此右指针左移
                    right--;
                }else if(nums[left] + nums[right] < target){
                    // 过小,因此左指针右移
                    left++;
                }else {
                    // 相等,加入序列中,左右指针同时向内移动一次
                    temp_ans = new ArrayList<>();
                    stack[++stack_index] = nums[left];
                    stack[++stack_index] = nums[right];

                    // 当前栈中的元素符合题目要求, 将其加入到List中去,并将该List加入到当前问题的解集中
                    for(int i = 0; i <= stack_index; i++){
                        temp_ans.add(stack[i]);
                    }
                    ans.add(temp_ans);

                    // 栈的清理工作,其实不做也可以,因为栈指针属于形参,不会影响外面的那个栈指针,
                    // 但是还是清理掉比较好,方便调试。
                    stack[stack_index--] = 0x3f3f3f3f;
                    stack[stack_index--] = 0x3f3f3f3f;

                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    while (right > left && right < nums.length - 1 && nums[right] == nums[right + 1]){
                        right--;
                    }
                }
            }
        }else {
            int target_temp;
            for(int i = begin; i < nums.length - k + 1; i++){
                if(i > begin && nums[i] == nums[i - 1]){
                    continue;
                }
                // 在固定一个数后,问题被降级为一个 k - 1 数之和 问题
                // 确定 k - 1 数之和 的目标和
                target_temp = target - nums[i];
                // 将当前选定的数字压入栈中,便于最后加入解集中
                stack[++stack_index] = nums[i];
                // 递归调用 k - 1 数之和 问题的求解
                List<List<Integer>> ans_temp = K_Sum_Recursive_Template(nums,stack, stack_index, k - 1, i + 1, target_temp);
                // 在选定当前数字的情况下, k - 1 数之和 问题求解完毕,
                // 将该数弹出栈,为选择下一个被选值做准备
                stack[stack_index--] = 0x3f3f3f3f;
                // 将当前解集加入当前 k数之和的解集中
                ans.addAll(ans_temp);
            }
        }
        return ans;
    }

    public static void test(){
        K_Sum_Recursive solution = new K_Sum_Recursive();
        int [] input = {0,0,0,0};
        int k = 4;
        int target = 0;
        solution.kSum(input, target, k);
    }
}



活动打卡代码 AcWing 568. 奇妙的数列

熊本熊本熊
2019-05-18 02:29

前面这两道题真的是,全是数学题,用了算法反而因为虚拟机的限制搞不出来,emmm,会爆堆
顺手把输入模板弄出来,唉,心累,Java的输入真的是心累

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

    String[] test = br.readLine().split(" ");
    a = Integer.valueOf(test[0]);
    b = Integer.valueOf(test[1]);
}

下面是代码

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Main{
    // public int[] pre;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        // Scanner reader = new Scanner(System.in);
        // int n = reader.nextInt();
        // int max_end = 0;
        int[] begin = new int[n];
        int[] end = new int[n];
        for(int i = 0; i < n; i++){
            String[] test = br.readLine().split(" ");
            begin[i] = Integer.valueOf(test[0]);
            end[i] = Integer.valueOf(test[1]);

            // begin[i] = reader.nextInt();
            // end[i] = reader.nextInt();
            // max_end = Math.max(max_end, begin[i]);
            // max_end = Math.max(max_end, end[i]);
        }
        Main Solution = new Main();
//        Solution.generate_arrays(max_end);

        for(int i = 0; i < n; i++){
            System.out.println(Solution.range_plus_2(begin[i], end[i]));
        }

    }

    // public void generate_arrays(int max_end){
    //     pre = new int[max_end + 1];
    //     for(int i = 1; i <= max_end; i++){
    //         if((i&1) == 1){
    //             // 奇数
    //             pre[i] = pre[i-1] + i - 1;
    //         }else{
    //             // 偶数
    //             pre[i] = pre[i-1] - i + 1;
    //         }
    //     }
    // }

    // public int range_plus(int l, int r){
    //     int ans = pre[r] - pre[l];
    //     if((r&1) == 1){
    //         // 右边为奇数
    //         ans -= r;
    //     }else{
    //         // 为偶数
    //         ans += r;
    //     }
    //     return ans;
    // }

    public int range_plus_2(int l, int r){
        int ans = 0;
        if((l&1) == 1){
            // 左为奇数
            if((r&1) == 1){
                // 右为奇数
                ans = (r-l)/2;
                ans -= r;
            }else{
                // 右为偶数
                ans = (r-l+1)/2;
            }
        }else{
            // 左为偶数
            if((r&1) == 1){
                // 右为奇数
                ans = (r-l + 1)/2;
                ans *= -1;
            }else{
                // 右为偶数
                ans = (r-l)/2;
                ans *= -1;
                ans += r;
            }
        }
        return ans;
    }

}


活动打卡代码 AcWing 567. 硬币

熊本熊本熊
2019-05-18 01:32
import java.util.Scanner;
import java.util.Arrays;

class Main{
    public static void main(String[] args){

        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int m = reader.nextInt();
        int ans = coin_change_2(n,m);
        System.out.print(ans);
    }
    // DP版完全背包问题
    public static int coin_change(int n, int m){
        int[] dp = new int[m + 1];
        Arrays.fill(dp, 0x3f3f3f3f);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= m; j++){
                dp[j] = Math.min(dp[j],dp[j-i] + 1);
            }
        }
        return dp[m];
    }
    // 简单版
    public static int coin_change_2(int n, int m){
        int ans = 0;
        for(int i = n; i >=1; i--){
            ans += m/i;
            m = m%i;
            if(m < n){
                i = m+1;
            }
        }
        return ans;
    }
}



熊本熊本熊
2019-05-17 09:19

现在这个是对的了,emmm (20190520)

我的想法是这样的:
此时已经把银行按照距离排序过了。
劫匪A,B从左边开始遍历每个银行,A用一个变量记录他造访过的银行里,最富有的有多少钱,B用一个变量记录,他如果打劫他面前的银行,再加上A访问过的银行里最富有的那家银行,最高能打劫多少钱;
这里,A只负责造访银行,每次由B来决定要不要打劫

大致规则就在上面,然后代码如下

private int rob_1(Bank[] banks, int d){
    int cur_max_money = 0;
    int n = banks.length;
    int ans = 0;
    int left = 0; int right = 1;
    // 先把右指针拉到第一个满足题目要求的点,然后开始遍历
    while(right < n && banks[right].location - banks[left].location < d){
        right++;
    }

    while(right < n){
        // 右指针不能越界
        while(left < right && banks[right].location - banks[left].location >= d){
            // 此时左点和右点之间的距离满足要求,同时,左边所有的点都和右边这个点之间距离满足要求
            // 该while循环保证了抢劫 1. right当前指向的银行 2. 包括left在内的 左边的任意一家银行 的所有方案是合法的

            // 更新一下左边银行最多的钱
            cur_max_money = Math.max(cur_max_money, banks[left].money);
            left++;
        }
        // 此时left距离right过近,right继续向右遍历
        // 这时,跟新一下最后的解
        // 即当前银行的钱加上前面满足要求的银行的钱的最高值
        ans = Math.max(ans, cur_max_money + banks[right].money);
        right++;
    }
    return ans;
}


(之前的遗留内容,已废弃,20190520)
我想了一下应该没问题啊,但是就是过不了,而且还容易超时,emmm,麻烦各位大佬帮我看一下这个思路有啥问题




熊本熊本熊
2019-05-17 06:07

之前怎么也想不明白最大公约数的解法,终于想清楚了,顺便写出来,万一有人需要呢,对吧。

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Main Solution = new Main();
        int t=sc.nextInt();
        int ans;
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            // 调用方法1
            ans = Solution.solution_2(n);
            // 调用方法2

            System.out.println(ans);
        }
    }
    /**
     * 暴力法
    */
    private int solution_1(int n){

        int N = 4*n;
        boolean[] mark=new boolean[N];
        // 首先把起点标记一下
        mark[0] = true;
        int m=0,ans=1;
        // 循环查找下一个标记的点
        while (mark[(m+n+1)%N] != true){
            m += n+1;
            m = m%N;
            mark[m]=true;
            ans++;
        }
        // 加上最后一次重复标记的点
        return ans + 1;
    }
    /**
     * 最大公约数的解法
    */

    private int solution_2(int n){
        int d=gcd(4*n, n+1);
        int ans=(4*n)/d;
        return ans + 1;
    }

    public int gcd(int a, int b){
        int r;
        while(b != 0){
            r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

}

最大公约数解法的解释:

首先,第一次重合的点一定是起点。

Why?由于小王必须从起点出发,假设我们第一次重合的点是A点,即A点一定要被打卡两次,也就是说,一定存在一条路径,是从 起点->A点(第一次到达) 的。

假设我们再一次到达了A点,训练结束。那么,也一定还存在一条路径,是从起点(再一次遇见)->A(再一次打卡)的,即,要想到达A点,就一定会先过起点。这样就说明,起点一定是比A点更早的重复打卡,即:A点是最早重合的点,这个假设不成立。

然后,就是打卡多少次的问题了。

由于一定是要走圈的整数倍,所以可以easy得到一个等式, $x \cdot ( 4 * n ) = y \cdot ( n + 1 )$ 这里的这个y就是我们要的答案。要使得y最小,即要求 $y \cdot ( n + 1 )$ 等于 4*nn+1的最小公倍数。设g为最大公约数,h为最小公倍数,则有: $[ (4 * n) \cdot ( n+1 ) ] = g * h$ , 且 $h = y \cdot ( n + 1 )$

则答案为:$y = \frac{[ (4 * n) \cdot ( n+1 ) ]}{g \cdot (n+1)} = \frac{4*n}{g}$

同样的,这里的最终答案忘了计算起点(第一次打卡),所以要加1




熊本熊本熊
2019-05-16 13:58

最大公约数可以用辗转相除法来求, 辗转相除法 。此外,还可以使用效率更高的Stein算法,但是实现也更麻烦,有兴趣的同学可以看看Stein算法
最小公倍数 = 两数乘积 除以 两数的最大公约数

最大公约数:

public int gcd(int a, int b){
    int r;
    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

最小公倍数

public int lcm(int a, int b){
    return a*b/gcd(a,b);
}


活动打卡代码 AcWing 90. 64位整数乘法

熊本熊本熊
2019-05-16 03:46
/*
求 a 乘 b 对 p 取模的值。

输入格式
第一行输入整数a,第二行输入整数b,第三行输入整数p。

输出格式
输出一个整数,表示a*b mod p的值。

数据范围
1≤a,b,p≤1018
输入样例:
3
4
5
输出样例:
2
*/
import java.util.Scanner;


public class Main{
    public static void main(String[] args){
        Main solution = new Main();
        Scanner reader = new Scanner(System.in);
        long a = reader.nextLong();
        long b = reader.nextLong();
        long p = reader.nextLong();
        long ans = solution.a_add_b(a,b,p);
        System.out.println(ans);
    }

    public long a_add_b(long a, long b, long p){
        long ans = 0; long k = a;
        while (b > 0){
            if( (b&1) == 1){
                ans += k;
                ans = ans%p;
            }
            k = k*2;
            k = k%p;
            b = b>>1;
        }
        ans = ans%p;
        return ans;
    }
}



熊本熊本熊
2019-05-16 02:58
import java.util.Scanner;


public class Main{
    public static void main(String[] args){
        Main solution = new Main();
        Scanner reader = new Scanner(System.in);
        int a = reader.nextInt();
        int b = reader.nextInt();
        int p = reader.nextInt();
        int ans = solution.a_power_b(a,b,p);
        System.out.println(ans);
    }

    public int a_power_b(int a, int b, int p){
        // 一种基本的方法就是简单的按照a^b的方法累乘,但是这样计算的时间复杂度是O(n)的,如果b很大的话,会超时
        // 一种优化方法是,按照b的二进制来累乘,计算出b的二进制表达,然后将其分解为2的幂相加的形式,然后计算出a^(2^n),
        // 这样可以将时间复杂度降低到log(N)

        // 这里必须使用long类型,不然对于某些比较大的数会溢出
        long ans = 1; long k = a;
        while (b > 0){
            if( (b&1) == 1){
                ans *= k;
                ans = ans%p;
            }
            k = k*k;
            // 这里没事也来模一下,乘数模几次没问题,最后的结果还是对的,
            // 我记得我在哪有一个证明来着,忘了,
            k = k%p;
            b = b>>1;
        }
        ans = ans%p;
        return (int)ans;
    }
}



熊本熊本熊
2019-05-15 13:39

如上一个题解所说,这个是并查集的入门题目,但是貌似没有人给出java的代码,因此这里写一个Java题解,权当抛砖引玉

首先定义并查集的模板

class Union_Find_Set{
    ArrayList<Integer> father = new ArrayList<>();
    int SIZE = 0;
    public Union_Find_Set(int size){
        this.SIZE = size;
        for(int i = 0; i < size; i++){
            father.add(i);
        }
    }

    public int find(int x) {
        // 递归版本
        if (x == father.get(x)) {
            return father.get(x);
        }
        // 递归寻找父节点
        int ans = find(father.get(x));
        // 找到结点之后,顺手把路径压缩一下,把根·父节点更新为这条链上所有结点的父节点,
        //免得后面还要这样递归来查
        father.set(x, ans);
        return ans;
    }

    // 非递归版本用的比较少,所以设置为private
    private int Find(int x){
        // 非递归版本
        while (father.get(x) != x){
            // 如果当前结点的父节点不是自己的话,就去查询他的父节点
            x = father.get(x);
        }
        // 当当前节点的父节点就是自己,说明找到了
        return x;
    }

    public void union(int a, int b){
        // 把两个不相交的集合合并为同一个集合
        // 这里把默认a小于b,这样可以避免形成环,
        // 不然可能形成a的父节点是b,b的父节点是a的情况,然后find的时候陷入死循环
        // 这里可能还存在没考虑到的情况,请提出,或者等我想清楚了再回来修改,23333
        // 但是对于这道题没问题
        // 第一次修改时间:2019-05-15
        int father_a = find(a);
        int father_b = find(b);
        father.set(father_b, father_a);
    }

    public boolean isInSameSet(int a, int b){
        return find(a) == find(b);
    }

    public int NumOfSet(){
    // 返回整个集合中现有的不相交的集合个数
        int ans = 0;
        for(int i =0; i < this.SIZE; i++){
            if(father.get(i) == i){
                ans++;
            }
        }
        return ans;
    }
}

然后是题目的代码:

public class Solution_547 {
    private class Union_Find_Set{
        ArrayList<Integer> father = new ArrayList<>();
        int SIZE = 0;
        public Union_Find_Set(int size){
            this.SIZE = size;
            for(int i = 0; i < size; i++){
                father.add(i);
            }
        }

        public int find(int x) {
            // 递归版本
            if (x == father.get(x)) {
                return father.get(x);
            }
            // 递归寻找父节点
            int ans = find(father.get(x));
            // 找到结点之后,顺手把路径压缩一下,把根-父节点更新为这条链上所有结点的直接父节点,免得后面还要这样递归来查
            father.set(x, ans);
            return ans;
        }

        // 非递归版本用的比较少,所以设置为private
        private int Find(int x){
            // 非递归版本
            while (father.get(x) != x){
                // 如果当前结点的父节点不是自己的话,就去查询他的父节点
                x = father.get(x);
            }
            // 当当前节点的父节点就是自己,说明找到了
            return x;
        }

        public void union(int a, int b){
            // 把两个不相交的集合合并为同一个集合
            int father_a = find(a);
            int father_b = find(b);
            father.set(father_b, father_a);
        }

        public boolean isInSameSet(int a, int b){
            return find(a) == find(b);
        }

        public int NumOfSet(){
            int ans = 0;
            for(int i =0; i < this.SIZE; i++){
                if(father.get(i) == i){
                    ans++;
                }
            }
            return ans;
        }
    }
    public int findCircleNum(int[][] M) {
        int N = M.length;
        Union_Find_Set set = new Union_Find_Set(N);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(M[i][j] == 1 && !set.isInSameSet(i,j)){
                    set.union(i, j);
                }
            }
        }
        return set.NumOfSet();
    }
}



熊本熊本熊
2019-05-15 03:42

刚看到这道题的时候没理解,想不出来,后来有人说跟leetcode316题有点像,感觉那个题目的描述清楚得多
我看题解里没人用递归的方法,这里提供一个,抛砖引玉

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Main solution = new Main();
        Scanner reader = new Scanner(System.in);
        String input = reader.next();
        char ans = solution.main(input);
        System.out.println(ans);

    }

    public char main(String input){
        if(input == null || input.length() == 0){
            return ' ';
        }
        if(input.length() == 1){
            return input.charAt(0);
        }
        input = input.toLowerCase();
        char ans = solution(new StringBuilder(input));
        return ans;
    }

    private char solution(StringBuilder input){
        String find = input.substring(0,1);
        int find_index = input.lastIndexOf(find);
        if(input.length() == 1 || input.lastIndexOf(input.substring(0,1))== 0){
            // 边界条件,即字符串被切分到不能再切分了,只剩一个了,
            // 或者说当前字符串的首字符在剩下的字符串里没有重复出现了,就返回当前字符
            return input.charAt(0);
        }
        // 当前字符在后续字符串中重复出现了,所以这里可以分为两种情况,比较一下哪种的字典序更小,然后返回

        // 1. 删掉后面出现的当前字符,然后把剩下的部分丢入递归继续判断
        //    但是其实不用再判断了,这一段字符串能出现的最小字典序就是当前字符
        char ans1 = input.charAt(0);
        // 2. 删掉当前字符,然后把剩下的部分递归继续判断
        char ans2 = solution(input.deleteCharAt(input.indexOf(input.substring(0,1))));

        return ans1 < ans2 ? ans1 : ans2;
    }
}