头像

JAVA小老弟




离线:4天前




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

public class Main{
    static int[] used;
    static int n;
    static int m;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        n =  Integer.valueOf(line[0]);
        m = Integer.valueOf(line[1]);
        arr = new int[n];
        String line2[] = r.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(line2[i]);
        }
        used = new int[n+10];
        Arrays.sort(arr);
        dfs(0,0);
    }

    public static void dfs(int x,int y){
        // 当选择的数字太多的时候也直接return
        if(y>m)
            return;
        if(y==m){
            for (int i = 0; i <n; i++) {
                if(used[i]==1)
                    System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }
        if(x>=n)
            return ;

        int k = x;
        int sum = y;
        // 先尽可能选择小的数字 保持字典序
        while(k<n && arr[x]==arr[k]){
            used[k] = 1;
            k++;
            sum++;
        }

        dfs(k,sum);
        // 然后一个个去掉
        for (int i = k-1; i >=x ; i--) {
            used[i] = 0;
            sum--;
            dfs(k,sum);
        }







    }
}




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

public class Main{
    static int n;
    static int m;
    static int[] used ;
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        n = Integer.valueOf(line[0]);
        m = Integer.valueOf(line[1]);
        used= new int[n+2];
        // 起点从第一个数字开始 0 代表当前已经选中的数字
        dfs(1,0);

    }

    public static void dfs(int x,int y){
        // 当前已经选中了m个数字
        if(y==m){
            for (int i = 1; i <=n ; i++) {
                if(used[i]==1)
                    System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
        // 超过界限说明所有的数字已经遍历完了
        if(x>n)
            return;
        // 使用当前数字
        used[x] = 1;
        dfs(x+1,y+1);
        used[x] = 0;
        // 不适用当前数字
        dfs(x+1,y);
    }
}


活动打卡代码 AcWing 885. 求组合数 I



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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader r=  new BufferedReader(new InputStreamReader(System.in));
        String line[] =r.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        int mod = (int)(Math.pow(10,9)+7);

        int[][] dp = new int[2010][2010];
        for (int i = 0; i <2010 ; i++) {
            for (int j = 0; j <=i ; j++) {
                // 当j==0 的时候==1
                if(j==0)
                    dp[i][j] = 1;
                else
                // 其他情况下 在i个苹果里取j个 有两种可能 i-1个取j个 或者 i-1个里取j-1个
                    dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])%mod;
            }
        }
        for (int i = 0; i <n ; i++) {
            String line2[] = r.readLine().split(" ");
            int a = Integer.valueOf(line2[0]);
            int b = Integer.valueOf(line2[1]);
            System.out.println(dp[a][b]);
        }
    }
}



package test;

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

public class main1{
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        for (int i = 0; i <n ; i++) {
            String line2[] = r.readLine().split(" ");
            long a = Integer.valueOf(line2[0]);
            long b = Integer.valueOf(line2[1]);
            long c = Integer.valueOf(line2[2]);
            System.out.println(find(a,b,c));
        }
    }

    public static long find(long x,long y,long z){
        long result = 1;
        long a = x;
        while(y!=0){
            if((int)(y&1)==1){
                result = (result * a) % z;
            }
            y =y>>1;
            a = a * a;
        }
        return result;
    }
}


活动打卡代码 AcWing 791. 高精度加法


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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        String line2[] = r.readLine().split(" ");
        String str1 = line[0];
        String str2 = line2[0];

        int max_length = Math.max(str1.length(),str2.length());
        // 给两个字符串补前缀0 补到长度相同
        if(str1.length()<max_length){
            int n = max_length-str1.length();
            for (int i = 0; i <n ; i++) {
                str1 = "0"+str1;
            }
        }
        else{
            int n = max_length-str2.length();
            for (int i = 0; i <n ; i++) {
                str2 = "0"+str2;
            }
        }
// 开辟数组威max_length+1 多一位怕进位
        int[] res = new int[max_length+1];
        int index = max_length;
        int pos = 0;
        for (int i = max_length-1; i >=0 ; i--) {
            int val = str1.charAt(i)-'0'+str2.charAt(i)-'0'+pos;
            pos = (val>=10)?1:0;
            res[index--] = val%10;
        }
        if(pos ==1)
            res[0] = 1;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i <=max_length ; i++) {
            if(i==0 ){
                if(res[i]==1)
                    sb.append(res[i]);
            }
            else
                sb.append(res[i]);
        }
        System.out.println(sb.toString());
    }
}




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

public class Main{
    static int[][] g;
    static int[] used=new int[100100];
    static int n;
    static int m;
    static int[] dis;
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String line[]=r.readLine().split(" ");
        n=Integer.valueOf(line[0]);
        m=Integer.valueOf(line[1]);

        g=new int[510][510];
        // 先用邻接表存储
        for (int i = 0; i <510 ; i++) {
            for (int j = 0; j <510 ; j++) {
                g[i][j]=0x3f3f3f;
            }
        }
        dis=new int[100100];
        for (int i = 0; i <m ; i++) {
            String line1[]=r.readLine().split(" ");
            int u=Integer.valueOf(line1[0]);
            int v=Integer.valueOf(line1[1]);
            int w=Integer.parseInt(line1[2]);
            // 将最小的进行存储
            g[u][v]=g[v][u]=Math.min(g[v][u],w);
        }

        int res=prim();
        if(res==0x3f3f3f)
            System.out.println("impossible");
        else
            System.out.println(res);
    }

    public static int prim(){
        int res=0;

        // 点到集合的距离定义为正无穷
        Arrays.fill(dis,0x3f3f3f);

        for (int i = 1; i <=n ; i++) {
            // 遍历从1-n  因为需要加入n个点
            int t=-1;// 标志一下是不是可以找到下一个更新的点
            //找到一个到集合距离是最短的点t 用t去更新到集合的距离
            for (int j = 1; j <=n ; j++) {
                if(used[j]==0 && (t==-1 || dis[t]>dis[j])) {
                    t = j;
                }
            }
            //如果这个点不存在的话 将第一次给排除出去 因为第一次总是特殊的
            if((i!=1 )&& (dis[t]==0x3f3f3f))
                return 0x3f3f3f;
            //当不是起点的时候 生成树权重++

            if(i!=1)
                res+=dis[t];
            //新加入了一个点 看看能不能更新距离 为下次寻找离集合最近的点做准备
            for (int j = 1; j <=n ; j++) {
                dis[j]=Math.min(dis[j],g[t][j]);
            }
            used[t]=1;
            System.out.println(t);
        }
        return res;
    }



}


活动打卡代码 AcWing 104. 货仓选址

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String s[]=r.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        String line[]=r.readLine().split(" ");
        int[] arr=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=Integer.parseInt(line[i]);
        }
        int res=0;
        Arrays.sort(arr);
            // 取中位数作为货舱的选址地方
            for (int i = 0; i <n/2 ; i++) {
                res+=arr[n-i-1]-arr[i];
            }
            System.out.println(res);



        }

}



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        if(root==null)
            return res;
        boolean flag = false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int n = queue.size();

        while(n!=0){
            List<Integer> temp = new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode tempnode = queue.poll();
                if(tempnode.left!=null)
                    queue.add(tempnode.left);
                if(tempnode.right!=null)
                    queue.add(tempnode.right);
                // 通过flag变量去控制之
                if(flag)
                    temp.add(0,tempnode.val);
                else
                    temp.add(tempnode.val);

            }
            flag =!flag;
            res.add(new LinkedList<>(temp));
            n = queue.size();
        }
        return res;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplication(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        // 记住概念 不要记住代码
        // p代表着当前新链表的摩羯点  而q代表着有可能成为插入的起点
        ListNode q = head;
        while(q!=null){
            if(q!=null && q.next!=null && q.val==q.next.val){
                while(q!=null && q.next !=null && q.val==q.next.val){
                    q = q.next;
                }
                q= q.next;
                p.next = q;
            }
            else{
                p .next = q;
                p = p.next;
                q =q.next;
            }
        }
        return dummy.next;
    }
}


活动打卡代码 AcWing 62. 丑数

class Solution {
    public int getUglyNumber(int n) {
        if(n==1)
            return 1;
        int[] arr = new int[10010];
        int i =1;
        int j=1;
        int k = 1;
        int index =1;
        arr[1] = 1;
        while(index!=n){
            int res = Math.min(arr[i]*2,arr[j]*3);
            res = Math.min(arr[k]*5,res);
            if(res == arr[i]*2) i++;
            if(res == arr[j]*3) j++;
            if(res == arr[k]*5) k++;
            arr[++index] = res;
        }
        return arr[index];
    }
}