算法练习题

算法练习题

算法题

回文判定二分：分巧克力二分：跳石头前缀和：灵能传输贪心练习题：翻硬币贪心练习题：最大最小公倍数

回文判定

public class Main{
    public static void main(String[] args){
      Scanner sc=new Scanner(System.in);
      String s=sc.nextLine();
      StringBuffer sb=new StringBuffer();
      sb.append(s);//StringBuffer的拼接相当于放到连续的数组
      sb.reverse();//StringBuffer的字符反转方法
      String ss=sb.toString();//反转的字符转成字符串与原字符对比
      if(s.equals(ss)){
        System.out.print("Y");
      }else{
        System.out.print("N");
      }
    }
}

二分：分巧克力

开始d的范围是1~最大边长D，就试试中间值D/2，如果这个值大了，就把范围缩小为 0D/2，如过这个值小了，就把范围缩小到D/2/D；第二次，取D/4试试…直到合适的为止

java

import java.util.Scanner;

public class Main{
private static int  N=100001;
public static void main(String[] args){
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int k=sc.nextInt();
  int []h=new int[N];
  int []w=new int[N];
  for(int i=1;i<=n;i++){
      h[i]=sc.nextInt();
      w[i]=sc.nextInt();
  }
  int d=0;//边长
  int L=1;
  int R=N;
  while(L<=R){
      int mid=(L+R)>>1;
      int cnt=0;
      for(int i=1;i<=n;i++){
           cnt+=(h[i]/mid)*(w[i]/mid);//n块，每块的个数和
      }
      if(cnt>=k){//够分
        L=mid+1;//新的搜索区间是右半部分，R不变，更新L=mid+1
        d=mid;
      }else{//不够分
          R=mid-1; //(L=R时跳出循环)新的搜索区间是左半部分，所以L不变，调整R=mid–1。
        }
      }
     System.out.print(d);  //输出符合的边长
  }
}

C++

#include
using namespace std;
int n,k;
int h[100010],w[100010];
bool check(int d){
    int num=0;
    for(int i=0;i=k) return true;    //够分
    else       return false;   //不够分
}
int main(){
    cin >>n>>k;
    for(int i=0;i>h[i]>>w[i];

    int L=1, R=100010;
//整数二分法的L、R、mid如果处理不当，极容易死循环。
//请仔细领会下面两种写法

//  第一种写法：
    while(L>1;   //除2，向右取整
        if(check(mid))     
            L=mid;  //新的搜索区间是右半部分，所以R不变，调整L=mid；
        else               
            R=mid-1; //新的搜索区间是左半部分，所以L不变，调整R=mid–1。
    }
    cout << L;

//  第二种写法：

    return 0;
}

二分：跳石头

import java.util.Scanner;

public class Main{
    static int n=0,m=0,len=0;
    static int []st=new int[50005];
   //判断二分的d能否满足条件m
    public static boolean check(int d){
        int pos=0;//记录当前位置
        int cnt=0;//累加可以移动的石头数和
        for(int i=1;i<=n;i++){
               if(st[i]-pos>1;
            if(check(mid)){
                L=mid+1;
                ans=mid;
            }else{
                R=mid-1;
            }
        }
        System.out.print(ans);
    }
}

前缀和：灵能传输

import java.util.*;
public class Main{
    public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int T=sc.nextInt();
    while(T!=0){
        T--;
        long n=sc.nextLong();
        long []a=new long [(int)n+2];
        long []s=new long [(int)n+1];
        for(int i=0;isn){//小在前，大在后
            long t=s0;
            s0=sn;
            sn=t;
        }

        long in0=0,inn=0;
        Arrays.sort(s);//排完序后寻找下标并记录下来
        for(int i=0;i<=(int)n;i++)
            if(s[i]==s0){
                in0=i;
                break;
            } 
        
        for(int i=(int)n;i>=0;i--)
            if(s[i]==sn){
                inn=i;
                break;
        }
    

        int l=0;
        int r=(int)n;
        long [] ans=new long[(int)n+2];//用于记录重叠后的数组
        long [] vis=new long[(int)n+2];//判断该数是否用过
        for(int i=(int)in0;i>=0;i-=2){// s0两步两步跳到最小值 
            ans[l++]+=s[i];
            vis[i]=1;
        }
        for(int i=(int)inn;i<=n;i+=2){//最后是 sn 两步两步跳到最大值
            ans[r--]+=s[i];
            vis[i]=1;
        }

        for(int i=1;i 
贪心练习题：翻硬币 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s1=sc.next();
        String s2=sc.next();
        char[] a=s1.toCharArray();
        char[] b=s2.toCharArray();
        int count=0;
        for(int i=0;i 
贪心练习题：最大最小公倍数 
最小公倍数，即三个数的质因数相乘（质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数）大于1的两个相邻的整数互质，如果任选两个数，则最大的最小公倍数就是n(n-1)。如果选三个，还要确定其是否两两互质，就要分奇偶判断；n是奇数，n,n-1,n-2两两互质；奇偶奇，公因子2只会在中间一个偶数中出现；公因子3，如果在n中出现（被n整除），就不会在n-2中出现；公因子5，同理3等等。所以n(n-1)(n-2)最大而且两两互质。n是偶数，n(n-1)(n-2)中n和(n-2)都有公因子2，不互为质数，换成式子n(n-1)(n-3)，这种情况还要考虑公因子3，如果n能被3整除，则n-3也可以被整除，也不互为质数，所以应该是(n-1)(n-2)(n-3)变成了奇偶奇的情况。总结
 1. n为奇，n(n-1)(n-2);n为偶
 2. n为偶且不被3整除，n(n-1)(n-3)
 3. n为偶且被3整除，(n-1)(n-2)(n-3)
 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long ans;
        if(n <= 2)    ans = n;
        else if(n % 2 != 0)
            ans = n * (n - 1) * (n - 2);
        else {
            if(n%3!=0) ans = n * (n-1) * (n-3);
            else ans=(n-1) * (n-2) * (n-3);
        }
        System.out.println(ans);
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718389.html