头像

JAVA小老弟


访客:3973

离线:3天前




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];
    }
}


活动打卡代码 AcWing 1574. 接雨水


import java.io.BufferedReader;
import java.io.*;

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]);
        String line2[] = r.readLine().split(" ");
        int[] arr = new int[n+2];
        for (int i = 1; i <=n ; i++) {
            arr[i] = Integer.valueOf(line2[i-1]);
        }

        int[] left = new int[n+10];
        int[] right = new int[n+10];

        int[] stk = new int[10010];
        int tt = 0;
        stk[0] = -1;

// 找到左边 最大的数 不用是第一个最大的数 所以这个栈只需要不断的加入 不需要删除
        for (int i = 1; i <=n ; i++) {
            if(stk[tt]<arr[i]){
// 可以往栈顶加元素
                left[i] = -1;
                stk[++tt] = arr[i];
            }            
            //如果加不了 
            else{
                left[i] = stk[tt];
            }

        }

        tt = 0;
        stk[0] = -1;
        for (int i = n; i >=1 ; i--) {
            if(stk[tt]<arr[i]){
                right[i] = -1;
                stk[++tt] = arr[i];
            }
            else{
                right[i] = stk[tt];
            }

        }

        int res = 0;
        for (int i = 1; i <=n ; i++) {

            if(left[i]!=-1 && right[i]!=-1){


                res = res + (Math.min(left[i],right[i])-arr[i]);
            }
        }
        System.out.println(res);
    }
}



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.LinkedList;
import java.util.List;

public class Main{
    static int n;
    static int[] arr;
    static int[] used;
    static List<Integer> res = new ArrayList<>();
    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]);
        arr = new int[n];
        used = new int[n];
        String line2[] = r.readLine().split(" ");
        for (int i = 0; i <n ; i++) {
            arr[i] = Integer.parseInt(line2[i]);
        }
        Arrays.sort(arr);
        dfs(0);
    }

    public static void dfs(int x){
        if(x==n){
            for (int i = 0; i <n ; i++) {
                System.out.print(res.get(i)+" ");
            }
            System.out.println();
            return;
        }
//这里下标从0开始 为的就是每个可能都遍历一次 字典序最小  这种做法9过不去
        for (int i = 0; i <n ; i++) {
            if(i!=0 && arr[i-1]==arr[i] && used[i-1]==0)
                continue;
            if(used[i]==0){
                used[i]=1;
                res.add(arr[i]);
                dfs(x+1);
                used[i]=0;
                res.remove(res.size()-1);
            }
        }
    }
}



class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
       List<List<Integer>> res = new ArrayList<>();
       for(int i=1;i<sum;i++){
           for(int j=i+1;j<sum;j++){
               int val = (i+j)*(j-i+1)/2;
               if(val==sum){
                   List<Integer> temp = new ArrayList<>();
                   for(int begin = i;begin<=j;begin++){
                       temp.add(begin);
                   }
                   res.add(new ArrayList<>(temp));
               }
               else if(val>sum){
                   break;
               }
               else{
                   continue;
               }
           }
       }
       return res;
    }
}



class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        if(k==0 || nums.length==0)
            return new int[]{};
        int[] tp = new int[10010];
        int left =0;
        int right = -1;
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            //滑出队头 left++
            if(i-k+1>tp[left])
                left++;
            // 当队列还满组条件且 还可以进行一个队列的插入 构建一个递减队列的时候 right--
            while(left<=right && nums[tp[right]]<=nums[i])
                right--;
            //找好位置进行插入
            tp[++right] = i;
            //如果窗口开始滑过0 则开始输出元素
            if(i-k+1>=0)
                res.add(nums[tp[left]]);
        }

        int[] result = new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i] = res.get(i);
        }
        return result;
    }
}


活动打卡代码 AcWing 1259. 二叉树遍历

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

public class Main{
    static int[] used = new int[40];
    static String res="";

    public static void dfs(Node root){
        if(root==null)
            return ;
        res = res + root.val;
        dfs(root.left);
        dfs(root.right);
        return ;
    }
    public static void main(String args[]) throws IOException{
        BufferedReader r= new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        String inorder = line[0];
        String line2[] = r.readLine().split(" ");
        String loader = line2[0];

        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<inorder.length();i++)
            map.put(inorder.charAt(i),i);

        Node[] queue = new Node[30];
        queue[0] = new Node(loader.charAt(0));
        for(int i =0,j=1;j<loader.length();){//i是当前的起点  j是下一层开始的起点 下一层起点的位置一开始是1  后面的话会变动i 也是
            for(int end = j;i<end;i++){//遍历当前结点的左右子树是不是都存在 遍历位置为i到j-1 先做备份end 否则j会变动
                //先输出在中序遍历中的位置
                int position = map.get(loader.charAt(i));//得到当前元素在中序遍历中的位置
                used[position] = 1;//已经使用
                if(position-1>=0 && used[position-1]==0){//查找中序遍历中左元素和右元素是不是被使用过 
                    queue[i].left = new Node(loader.charAt(j));//没有被使用过 添加层次遍历的下一个元素
                    queue[j++] = queue[i].left;//并且将该元素添加到 队列中
                }
                if(position +1<loader.length() && used[position+1]==0){
                    queue[i].right = new Node(loader.charAt(j));
                    queue[j++] = queue[i].right;
                }
            }
        }

        dfs(queue[0]);
        System.out.println(res);
    }
}

class Node{
    char val;
    Node left;
    Node right;
    public Node(char val){
        this.val = val;
    }
}