|
贪心算法：保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
问题1：甲乙两选手比赛，手中各有一些牌，每个牌面对应一个点数，双方出牌后点数大的赢一手，先给出两位选手手中牌的点数，求出甲最多能赢乙多少手
贪心策略：给乙剩余最小的牌面分配能赢的最小的牌
num = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
a1 = 0
b1 = 0
count = 0
while a1 < len(a) and b1 < len(b):
? ? if b[b1] < a[a1]:
? ? ? ? b1 +=1
? ? ? ? count += 1
? ? a1 += 1
print(count)
问题2：区间问题，给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数，起止相连不算重叠
策略：选择的区间结尾越小，留给其他区间的空间就越大，就越能保留更多的区间，故优先保留结尾小且不相交的区间。
问题3：买卖股票的最佳时机，给定一个数组，他的第i个元素是一只给定股票第i天的价格，设计一个算法来计算你能获取的最大利润（你必须在再次购买之前出售掉之前购买的股票）
策略：如果今天买明天卖可以赚钱，那就买入
1．与运算符
与运算符用符号“&”表示，其使用规律如下：
两个操作数中位都为1，结果才为1，否则结果为0，例如下面的程序段。
“a”的值是129，转换成二进制就是10000001，而“b”的值是128，转换成二进制就是10000000。根据与运算符的运算规律，只有两个位都是1，结果才是1，可以知道结果就是10000000，即128。
2．或运算符
或运算符用符号“|”表示，其运算规律如下：
两个位只要有一个为1，那么结果就是1，否则就为0，下面看一个简单的例子。
a 的值是129，转换成二进制就是10000001，而b 的值是128，转换成二进制就是10000000，根据或运算符的运算规律，只有两个位有一个是1，结果才是1，可以知道结果就是10000001，即129。
3．非运算符
非运算符用符号“~”表示，其运算规律如下：
如果位为0，结果是1，如果位为1，结果是0，下面看一个简单例子。
4.异或运算：a^b ? ? a，b相同为0，不同为1
可以理解为两个无穷位二进制数每一位进行异或运算
性质：
1.?? ?0^N=N?? ?N^N=0
2.?? ?符合交换律和结合律
3.?? ?同一批数异或，不管顺序如何结果都一样
交换两个数可以用异或运算：a = 甲，b = 乙
a = a ^ b;?? ??? ?a=甲^乙，b=乙
b = a ^ b;?? ?a=甲^乙，b=甲^乙^乙=甲
a = a ^ b;?? ??? ?a=甲^乙^甲，b=甲
逻辑左移=算术左移：高位溢出，低位补0
逻辑右移：低位溢出，高位补0
算术右移：低位溢出，高位用符号位的值补
比如一个有符号位的8位二进制数10101010，[]是添加的数字
逻辑左移一位：0101010[0]
逻辑左移两位：101010[00]
算术左移一位：0101010[0]
算术左移两位：101010[00]
逻辑右移一位：[0]1010101
逻辑右移两位：[00]101010
算术右移一位：[1]1010101
算术右移两位：[11]101010
算术左移和算术右移主要用来进行有符号数的倍增、减半
逻辑左移和逻辑右移主要用来进行无符号数的倍增、减半
（Java中是没有无符号数据类型的，C和C++中有）
符号?? ?例子?? ?解释
<<?? ?num<< n?? ?相当于 num×2的n次方，算数左移（逻辑左移）
>>?? ?num>>n?? ?相当于num2nnum2n，算数右移
>>>?? ?num>>>n?? ?逻辑右移，当num为正数和算术右移一个效果
面试题：一个数组中有两种奇数个的数，多种偶数个的数，找出两种奇数个的数
public class Test {
? ? public static void main(String[] args) {
? ? ? ? int[] arr = new int[]{1,1,2,2,2,3,3,3,};
? ? ? ? int eor = 0;
? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? eor ^= arr[i];
? ? ? ? }
? ? ? ? //eor = a^b, eor!=0, eor必然有一个位置上是1
? ? ? ? int rightOne = eor & (~eor + 1);//提取出最右边的1
? ? ? ? int onlyOne = 0;//eor'
? ? ? ? for(int cur:arr) {
? ? ? ? ? ? if ((cur & rightOne)==1){
? ? ? ? ? ? ? ? onlyOne ^= cur;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println(onlyOne + " "+ (eor^onlyOne));
? ? }
}
选择排序：从0~n-1个数中选出最小的放在0位置，再依次循环n遍
冒泡排序：0~1排序，1~2排序，n-1~n排序，每次排序冒出一个最大的放在最后，循环n次
算法流程按最差情况来估计时间复杂度
插入排序：
? ? ? ? for (int i = 1; i < arr.length; i++) {?? ?//让0~i之间有序
? ? ? ? ? ? for (int j = i-1; j >=0&&arr[j]>arr[j+1] ; j--) {?? ?//把i和i+1比较
? ? ? ? ? ? ? ? swap(arr,j,j+1);
? ? ? ? ? ? }
? ? ? ? }
二分法时间复杂度为O(logN)
归并排序：时间复杂度O(N*logN）,额外空间复杂度N2
public static void process(int[] arr,int l,int r){
? ? if (l == r){
? ? ? ? return;
? ? }
? ? int mid = l+((r-l)>>1);
? ? process(arr,l,mid);
? ? process(arr,mid+1,r);
? ? merge(arr,l,mid,r);
}
public static void merge(int[] arr,int l,int m,int r){
? ? int[] help = new int[r-l+1];
? ? int i = 0;
? ? int p1 = l;
? ? int p2 = m+1;
? ? while(p1<=m && p2<=r){
? ? ? ? help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
? ? }
? ? while(p1 <= m){
? ? ? ? help[i++] = arr[p1++];
? ? }
? ? while(p2 <= r){
? ? ? ? help[i++] = arr[p2++];
? ? }
? ? for (int j = 0; j < help.length; j++) {
? ? ? ? arr[l+i] = help[i];
? ? }
}
快速排序：时间复杂度为O(N*logN)，额外空间复杂度：logN
public static void quickSort(int[] arr,int l,int r){
? ? if (l < r){
? ? ? ? swap(arr,l + (int)(Math.random() * (r-l+1)),r);
? ? ? ? int[] p = partition(arr,l,r);
? ? ? ? quickSort(arr,l,p[0]-1);//<区
? ? ? ? quickSort(arr,p[1]+1,r);//>区
? ? }
}
//这是一个处理arr[1..r]的函数，默认以arr[r]做划分，arr[r]->p ? ? <p ?==p ?>p，返回等于区域（左边界，右边界），所以返回一个长度为2的数组
public static int[] partition(int[] arr,int l,int r){
? ? int less = l -1;//<区右边界
? ? int more = r;//>区左边界
? ? while(l<more){//l表示当前数的位置arr[r]->划分值
? ? ? ? if (arr[l] < arr[r]){//当前数<划分值
? ? ? ? ? ? swap(arr, ++less, l++);
? ? ? ? }else if (arr[l] > arr[r]){
? ? ? ? ? ? swap(arr, --more, l);
? ? ? ? }else{
? ? ? ? ? ? l++;
? ? ? ? }
? ? }
? ? swap(arr, more, r);
? ? return new int[]{less+1, more};
}
堆结构：用数组实现的完全二叉树结构
堆排序：时间复杂度NlogN，额外空间复杂度O1
//某个数现在处于index位置上，往上继续移动
public static void heapInsert(int[] arr,int index){
? ? while(arr[index] > arr[(index-1)/2]){
? ? ? ? swap(arr,index,(index-1)/2);
? ? ? ? index = (index-1)/2;
? ? }
}
//某个数在index位置上，能否往下移动
public static void heapify(int[] arr,int index,int heapSize){
? ? int left = index * 2 +1;//左孩子的下标
? ? while(left < heapSize){//下方还有孩子时
? ? ? ? //两个孩子中，谁的值大，把下标给largest
? ? ? ? int largest = left+1 < heapSize && arr[left+1] > arr[left]? left+1: left;
? ? ? ? //父和孩子之间，谁的值大，把下标给largest
? ? ? ? largest = arr[largest] > arr[index]? largest: index;
? ? ? ? if(largest == index){
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? swap(arr,largest,index);
? ? ? ? index = largest;
? ? ? ? left = index*2+1;
? ? }
}
//全过程
public static void heapSort(int[] arr){
? ? if (arr == null||arr.length < 2){
? ? ? ? return;
? ? }
? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? heapInsert(arr,i);//插入每一个数形成大根堆
? ? }
? ? int heapSize = arr.length;
? ? swap(arr,0,--heapSize);//最后一个数和第一个数进行交换，然后把最后一个数剔除；
? ? while(heapSize > 0){
? ? ? ? heapify(arr,0,heapSize);
? ? ? ? swap(arr,0,--heapSize);
? ? }
}
对于所有比较器：返回正数，第二个参数放前，返回负数，第一个参数放前
基数排序（桶排序）：只有数字才能使用
public static void radixSort(int[] arr,int l,int r,int digit){
? ? final int radix = 10;
? ? int i = 0,j = 0;
? ? //有多少个数准备多少个辅助空间
? ? int[] bucket = new int[r-l+1];
? ? for (int d = 1; d < digit; d++) {//有多少位就进出几次
? ? ? ? //10个空间
? ? ? ? //count[0] 当前位（d位)是0的数字有多少个
? ? ? ? //count[1] 当前位（d位）是（0~1）的数字有多少个
? ? ? ? //count[i] 当前位（d位）是（0~i）的数字有多少个
? ? ? ? int[] count = new int[radix];//count[0,9]
? ? ? ? for (int i = l; i <= r; i++) {
? ? ? ? ? ? i = geiDigit(arr[i],d);//获取当前位数上的数字
? ? ? ? ? ? count[j]++;//统计d位上是i的数字的个数
? ? ? ? }
? ? ? ? for (int i = 1; i < radix; i++) {
? ? ? ? ? ? count[i] = count[i] + count[i-1];//统计d位上是0~i的数字的个数
? ? ? ? }
? ? ? ? for (int i = r; i >= l ; i--) {
? ? ? ? ? ? j = getDigit(arr[i],d);
? ? ? ? ? ? bucket[count[i]-1] = arr[i];
? ? ? ? ? ? count[j]--;//从后往前
? ? ? ? }
? ? ? ? for (int k = l,j = 0; k < r; k++,j++) {
? ? ? ? ? ? arr[k] = bucket[j];//根据d位排好序再拷贝到arr中重新根据d+1位排序
? ? ? ? }
? ? }
}
|