题目 解题结果 解题思路:动态规划 题中提到“最高金额”,即求最优解代价。贪心策略和动态规划都可用于求解最优解问题。此问题是动态规划问题。 定义最优解代价,题目已给出:“盗取金额总数”,dp[i]表示前i个房屋可获取的金额。 定义最优解结构 如果dp[i-1]不包括最末尾房屋,则直接加上第i个房屋的金额(nums[i-1]),dp[i] = dp[i-1] + nums[i-1]; 否则 dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]); 递归求解最优解 注意初始化时要考虑dp…

2020年2月19日 0条评论 14点热度 阅读全文

解题思路:逆向思维 若X >= Y,则只有递减操作可以执行,返回X- Y; 若X<Y,则采用逆向思维。 正向思维是需要考虑先递减1,再乘以2,难以确定是在X= Y/2、Y/4……中的什么时刻递减1。 以小化大是困难的 逆向思维可以一直除以2(Y/=2),直至Y小于X,再执行加1操作 以大化小是容易的 使用递归结构实现,当Y>X时,每次只考虑最后一步,如果Y为偶数,则到Y的最后一步是乘2 ,如果Y为奇数,则到Y的最后一步是减1 解题代码 class Solution { public static …

2020年2月19日 0条评论 4点热度 阅读全文

动态规划解题思路 难度在于定义最优解的结构。 根据动态规划思想容易定义出dp[i][j]表示word1的前i段与word2的前j段的编辑距离。 最难想到的是最优解的结构,即替换,删除和插入三种操作可以分别用dp[i-1][j-1] +1,dp[i-1][j] +1和dp[i][j-1] +1表示。 dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数 所以, 当 word1[i] == word2[j],dp[i][j] = dp[i-1][j-1]; 当 word1[i] …

2020年2月17日 0条评论 5点热度 阅读全文

解题思路 从根节点开始遍历树。 在找到 p 和 q 之前,将父指针存储在Map<TreeNode,TreeNode> fatherMap。 使用fatherMap获得 p 的所有祖先,并添加到一个称为祖先的集合中。 同样遍历节点 q 的祖先。如果祖先存在于为 p 设置的祖先中,这意味着这是 p 和 q 之间的最近共同祖先(同时向上遍历) 算法效率有点低,有时间再改进吧 解题代码 /** * Definition for a binary tree node. * public class TreeNod…

2020年2月1日 0条评论 3点热度 阅读全文

开始出错原因:对n计算错误,误以为1+(letter[‘n’ - ‘a’]-1) / 2,应该是(letter[‘n’ - ‘a’]-1) / 2; import java.util.Scanner; /** * Main.注意考虑到边界情况与特殊情况 * @author : cxc **/ public class Main { public static void main(String[] args) { Scanner myin = new Scanner(System.in,"utf-8"); Strin…

2019年12月16日 0条评论 3点热度 阅读全文

代码: import java.util.Scanner; /** * Main.注意考虑到边界情况与特殊情况 * @author : cxc **/ public class Main { public static void main(String[] args) { Scanner myin = new Scanner(System.in,"utf-8"); int n = myin.nextInt(); int[] myint = new int[n]; for(int i=0;i<n;i++){ m…

2019年12月13日 0条评论 6点热度 阅读全文

import java.util.Scanner; import java.util.regex.Matcher; import java.util.regex.Pattern; /** * Main.注意考虑到边界情况与特殊情况 * @author : cxc **/ public class Main { /** * 解析规则,将规则转换成正则表达式 * 匹配规则 * @param s * @param urlrules * @param urlrulesname */ public static void I…

2019年12月13日 0条评论 3点热度 阅读全文

问题链接:CCF201909-2 小明种苹果(续) 提交结果:(在超时的边缘……) 注意:若第44-45行条件为badtreeorder[i-2] == badtreeorder[i-1] && badtreeorder[i-1] == badtreeorder[i],若为若条件设为badtreeorder[i] == badtreeorder[i+1]&& badtreeorder[i+1] == badtreeorder[i+2] 将出错。 java代码: import java…

2019年12月10日 0条评论 7点热度 阅读全文

写博客的原因是阅读了CCF-CSP认证历年真题解(C/C++),准备CCF的同时想写一个java版 CCF每题要获得100分,仅仅使用原题的样例来测试是不够的,需要自己设计一些样例,并且需要考虑特殊的边界条件。 2019.09 第17次 java题解 CCF201909-1 小明种苹果(java100分) CCF201909-2 小明种苹果(续)(java) C/C++题解 CCF201909-1 小明种苹果(C/C++100分) CCF201909-2 小明种苹果(续)(C/C++100分) 2019.03 第1…

2019年12月10日 0条评论 9点热度 阅读全文

CodeForces - 1166A 代码: import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner in1 = new Scanner(System.in); int m = in1.nextInt(); Map<String,Integer> namemap = new Ha…

2019年8月2日 0条评论 5点热度 阅读全文