贪心与动态规划

import java.util.Scanner;
 
public class Main{  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        int n = sc.nextInt();  
        /* 
         * 思路：贪心算法; 
         * 从第一个数开始, 寻找可以一个可以跳最远的点; 
         * 例1：3 1 2 4 1 0 0 
         * 1.从第一个位置0,可以跳到位置1和位置2和位置3; 
         * 2.如果跳到位置1,那么最远就可以跳到位置(1+1); 
         * 3.如果跳到位置2,那么最远就可以跳到位置(2+2); 
         * 4.如果跳到位置3,那么最远就可以跳到位置(3+4); 
         * 5.故选择跳到位置3 ,重复1.2.3步; 
         *  
         * 算法分析： 
         * 1.如果选择跳到位置3 ,就无法跳到位置2和位置3, 那么会不会因此错过最优解？ 答：不会！ 
         * 2.因为任意位置1和位置2能到达的位置, 位置3都可以到达; 
         * 3.故不会错过最优解; 
         */  
        int[]a = new int[n];  
        for(int i= 0 ;i< n ;i++) {  
            a[i] = sc.nextInt();  
        }  
        int i;  
        int l;  //左边界       控制搜索的起始位置  
        int r;  //右边界       控制搜索的终止位置  
        //循环条件i的变化是在方法体中指定的，for循环本身不再进行i变化，后面i=l
        for( i= 0 ;i< n && a[i]!= 0 ;) { //当a[i]==0 时 , 该位置为可到达的最远位置  
            r = i + a[i];  
            l = i + 1;   
            for(int j= i+1 ;j< n && j<= i+a[i] ;j++) {    //  
                if(j+a[j] >= r){ //遍历可到达位置 能到达的最远位置  
                    r = j+ a[j];    //更新左右边界  
                    l = j;  
                }  
            }  
            i = l;  //左边界  
              
        }  
        //根据下标能不能到达终点判断
        if(i< n-1) {  
            System.out.println("false");  
              
        }else{  
            System.out.println("true");  
        }  
    }  
}

package cupidity;

import java.util.Scanner;

public class pj1 {
	
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		//会议数量
		int num = -1;
		//最后需要的会场数
		int geshu = 0;
		
		num = input.nextInt();// 输入待安排的活动个数
//		System.out.println("总个数："+ num);
		//双数组
		int[] s = new int[num];
		int[] f = new int[num];
		for (int i = 0; i < num; i++) {
			s[i] = input.nextInt();
			f[i] = input.nextInt();
		}

		// 按照演出开始时间排序,这是什么排序？
		//选择排序，正宗的选择排序应该是：两个for循环的范围和这里是相同的，从i后面选，前面是已经排好序的
		//只不过原本是每一次都选出最小的，现在是不保存index最小位置了，只要是小的立刻更新到i的位置，最后还是能保证最小的那个值在s[i]位置选出来，时间复杂度不变但是肯定有交换的消耗。
		//记住几种基本排序的特性就行，选择是选小的往后if比较
		//冒泡是排好后面，第二层for减去已经排好序的部分，正好和选择相反

		//插入排序是相比较难理解一点的，我们随便选一个数，一般是从第二个开始，第一个不用插，第二个才考虑插到前面还是后面
		//将这个数取出来，然后遍历该数之前的数（前面的数已经是排好序的了），如果前面这个数大于当前待排序的数（假如下标是j），那么让j+1位置元素变为j的元素，后边已经遍历过去的元素（我们是从后往前找小于的值然后插在其后）
		//后面的元素一定是都往后挪了一位的（不会越界的原因是，假如n-1都拍排好了，往后挪一个是肯定没事的，因为我们第n个是待排的，根本不会对其进行+1操作，只会对前面有序的n-1个元素进行+1）
		//最后一旦找到小于的元素索引为j了，当然退出循环判断下j+1 != i，满足就可以j+1的位置替换成待排元素了，不判断也可以，因为满足这个说明前面的就小于本身，那么此时完全可以省略赋值步骤
		for (int i = 0; i < s.length; i++) {
			int temp1 = 0;
			int temp2 = 0;
			for(int j = i+1; j < s.length; j++) {
				//从小到大排序
				if (s[i] > s[j]) {
					//三步s[i]和s[j]交换
					temp1 = s[i];
					s[i] = s[j];
					s[j] = temp1;
					//别忘了把结束时间交换，s和f的元素是对应的
					temp2 = f[i];
					f[i] = f[j];
					f[j] = temp2;
				}
			}
		}
		
		// 双重循环得到安排的会场
		int[] anpai = new int[num];
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				//数组默认为0，如果下面判断成立则不为0，遍历起始时间必须大于上一次保存的会议的结束时间
				//为什么不直接判断成功就++而是双重循环呢？一定要理解这里
				//原因是anpai[j]代表了一个会场，他不为0代表被占用了，这里和会场安排时间还不一样，会场安排时间是求最多能安排多少个，不符合的直接扔掉
				//而时间选择会场即使不符合第一个会场anpai[0],我该应该继续遍历anpai[j]看后面的会场符不符合我的结束时间，总能找到一个落脚点（因为会场数量的数组长度和会议数都相同了），最后求出的是一个最优解，当然也不一定是唯一
				//anpai[0]不符合就开辟anpai[1]，anpai[1]符合了就把会议放进去然后更新结束时间（结束时间演唱一定是延长了），原因是当前会议的起始时间都大于anpai[j]了，那么该会议的结束时间也一定是大大于当前会场的结束时间的。
				if (anpai[j] < s[i]) {
					anpai[j] = f[i];
					break;
				}
			}
		}
		
		// 遍历安排的数值，找出被安排的个数
		for (int i = 0; i < num; i++) {
			if (anpai[i] != 0) {
				geshu++;
			}
		}
		System.out.println("至少安排的会场个数："+geshu);
	}
}

package TestSort;

import java.util.Arrays;

public class Test_InsertSort {
    public static void InsertSort(int[] arr){
        int insertVal = 0;
        int insertIndex = 0;
        for(int i = 1; i < arr.length; i++){
            //定义待插入的数
            insertVal = arr[i];
            insertIndex = i - 1;//待插入数前面数的下标

            //给insertVal找到插入的位置
            //insertIndex >= 0是保证给insertVal找到插入位置时，不越界
            //insertVal < arr[insertIndex] 如果符合该判断，就说明还没有找到插入位置，就需要将arr[insertIndex]后移
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            //当退出while循环时，说明插入的位置已经找到，insertIndex + 1
            if(insertIndex + 1 != i){
                arr[insertIndex + 1] = insertVal;
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {23, 43, 3, 32, 67, 78, 34, 56};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        InsertSort(arr);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

}