头像

单箭头


访客:8380

离线:10个月前



单箭头
2019-06-10 05:47

java 代码

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();
        MergeSort(arr,0,n-1);
        for(int i=0;i<n;i++)
            System.out.print(arr[i]+" ");
    }
    private static void MergeSort(int[] arr,int l,int r){
        if(l>=r) return;
        int mid=(l+r)/2;
        MergeSort(arr,l,mid);
        MergeSort(arr,mid+1,r);
        merge(arr,l,r);
    }
    private static void merge(int[] arr,int l,int r){
        int mid=(l+r)/2;
        int[] tmp=new int[r-l+1];
        int i=l,j=mid+1,k=0;
        while(i<=mid && j<=r){
            tmp[k++]=arr[i]>=arr[j]?arr[j++]:arr[i++];
        }
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=r) tmp[k++]=arr[j++];
        i=0;
        while(l<=r){
            arr[l++]=tmp[i++];
        }
    } 
}



单箭头
2019-06-10 05:46

java 代码

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();

        quickSort(arr,0,n-1);
        for(int i=0;i<n;i++)
            System.out.print(arr[i]+" ");
    }
    private static void quickSort(int[] arr,int l,int r){
        int start=l,end=r;
        int base=arr[l];
        while(l<r){
            while(l<r && arr[r]>=base) r--;
            arr[l]=arr[r];
            while(l<r && arr[l]<=base) l++;
            arr[r]=arr[l];
        }
        arr[l]=base;
        if(l>start) quickSort(arr,start,l-1);
        if(end>l) quickSort(arr,r+1,end);
    }
}



单箭头
2019-06-10 05:45

java 代码

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();
        arr=buildMaxHeap(arr,n);//构建大根堆
        for(int i=n-1;i>0;i--){
            int tmp=arr[i];
            arr[i]=arr[0];
            arr[0]=tmp;
            adjustDownToUp(arr,0,i);//自底向上,将最大元素调整位置
        }
        for(int i=0;i<m;i++)
            System.out.print(arr[i]+" ");
    }
    private static int[] buildMaxHeap(int[] arr,int n){
        for(int i=(n-1-1)/2;i>=0;i--)
            adjustDownToUp(arr,i,n);
        return arr;
    }
    private static void adjustDownToUp(int[] arr,int  k,int length){
        int tmp=arr[k];
        for(int i=2*k+1;i<length;i=2*i+1){
            if(i+1<length && arr[i+1]>arr[i]) i++;//取两个子节点的较大值
            if(tmp>arr[i]) break;
            else{
                arr[k]=arr[i];//交换结点
                k=i;
            }
        }
        arr[k]=tmp;
    }
}



单箭头
2019-05-16 14:02

java 代码

public class 气球游戏 {
    /**
     * 使用滑动窗口求解
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int[] colors=new int[n];
        for (int i=0;i<n;i++) {
            colors[i]=sc.nextInt();
        }
        int res=minWindow(colors,m);
        System.out.println(res);
    }
    private static int minWindow(int[] nums,int m){
        int cnt=m;//判断是否包含所有颜色
        int[] dict=new int[m+1];//记录颜色出现的次数
        for (int i=1;i<=m;i++){
            dict[i]++;
        }
        int begin=0,end=0;
        int width=Integer.MAX_VALUE;
        while (end<nums.length){
            int endNum=nums[end++];
            if (dict[endNum]-->0)
                cnt--;
            while (cnt==0){
                if (end-begin<width)
                    width=end-begin;
                int beginNum=nums[begin++];
                if (dict[beginNum]++==0)
                    cnt++;
            }
        }
        return width==Integer.MAX_VALUE?-1:width;
    }
}




单箭头
2019-05-16 13:01

java 代码

public class 串01 {
    /**
     * 两个思路:一个是使用栈,一个是直接只要01个数相同那必然就消完了
     * @param args
     */
    public static void main1(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        char[] chars=sc.nextLine().trim().toCharArray();
        Stack<Character> stack=new Stack<>();
        stack.push(chars[0]);
        for(int i=1;i<n;i++){
            while (!stack.isEmpty()&& i<n && chars[i]!=stack.peek()){
                stack.pop();
                i++;
            }
            if (i<n) stack.push(chars[i]);
        }
        System.out.println(stack.isEmpty()?0:stack.size());
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        char[] chars=sc.nextLine().trim().toCharArray();
        int zero=0,one=0;
        for (int i=0;i<n;i++){
            if (chars[i]=='0') zero++;
            else one++;
        }
        System.out.println(Math.abs(zero-one));
    }
}



单箭头
2019-05-15 01:21

java 代码

public class 括号序列 {
    private static final int mod=1000000007;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        char[] str1=sc.nextLine().trim().toCharArray();
        char[] str2=sc.nextLine().trim().toCharArray();
        int[] cnt1=new int[str1.length+1];
        int[] cnt2=new int[str2.length+1];
        Valid(cnt1,str1);
        Valid(cnt2,str2);
        //如果两个合并后不是合法的,那就不用合并了
        if(cnt1[str1.length]+cnt2[str2.length]!=0) System.out.println(0);
        else {
            //dp(i,j):就是第一个序列的前i个括号,与第二个序列的前j个括号,交错组成的合法括号序列个数
            int[][] dp=new int[str1.length+1][str2.length+1];
            for(int i=0;i<=str1.length;i++){
                for (int j=0;j<=str2.length;j++){
                    //初始化
                    if(i==0 && j==0) dp[i][j]=1;
                    else {
                        if(cnt1[i]+cnt2[j]>=0){
                            if(i>0) dp[i][j]+=dp[i-1][j];
                            if (j>0) dp[i][j]+=dp[i][j-1];
                            dp[i][j]%=mod;
                        }
                    }
                }
            }
            System.out.println(dp[str1.length][str2.length]);
        }
    }
    private static void Valid(int[] cnt,char[] chars){
        for(int i=0;i<chars.length;i++){
            if (chars[i] == '(') {
                cnt[i+1]=cnt[i]+1;
            }else cnt[i+1]=cnt[i]-1;
        }
    }
}
/**
 * 类型题思路总结:
 * 对于括号序列,如果将左括号看做1,右括号看做-1,那么合法序列必然满足:
 * ① 从左向右遍历过程中,和cnt>=0;
 * ② 遍历结束后,和cnt=0.
 * 然后对于合法括号序列,一般都是使用栈来进行处理,左括号入栈,遇到右括号出栈,最后判断栈是否为空
 */



单箭头
2019-05-14 14:40

java 代码

package com.company.ForTruth.拼夕夕;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.io.*;

public class 避嫌抢劫 {
    static class bank{
        int location,money;
        public bank(int a,int b){
            this.location=a;
            this.money=b;
        }
    }

    /**
     * 暴力必然超时
     * @param args
     */
    public static void main1(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),d=sc.nextInt();
        bank[] banks=new bank[n];
        for (int i=0;i<n;i++){
            banks[i]=new bank(sc.nextInt(),sc.nextInt());
        }
        int res=0;
        for(int i=0;i<banks.length;i++){
            for(int j=i+1;j<banks.length;j++){
                if(Math.abs(banks[i].location-banks[j].location)>=d)
                    res=Math.max(res,banks[i].money+banks[j].money);
            }
        }
        System.out.println(res);
    }

    /**
     * 这个是对于双指针做法的普遍优化,这里有一个遍历条件就是距离要大于等于d,所以将位置按照升序排序,
     * 就是只要遍历i以及i前面的银行,找到最大钱就可以。这个就是双指针做法优化的模板。
     * 这里说一下,这个代码AC不AC全凭运气,有时候超时有时候就AC了,最后检查出来原因在于对于输入数据的读取
     * @param args
     */
    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), d = sc.nextInt();
        bank[] banks = new bank[n];
        for (int i = 0; i < n; i++) {
            banks[i] = new bank(sc.nextInt(), sc.nextInt());
        }
        int res=0,curMax = 0, j = -1;
        // 按位置升序排序
        Arrays.sort(banks, Comparator.comparing(bank -> bank.location));
        for(int i=0;i<banks.length;++i){
            while (j+1<i && Math.abs(banks[i].location-banks[j+1].location)>=d){
                ++j;
                curMax = Math.max(curMax, banks[j].money);
            }
            res = Math.max(res, curMax + banks[i].money);
        }
        System.out.println(res);
    }

    /**
     * 换了输入数据的读取就完全A,百度了下看到是Scanner的平均耗时是BufferedReader的10倍左右
     * @param input
     * @return
     */
    private static int[] stringToint(String input) {
        String[] parts = input.trim().split(" ");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] firstLine = stringToint(br.readLine().trim());
        int n = firstLine[0], d = firstLine[1];
        bank[] banks = new bank[n];

        for (int i = 0; i < n; ++i) {
            String line = br.readLine();
            if (line == null || line.length() == 0)
                break;
            int[] num = stringToint(line);
            banks[i] = new bank(num[0], num[1]);
        }

        int res=0,curMax = 0, j = -1;
        // 按位置升序排序
        Arrays.sort(banks, Comparator.comparing(bank -> bank.location));
        for(int i=0;i<banks.length;++i){
            while (j+1<i && Math.abs(banks[i].location-banks[j+1].location)>=d){
                ++j;
                curMax = Math.max(curMax, banks[j].money);
            }
            res = Math.max(res, curMax + banks[i].money);
        }
        System.out.println(res);
    }
}





单箭头
2019-05-14 14:03

java 代码

public class 趣味字母卡片 {
    /**
     * 这个题目就是每次事实上不知道到底去除其重复字母前面的那个还是后面的那个,是一个变化的。所以如果不断去判断去除不去除很麻烦,
     * 那就暴力遍历。直接a~z开始遍历,假设a,先对于字符串中的字符进行统计次数,然后如果a前面的字母均可以被去除,即均a前面的字母
     * 出现次数是大于1的。并且在遍历到a那个位置为止,并不是全部出现完了。
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine().toLowerCase();
        char[] chars=str.toCharArray();
        HashMap<Character,Integer> map=new HashMap<>();
        for(char c:chars){
            if(!map.keySet().contains(c)) map.put(c,1);
            else map.put(c,map.get(c)+1);
        }
        boolean T=false;
        for(char c='a';c<='z';c++){
            HashMap<Character,Integer> map1=new HashMap<>(map);
            if(!map1.keySet().contains(c)) continue;
            for(int i=0;i<chars.length;i++){
                char t=chars[i];
                if(t==c) {
                    T=true;
                    break;
                }
                if(map1.get(t)==1) break;
                map1.put(t,map1.get(t)-1);
            }
            if (T) {
                System.out.println(c);
                break;
            }
        }
    }
}




单箭头
2019-05-14 12:52

java 代码

public class 爱健身的小王 {
    /**
     * 这个做法是请恕我脑子有坑去暴力做,遍历虽然AC
     * @param args
     */
    public static void main1(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            boolean[] res=new boolean[4*n];
            int m=0,cnt=0;
            while (res[m+n+1]!=true){
                m=m+n+1;
                res[m]=true;
                cnt+=1;
                if(m+n+1>4*n-1){
                    m-=(4*n);
                }
            }
            System.out.println(cnt+1);
        }
    }

    private static int gcd(int x,int y){
        return y==0?x:gcd(y,x%y);
    }
    /**
     * 这个是最小公约数的,时间上是比暴力短的
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
            int n = sc.nextInt();
            int d=gcd(4*n,n+1);
            int res=4*n/d+1;
            System.out.println(res);
        }
    }
}




单箭头
2019-05-12 14:15

java 代码

//import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> stack=new LinkedList<>();
        stack.offer(root);
        boolean T= true;
        int cnt=1,tmp=0;
        List<Integer> list=new ArrayList<>();
        while(!stack.isEmpty()){
            TreeNode cur=stack.poll();
            if(T) list.add(cur.val);
            else list.add(0,cur.val);
            cnt--;
            if(cur.left!=null) {
                stack.offer(cur.left);
                tmp++;
            }
            if(cur.right!=null) {
                stack.offer(cur.right);
                tmp++;
            }
            if(cnt==0){
                cnt=tmp;
                tmp=0;
                res.add(list);
                list=new ArrayList<>();
                T=!T;
            }
        }
        return res;
    }
}