Arithmetic学习笔记

# 二.贪心算法

# 基础部分

概念：

在对问题求解时，总是做出在当前看来使最好的选择。也就是说，不从整体最优上加以考虑，他说做出的仅是在某种意义上的局部最优解。

思想策略

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

基本步骤

  • 1.建立数学模型来描述问题
  • 2.把求解的问题分成若干个子问题
  • 3.对每一子问题求解，得到子问题的局部最优解
  • 4.把子问题的局部最优解合成原来问题的一个解

适用贪心法求解的经典问题

  • 活动选择问题
  • 钱币找零问题
  • 背包问题
  • 小船过河问题
  • 区间覆盖问题
  • 销售比赛
  • Huffman 编码
  • Dijkstra 算法（求解最短路径）
  • 最小生成树算法

# 题目部分

题目 1

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”

输出: “bab”

注意: “aba”也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

tips: 回文字符串：正读反读都一样


bab
<template>
  <div>
    <input style="width:100%" v-model="str" placeHolder="请输入值" />
    <br />
    <button @click="handleClick" style="margin-top:10px;text-align:center">
      确定
    </button>
    <div class="box-vue">{{ message }}</div>
  </div>
</template>
<script>
let targetArithmetic = (str) => {
  let aaa = ""
  let arr = str.split("")
  for (let i = 0; i < arr.length; i++) {
    for (let j = arr.length - 1; j > i; j--) {
      if (arr[i] === arr[j]) {
        let targetArr = arr.slice(i + 1, j)
        let targetString = targetArr.join("")
        if (
          targetString === targetArr.reverse().join("") &&
          aaa.length < j - i + 1
        ) {
          aaa = arr.slice(i, j + 1).join("")
        }
      }
    }
  }
  return aaa
}
export default {
  data: () => ({
    str: "babad",
    message: "",
  }),
  created() {
    this.handleClick()
  },
  methods: {
    handleClick() {
      this.message = targetArithmetic(this.str)
    },
  },
}
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
显示代码 复制代码

2.有一楼梯共 m 级，若每次只能跨上一级或二级，要走上第 m 级，共有多少走法？


89
<template>
  <div>
    <input style="width:100%" v-model="str" placeHolder="请输入值" />
    <br />
    <button @click="handleClick" style="margin-top:10px;text-align:center">
      确定
    </button>
    <div class="box-vue">{{ message }}</div>
  </div>
</template>
<script>
let targetArithmetic = (m) => {
  if (m === 1 || m === 2) return m
  return targetArithmetic(m - 1) + targetArithmetic(m - 2)
}
export default {
  data: () => ({
    str: "10",
    message: "",
  }),
  created() {
    this.handleClick()
  },
  methods: {
    handleClick() {
      this.message = targetArithmetic(+this.str)
      console.log(this.message)
    },
  },
}
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
显示代码 复制代码

3.给定 K 个整数的序列{N1,N2,...,NK},其任意连续子序列可表示为{Ni,Ni+1,...,Nj}，其中 1<=i<=j<=k。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{-2,11,-4,13,-5,-2}，其最大连续子序列为{11,-4,13}，最大和为 20。

4.长江俱乐部在长江设置了 n 个游艇出租站 1,2,…n，游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)，设计一个算法，计算出从出租站 1 到出租站 n 所需要的最少租金。

测试用例： 3（站数） 515（第一站到其他相应各站的租金） 7（第二站到其他相应各站的租金） 输出： 12

← 三.递归算法 →