1. 首页
  2. 文章中心
  3. 算法

研究生算法课程笔记

66 阅读 0 评论
我是靠谱客的博主 端庄月亮，最近开发中收集的这篇文章主要介绍研究生算法课程笔记，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

    • 1.1、最长合法区间
      • 题目
      • 题解
    • 1.2、Ahpelios会数数
      • 题目
      • 题解
    • 1.3、kstring
      • 题目
      • 题解
    • 1.4、杰哥与数字
      • 题目
      • 题解
    • 2.1、杰哥和序列
      • 题目
      • 题解
    • 2.2、YY and Lucky Number
      • 题目
      • 题解
    • 2.3、YY and One
      • 题目
      • 题解

1.1、最长合法区间

题目

在这里插入图片描述

题解

C语言代码

#include<stdio.h>
#include<stdlib.h>

int max(int a, int b) {
	return a > b ? a : b;
}

int main() {
	int n;
	scanf("%d", &n);
	int *arr = (int *)malloc(n * sizeof(int));
	int flags[100000];
	int i = 0;
	for (i = 0; i < n; i ++) {
		scanf("%d", &arr[i]);
	}
	
	i = 0;
	int j = 1;
	int maxIntervel = 1;
	int count = 1;
	flags[arr[i]] = 1;
	int iNum, jNum;
	while (j < n) {
		jNum = arr[j];
		flags[jNum] ++;
		if (flags[jNum] == 1) {
			count ++;
			while (count > 2) {
				iNum = arr[i];
				flags[iNum] --;
				if (flags[iNum] == 0) {
					count --;
				}
				i ++;
			}
		}
		maxIntervel = max(maxIntervel, j - i + 1);
		j ++;
	}
	
	printf("%d", maxIntervel);
	return 0;
}

Java代码
评判机制问题，同一解法，JAVA只能得8分，提示内存超出限制

import java.util.Scanner;

/**
 * 最长合法区间
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = in.nextInt();
        }

        int[] flags = new int[100000];
        int count = 1;
        int maxInterval = 1;
        int i = 0, j = 1;
        flags[numbers[0]] = 1;
        while (j < n) {
            int num = numbers[j];
            flags[num] ++;
            if (flags[num] == 1) {
                count ++;
                while (count > 2) {
                    int iNum = numbers[i];
                    flags[iNum] --;
                    if (flags[iNum] == 0) {
                        count --;
                    }
                    i ++;
                }
            }
            maxInterval = Math.max(maxInterval, j - i + 1);
            j ++;
        }
        System.out.println(maxInterval);
    }
}

1.2、Ahpelios会数数

题目

在这里插入图片描述

题解

C代码

#include<stdio.h>
int map[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int countNum(int num) {
	if (num == 0) {
		return map[0];
	}
	int sum = 0;
	while (num > 0) {
		sum += map[num % 10];
		num /= 10;
	}
	return sum;
}

int main() {
	int n, i;
	long res = 0;
	scanf("%d", &n);
	for (i = 0; i <= n; i ++) {
		res += countNum(i);
	}
	
	printf("%d", res);
	return 0;
}

Java代码

import java.util.Scanner;

public class Main {
    public static int[] map = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long res = 0;
        for (int i = 0; i <= n; i++) {
            res += dealNumStr(String.valueOf(i));
        }
        System.out.println(res);
    }


    public static int dealNumStr(String numStr) {
        int total = 0;
        for (int i = 0; i < numStr.length(); i++) {
            String s = numStr.substring(i, i + 1);
            total += map[Integer.parseInt(s)];
        }
        return total;
    }
}

1.3、kstring

题目

在这里插入图片描述

题解

C++代码
评优代码只有6分

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int k;
	string input;
	cin>>input>>k;
	int len = input.size()-k+1;
	for(int a=0; a<26; a++) {
		multimap<string,int> node;
		for(int i=0; i<len; i++) {
			char head = input[i];
			if(head == (char)(a+'a'))
				node.insert(pair<string,int>(input.substr(i,k),i+1));
		}
		if(!node.size()) continue;
		multimap <string,int>::iterator it ;
		for(it= node.begin(); it!=node.end(); ++it) {
			printf("%d ",it->second);
		}
		node.clear();
	}
	return 0;
}

Java代码
5分

import java.util.*;

/**
 * kstring
 */
public class Q1_Kstring {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int k = in.nextInt();
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < 26; i++) {
            treeMap.clear();
            for (int j = 0; j <= s.length() - k; j++) {
                if (s.charAt(j) == 'a' + i) {
                    // 字符串最后加上j是为了避免TreeMap键值相同时的覆盖操作
                    treeMap.put(s.substring(j, j + k) + j, j + 1);
                }
            }
            if (treeMap.size() > 0) {
                for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
                    System.out.print(entry.getValue() + " ");
                }
            }
         }
    }
}

1.4、杰哥与数字

题目

在这里插入图片描述

题解

Java代码10分

import java.util.Scanner;

public class Q1_JacksonNumber {
    /*
     * 记录n是否存在某个数字
     */
    static boolean[] bits = new boolean[10];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // 初始化bits
        int temp = n;
        while (temp > 0) {
            bits[temp%10] = true;
            temp /= 10;
        }

        int count = 0;
        for (int i = 1; i * i <= n; i ++) {
            if (n % i != 0) {
                continue;
            }
            int b = n/i;
            if (i == b) {
                if (hasSameBit(i)) {
                    count ++;
                }
            } else {
                if (hasSameBit(i)) {
                    count ++;
                }
                if (hasSameBit(b)) {
                    count ++;
                }
            }
        }

        System.out.println(count);
    }

    public static boolean hasSameBit(int num) {
        while (num > 0) {
            if (bits[num%10]) {
                return true;
            }
            num /= 10;
        }
        return false;
    }
}

2.1、杰哥和序列

题目

在这里插入图片描述

题解

Java代码8分，内存超出限制

import java.util.Scanner;

/**
 * 杰哥和序列
 */
public class Q2_1 {
    public static int[] nums;
    public static int[] temp;
    public static int res = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        nums = new int[n];
        temp = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        countInversionPair(0, nums.length - 1);
        System.out.println(Math.min(a, b) * res);
    }

	// 计算数组中逆序对个数
    public static void countInversionPair(int left, int right) {
        if (left < right) {
            int mid = left + (right - left)/2;
            countInversionPair(left, mid);
            countInversionPair(mid + 1, right);

            int begin = mid;
            int end = right;
            int index = end;
            while (index >= left) {
                if (nums[begin] > nums[end]) {
                    res += end - mid;
                    temp[index --] = nums[begin --];
                } else {
                    temp[index --] = nums[end --];
                }
                if (begin == left - 1) {
                    while (index != left - 1) {
                        temp[index --] = nums[end --];
                    }
                }
                if (end == mid) {
                    while (index != left - 1) {
                        temp[index --] = nums[begin --];
                    }
                }
            }

            for (int i = left; i <= right; i++) {
                nums[i] = temp[i];
            }

        }

    }

}

C++代码10分

#include<bits/stdc++.h>
#define ll long long
#define N 100000+9

using namespace std;

int n, nums[N], temp[N];
ll a,b,num=0;

void countInversionPair(int l,int r){
    if( l!=r ){
        int mid=(l+r)>>1;
        countInversionPair(l,mid);
        countInversionPair(mid+1,r);
        int index=r,begin=mid,end=r;
        while( index>=l ){
            if( nums[begin]>nums[end] ){
                num+=(end-mid);
                temp[index--]=nums[begin--];
            }
            else
                temp[index--]=nums[end--];
            if( begin==l-1 ) while( index!=l-1 ) temp[index--]=nums[end--];
            if( end==mid ) while( index!=l-1 ) temp[index--]=nums[begin--];
        }
        for( int i=l ; i<=r ; i++ ) nums[i]=temp[i];
    }
}

int main()
{
    scanf("%d %lld %lld",&n,&a,&b);
    for( int i=1 ; i<=n ; i++ ) scanf("%d",&nums[i]);
    a=min(a,b);
    countInversionPair(1,n);
    printf("%lld",num*a);
    return 0;
}

2.2、YY and Lucky Number

题目

在这里插入图片描述

题解

C++代码9分

#include <bits/stdc++.h>

using namespace std;

int cache[10] = {0, 9, 99, 351, 927, 2151, 4671, 9783, 20079, 40743};
int digest[11] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,1000000000};
int bitSet[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int onlyTwoNum(int num) {
	if (num == 0) {
		return 1;
	}
	int i = 0;
	for (i = 0; i < 10; i ++) {
		bitSet[i] = 0;
	}
	int count = 0;
	while (num > 0) {
		int b = num % 10;
		if (bitSet[b] == 0) {
			bitSet[b] = 1;
			count ++;
		}
		num /= 10;
	}
	return count <= 2;
}

long luckyNumber(long num, int length) {
	// 获取最高位
	int topDigit = num / digest[length];
	// length - 1 位下的luckyNum的数目 和 枚举所有最高位的luckyNum的数目
	// 若num = 51458 那么，现在只需要统计 5xxxx 中luckyNum的数目
	long res = cache[length - 1] + (cache[length] - cache[length - 1]) / 9 * (topDigit - 1);
	for (int i = topDigit * digest[length]; i <= num; i++) {
		if (onlyTwoNum(i)) {
			res ++;
		}
	}
	return res;
}

int main()
{
	long n;
	cin>>n;
	int length = 0, temp = n;
	while (temp > 0) {
		temp /= 10;
		length ++;
	}
	int res;
	if (n == 1000000000) {
		res = cache[9] + 1;
	} else {
		res = luckyNumber(n, length);
	}
	cout<<res;
	return 0;
}

Java代码8分

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static int[] cache = {0, 9, 99, 351, 927, 2151, 4671, 9783, 20079, 40743};
    public static int[] digest = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    public static Set<Integer> bitSet = new HashSet<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int res;
        if (n == 1000000000) {
            res = cache[9] + 1;
        } else {
            res = luckyNumber(n);
        }
        System.out.println(res);
    }

    public static int luckyNumber(int num) {
        // 获取位数
        int length = String.valueOf(num).length();
        // 获取最高位
        int topDigit = num / digest[length];
        // length - 1 位下的luckyNum的数目 和 枚举所有最高位的luckyNum的数目
        // 若num = 51458 那么，现在只需要统计 5xxxx 中luckyNum的数目
        int res = cache[length - 1] + (cache[length] - cache[length - 1]) / 9 * (topDigit - 1);


        for (int i = topDigit * digest[length]; i <= num; i++) {
            if (onlyTwoNum(i)) {
                res ++;
            }
        }
        return res;
    }

    public static boolean onlyTwoNum(int num) {
        if (num == 0) {
            return true;
        }
        bitSet.clear();
        while (num > 0) {
            bitSet.add(num % 10);
            num /= 10;
        }
        return bitSet.size() <= 2;
    }

}

2.3、YY and One

题目

题解

Java代码10分

import java.util.Scanner;

public class Main {
    public static long[] oneNum = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111L, 111111111111L, 1111111111111L, 11111111111111L};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        System.out.println(oneTotal(n));
    }

    public static long oneTotal(long num) {
        num = Math.abs(num);
        if (num == 0) {
            return 0;
        }

        int length = String.valueOf(num).length();
        long res1 = Math.abs(num - oneNum[length]);
        long res2 = Math.abs(num - oneNum[length + 1]);

        // 判断xxxx与1111和11111哪个更接近
        if (res1 < res2) {
            return length + oneTotal(res1);
        } else {
            return length + 1 + oneTotal(res2);
        }
    }

}

C++代码10分

#include <bits/stdc++.h>
using namespace std;
long long oneNum[15] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111};

long long mathAbs(long long num) {
    return num < 0 ? -num : num;
}

int getLength(long long num) {
    int len = 0;
    while (num > 0) {
        len ++;
        num /= 10;
    }
    return len;
}

long long oneTotal(long long num) {
	num = mathAbs(num);
	if (num == 0) {
		return 0;
	}

	int length = getLength(num);
	long long res1 = mathAbs(num - oneNum[length]);
	long long res2 = mathAbs(num - oneNum[length + 1]);

	// 判断xxxx与1111和11111哪个更接近
	if (res1 < res2) {
		return length + oneTotal(res1);
	} else {
		return length + 1 + oneTotal(res2);
	}
}

int main()
{
	long long n;
	cin >> n;

	cout << oneTotal(n) << endl;
	return 0;
}

最后

以上就是端庄月亮为你收集整理的研究生算法课程笔记的全部内容，希望文章能够帮你解决研究生算法课程笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(44)

相关文章

ASP.NET 环境下的页面验证控件
ASP.NET 环境下的页面验证控件
计算机软件与理论主修课程,软件工程专业主修课程
计算机软件与理论主修课程,软件工程专业主修课程
.NET的身份验证方式有哪些？分别是什么原理？
.NET的身份验证方式有哪些？分别是什么原理？
国二c语言题目给分,及三计算机国二c语言个别考题分析.docx
国二c语言题目给分,及三计算机国二c语言个别考题分析.docx
研究生算法课程笔记
研究生算法课程笔记
推荐系统学习(一)
推荐系统学习(一)
CMMI的五个级别及其特征
CMMI的五个级别及其特征
大数据之一：几个概念
大数据之一：几个概念

评论列表共有 0 条评论

立即
投稿
返回
顶部