当前位置: 首页 > news >正文

学做网站多久官网排名优化方案

学做网站多久,官网排名优化方案,网站快速排名是怎么做的,怎样推荐企业建设网站和互联网推广题目: 力扣514 : 自由之路 . - 力扣(LeetCode) 题目的详细描述,直接打开力扣看就是了,下面说一下我对题目的理解: 事例1: 输入: ring "godding", key "gd" 输出: 4. 1. ring的第…

题目: 力扣514 : 自由之路  . - 力扣(LeetCode)

题目的详细描述,直接打开力扣看就是了,下面说一下我对题目的理解:

事例1:

输入: ring = "godding", key = "gd"
输出: 4.

1. ring的第一个字符默认是指向12点方向的,这一点很重要

2. key的第一个字符为g,而ring中首字符和末尾字符都为g。因此,必然存在选择首字符的g还是末尾字符g的问题。

3. 即使ring中第一个字符为g,也还存在存在顺时针旋转和逆时针旋转的问题。(当然,当前案例比较极端,如果第一个字符不为g,理解起来更合适)

4. 这一题要求的是旋转的最小步数。因此,最终的值必然是获取最小值的。

5. 那么整体串起来分析:

        ring = "godding", key = "gd"

       

字符godding
下标0123456

a1. 如果ring的第一个g旋转,顺时针步数为0;逆时针步数为7;算上最终确认的1步,因此就               是在 1 和 8中选取最小值,选取1

a2. 接着a1继续分析,既然key的第一个字符已经确定了。那么key的第二个字符d又该选择                   了。我们到底是用下标为2的d呢,还是使用下标为3的d呢?

选择1: 下标为2的d,从a1的g顺时针旋转只需要2步,逆时针旋转需要5步,。算上确认的1步,就是在3和6中选取最小值,选取3

选择2: 下标为3的d, 从a1的g顺时针旋转只需要3步,逆时针旋转需要4步。算上确认的1步,就是在4和5中选取最小值. 选取 4

如果g使用的是ring中第一个字符,针对以上2种选择,最好的选择就是使用下标为2的d,顺时针旋转2步,即3步。  那么,总的代价就是 1 + 3 = 4。

开头,我们就说过,ring中有开头和结尾都存在g,因此存在选择的问题。

b1. 如果我们使用ring中下标为6的g最为key的开头。顺时针旋转需要1步,逆时针旋转需要6步,算上最终确认的1步,就是2步和7步。选取最小值2.

b2. 接着b1继续分析,既然key的第一个字符已经确定了。那么key的第二个字符d又该选择        了。我们到底是用下标为2的d呢,还是使用下标为3的d呢?

选择1: 下标为2的d,从b1的g顺时针旋转只需要4步,逆时针旋转需要3步,。算上确认的1步,就是在5和4中选取最小值,选取4

选择2: 下标为3的d, 从b1的g顺时针旋转只需要3步,逆时针旋转需要4步。算上确认的1步,就是在4和5中选取最小值. 选取4

如果g使用的是ring中最后一个字符,针对以上2种选择,最好都为4。  那么,总的代价就是 2 + 4 = 6。

最终,如果以ring中第一个g作为旋转选择,最小的步数为4;  以ring中最后一个g作为旋转选择,那么最小步数为6;  因此,当前案例最小步数为 Math.min(4, 6).

递归代码:

package 刷题.第三天;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** 力扣514: 自由之路* https://leetcode.cn/problems/freedom-trail/*/
public class C2_FreeDomTtail_leet514_递归 {//递归版本public int findRotateSteps(String ring, String key) {if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {return 0;}char[] source = ring.toCharArray();char[] target = key.toCharArray();//记录下每个字符的位置,有可能存在重复值的情况HashMap<Character, List> map = new HashMap<Character, List>();for (int i = 0; i < ring.length(); i++) {if (map.containsKey(source[i])) {//放入下标的位置map.get(source[i]).add(i);}else {List list = new ArrayList();list.add(i);map.put(source[i], list);}}return process(map, source, 0, target, 0);}public int process (Map<Character, List> map,char[] source, int sourceStartIndex,char[] target, int targetIndex) {if (targetIndex == target.length) {return 0;}List<Integer> ops = map.get(target[targetIndex]);int minStep = Integer.MAX_VALUE;for (int i = 0; i < ops.size(); i++) {//从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;//深度优先遍历; 此时source的的开始位置为 ops.get(i)minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1));}return minStep;}//获取从最小长度public int getMinSteps(int start, int end, int size){//如果start < end, 则是顺时针; 反之, 逆时针int step1 = Math.abs(start - end);//如果step1是顺时针,那么step则是逆时针; 反之,顺时针int step2 = size - step1;return Math.min(step1, step2);}public static void main(String[] args) {C2_FreeDomTtail_leet514_递归 ss = new C2_FreeDomTtail_leet514_递归();String source = "godding";String target = "gd";System.out.println(ss.findRotateSteps(source, target));}
}

测试结果:

超时是好事情,说明整体逻辑大概率是没有问题的。超时,说明递归计算的次数有问题。上方的分析过程中,a2和b2 都是针对d进行逻辑判断的,明显存在重复的过程。那么,就需要在递归的基础之上添加缓存了,俗称记忆化搜索。

我之前在说动态规划的时候就说过,如果表结构依赖不严格,或者说即使依赖严格表结构,但是没有优化的空间。  递归 + 缓存 == 动态规划。

递归+缓存版本:

package 刷题.第三天;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** 力扣514: 自由之路* https://leetcode.cn/problems/freedom-trail/*/
public class C2_FreeDomTtail_leet514_递归_缓存 {//递归 + 缓存public int findRotateSteps(String ring, String key) {if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {return 0;}char[] source = ring.toCharArray();char[] target = key.toCharArray();//记录下每个字符的位置,有可能存在重复值的情况HashMap<Character, List> map = new HashMap<Character, List>();for (int i = 0; i < ring.length(); i++) {if (map.containsKey(source[i])) {//放入下标的位置map.get(source[i]).add(i);}else {List list = new ArrayList();list.add(i);map.put(source[i], list);}}int[][] dp = new int[source.length][target.length];for (int i = 0; i < source.length; i++) {for (int j = 0; j < target.length; j++) {//代表没算过dp[i][j] = -1;}}return process(map, source, 0, target, 0, dp);}public int process (Map<Character, List> map,char[] source, int sourceStartIndex,char[] target, int targetIndex,int[][] dp) {if (targetIndex == target.length) {return 0;}//缓存if (dp[sourceStartIndex][targetIndex] != -1) {return dp[sourceStartIndex][targetIndex];}List<Integer> ops = map.get(target[targetIndex]);int minStep = Integer.MAX_VALUE;for (int i = 0; i < ops.size(); i++) {//从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;//深度优先遍历; 此时source的的开始位置为 ops.get(i)minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1, dp));dp[sourceStartIndex][targetIndex] = minStep;}return minStep;}//获取从最小长度public int getMinSteps(int start, int end, int size){//如果start < end, 则是顺时针; 反之, 逆时针int step1 = Math.abs(start - end);//如果step1是顺时针,那么step则是逆时针; 反之,顺时针int step2 = size - step1;return Math.min(step1, step2);}public static void main(String[] args) {C2_FreeDomTtail_leet514_递归_缓存 ss = new C2_FreeDomTtail_leet514_递归_缓存();String source = "godding";String target = "gd";System.out.println(ss.findRotateSteps(source, target));}
}

测试结果:

84%的胜率,8毫秒,已经相当优秀了。其实,这就是最优解

第三版本:纯动态规划

动态规划,那就需要分析递归的逻辑了。下面以ring作为行,以key作为列

第一步:

0 (g)1 (d)
0 (g)

下标0的g: 

顺时针:1步

逆时针:8步

选取1步

1 (o)
2 (d)

3 (d)

4 (i)
5 (n)
6 (g)

下标6的g :

顺时针:2步

逆时针:7步

选取2步

第二步:

0 (g)1 (d)
0 (g)

下标0的g: 1步

1 (o)
2 (d)

下标为2的d:

从下标为0的g过来,

顺时针2步,逆时针5步,

算上确认的1步,

就是3步和6步,选取小值,即3步

从下标为6的g过来,

顺时针3步,逆时针4步,

算上确认的1步,

就是4步和5步,选取小值,即4步

最终值就是:

1+3 和 2 +4选取小的。即4步

1是下标为0的g耗费的1步

2是下标为6的g耗费的2步

3 (d)

下标为3的d:

从下标为0的g过来,

顺时针3步,逆时针4步,

算上确认的1步,

就是4步和5步,选取小值,即4步

从下标为6的g过来,

顺时针4步,逆时针3步,

算上确认的1步,

就是5步和4步,选取小值,即4步

最终值就是:

1+4 和 2 +4选取小的。即5步

1是下标为0的g耗费的1步

2是下标为6的g耗费的2步

4 (i)
5 (n)
6 (g)下标6的g : 2步

因此,最终最小的步数就是当key遍历完最后一个字符得到,即 1 + 3 = 4步;

纯动态规划

package 刷题.第三天;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** 力扣514: 自由之路* https://leetcode.cn/problems/freedom-trail/*/
public class C2_FreeDomTtail_leet514_动态规划 {//纯动态规划public int findRotateSteps(String ring, String key) {if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {return 0;}char[] source = ring.toCharArray();char[] target = key.toCharArray();//记录下每个字符的位置,有可能存在重复值的情况HashMap<Character, List> map = new HashMap<Character, List>();for (int i = 0; i < ring.length(); i++) {if (map.containsKey(source[i])) {//放入下标的位置map.get(source[i]).add(i);}else {List list = new ArrayList();list.add(i);map.put(source[i], list);}}int[][] dp = new int[source.length][target.length + 1];//最终返回的最小值int finalMinStep = Integer.MAX_VALUE;//第一列List<Integer> ops = map.get(target[0]);for (int index : ops) {dp[index][0] = getMinSteps(0, index, source.length) + 1;//如果要拼接的key只有一个字符,直接获取最小值即可finalMinStep = Math.min(finalMinStep,  dp[index][0]);}//如果要拼接的字符长度超过1,那么finalMinStep的值需要//等到 target的最后一列才能确定if (target.length > 1) {finalMinStep = Integer.MAX_VALUE;}//列遍历,从第二列开始往后遍历for (int i = 1; i < target.length ; i++){//当前列对应的行信息List<Integer> ops2 = map.get(target[i]);//当前列前一列对应的行信息List<Integer> ops3 = map.get(target[i-1]);for (int j : ops2)  //结束{//j行i列的默认最小值int minStep = Integer.MAX_VALUE;for(int m : ops3) //开始{//从m行到j行的步数int curStep = getMinSteps(m, j, source.length) + 1;//dp[m][i-1] : 从0到m累计步数//dp[j][i-1] + curStep : 代表从0行到j行累计步数int steps = dp[m][i-1] + curStep;//更新j行i列的最小值minStep = Math.min(minStep, steps);dp[j][i] = minStep;}//要拼接字符串的最后一个字符,也就是说可以//已经全部拼接完了if (i == target.length - 1) {finalMinStep = Math.min(finalMinStep, dp[j][i]);}}}return finalMinStep;}//获取从最小长度public int getMinSteps(int start, int end, int size){//如果start < end, 则是顺时针; 反之, 逆时针int step1 = Math.abs(start - end);//如果step1是顺时针,那么step则是逆时针; 反之,顺时针int step2 = size - step1;return Math.min(step1, step2);}public static void main(String[] args) {C2_FreeDomTtail_leet514_动态规划 ss = new C2_FreeDomTtail_leet514_动态规划();/*String source = "godding";String target = "gd";*/String source = "eh";String target = "h";System.out.println(ss.findRotateSteps(source, target));}
}

测试结果:

10毫秒,76%胜率,也还行。

第四种解法,即官方解法。因为胜率没有我写的两个版本的高,我就不说了。

官方代码胜率:

http://www.ds6.com.cn/news/13490.html

相关文章:

  • 微网站开发平台有哪些好的百度推广助手app下载
  • 网页生成助手seo导航
  • 他达拉非能延时多久seo服务公司招聘
  • 青岛建站模板厂家网站seo排名优化软件
  • 跨境电商平台数据优化关键词排名哪家好
  • 外贸企业网站功能要求互联网公司排名
  • 新余网站开发公司seo优化方法有哪些
  • 金融类网站模板北京网站优化技术
  • 本地门户网站源码职业技能培训有哪些
  • 动漫设计与制作软件下载佛山市seo推广联系方式
  • 做网站推广需要什么百度电话怎么转人工
  • 坪山附近公司做网站建设哪家技术好南京seo排名扣费
  • 互动企业展厅设计公司seo线下培训机构
  • 做58同城的网站要多少钱如何去做网络营销
  • 洛阳霞光做网站windows优化大师自动下载
  • 保山企业网站建设惠州疫情最新情况
  • 网站建设与网页设计如何制作网页教程
  • 做网站要会哪些知识松松软文
  • wordpress提货下载搜索引擎优化的作用
  • 在线做qq空间的网站吗公司seo
  • 网站网络推广方案seo代理
  • 专门做灯具海报的网站软文代写新闻稿
  • 做外贸网站推广关键词优化seo公司
  • 电信宽带做网站服务器吗seo教学网站
  • 网站建设俄语百度关键词的费用是多少
  • 安徽省芜湖建设定额网站百度搜索优化平台
  • 网站编程多少钱山东百搜科技有限公司
  • wordpress安全证书百度快照优化推广
  • 做套网站多少钱嵌入式培训
  • 天津专业网站建设公司武汉网站优化