> 技术文档 > 力扣.26删除有序数组中的重复项力扣121.买卖人股票的最佳时机力扣.1143最长公共子序列力扣72.编辑距离力扣12.整数转罗马数字

力扣.26删除有序数组中的重复项力扣121.买卖人股票的最佳时机力扣.1143最长公共子序列力扣72.编辑距离力扣12.整数转罗马数字


 

目录

 

力扣.26删除有序数组中的重复项

力扣121.买卖人股票的最佳时机

力扣.1143最长公共子序列

力扣72.编辑距离

力扣12.整数转罗马数字


力扣.26删除有序数组中的重复项

i,j双指针,我认为这个是特别精妙的,我一直想比如什么重复拿个map,再拿个保证有序的

一个表示当前不重复的位置,另一个去遍历

class Solution { public int removeDuplicates(int[] nums) { int n=nums.length; int i=0; for(int j=0;j<n;j++){ if(nums[i]!=nums[j])//++i,当前位置假如下标是 0 j的下标是1 i的下标和j二者移动 nums[++i]=nums[j]; } return i+1; }}

这个可能更通用一点的思想,比如map检查是否有重复啥的 

class Solution { public int removeDuplicates(int[] nums) { int n=nums.length; int count=0;  int k=0; HashMap map=new HashMap(); Queueq=new LinkedList(); for(int i=0;i<nums.length;i++){ if(map.get(nums[i])==null){ //数据使用哈希表标记一下 map.put(nums[i],i); q.add(nums[i]);  nums[k++]=nums[i]; count++; } } return count; }}

力扣121.买卖人股票的最佳时机

f[i]:第i天处于持股状态,f[i-1],

这个f[0]:初始化 很重要,初始化f[0]=(第一天就买入状态 -price[0])

f[i]=(f[i-1],-price[i])

t[i]=(t[i-1],f[i-1]+price[i]);

 public int maxProfit(int[] prices) { //f[i]:在i天处于持股状态的最大利润 int n=prices.length; int max=0; int []f=new int[n]; //t[i]:第i天处于不持股的最大利润,多状态,状态相互转移 int []t=new int[n]; f[0]=-prices[0]; for(int i=1;i<n;i++){ f[i]=Math.max(f[i-1],-prices[i]); } for(int i=1;i<n;i++){ t[i]=Math.max(t[i-1],f[i-1]+prices[i]); max=Math.max(t[i],max); } return Math.max(0,max); }

力扣.1143最长公共子序列

两个数组的比较,怎么表示两个元素的状态

两个数组比较状态,一般是二维数组横向比较

难的地方,就是这个状态表示我认为很复杂

dp[i][j]=text1的0-i-1位置,text2[0,j-1]位置的最大公共子序列值

其余就还好,还有一个难点,就是为什么是i-1,和j-1而不是i,j

if(a[i-1]==b[j-1])

dp[i][j]=dp[i-1][j-1]+1

else

dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])二者取最大值。因为要看看i-1和j,i和j-1这两个是距离i,j最近的距离(想一下)

然后难点2:初始化,因为是i-1,到j-1,所以我们只需要扩展1位,然后dp[0][0]:属于是前-1个,所以不考虑了,那么就无需初始化,只需要扩展一行就好,其余的就是正常写

class Solution { public int longestCommonSubsequence(String text1, String text2) { char[]a=text1.toCharArray(); char[]b=text2.toCharArray(); int n=a.length; int m=b.length; int[][]dp=new int[n+1][m+1]; //dp[i][j]:text1 0-i-1位置,text2 0-j-1位置的最大值 //dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+1 //dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i-1]==b[j-1]){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[n][m]; }}

力扣72.编辑距离

这道题感觉难的地方就是状态太多,主要是修改,还有就是状态表示

这道题写的时候,就肯定想要用dp

因为看示例1,示例2这俩看起来不同,但是实例2,假如吧后面的tion去掉,inten 和execu

这是不是又是一个题目(就是这种可以变成重复题目的 ,我认为是dp的关键,多个重叠的问题)

其次就是替换的状态比较难想,替换就是可以理解为替换后,两个就肯定相等了,所以去拿相等那个条件的表达式,然后再去+1因为你替换也属于一个操作步骤

再一个难点就是初始化

dp[i][0]:表达意思是什么,一个长度是0((你假如说是-1,那么另一个就是i-1,所以没必要)),一个长度是i,你把这个长度全部剪去,就没有长度了

dp[0][j]:同理,一个0(你假如说是-1,那么另一个就是j-1,所以没必要),一个长度是j,那么把长度全部剪没就好了

class Solution { public int minDistance(String word1, String word2) { // inten execut int n=word1.length(); int m=word2.length(); int max=0; if(n!=m){ max=Math.abs(n-m); } //dp[i][j]:表示下标以(i-1)word1结尾和(j-1)结尾的word2,最近的编辑距离是dp[i][j] int[][]dp=new int[n+1][m+1]; for(int i=0;i<=n;i++)dp[i][0]=i; for(int j=0;j<=m;j++)dp[0][j]=j; //max horse ros 两个比较其中的字母,起码要更新两次,然后 for(int i=1;i<n+1;i++){ for(int j=1;j<m+1;j++){ if(word1.charAt(i-1)==word2.charAt(j-1)){ dp[i][j]=dp[i-1][j-1]; }else{ dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1; } } } return dp[n][m]; }}

力扣12.整数转罗马数字

这个题,感觉想着最难的就是,你需要把列表全部写上,不然,一直IF判断会非常麻烦,一旦你把这个列表一列出来,就好写了。

class Solution { int []values={1000,900,500,400,100,90,50,40,10,9,5,4,1}; String[]systembol={\"M\",\"CM\",\"D\",\"CD\",\"C\",\"XC\",\"L\",\"XL\",\"X\",\"IX\",\"V\",\"IV\",\"I\"}; public String intToRoman(int num) { StringBuffer sb=new StringBuffer(); for(int i=0;i=value){ num-=value; sb.append(symbol); } if(num==0){ return sb.toString(); } } return \"\"; }}