- 博客(366)
- 收藏
- 关注
RSS订阅
原创 Leetcode题目汇总（持续更新）
一开始想写Pat甲上的题，但Pat甲上的题考查太单一了，大部分是一些数据结构、图的题，听说Leetcode不错，就刷这个了，发现这个OJ和其它的OJ不太一样，以函数的形式提交题目，样例不能在本地测了，以下每一道题的代码都会有C和Java两份，其实刷算法题用什么语言都大同小异。更新的会非常慢。。。。。1.Two Sum2.Add Two Numbers3.Longest Substrin...
2018-11-13 18:38:27
643
原创 判断合法出栈序列
PIPI现有a-z 26个小球模拟出入栈操作，小球按照a~z的顺序压入栈，在栈顶的元素可以随时被取出，在游戏开始前给出任意26个字母的一些排列，问是否能够由出栈顺序得到这个排列。输入输入包含多组测试用例。每组测试用例包含26个字母组成的一个序列。输出若出栈顺序合法，输出"yes",否则输出"no".样例输入abcdefghijklmnopqrstuvwxyzza...
2019-06-25 19:44:32
1913
原创 FZU - 2203 单纵大法好（贪心+二分）
两年前的坑现在补上，经典的贪心+二分#include <stdio.h>#include <string.h>const int maxn = 200005;int N,K,A,M;int pos[maxn];bool vis[maxn];bool judge(int m){ int i,cnt,len; memset( vis,fals...
2019-05-23 21:17:05
348
原创 HDU - 3345 War Chess（优先队列+BFS）
两年前的坑现在补上，广搜，把点加入优先队列里#include <stdio.h>#include <string.h>#include <queue>using namespace std;int n,m,total;char mp[108][108],ans[108][108];int vis[108][108];int to[4][2] ...
2019-05-23 21:15:22
274
原创 POJ - 1330 Nearest Common Ancestors（倍增LCA）
裸的求LCA，用的倍增，就是为了记个模板，似懂非懂，以后有时间就弄懂这些算法(大概率不会了。。。。。。)#include <queue>#include <stdio.h>#include <string.h>using namespace std;const int MAXN = 10010;const int DEG = 20;stru...
2019-05-23 08:24:32
231
原创 POJ - 3171 Cleaning Shifts（DP+线段树优化）
题意：头牛，每头牛在到时间段干活并需要数量的钱，想要在到时间段的每一时刻都有牛在干活，最少需要多少钱？思路：首先把不在到时间段干活的牛给去除，在把剩下的牛按照从小到大排序，表示从到都有牛干活的最下花费，挨个遍历每个时间段，有： 其中找最小值部分可以用线段树来优化#include <...
2019-05-21 19:44:25
265
原创 POJ - 3734 Blocks（矩阵快速幂）
题意：个球，有红黄蓝绿4种颜色，要求红球和绿球有偶数个，有多少种排列方式？思路：：红球与绿球都为偶数的个数：红球与绿球恰有一个为偶数的个数：红球与绿球都为奇数的个数#include <stdio.h>#include <vector>using namespace std;const int mod = 10007;typedef ...
2019-05-20 09:41:19
203
原创 POJ - 3254 Corn Fields (状压DP)
题意：个格子，有些可以放牛，有些不可以放牛，放的牛不能相邻，问共有多少种放牛的方案？思路：状压，表示第行状态为前行的方案数目，外层循环一行一行的枚举，内层嵌套枚举第行的状态和第行的状态，最后答案为#include <stdio.h>#include <string.h>const int mod = 100000000;int dp[15][1 <&l...
2019-05-19 19:18:02
196
原创 POJ - 2441 Arrange the Bulls （状压DP）
题意：头牛，个牛棚，每个牛棚只能有一头牛，每头牛都只能在自己喜欢的牛棚里，给每头牛安排位置，总共有多少种安排方案？思路：每个牛棚可以放牛也可以不放牛，个牛棚，故可以用状压，表示状态下，给前i头牛分配牛棚的方案数 ( & ，)当前状态只与上一状态有关，可以用滚动数组来节省空间#include <stdio.h>#include <string....
2019-05-19 18:23:31
226
原创 POJ - 3411 Paid Roads（Dijkstra+状压）
题意：个城市，条单向路，每一条路从到，如果之前已经经过了城市，花费可以为也可以为，没有经过城市，花费为，求从城市到的最小花费思路：求最短路，多加一维表示已经走过的点的集合。#include <stdio.h>#include <string.h>#include <queue>#include <algorithm>const in...
2019-05-19 17:23:09
251
原创 POJ - 1795 DNA Laboratory（状压DP）
题意：个只包含字母的字符串，求出包含这n个字符串的最短字符串思路：1.首先除去相同的和被包含在其它字符串里的字符串2.求出，把第i个字符串放到第j个字符串前花费3.状压，，第个字符串在最前面，状态为情况下的最小花费边界：递推方程：这样就求出了最短长度下的第一个字符串s4.从开始贪心的求出最优解#include <stdio.h>#include ...
2019-05-19 17:12:30
292
原创 POJ - 2836 Rectangular Covering（状压DP+几何）
题意：平面上有n个点，要求用矩形去覆盖所有的点，每一个矩形至少覆盖两个点，每一个点可以被重复覆盖，求最小的能覆盖所有点的矩形的面积。思路：枚举两个点，一个矩形覆盖这两个点的最小面积是以这两个点为对角线，所以我们可以得到个矩形，求出这些矩形的面积和覆盖的点，接下来就是状压了： ...
2019-05-19 16:53:16
196
原创 POJ - 2886 Who Gets the Most Candies? （线段树+反素数）
题意：有个小盆友围成一圈，从第个小朋友开始，选中谁谁退圈，每个小朋友都有一个数，这个数为正数表明下一个选中的小朋友即为这个小朋友左边第个小朋友，为负数表明下一个选中的小朋友为这个小朋友右边第个小朋友。每个小朋友退圈即可获得的因子数的糖果数，为这个小朋友是第几个退圈的，输出这个获得最多的糖果的小朋友的名字和她获得的糖果数。思路：个小朋友，获得最多的糖果的那个人的编号为中有最多因子数的那个数，所以...
2019-05-18 09:41:58
272
原创 POJ-2991 Crane（线段树）
题意：给出n条线段，开始时n条线段一词首尾相连，与地面垂直，c次操作，每次操作给出,，让线段和之间德角度变为度，并输出第n条线段的前端坐标。思路：线段树，区间存储的线段的向量坐标，父亲节点的向量坐标就等于儿子节点的向量坐标相加，在存储一个角度变量，类似于懒惰标记的作用，将一条线段逆时针旋转v度后的坐标为顺时针：#include <math.h>#incl...
2019-05-16 21:40:47
247
原创 POJ - 3279 Fliptile(反转)
题意：一个01矩阵，每翻转一个格子，这个格子的上下左右的格子都会被翻转，要把整个矩阵的格子都翻转为0，求需要翻转的最小次数，最小次数的解为多个时，输出字典序最小的一组。解不存在输出IMPOSSIBLE。思路：如果暴力搜索的话有种翻转的方法，超时。如果第一行是否翻转已经确定，那么第二行是否翻转也确定了，同理除了最后一行其余所有的格子是否翻转都已确定了，如果最后一行有1的话就说明不存在可行解。所以...
2019-05-15 14:40:24
625
原创 POJ - 3320 Jessica's Reading Problem（尺取法）
题意：求最少的连续读的页数能读到所有的知识点思路：尺取法，把所有的知识点的编号放到set里求出知识点的个数，在尺取过程中用map记录当前以学知识点的个数。#include <map>#include <set>#include <stdio.h>#include <algorithm>#define maxn 1000005usi...
2019-05-15 14:20:28
195
原创 数论基础
欧几里德算法即求两个数的最大公因子int GCD(int a,int b){ if(b == 0) return a; else return GCD(b,a % b);}扩展欧几里德算法它可以用来求解（a，b，c为整数）的方程的一组整数解，事实上，只有时，此方程才有整数解。具体实现ll exgcd(ll a,ll b,ll& x,ll&am...
2019-05-13 21:57:02
361
原创 UVA - 11582 Colossal Fibonacci Numbers!（取模）
题意：输入两个非负整数a，b（0 <= a,b < 2^64）和 n（1<= n < 1000)，输出f（a^b) % n，f为斐波那契数列。思路：所有计算都是对n取模的，不妨设F(i) = f(i) % n，当f(i - 1)，f(i)出现重复时，整个序列就开始重复。余数最多有n种，所以最多n*n项就会出现重复，所以先计算出周期，再用快速幂求出a^b%M即可。#...
2019-05-11 21:06:35
260
原创 POJ - 1061 青蛙的约会 （扩展欧几里得找最小正整数解）
题意：两只青蛙在圆圈上追赶，圆圈我们可以看作是一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。总长L米。现在要你求出它们跳了几次以后才会碰面。思路：设跳了t次以后才会碰面，则有(x + tm) % L = (y + tn) % L，即 (x + tm) - (y + tn) = PL，整理得：(n -...
2019-05-10 09:29:46
353
原创 POJ - 3292 Semi-prime H-numbers (埃氏筛思想）
题意：H数为4n + 1这样的数，H数的乘法是封闭的，H素数只能表示为1和它本身的乘积，除了H素数，其余的都是H合数，半素数是恰好能表示为两个H素数的乘积，给出一个数X，输出这个数以及小于等于这个数的半素数的个数思路：埃氏筛思想#include <stdio.h>const int maxn = 1000005;int a[maxn],cnt[maxn];void in...
2019-05-09 21:46:40
246
原创 POJ 3421 X-factor Chains（素数分解定理+组合数学）
题意：给出一个数X，找出1~X的因子序列，使得前一个数可以整除后一个数，求满足条件的最大链长以及有多少个最长链思路：根据素数分解定理：X=p1^a1 * p2^a2 * pn^an，最大链长等于a1 + a2 + ..... + an，即素因子的个数，最长链长数就是这些素因子的排列组合数。根据多重组合数可得这些素因子得排列组合数位（a1 + a2 + ..... + an)! / (a1! *...
2019-05-09 21:37:03
378
原创 [LeetCode ] Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at ...
2018-12-05 16:24:01
177
原创 [LeetCode ] House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent hous...
2018-12-05 16:20:32
153
原创 [LeetCode ] Weekly Contest 113
Largest Time for Given DigitsGiven an array of 4 digits, return the largest 24 hour time that can be made.The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a ti...
2018-12-03 16:29:04
212
原创 [LeetCode ] Weekly Contest 112
Minimum Increment to Make Array UniqueGiven an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.Return the least number of moves to make every value in A unique...
2018-11-27 11:14:47
185
原创 [LeetCode ] Best Time to Buy and Sell Stock系列题解
这一系列的题目的基本模型是给出n天每天股票的价格，可以在任意一天买股票，在之后的任意一天把股票卖出，赚取差价，限制是手中最多有一张股票，必选把手中的股票卖掉才能再买股票。求最大获利。题目1：Best Time to Buy and Sell Stock这是最简单的一道题，在基本模型的基础上添加了一个限制条件，最多交易一次。我们从第一天开始遍历，维护一个已经遍历过的股票的最小价格mi...
2018-11-24 21:02:21
342
原创 [LeetCode ] Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assum...
2018-11-22 14:14:25
215
原创 [LeetCode ] Basic Calculator
Implement a basic calculator to evaluate a simple expression string.The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty s...
2018-11-22 09:02:41
223
原创 [LeetCode ] Minimum Absolute Difference in BST
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.Example:Input: 1 \ 3 / 2Output:1Explanation:T...
2018-11-20 11:04:41
166
原创 [LeetCode ] Weekly Contest 111
Valid Mountain ArrayGiven an array A of integers, return true if and only if it is a valid mountain array.Recall that A is a mountain array if and only if:A.length >= 3 There exists some i...
2018-11-18 19:07:33
333
原创 [LeetCode ] Long Pressed Name
Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.You examine the typed characte...
2018-11-17 10:00:31
205
原创 [LeetCode ] H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.According to the definition of h-index on Wikipedia: "A s...
2018-11-17 09:18:48
258
原创 [LeetCode] Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.Example:Input: [0,1,0,3,12]Output: [1,3,12,0,0]Note:You...
2018-11-16 15:31:27
155
原创 [LeetCode ] Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.Example 1:Input: s = "anagram", t = "nagaram"Output: trueExample 2:Input: s = "rat", t = "car"Output: f...
2018-11-16 14:45:39
145
原创 [LeetCode ]Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.Example 1:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.E...
2018-11-15 19:12:10
211
原创 [LeetCode] Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).You may assume nums1 and ...
2018-11-14 19:44:50
202
原创 [LeetCode] Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.Example 1:Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:...
2018-11-14 19:09:59
220
原创 [LeetCode] Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same...
2018-11-13 17:13:34
183
原创 [LeetCode] Add Two Numbers（链表合并+模拟加法）
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return ...
2018-11-13 17:08:10
366
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人