19821220-CSDN博客

原创保研面试英文算法题临时抱佛脚训练思路系列——搜索专题

专题二 DFS与BFSA1103 Integer FactorizationThe K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K

2020-09-18 14:11:06 222

原创保研面试英文算法题临时抱佛脚训练思路系列——动态规划

专题一动态规划A1007 Maximum Subsequence SumGiven a sequence of K integers { N1N_1N1 , N2N_2N2 , …, NKN_KNK }. A continuous subsequence is defined to be { NiN_iNi , Ni+1N_{i+1}Ni+1 , …, NjN_jNj } where 1≤i≤j≤K. The Maximum

2020-09-16 20:10:52 558

原创《算法笔记》Codeup练习 11.3小节最长不下降子序列（LIS）

问题A 最长不下降子序列（LIS）题目大意给定一个序列，求其不下降子序列的最大长度。（子序列不要求连续）思路动态规划dp[i]=max{dp[j]+1,dp[i]}dp[i]初始化全为1代码#include <iostream>#include <cstdio>using namespace std;int main(int argc, const char * argv[]) { int N; int num[1001],dp[1001];

2020-08-12 23:49:35 130

原创 PAT自主训练记录甲级A1007 Maximum Subsequence Sum

A1007 Maximum Subsequence Sum（25分）题目描述Given a sequence of K integers { N1N_1N1 , N2N_2N2 , …, NKN_KNK }. A continuous subsequence is defined to be { NiN_iNi , Ni+1N_{i+1}Ni+1 , …, NjN_jNj } where 1≤i≤j≤K. The Maximum Su

2020-08-11 17:57:43 113

原创《算法笔记》Codeup练习 11.2小节最大连续子序列和

问题A 最大连续子序列和题目大意给定一串数列，求其连续自序列的和最大值，并输出自序列的起始和结束端的数值。思路考虑到要输出自序列的两端数值，采用结构体。有三个属性：value：该位置的数字startV：以该位置为结尾的连续子序列和最大的子序列的开始值dp：以该位置为结尾的连续子序列和的最大值利用动态规划的思想，dp[i]=max{dp[i-1]+num[i-1],num[i-1]}、dp[0]=num[0]，同时根据具体情况更新startV的值。注意当序列里的数字都是负数时，最大和输

2020-08-11 17:38:12 136

原创《算法笔记》Codeup练习 11.1小节动态规划的递归写法和递推写法

问题A Fibonacci题目大意给一个数n，求它的斐波拉契数的结果。思路有好几种做法，这里就用动态规划的递归写法吧。过程中犯的错误这题似乎是多组测试数据，不是一组，刚开始当一组写了。初始化dp数组值为-1时，不可以直接 int dp[31]={-1};需要用循环来初始化。代码#include <cstdio>#include <iostream>using namespace std;int dp[31];int Fibonacci(int n){

2020-08-10 16:40:07 114

原创 PAT自主训练记录甲级A1049 Counting Ones

A1049 Counting Ones(30分)题目描述The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.Input

2020-08-10 10:48:10 117

原创 PAT自主训练记录乙级B1008 数组元素循环右移问题

B1008 数组元素循环右移问题（20分）题目描述一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0A_0A0A1A_1A1⋯AN−1A_{N−1}AN−1）变换为（AN−MA_{N−M}AN−M⋯AN−1A_{N−1}AN−1A0A_0A0A1A_1A1⋯AN−M−1A_{N−M−1}AN−M−1）（最后M个数循环移至最前面的M个位置）。如果需

2020-08-07 16:04:01 104

原创 PAT自主训练记录甲级A1008 Elevator

A1008 Elevator（20分）题目描述The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up on

2020-08-06 18:48:36 128

原创 PAT自主训练记录甲级A1104/乙级B1049 数列的片段和

A1104 Sum of Number Segments（20分）附有详细解释以及代码的博文链接：https://blog.csdn.net/qq_21394327/article/details/106975016点击跳转题目描述Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2

2020-08-05 23:55:28 813

原创《算法笔记》Codeup练习 5.2小节最大公约数与最小公倍数

问题A Least Common Multiple题目大意多组测试数据，每组数据占一行。每行第一个数据m代表这组有m的数求最小公倍数，后接m个数值。思路循环输入m个数，用一个变量记录当前的最小公倍数，之后每输入一个就与当时的最小公倍数变量一起求最小公倍数。这题的测试数据应该是默认数据按照递增输入的，同时也就顺便保证了当前的最小公倍数比即将输入的数值小。代码#include <iostream>#include <stdio.h>#include <algor

2020-08-05 15:42:52 143

原创《算法笔记》Codeup练习 5.1小节简单数学问题

问题A 守形数题目大意给一个整数N（2≤N＜100），判断N平方后的数的地位部分是否为N。例：25225^2252=625，低位部分是25，则25是守形数。思路首先得出N的位数w，接着用N对10m10^m10m求余，判断余数是否等于N。代码#include <iostream>#include<stdio.h>#include<cstdio>#include<math.h>#include<algorithm>using n

2020-08-05 11:18:03 396

原创《算法笔记》Codeup练习 4.7小节其他高技巧与算法

问题A 找第K大数题目大意给定一个长度为n（1≤n≤1,000,000）的无序正整数序列，以及另一个数k（1≤k≤1,000,000）（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。）注意这题可以选择把数字排序之后，输出第k个数字（这样也是可以通过的）不过有更有的解法——随机选择。有个快排的思想在里面。#include<stdio.h>#include<cstdio>#include<iostream>#include<cm

2020-08-04 13:40:39 192

原创 PAT自主训练记录甲级1093 Count PAT‘s

A1093 Count PAT’S（25分）题目描述The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.Now given any string, you are sup

2020-08-04 13:33:07 155

原创 PAT自主训练记录甲级1069/乙级1019 The Black Hole of Numbers

1069 The Black Hole of Numbers（20分）题目描述For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second nu

2020-08-04 13:16:47 141

原创《算法笔记》Codeup练习 4.6小节 two pointers

问题A 二路归并排序(mergeSort)递归法题目大意就是最基础的递归二路归并排序的算法思想。注意这题测试结果Runtime Error80就是正确的。//// main.cpp// 二路归并排序（mergesort）递归法//// Created by JustforStar on 2020/7/25.// Copyright © 2020 JustforStar. All rights reserved.//#include<stdio.h>#includ

2020-07-25 21:39:56 215

原创 PAT自主训练记录甲级1029 Median

1029 Median（25分）题目描述Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences i

2020-07-24 15:53:16 103

19821220的博客