脚本宝典收集整理的这篇文章主要介绍了蓝桥杯算法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

1.位运算

@H_512_2@

• 位运算符
• 在处理整形数值时，可以直接对组成整形数值的各个位进行操作。这意味着可以使用屏蔽技术获得整数中的各个位(? ? )
• &(与)、| (或)、^(异或)、~ (非/取反)
• ">>“和”<<"运算符将二进制位进行右移或者左移操作
• ">>>"运算符将用0填充高位; >>运算符用符号位填充高位，没有<<<运算符
• 对于int型，1<<35与1<<3是相同 的，而左边的操作数是long型时需对右侧操作数模64
• 与:都为1结果为1，或:有一个为1结果为1，异或:二者不同时结果为1

@H_126_80@

a	b	~a	a&b	a|b	a^b
1	1	0	1	1	0
0	1	1	0	1	1
0	0	1	0	0	0

• 判断奇偶数 x&1=1为奇数 =0为偶数 原因：奇数最后一位是1，&1后为1，偶数最后一位为0，&1后为0

• 获取二进制位是1还是0 (两种解决方案) 86的二进制第5位是1还是0？

1.1先左移4位和86与运算，结果再右移，和为1则为，为0则为0

2. 86右移4位，然后结果为和1与运算，结果1则为，为0则为0 86>>4&1

   • 交换两个整数变量的值

     int a=2,b=1;
     a=a^b;
     b=a^b;
     a=a^b;
     System.out.PRintln("a=="+a+",b=="+b);
     

   • 不用判断语句，求整数的绝对值

     int a=-88;
     System.out.println((a^a>>31)+(a>>>31));
     

     结果：88

   • 异或，可以理解为不进位加法:1 +1=0 , 0+0=0 , 1+0=1

   2. 性质 1、交换律可任意交换运算因子的位置,结果不变 2、结合律 3、对于任何数x ,都有x^x=0 , x^0=x,同自己求异或为0 ,同0求异或为自己 1 1 0 1 ^1 1 0 1 ———— 0 0 0 0 4、自反性A^BB=A^0=A ,连续和同一一个因子做异或运算,最终结果为自己

题1:找出唯一成对的数

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来;不用辅助存储空间，能否设计一个算法实现?

import java.util.Arrays;
import java.util.Random;
/**
 * 由于A^A=0
 * A^0=A
 * 所以在数组中的所有数进行^可以消去相同的数 结果为奇数个数的那个数据
 * 例如： 1^1^2^2^3=3
 * 所以找唯一成对的数可以写两个循环
 * 第一个循环对在该范围的数据进行^
 * 第二个循环利用第一个循环的结果对该数组中的数据进行^
 * 得到的结果就是唯一成对的数  因为这样成对的数据异或了三次
 */
public class Main {
    public static void main(String[] args) {
        int N=11;
        int[] arr=new int[N];
        for (int i = 0; i <arr.length-1 ; i++) {
            arr[i]=i+1;
        }
        arr[N-1]=new Random().nextInt(N-1)+1;
        int index=new Random().nextInt(N);
        int t;
        t=arr[N-1];
        arr[N-1]=arr[index];
        arr[index]=t;
        System.out.println(Arrays.toString(arr));
        int x=0;
        for (int i = 0; i <N-1 ; i++) {
            x=x^(i+1);
        }
        for (int i = 0; i <N ; i++) {
            x^=arr[i];
        }
//		x^x=0,出现两次的消去，剩下出现三次的
        System.out.println(x);
//        辅助空间方法
        int[] h=new int[N];
        for (int i = 0; i <N ; i++) {
            h[arr[i]]++;
        }
        for (int i = 0; i < N; i++) {
            if(h[i]==2){
                System.out.println(i);
            }
        }
    }
}

题2:找出落单的那个数

一个数组里除了某一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

题3:二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。 例: 9的二进制表示为1001，有2位是1

import java.util.Scanner;

public class _1的个数 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        System.out.println(Integer.toString(N,2));
        int count=0;
 /**
 * 第一种解法
 * int类型是32位  利用移位操作
 * N与 1 10 100 1000 ....做&运算 的结果如果等于1<<i位后的结果则计数
 * 就比如：N假设为1001
 * 10001&00001 == 00001 相等 则计数 说明该位置为1
 * ...........
 * 10001&10000 == 10000 说明该位置为1
 * 相等的次数即为1的个数
 *
 * 当然这种是1进行左移操作， 也可以利用N来进行右移与1进行&操作进行判断1的个数
 * */
        for (int i = 0; i < 32; i++) {
            if((N&1<<i)==1<<i){
                count++;
            }
        }
        System.out.println(count);
/**
 * 另一种解法
 * 这种解法的思想就是，把N中的每个一干掉，最后当N为0的时候 干掉1的次数也就是N中1的个数
 * 例如  1100
 * 1100-1=1001然后与1100做&运算 低位的1就被干掉了 N变为1000
 * 1000-1=0111 然后与1000做&运算 N变为0 由此可见1的个数为2
 * 干掉1的次数也就是1的个数
 * */
        count=0;
        while(N!=0){
            N=(N-1)&N;
            count++;
        }
        System.out.println(count);
    }
}      

题4:是不是2的整数次方

用一条语句判断一个整数是不是2的整数次方。

//2的整数次方 也就是说对应二进制位上只有一个是1 其他全为0 即1的个数为1  当然前提是n>0
if((N>0&&((N-1)&N)==0)){
    System.out.println("yes");
}else{
    System.out.println("no");
}

题5:将整数的二进制奇偶位互换

1&保留，0&置零，0^保留

/**
 * 例如 1001 变为0110
 * 1001&1010=1000保留偶数位
 * 1001&0101=0001保留奇数位
 * 偶数位右移  >> 0100
 * 奇数位左移  >> 0010
 * 两者异或  0100^0010=0110
 * 可得结果
 * */
public class _奇偶位交换 {
    public static void main(String[] args) {
        int a=6;
        System.out.println(m(a));
       	//结果为9
    }
    private static int m(int i){
        int ou=i&0xaaaaaaaa;//和1010 1010 ...做与运算得到偶位
        int ji=i&0x55555555;//和0101 0101 ...做与运算得到奇位
        return (ou>>1)^(ji<<1);
    }
}

题6:0~1间浮点实数的二进制表示

给定一个介于0和1之间的实数， (如0.625) ，类型为double,打印它的二进制表示(0.101,因为小数点后的二进制分别表示0.5,0.25.0.12…)。 如果该数字无法精确地用32位以内的-进制表示，则打印“ERROR”

public class _浮点数二进制表示 {
    public static void main(String[] args) {
        double m=0.625;
        StringBuilder re=new StringBuilder("0.");
        while(m>0){
            m=m*2;//乘2:挪整
            if(m>=1){//判断整数部分
                re.apPEnd("1");
                m=m-1;//消除整数部分
            }else{
                re.append("0");
            }
        }
        if(re.length()>34){
            System.out.println("ERROR");
            return;
        }
        System.out.println(re);
    }
}

题7:出现k次与出现1次

数组中只有-一个数出现了1次，其他的数都出现了k次，请输出只出现了1次的数。

方法一：位运算

​ 2 个相同的2 进制数做不进位加法，结果为0 ​ 10个相同的10进制数做不进位加法，结果为0 ​ k 个相同的k 进制数做不进位加法，结果为0

​ 1.如何将一个数转化为K进制的数(java中有封装好的方法,直接使用Integer.toString(int i,int radix))

​ 2.如何进行不进位的加法(将按位加后的数模k就行)

public class _07_出现K次 {
    public static void main(String[] args) {
        int[] arr = {2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6, 0, 0, 0};
        int len = arr.length;
        char[][] kRadix = new char[len][];
        int k = 3;
           int maxLen = 0;
        //转成k进制字符数组
        //对于每个数字
        for (int i = 0; i < len; i++) {
            //求每个数字的三进制字符串并翻转，然后转为字符数组
            kRadix[i] = new StringBuilder(Integer.toString(arr[i], k)).reverse().toString().toCharArray();
            if (kRadix[i].length > maxLen)
                maxLen = kRadix[i].length;
        }
        //不进位加法
        int[] resArr = new int[maxLen];
        for (int i = 0; i < len; i++) {
            //  不进位加法
            for (int j = 0; j < maxLen; j++) {
                if (j >= kRadix[i].length)
                    resArr[j] += 0;
                else
                    resArr[j] += (kRadix[i][j] - '0');
            }
        }
        int res = 0;
        for (int i = 0; i < maxLen; i++) {
            res += (resArr[i] % k) * (int) (Math.pow(k, i));// 8%3=2,
        }
        System.out.println(res);
    }
}    
    

方法二：HashMap

/**
 * 解法2-使用HashMap(更容易想到)
 * @param nums
 * @return
 */
public static int getOnce2(int[] nums) {
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	for (int i = 0; i < nums.length; i++) {
		if(map.containsKey(nums[i])) {
			int num = map.get(nums[i]);
			num++;
			map.put(nums[i], num);
		}else {
			map.put(nums[i], 1);
		}
	}
	ITerator<Integer> iterable = map.keySet().iterator();
	while(iterable.hasNext()) {
		int key = iterable.next();
		if(map.get(key)==1) {
			return key;
		}
	}
	return -1;
}

2.递归

• 递归设计经验 找重复(子问题) 找重复中的变化量→参数 找参数变化趋势→设计出口
• 练习策略 循环改递归 经典递归 大量练习，总结规律，掌握套路 找到感觉，挑战高难度

2.1.求n的阶乘

  /**
   * F1(n):求n的阶乘-->f1(n-1)求n-1的阶乘
   * 找重复：n*(n-1)的阶乘,求n-1的阶乘是原问题的重复（规模更小）——子问题
   * 找变化：变化的量应该作为参数
   * 找边界：出口*/
  static int f1(int n) {
    if (n == 1)
      return 1;
    return n * f1(n - 1);
  }

2.2.打印i到j

  /**
   * 打印i到j
   * 找重复：
   * 找变化：变化的量应该作为参数
   * 找边界：出口*/
  static void f2(int i, int j) {
    if (i > j)
      return;
    System.out.println(i);
    f2(i + 1, j);
  }

2.3.对数组元素求和

/**
   * 对arr的所有元素求和
   * 找重复：
   * 找变化：变化的量应该作为参数
   * 找边界：出口
   *@param arr
*/
  static int f3(int[] arr, int begin) {
    if (begin == arr.length - 1) {
      return arr[begin];
    }
	return arr[begin] + f3(arr, begin + 1);
  }

2.4.翻转字符串

//翻转字符串
  static String reverse(String src, int end) {
    if (end == 0) {
      return "" + src.charAt(0);
    }
    return src.charAt(end) + reverse(src, end - 1);
  }

分解为:直接量+小规模子问题

分解为:多个小规模子问题（斐波那契）

2.5.斐波那契第n项

//斐波那契第n项
static int fib(int n){
    if(n==1||n==2){
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

斐波那契数列问题 等价于两个子问题:求前一项、求前二项 两项求和

2.6辗转相除求最大公因数

//辗转相除求最大公因数
//m%n=k1
//n%k1=k2
//直到k等于0 说明参数中第一位的数 就是最大公约数
static int gcd(int m,int n){
    if(n==0){
        return m;
    }
    return gcd(n,m%n);
}

2.7递归形式插入排序

0~倒数第一个排序等价于: 对数组的0~倒数第二个元素，这部分排序 然后把是后一个元素插入到这个有序的部分中

static void insertSort(int[] arr, int k) {
    if (k == 0) {
        return;
    }
    //对前k-1个元素排序
    insertSort(arr, k - 1);
    //把位置k的元素插入到前面的部分
    int x = arr[k];
    int index = k - 1;
    while (index > -1 && x < arr[index]) {
        arr[index + 1] = arr[index];
        index--;
    }
    arr[index + 1] = x;
}

2.8汉诺塔

1-N从A移动到B，C作为辅助 等价于： 1、1~N-1从A移动到C，B为辅助 2、把N从A移动到B 3、1~N-1从C移动到B，A为辅助

/**
* 将N个盘子从source移动到target的路径的打印
*
* N      初始的N个从小到达的盘子，N是最大编号
* source 原始柱子
* target 辅助的柱子
* help   目标柱子
*/
static void printHanoiTower(int N, String source, String target, String help) {
    if (N == 1) {
        System.out.println("move " + N + " From " + source + " to " + target);
    } else {
        printHanoiTower(N - 1, source, help, target); // 先把前N-1个盘子挪到辅助空间上去
        System.out.println("move " + N + " from " + source + " to " + target);  // N可以顺利到达target
        printHanoiTower(N - 1, help, target, source); // 让N-1从辅助空间回到源空间上去
    }
}

printHanoiTower(3, "A", "B", "C");
//从1-N从A移动到B，C为辅助

2.9二分查找递归解法

全范围内二分查找 等价于三个子问题： 左边找（递归） 中间比 右边找（递归） 注意：左查找和右查找只选其一

static int binarySeArch(int[] arr,int low,int high,int key){
    if(low>high)
        return -1;
    int mid=low+((high-low)>>1);
    int midVal=arr[mid];
    if(midVal<key){
        return binarySearch(arr,mid+1,high,key);
    }
    else if (midVal>key){
        return binarySearch(arr,low,mid-1,key);
    }else{
        return  mid;
    }
}

• 找重复
• 1、找到一种划分方法
• 2、找到递推公式或者等价转换 都是父问题转化为求解子问题
• 找变化的量 变化的量通常要作为参数
• 找到出口 根据参数变化的趋势，对边界进行控制，适时终止递归

2.10算法复杂度

• n!的弱.上界是n^n，因此增长速度非常快，这意味着单位时间内可求解的问题很小，换言之，超慢

• 2^n这样的指数函数增长非常快，这种算法可以认为超慢

• O(n2)和O(n3)增长很快，算法很慢，至少优化到nlgn，O(n2)的有冒泡排序，直接插入排序，选择排序

• nlgn可以认为是及格的算法吧，一般分治法可以缩小层数为lgn，而每层的复杂度一般为O(n)，例如归并排序算法、快速排序算法

• O (n)叫做线性算法，这种算法比较优秀，或者问题本身比较简单，比如求连续求和最大子数组的线性解

• O(sqrt(n))当然比O(n)更快，不是没有，但这种很少

• lgn就是很优秀的算法了，比如二分查找法，但是这种算法往往对输入数据的格式是有要求的，二分查找要求输入数据有序

• 还有一种是常量，无论规模怎么扩大，都花固定时间，这是为数极少的效率最高的算法了，多数是数据很规则

2.10.1递归算法复杂度

2.10.2排序算法的稳定性

• 稳定:如果a原本在b前面，而a=b ,排序之后a仍然在b的前面。
• 不稳定:如果a原本在b的前面，而a=b ,排序之后a可能会出现在b的后面。

2.10.3算法稳定性

题1:小白上楼梯(递归设计)

小白正在上楼梯，楼梯有n阶台阶，小白一次可以上1阶，2阶或者3阶，实现一个方法,计算小白有多少种走完楼梯的方式。

提示：设n阶台阶的走法数为f(n)。如果只有1个台阶，走法有1种（一步上1个台阶），即f(1)=1；如果有2个台阶，走法有2种（一种是上1阶，再上1阶，另一种是一步上2阶），即f(2)=2；如果有3个台阶，走法有4种（一种每次1阶，共一种；另一种是2+1，共两种；第三种是3，共1种），即f(3)=4；

当有n个台阶（n>3）时，我们缩小问题规模，可以这样想：最后一步有三种情况，走1步（之前上了n-1个台阶，走法为f(n-1)种），走2步（之前上了n-2个台阶，走法为f(n-2)种），走3步，（之前上了n-1个台阶，走法为f(n-3)种，f(n)=f(n-1)+f(n-2)+f(n-3),n>3

import java.util.Scanner;

public class _小白上楼梯 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (true) {
            int N=sc.nextInt();
            int re=f(N);
            System.out.println(re);
        }
    }
    private static int f(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        if(n==3){
            return 4;
        }
        return f(n-1)+f(n-2)+f(n-3);
    }
}

题2 :旋转数组的最小数字(改造二分法)

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入-一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 个旋转,该数组的最小值为1.

public class _旋转数组最小值 {
    static int f(int arr[]){
        int be=0;
        int end=arr.length-1;
        //没有旋转直接返回第一个
        if(arr[be]<arr[end]){
            return arr[be];
        }
        while (be+1<end){
            int mid=be+((end-be)>>1);
            if(arr[mid]>=arr[be]){//左边有序，最小值在右边（无序）
                be=mid;
            }else{
                end=mid;
            }
        }
        return arr[end];//最后剩两个元素，右边的位最小值
    }

    public static void main(String[] args) {
        System.out.println(f(new int[]{4,5,6,2,3}));
    }
}

题3 :在有空字符串的有序字符串数组中查找

有个排序后的字符串数组,其中散布着一些空字符串,编写-一个方法,找出给定字符串(肯定不是空字符串)的索引。

1. begin end
2. while
   1. 取中值
   2. 对于出现空串的处理
   3. 比较改变begin或end
3. return -1

public class _在有空字符串的有序字符串数组中查找 {
    static int index(String[] arr,String p){
        int begin=0;
        int end=arr.length-1;
        while(begin<end){
            //取中值
            int mid=begin+((end-begin)>>1);
            //对于出现空串的处理
            while(arr[mid].equals("")){
                mid++;
                if(mid>end){//防止死循环
                    return -1;
                }
            }
            //比较改变begin或end
            if(arr[mid].COMpareTo(p)>0){
                end=mid-1;
            }else if(arr[mid].compareTo(p)<0){
                begin=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] arr = {"a", "", "ac", "", "ad", "b", "", "ba"};
        int res = index(arr, "abc");
        System.out.println(res);
    }
}

题4 :最长连续递增子序列(部分有序)

(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。

public class _最长连续递增子序列 {
    static int findLengthOfLCIS(int[] nums) {
        if(nums.length == 0)
            return 0;
        int max = 0;
        int count = 1;
        for(int i=0;i<nums.length - 1;i++){
            if(nums[i] < nums[i+1]){
                count++;
            }else{
                max = Math.max(count,max);
                count = 1; 
            }
        }
        max = Math.max(count,max);
        return max;
    }
    public static void main(String[] args) {
        System.out.println(findLengthOfLCIS(new int[]{1,3,5,4,7}));
    }
}

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length<1){
            return 0;
        }
        int ans=1;
        int slow=0;
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                ans=Math.max(i-slow+1,ans);
            }else{
                slow=i;
            }
        }
        return ans;
    }
}

题5:设计一个高效的求a的n次幂的算法

static int pow(int a, int n) {
    if (n == 0) return 1;
    int res = a;
    int ex = 1;
    //能翻
    while ((ex << 1) <= n) {
      //翻
      res = res * res;
      //指数
      ex <<= 1;
    }
    //不能翻
    //差n-ex次方没有去乘到结果里面
    return res * pow(a, n - ex);
  }
//or
    public static double pow1(double a,int n ){
        if(n==1) return a;
        return Math.pow(pow1(a,(n>>1)),2) *(n%2!=0 ? a:1);
    }

题6：快速幂

#include<bits/stdc++.h>
#include <cmath>

using namespace std;

double _pow(double x,int n)
{
    if(n==1) return x;
    return pow(_pow(x,n>>1),2)*(n&1 ? x : 1);

}
double _pow1(double x,int n)
{
    double ans = 1;
    while (n)
    {
        if(n&1)
            ans*=x;
        x=x*x;
        n>>1;
    }
    return ans;
}

int main()
{
   cin.sync_with_stdio(false);
   cin.tie(nullptr);
   double x;
   int n;
   cin>>x>>n;
   cout<<_pow(x,n);

   return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的蓝桥杯算法全部内容，希望文章能够帮你解决蓝桥杯算法所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。