题目 解题结果 解题思路：动态规划 题中提到“最高金额”，即求最优解代价。贪心策略和动态规划都可用于求解最优解问题。此问题是动态规划问题。 定义最优解代价，题目已给出：“盗取金额总数”，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…

解题思路：逆向思维 若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 …

动态规划解题思路 难度在于定义最优解的结构。 根据动态规划思想容易定义出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] …

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

开始出错原因：对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…

代码： 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…

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…

问题链接：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…

写博客的原因是阅读了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…

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…