- 博客(48)
- 收藏
- 关注
RSS订阅原创 Leetcode 102. 二叉树的层序遍历
题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。思路：广度优先遍历搜索（BFS），在Java中用List+Queue实现。1.首先将每一层的点加入到队列中（从根节点开始）2.对于每一层而言，只需要得到当前非空队列的大小，即当前层的节点数量，对每个节点进行左右子节点的判断，即若存在子节点，则加入到队列中。Java代码：/** * Definition for a binary tree node. * public class Tre
2020-12-21 14:51:56
77
原创 Leetcode 746. 使用最小花费爬楼梯
题目描述：数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。思路：对于每一层楼梯来说，设其最小话费为dp[i]，那么dp[i] = min( dp[i-1]+cost[i-1], dp[i-2]+cost[i-2] )。Java代码：class Sol
2020-12-21 11:39:53
75
原创 Leetcode 714. 买卖股票的最佳时机含手续费
题目描述:给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。思路:每一天都只有有股票在手和没股票在手两种状态，前着对应卖和不卖，后者对应买和不买。Java代码：class Solution { public int[][] dp = new int[50050][2];
2020-12-17 18:06:59
83
1
原创 Leetcode 290. 单词规律
题目描述：给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。思路：利用HashMap将字符串和字符双向对应起来，遍历判断。Java代码：class Solution { private ConcurrentMap<String,Character> map1 = new ConcurrentHashMap&l
2020-12-16 13:25:19
69
原创 Springboot Error parsing Mapper XML
记录一下Springboot项目中的一些错误。org.springframework.beans.factory.UnsatisfiedDependencyException: Error creating bean with name 'competitionController': Unsatisfied dependency expressed through field 'competitionService'; nested exception is org.springframework.be
2020-12-03 10:48:58
2170
原创 Leetcode 17.电话号码的字母组合
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。解题思路：把每个键对应的字符串存下来，用dfs对数字字符串每一位进行枚举。Java代码：class Solution { String[][] num = new String [10][6]; public List<String>ans = new ArrayList<String>(); publi
2020-12-01 13:46:00
55
原创 Leetcode 16.最接近的三数之和
题目描述：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。解题思路：先将每个数乘3，减去target，然后两重循环+二分找出绝对值最小的三数之和。（为什么二分这么慢。。。）Java代码：class Solution { public int threeSumClosest(int[] nums, int target) { int
2020-12-01 11:43:56
52
原创 Leetcode 15.三数之和
题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。解题思路：先将数组排序，然后循环找出两个数的和，用二分查找找出剩余的那个数。要注意不能重复。Java代码：class Solution { public List<List<Integer>> threeSum(int[] nums) {
2020-12-01 10:48:44
55
原创 Leetcode 14.最长公共前缀
题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。解题思路：第一种就是纵向比对，当比较到当前位置字符不全相等时就可以返回当前位置前当字符串。第二种是二分查找，二分的条件是当前长度的前缀是否都相同。第三种是先排序，然后纵向比较第一个和最后一个字符串的最长前缀。总的来说第一种和第三种复杂度差不多，第二种复杂度较大。Java代码：class Solution { public String longestCommonPrefix(Stri
2020-12-01 10:07:44
63
原创 Leetcode 13.罗马数字转整数
题目：给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。字符 数值I 1V 5X 10L 50C 100D 500M 1000I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90
2020-12-01 09:43:29
71
原创 Leetcode 12.整数转罗马数字
题目：给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。字符 数值I 1V 5X 10L 50C 100D 500M 1000I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
2020-12-01 09:06:26
54
原创 Leetcode 11.盛最多水的容器
题目描述：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。解题思路：用两个值l,r表示区间的起止下标，如果height[l]<height[r]，l向后移，否则r向前移。这样做的原理是，如果有一方较小，如果移动较大的一方，所得到的面积只会更小，而移动较小的一方，可以准确地遍历出最大的区域面
2020-11-30 17:43:15
59
原创 Leetcode 955. 删列造序 II
题目：给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。比如，有 A = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 A 为["bef", "vyz"]。假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（A[0] <= A[1] <= A[2] ... <= A[A.length - 1]）排列的，然后请
2020-11-27 18:03:29
69
原创 Leetcode 09.回文数
题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。负数因为带负号的原因不可能回文，其余的只要判断其回文的数是否相等即可。class Solution { public boolean isPalindrome(int x) { if(x < 0)return false; int a = x; int b = 0; while(x > 0) { b
2020-11-20 17:31:58
49
原创 Leetcode 08.字符串转换整数 (atoi)
题目描述：请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一
2020-11-20 17:17:17
79
原创 Leetcode 07. 整数反转
题目描述：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。思路：因为当数的范围超过int时，再进行计算将会得到非预期的答案，可以利用这个特点。Java代码：class Solution { public int reverse(int x) { int ans = 0; while (x != 0) { //每次在下一位加上去后除以10和之前的答案比较，如果不一样说明超限了 if((ans * 1
2020-11-20 16:17:22
50
原创 Leetcode 06.Z 字形变换
题目描述：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。思路：这题很容易得出一、第一行和最后一行两个字符下标相差2*(numRows - 1)二、其余行两个字符相差为2*(numRows - 1) - 2i 和 2i （i表示行数，从0开始）Java代码：class Solution { public String convert(String s, int numRows) { int len = s.length(); if(
2020-11-20 15:05:36
62
原创 Leetcode 05.最长回文子串
题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。思路1:动态规划，对长度从1到len的字符串判断是否为回文，时间复杂度O(nn)，空间复杂度O(nn)。Java代码：class Solution { public String longestPalindrome(String s) { int len = s.length(); int[][] dp = new int[1010][1010];
2020-11-10 17:18:18
64
原创 Leetcode 3.无重复字符的最长子串
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。Java代码：class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0, start = 0; int[] map = new int[130];//用数组来存比较省时间 int len = s.length(); for (int i = 0; i < l
2020-10-31 13:53:34
80
原创 Leetcode 2.两数相加
题目描述：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。Java代码：/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListN
2020-10-31 13:21:35
52
原创 Leetcode 1.两数之和
题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。Java代码：class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); for (int i = 0; i &
2020-10-31 13:02:11
51
原创 Leetcode 983.最低票价
题目描述：这道题肯定是采用动态规划的方法。1.设一个dp数组表示完成当前计划后的最小花费；2.首先要处理出每一个一个计划日对于7天通行证和30天通行证的最优前计划日（即最小）。3.假定每一天都买一张为期为一天的通行证，那么花费以costs[0]累加；4.对于7天通行证来说，遍历从当前计划日的前计划日开始到当前计划日，比较得出最小的花费（min(dp[i],dp[j]+costs[1])）。5.对于30天通行证来说，也同样如此。最后得到的dp[len-1]就是要返回的答案。代码：class
2020-05-08 23:33:41
122
原创 POJ 3176 Cow Bowling
题意：有一个n行的矩阵，第一行有一个数，每一行比上一行多一个数，从第一行开始，可以加左下或右下的数，问到最后一行的结果最大是多少。思路：虽然是dp专题，但是还是比较像是贪心。遍历每一个数，更新其值为自身加上左上和右上中的最大值，最后比较最后一行的最大值得出答案。代码：#include<iostream>#include<algorithm>#include<...
2020-03-18 09:46:58
83
原创 POJ 3262 Protecting the Flowers
题意：有n头牛，赶每头牛回去和赶回来的时间是Ti，留下的每头牛每分钟会吃Di的草，每次只能赶一头牛，问最少会吃多少的草。思路：每次赶牛回去，留下的牛会吃掉所有牛的Di和乘上赶这头牛回去的时间的两倍，所以要让Di大，Ti小的牛先被赶回去，即按照Di/Ti从大到小排序。代码：#include<iostream>#include<algorithm>#include&l...
2020-03-17 23:30:34
123
1
原创 POJ 2393 Yogurt factory
题意：有一家酸奶场，每周可以用C_i的价格产生一个单位的酸奶，每周要供应Y_i单位的酸奶，酸奶保存一周要s的价格，问最少要多少钱能满足每周提供要求的酸奶。思路：按照每周每单位酸奶最少的价格，贪心求出答案。代码：#include<iostream>#include<algorithm>#include<stdlib.h>#include<math...
2020-03-13 23:19:48
88
原创 POJ 2376 Cleaning Shifts
题意：有n个区间，要选择最少的区间使区间包含1—T中所有的数。思路：用结构体存储区间的左值和右值，先按照开始时间从小到大排，开始时间一样的时候按结束时间从大到小排。代码：#include<stdio.h>#include<stdlib.h>#include<iostream>#include<algorithm>using names...
2020-03-10 22:42:56
54
原创 POJ 3050 Hopscotch
题意：有一个5*5的矩阵，一共25个数，都是一位，每个位置可以上下左右四个方向走，可以走过去再走回来，问一共有多少种不同的长度为6的数字顺序（如111211）这样。思路：对每一个位置进行dfs，用string记录数字顺序，用map标记。代码：#include<iostream>#include<map>#include<string.h>using ...
2020-03-04 10:31:36
83
原创 POJ 3187 Backward Digit Sums
题意：给定n和sum，使得1-n的n个连续的数字排列后，每相邻两个相加直到只剩一个数的时候，这个数等于sum，要求输出最小的字典序的答案。思路：先预处理出杨辉三角形的矩阵，然后对1-n这n个数全排列，计算是否等于sum，等于就可以直接输出答案了。代码：#include<iostream>#include<algorithm>using namespace std;...
2020-03-04 01:21:34
98
原创 POJ 3009 Curling 2.0
题意：有一个小球，从2开始，要滚到3,。1表示障碍，0表示通行，当小球滚动时碰到障碍就会停下并且击碎障碍，这样是一次滚动，问小球最少要滚动多少次能到达目的地3。滚动次数超过10输出-1。思路：dfs+回溯。往四个方向，碰到1的时候就接下去dfs，把碰到的1标记成0,。碰到3的话就取滚动次数小的答案。他的输入是先输入列，再输入行，一开始看错了，一直WA。代码：#include<iost...
2020-02-27 22:23:12
137
原创 poj 3669 Meteor Shower
题意：一个人从原点出发，可以在第一象限（包括原点）活动，有M颗陨石，每颗陨石输入一个x，y，time，表示陨石砸落的地点坐标和时间，在这个坐标的上下左右也会被摧毁，摧毁后的路就走不通了，问能不能找到一个安全的地点，输出找到这个地点的最短时间，找不到输出-1。思路：先将所有陨石落点及其四周更新为最早被摧毁时间，然后开始bfs找到最短时间到达安全地点。代码：#include<iostre...
2020-02-20 15:56:24
106
原创 Aizu 0558 Cheese
题意：今年JOI镇的干酪工厂也开始生产干酪，老鼠从窝里爬了出来。JOI町东西南北划分整理，各划分为蜂巢、干酪工厂、障碍物、空地中的任意一个。老鼠从窝里出发，去所有的干酪工厂吃干酪。这个镇上有N家干酪工厂，每个工厂只生产一种干酪。奶酪的硬度根据工厂不同而不同，恰好有一个奶酪工厂生产硬度从1到N的奶酪。老鼠最初的体力是1，每吃一个奶酪体力就增加1。但是，老鼠不能吃比自己的体力更硬的奶酪。老鼠可...
2020-02-20 10:56:37
129
原创 Aizu 0118 Property Distribution
题意：一个nm的矩阵，有 ‘#’、’@’、’’ 三种符号，分别表示3种不同的果树。上下左右相邻的算是一个区域，不同果树不能在同一区域，问有多少区域。思路：dfs，每个未标记的点都dfs一遍，将搜过的点都标记一下。代码：#include<bits/stdc++.h>using namespace std;int vis[110][110];string s[110];i...
2020-02-17 12:03:34
75
原创 poj1979 Red and Black
题目描述：给定一个n*m的图，由 ‘#’、’.’、’@’ 组成。’#’ 表示阻碍，’.’ 表示空地，’@’ 表示起点。可以往上下左右的空地走，问最多能经过多少空地。思路：dfs，只要从起点开始每个点上下左右往下搜，走过的点标记一下就好了。代码：#include<bits/stdc++.h>using namespace std;typedef long long ll;...
2020-02-16 23:02:39
130
原创 Codeforces 1255D.Feeding Chicken
题目链接：http://codeforces.com/contest/1255/problem/D题目大意：有k只鸡，n*m的地，然后有几块地是有米的。每只鸡占领的地是连续的，要让占领的有米的地最多的-占领有米的地最少的差最小。思路：差值肯定是0或1，如果有米的地的数量是鸡的倍数那差值就是0，否则就是1。然后只要横着遍历S型或者竖着遍历S型就可以了。我采用的是横着遍历。#include&l...
2019-11-26 21:22:13
127
原创 codeforces 1131D.Gourmet choice
题目链接：http://codeforces.com/problemset/problem/1131/D题目大意：有一个n*m的矩阵，里面填满比较符号，表示n个数字跟m个数字之间的关系，现在问能不能找到最大的数字最小的并且符合矩阵的所有n+m个数字。思路：因为有’=’，所以先把所有相等的用并查集并为一个点，然后再把不相等的存入vector最后用拓扑排序解决。代码：#include<i...
2019-10-16 19:15:10
127
原创 codeforces 1244F.Chips
题目链接：http://codeforces.com/problemset/problem/1244/F题目大意：有一个黑球和白球串起来的环，如果当前位置是白球，且它的左边一个和右边一个是黑球，那么下一秒这个球变成黑球。白球也是同样的规则，问经过k次之后的状态。思路：可以发现如果有两个相同的球相连的话，那么就颜色永远不变并且每秒都会往外扩张。每次只要比较黑球和白球谁先扩张到或者都没扩张到的话就...
2019-10-15 20:41:29
128
原创 codeforces 1141 F2.Same Sum Blocks (Hard)
题目链接：https://codeforces.com/contest/1141/problem/F2题目大意：有一个长度为n的数组，找出最大数量的不同的连续的区间和相同。思路：离散化+暴力。先把每个区间值存好，对于每个值的区间进行排序，然后找出最大的数量。比较简单。代码：#include<bits/stdc++.h>using namespace std;map<i...
2019-10-12 14:34:36
122
原创 codeforces 1132F Clear the String
题目链接：https://codeforces.com/problemset/problem/1132/F题目大意：有一个长度为n的字符串，没次可以删除连续的相同字母，问最少几次可以可以全部删完。思路：区间dp。对于[i,j]区间来说，如果s[i]==s[j]，那么[i,j]的删除次数就是[i,k]+[k+1,j]-1，否则就是[i,k]+[k+1,j]。代码：#include<bi...
2019-10-12 14:04:23
160
原创 codeforces 1172B
题目链接：https://codeforces.com/contest/1172/problem/B题目大意：给定n个点的连通图，不含环。点可以放在圆上的任意位置，问有多少种情况给定的线不相交。由题可得任意放点的话一共会有n!种，减去有相交线的就是答案。思路：其实可以先算出一个位置的情况有多少种，然后再乘以n就好了。一个位置的算法就是每个点的度相乘。其实这题感觉就是道数学题。代码：#inc...
2019-10-09 19:20:34
69
原创 codeforces 1183H
题目链接：https://codeforces.com/contest/1183/problem/H题目大意：给一个长度为n的字符串，有没有至少k个不同的子序列，有的话输出最少的花费。每个子序列的花费为原串长度减去子序列长度。思路：首先不考虑重复的情况下可以得到2^n个子序列，这中间有些是重复的要去掉。dp。代码：#include<bits/stdc++.h>using na...
2019-10-09 18:24:19
302
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人