这是一道京东校招的笔试题目，有两种实现方式，最好的实现方式是通过贪心算法，本篇还未通过贪心算法实现，后续会继续实现。

  • 题目描述
  • 思路
  • 代码

题目描述

在英文的输入中，我们经常会遇到大小写切换的问题，频繁切换大小写会增加我们的按键次数，也会降低我们的打字效率。 众所周知，切换大小写有两种方式：

  • 一种是按下”caps locks”，也就是大写锁定键，这样一来，之后的输入模式都会被切换。
  • 另一种是同时按下shift和需要打印的字母，可以临时切换大小写（算作按下两个键）。
    已知初始状态下，打字模式是小写，现在给出需要打印的字符串（区分大小写），请你计算出最少需按键多少次才能打印出来。

输入：

输入第一行仅包含一个正整数n，表示字符串的长度（1<=n<=1000000)
输入第二行包含一个长度为n的字符串，仅包含大小写字母

输出：

输出仅包含一个正整数，即最少的按键次数。

样例输入：

6
AaAAAA

样例输出：

8

思路

这是一道值得思考的题

  • 如果当前是小写模式，并且当前字母是小写，那么直接加一，这样最省事。
  • 如果当前是小写模式，而当前字母是大写，这样就有两种选择了。
  1. 按下caps lock键，切换到大写模式
  2. 同时按下shift键和当前字母。

  • 那么哪种模式好呢？

    这就需要看一看它的下一个字符，如果仍然为大写，那么当然按下caps lock更好，并切换成当前为大写模式；
    如果为小写，那么按下shift最好。

  • 大写反之

注意点

  • 大写和小写总共两种状态，我们可以用0表示小写，1表示大写。
  • 对最后一个字符进行处理，if i == len(s)-1: …，这样只要没到最后一个字符，就可以在后面通过判断i 和 i+1来处理。

代码

简单逻辑做法

javascript
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
function isUpper (code) { // 判断字母是否为大写
  return code === code.toUpperCase()
}

function checkMin(len,arr) {
  var num = 0 // 按下次数
  var status = 0 // 0代表当前状态为小写 1代表大写
  for (var i = 0;i<len;i++){
    if(isUpper(String(arr[i]))){ // 如果是大写
      if (status === 0){
        if (isUpper(String(arr[i + 1])) && i !== (len-1)){ // 判断大写的字母是否连续
          status = 1
        }
        num += 2
      } else {
        num += 1
      }
    }
    else{ // 如果是小写
      if (status === 0){
        num += 1
      } else {
        num += 2
        status = 0
      }
    }
  }
  return num
}
var arr = 'AAAaAAaAaaA'
var arr1 = 'AaAAAA'
checkMin(10,arr) // 15
checkMin(7,arr1) // 6