蓝桥杯笔记2

对蓝桥杯进行一个临时抱佛脚

1.排序

集合排序

java.util.Collections.sort(java.util.List)

java.util.Collections.sort(java.util.List, java.util.Comparator)	

​ Arrays.sort();
Arrays.sort(int[] a, int fromIndex, int toIndex)；
​ //Arrays.sort(数组名,起始下标,终止下标);
​ //（默认排序为升序排序）

如果一个数组初始化时已经赋值。则sort函数可以另外一种格式

Arrays.sort(数组名);

sort函数的格式变为: Arrays.sort(数组名, 起始下标, 终止下标, new cmp());

Set排序

Set是一类集合，简单来说就是将元素去重，没有顺序地放进集合里边

1. 放到TreeSet里面排序

           Set<String> set = new HashSet<>();
           set.add("2");
           set.add("1");
           set.add("5");
           set.add("3");
           set.add("4");
   //方法一    
       Set<String> sortSet = new TreeSet<String>(new Comparator<String>() {
           @Override
           public int compare(String o1, String o2) {
               return o2.compareTo(o1);//降序排列
           }
       });
   //方法二
   	    Set<String> sortSet = new TreeSet<String>((o1, o2) -> o2.compareTo(o1));
           sortSet.addAll(set);

2. 将Set放入List中排序

   方法同集合排序

Map排序

这里我只知道TreeMap，迭代器

public class TreeMapTest {
    public static void main(String[] args) {
        Map<String, Object> map = new TreeMap<String, Object>(
                new Comparator<String>() {
                    @Override
                    public int compare(String obj1, String obj2) {
                        // 降序排序
                        return obj2.compareTo(obj1);
                    }
                });
        map.put("2019-03", "ccccc");
        map.put("2018-12", "aaaaa");
        map.put("2019-01", "bbbbb");
        map.put("2019-02", "ddddd");

        Set<String> keySet = map.keySet();
        Iterator<String> iter = keySet.iterator();

        while (iter.hasNext()) {
            String key = iter.next();
            System.out.println(key + ":" + map.get(key));
        }
    }
}

自定义排序

int compare(Object o1, Object o2) 返回一个基本类型的整型
如果要按照升序排序，
则o1 小于o2，返回-1（负数），相等返回0，01大于02返回1（正数）
如果要按照降序排序
则o1 小于o2，返回1（正数），相等返回0，01大于02返回-1（负数）

import java.util.Comparator;
import java.util.Scanner;
import java.util.Arrays;
class shu{
	int x;
}
class cmp implements Comparator<shu>{
	public int compare(shu a,shu b){
		if(a.x<b.x){
			return 1;
		}
		else if(a.x>b.x){
			return -1;
		}
		else{
			return 0;
		}
		//可以简化成
		//return b.x-a.x
	}
}
public class Main {	

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		shu num[] = new shu[100];
		for(int i=0;i<n;i++){
			num[i]=new shu();    ///这个地方容易漏  
			num[i].x=sc.nextInt();
		}
		
		Arrays.sort(num,0,n,new cmp());
		
		for(int i=0;i<n;i++){
			if(i==n-1){
				System.out.println(num[i].x);  
			}
			else{
				System.out.print(num[i].x+" ");  
}			
		}
		sc.close();

}
	}

对象的比较

1.重写基类继承过来的equals方法，例如

@Override
public boolean equals(Object obj) {
    return this.k.equals(((Line)obj).k) && this.b.equals(((Line)obj).b);
}

2.比较器

Comparator位于包java.util下，而Comparable位于包java.lang下，Comparable接口将比较代码嵌入自身类中，而后者在一个独立的类中实现比较。
像Integer、String等这些基本类型的Java封装类都已经实现了Comparable接口，这些类对象本身就支持自比较，直接调用Collections.sort()就可以对集合中元素的排序，无需自己去实现Comparable接口。
而有些自定义类的List序列，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较，也就是指定使用Comparator（临时规则排序，也称作专门规则排序），如果不指定Comparator，那么就用自然规则排序，这里的自然顺序就是实现Comparable接口设定的排序方式。
若一个类要实现java.util.Comparator接口：它一定要实现int compare(T o1, T o2) 函数，而另一个可以不实现boolean equals(Object obj) 函数

1. int compare(T o1, T o2) 是比较o1和o2的大小

如果返回值为负数意味着o1比o2小，否则返回为零意味着o1等于o2，返回为正数意味着o1大于o2

例子如下:

public class Car implements Comparable<Car>{
    private String name;
    private int price;
    private int age;
    



​    public Car(String name , int price , int age){
​        this.name = name;
​        this.price = price;
​        this.age = age;
​    }

 

​    public String getName() {
​        return name;
​    }
​     
​    public void setName(String name) {
​        this.name = name;
​    }
​     
​    public int getPrice() {
​        return price;
​    }
​     
​    public void setPrice(int price) {
​        this.price = price;
​    }
​    public int getAge() {
​        return age;
​    }
​     
​    public void setAge(int age) {
​        this.age = age;
​    }
​       @Override
​    public String toString() {
​        return "Car{" +
​                "name='" + name + '\'' +
​                ", price=" + price +
​                ", age=" + age +
​                '}';
​    }
​    @Override
​    public int compareTo(Car car) {
​        return this.price - car.price;
​    }

}

public class Test {
    public static void main(String args[]){
        ArrayList<Car> list = new ArrayList<>();
        list.add(new Car("宝马" , 12 , 2019));
        list.add(new Car("大众" , 10 , 2015));
        list.add(new Car("蓝比基尼" , 50 , 2018));
        Car[] cars = list.toArray(new Car[list.size()]);

        Arrays.sort(cars, new Comparator<Car>() {//添加一个外部排序器即可
            @Override
            public int compare(Car car, Car t1) {
                return t1.getAge() - car.getAge();
            }
        });
        for(Car car : cars){
            System.out.println(car);
        }
    }

}

2.二分查找

基本模板：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

接着来一个很简单的应用：

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;

}

自己的理解：首先输入要找的数，以及搜寻它的范围，接着将这个范围取一个中间值mid，进入循环…进行比较，更改lefr和right的位置，如果最后right和left相等，就说明找到了

3.贪心算法

模板:

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;
}

基本思路：

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

背包问题

当前有N件物品和一个容积为V的背包。已知第i件物品的体积是C,价值是Wi。
由于每种物品有且仅有一-件，因此只能选择放或不放，我们称之为01背包问题。
现在你需要选出若干件物品，在它们的重量之和不超过V的条件下，使得价值总和尽可能大。
对于每个物品是否要装入背包，我们自然可以进行暴力枚举或搜索，但是如果要暴力地去做，那么时间复杂度会非常的高，这

/**

定义一个物体类
*/
class Body{
int id;// 物体的序号
int w;// 物体的重量
int p;// 物体的价值
}

/**

 * 一般背包问题的代码实现
 * @param w：每个物体重量的数组
 * @param p：每个物体收益的数组
 * @param m：背包载重
 * @return 结果集（放入哪几个物体、每个物体放入多少部分）
   */
   List<Body> commonPackage( int[] w, int[] p, int m ){
   // 构造物体对象列表（将入参存储在List<Body>中）
   List<Body> bodys = new ArrayList<>();
   for ( int i=0; i<w.length; i++ ) {
       bodys.add(new Body(w[i],p[i]));
   }
   // 对性价比排序（从高到低排序）
   Collections.sort(bodys, new Comaprator<Body>(){
       int compare(Body b1,Body b2){
        return b2.p/b2.w-b1.p/b1.w;
    }
});
// 将物体按照性价比从高到低依次加入背包
int rest = m;// 剩余重量
int i=0;
List<Body> results = new ArrayList<>();// 存放结果集
for(; i<bodys.size(); i++){
    if ( rest<bodys.get(i).w )
        break;
    Body curBody = bodys.get(i);
    results.add(curBody);
    rest -= curBody.w;
}
// 计算最后一个物体能放入的部分
Body lastBody = bodys.get(i);
results.add(new Body(lastBody.id,rest,(lastBody.p*rest/lastBody.w));
}
   
         

### 找钱问题

**假设有 25 分、10 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？**
**贪心策略：每一次都优先选择面值最大的硬币**
**① 选择 25 分的硬币，剩 16 分**
**② 选择 10 分的硬币，剩 6 分**
**③ 选择 5 分的硬币，剩 1 分**
**④ 选择 1 分的硬币**
**最终的解是共 4 枚硬币**
**✓ 25 分、10 分、5 分、1 分硬币各一枚**import java.util.Arrays;

```javascript
public class CoinChange {
    public static void main(String[] args) {
        int[] faces = {25,10,5,1};
        Arrays.sort(faces);//1,5,10,25
        int money = 41,coins = 0;

        for (int i = faces.length-1; i >=0 ; i--) {
            if (money < faces[i]){
                continue;
            }
            money -= faces[i];
            coins++;
            System.out.println(faces[i]);
            i = faces.length;
        }
        System.out.println("一共需要"+coins+"枚硬币");
    }

}

运行结果：
25
10
5
1
一共需要4枚硬币

4.DFS和BFS

无特殊情况，DFS就用递归实现，BFS就用队列实现。

DFS

现在小学的数学题目也不6是那么好玩的。
看看这个寒假作业：

   □ + □ = □
   □ - □ = □
   □ × □ = □
   □ ÷ □ = □
1
2
3
4

(如果显示不出来，可以参见【图1.jpg】)

每个方块代表1~13中的某一个数字，但不能重复。
比如：

6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

以及：

 7  + 6 = 13
 9  - 8 = 1
 3  * 4 = 12
 10 / 2 = 5
1
2
3
4
5

就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
注意:该题全排列会超时。

#include<bits/stdc++.h>
int count=0;
int v[15],a[15];
void dfs(int n)
{
	if(n==3)
	{
		if(a[0]+a[1]!=a[2])
			return;
	}
	if(n==6)
	{
		if(a[3]-a[4]!=a[5])
			return;
	}
	if(n==9)
	{
		if(a[6]*a[7]!=a[8])
			return;
	}
	if(n==12)
	{
		if(a[10]*a[11]==a[9])
			count++;
		return;
	}
	for(int i=1;i<=13;i++)
	{
		if(v[i]==0)
		{
			v[i]=1;
			a[n]=i;
			dfs(n+1);
			v[i]=0;
		}
	}
}
int main()
{
	dfs(0);
	printf("%d",count);
	return 0;
}

BFS

5.Dijkstra

这是蓝桥杯的最短路径问题：

package _lanqiaobei;

import java.util.Arrays;




public class Ways {
    static int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
      }
	public static void main(String[] args) {
		int[][] point=new int[2022][2022] ;
		int[] dist=new int[2022];
		boolean[] visit=new boolean[2022];
		Arrays.fill(dist,Integer.MAX_VALUE);
		for(int i=0;i<2022;i++) {
			for(int j=0;j<2022;j++) {
				if(i==j) {
					point[i][j]=0;
				}else if(Math.abs(i - j) <= 21) {
					point[i][j]=i*j/gcd(i,j);
				}else {
					point[i][j]=Integer.MAX_VALUE;
				}
			}
		}
		dist[1]=0; 
		for(int i=1;i<2022;i++) {
			int u=0;
			int min=Integer.MAX_VALUE;
			for(int j=1;j<2022;j++) {
				if(visit[j]==false&&dist[j]<min) {
					min=dist[i];
					u=j;
				}

			}
			visit[u]=true;
			for(int j=1;j<2022;j++) {
				if(point[u][j]!=Integer.MAX_VALUE&&dist[u]+point[u][j]<dist[j]) {
					dist[j] = dist[u] + point[u][j];
				}
			}
		}
		System.out.println(dist[2021]);
		
	}

}

6.动态规划

https://blog.csdn.net/u011612364/article/details/117516638?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164942540716780271924704%2522%252C%2522scm%25

7.计算几何

例题：https://blog.csdn.net/LHF_hai/article/details/79241508

8.树

二叉树的前、中、后序遍历，树状数组，最小生成树（Kruskal）。

9.栈和队列

Map:https://blog.csdn.net/haojiagou/article/details/88168835?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164942497316780271971557%2522%252C%2522scm%2522

vector:https://blog.csdn.net/Listening_music/article/details/7034070?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164942503216780255270826%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164942503216780255270826&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-7034070.142^v7^pc_search_result_cache,157^v4^control&utm_term=vector+java&spm=1018.2226.3001.418

set:https://blog.csdn.net/lushuaiyin/article/details/7381478?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164942525116782184652105%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164942525116782184652105&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-6-7381478.142^v7^pc_search_result_cache,157^v4^control&utm_term=set+java&spm=1018.2226.3001.4187

pair:https://blog.csdn.net/dydy12232/article/details/105953310?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164942533316780271935036%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164942533316780271935036&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-105953310.142^v7^pc_search_result_cache,157^v4^control&utm_term=pair+java&spm=1018.2226.3001.4187

10.简单数学

最小公倍数

两数相乘除公倍数

最大公约数

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

素数的筛选

package com.imooc.test2;

/**

 * 利用筛选法查找100以内的素数
   */
public class Test {
   public static void main(String[] args) {
       // 定义一个int类型的数组
       int[] a = new int[101];
       int i,j;
 
   // 初始化整个数组，全部初始化为1
   for (i = 0; i <101 ; i++) {
       a[i] = 1;
   }

   for (i=2;i<101;i++){
       if(a[i]!=0){
           for (j=i+i;j<101;){
               // 如果能被整除，说明是一个数的倍数，赋值为0
               if(j%i==0){
                   a[j]=0;
                j = j+i;
               }
           }
       }
   }

   // 遍历筛选后的数组，输出100以内的素数
 
      for ( i = 2; i < 101; i++) {
        if (a[i]==1){
            System.out.println(i);
        }
    }
 
}
}

三角形公式

1.已知三角形底a，高h，则 S=ah/2

2.已知三角形三边a,b,c，则

（海伦公式）（p=(a+b+c)/2）

S=sqrt[p(p-a)(p-b)(p-c)]

=sqrt[(1/16)(a+b+c)(a+b-c)(a+c-b)(b+c-a)]

=1/4sqrt[(a+b+c)(a+b-c)(a+c-b)(b+c-a)]

3.已知三角形两边a,b,这两边夹角C，则S=1/2

absinC，即两夹边之积乘夹角的正弦值。

4.设三角形三边分别为a、b、c，内切圆半径为r

则三角形面积=(a+b+c)r/2

5.设三角形三边分别为a、b、c，外接圆半径为R

则三角形面积=abc/4R

等差数列，等比数列

等差数列和公式：Sn=n(a1+an)/2=na1+n(n-1)/2 d

等比数列求和公式：q≠1时 Sn=a1(1-q^n)/(1-q)=(a1-anq)/(1-q)

更多。。。