day16

[0344.反转字符串]

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
};

• 这道题 确实简单 只要想到链表反转 用到双指针法 那么这道 数组反转 比链表反转 更简单 这么简单的题 确实几分钟就写出来了 但是要注意以下几点
• 一是 代码过于冗余

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int left = 0, int right = s.size() - 1; left <= s.size()/2; left++, right--) {
            swap(s[left], s[right]);
        }
    }
};

• • 自己动手写了同标准答案类似的代码 有以下几点错误
    1. for循环里的left right 只定义一次就够了
    2. left取值范围问题 假设总长是5 那么left取到2就可以 所以s.size()/2没错 不用额外+1或-1 但是注意注意！！！！left默认是从0开始取值的 数组下标就是这样默认规定的 所以 应该是left < s.size()/2 而不是left <= s.size()/2

• 二是 库函数的调用问题

  • 原则是 如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。 毕竟面试官一定不是考察你对库函数的熟悉程度 ；

    如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

  • 例如本题 不可以用reverse函数 但可以用swap函数

• 三是 动手写代码 竟然遇到了这样一个问题：现在写完代码 才知道 哦 不论是 整形数组 还是字符数组 双指针法 我都是设置指针 用来指向数组下标的 那么数组下标 不论数组是存放的什么类型的变量 数组下标都是整形吧 那么我设置的left right 都是int 也就是说 ·int left = 0; 而我刚开始敲代码时 还想着 既然是字符数组 那么指针应该是指向字符的 那么我应该设置成字符类型的指针 那么char *left = 0; ！！！要注意 指向字符类型的指针 是要设置成字符指针 但我们这里是数组 虽然我们叫它双指针法 但这是一个总体 概括性概念 在数组里 双指针 具体表现形式 就是 “双下标”了 下标都是整形 所以就设置成int left = 0这样的 那么如果在 链表里 双指针 具体表现形式 就是“结点指针” 故而设置成ListNode *p这样的

[0541.反转字符串II]

class Solution {
public:
    void rev(string s, int k, int left, int right) {
        for (; left < k; left++, right-- ) {
            swap(s[left], s[right]);
        }
    }
    string reverseStr(string s, int k) {
        int left = 0;
        for(int i = 0; i < s.size()/(2 * k); i++) {
            int right = left + k - 1;
            rev(s, k, left, right);
            left += 2 * k;
        }
        return s;
    }
};

• 对比了标准答案 错误地方主要两处 分别是rev函数定义语句不正确 二是主函数reverseStr里面没有判断剩下字符串长度不够2k的两种情况 下的反转
• rev函数 的改正（还没看思路 只是对比了 一些语句） 以下均为正确搭配！！！！
  • void reverseString(vector<char>& s, int left, int right) //无返回类型 输入参数为字符数组取地址
  • void reverseString(string& s, int left, int right) //无返回类型 输入参数为字符串型取地址
  • string reverseStr(string s, int left, int right) //返回类型是string型 输入参数string型
• reverseStr函数的改正 剩下字符串长度可表示为s.size() - left 那么分情况就好 ！！！注意这里考虑长度 就不要考虑下标了 只要验证了长度s.size()=7的话 left=2*k=2 * 2 = 4的话 那么相减=3 用3和真实数出来剩余字符串长度确实是3 相比 一样！ 那么就不需要再考虑什么s.size()-1或者+1 < 或者<=了

class Solution {
public:
    void rev(string &s, int left, int right) {
        for (; left < right; left++, right-- ) {
            swap(s[left], s[right]);
        }
    }
    string reverseStr(string s, int k) {
        int left = 0;
        for(int i = 0; i < s.size()/(2 * k); i++) {
            int right = left + k - 1;
            rev(s, left, right);
            left += 2 * k;
        }
        if (s.size() - left < k) {
                rev(s, left, s.size() - 1);
            }
        if ((s.size() - left < 2 * k) && (s.size() - left >= k)) {
                rev(s, left, left + k - 1);
            }
        return s;
    }
};

• 看了卡哥的 确实比我简单一些 因为他把三个情况（剩余长度 要么大于2k 要么在k和2k之间 要么小于k）中的两种情况(前两种) 合二为一了 那么

class Solution {
public:
    string rev(string &s, int left, int right) {
        for (; left < right; left++, right-- ) {
            swap(s[left], s[right]);
        }
        return s;
    }
    string reverseStr(string s, int k) {
        int left = 0;
        for(int i = 0; i < s.size(); i+= (2 * k)) {
            if (s.size() - left < k) {
                rev(s, left, s.size() - 1);
                break;
            }
            rev(s, left, left + k - 1);
            left += 2 * k;
        }
        return s;
    }
};

• 这个是可以 运行成功的
  • 与卡哥的区别在于 我的 是把长度少于k个的情况 先写 卡哥是后写 先写的话要记得break 因为后面就不需要再循环了（见上面代码） 后写的话要记得continue 因为后面还需要再继续循环的 （见下面卡哥代码）
  • 此外 这个思路 相比于我的最开始的思路 有一个区别是for循环 虽然这两个for循环是等价的 但明显卡哥的（也就是我后来的这个for循环）更简洁些 因为 i就可以直接取每次的left值 那么 相比于 i只是单独负责控制次数 还需要再额外shezhileft值来说 就更简便些 ！！！注意 这里i就是每次不再是i++; 而应该是i += (2 * k); 这一点也使我没有想到的写法

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s, i, i + k - 1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s, i, s.size() - 1);
        }
        return s;
    }
};

[剑指Offer05.替换空格]

• 我的思路：字符串》》1.》》数组》》2.》》查找空格 并赋值20%》》》》结束？ 但存在诸多问题

1. 字符串 如何转化为 数组？ 两者又有什么区别？

   • 首先 知道了两者有什么区别 那么 “所谓的转换方法”就显而易见了

     • 字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。

       在C语言中，把一个字符串存入一个数组时，也把结束符 '\0'存入数组，并以此作为该字符串是否结束的标志。

       例如这段代码：

       char a[5] = "asd";
       for (int i = 0; a[i] != '\0'; i++) {
       }
       

       在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用'\0'来判断是否结束。

       例如这段代码:

       string a = "asd";
       for (int i = 0; i < a.size(); i++) {
       }
       

       那么vector< char > 和 string 又有什么区别呢？

       其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。

       所以想处理字符串，我们还是会定义一个string类型

     • 简而言之 字符串string 是特殊的字符数组char a[] 。 它不仅能被当成数组一样 按下标访问每个元素 还有数组没有的函数 方便操作。

   • 那么 既然字符串 都可以按下表 来访问每个字符元素 也就不需要 转化为数组

2. 但 在查找并赋值前 这里有一个问题需要注意 就是不同类型的元素所需空间大小是不同的

   • 如果 是整型数组 那么要求把所有元素值为1的替换为目标值3 直接找到并赋值就好了
   • 但 这里是字符串 待替换字符是空格字符 占一个字节 而目标字符是20%占两个字符 因此不能直接 像之前一样 找到并赋值 而是要 先扩容

3. 关于 查找并赋值

   • 常规思路 两层for循环 即指针从前往后
   • 优化版本 即指针从后往前 可使得后面的元素 一次性把位置移动到位 并且不影响前面的元素 而如果从前往后 前面的移动会影响后面的元素位置 每次循环都会多做一些不能一步到位的无用功

4. 分析了半天 其实就是 基础语法和语句表达问题太多 导致看了思路也不能写出代码

class Solution {
public:
    string replaceSpace(string s) {
        int countSpace = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                countSpace++;
            }
        }
        int left = s.size() - 1;
        s.resize(s.size() + countSpace * 2);  //扩宽数组长度的函数resize()
        int right = s.size() - 1;
        while (left < right) {
            if (s[left] == ' ') {
                s[right] = '0';
                s[right-1] = '2';
                s[right-2] = '%';
                left--;
                right = right - 3;
                continue;
            }
            s[right] = s[left];
            left--;
            right--;
        }
        return s;
    }
};

• resize()函数
• 卡哥 没用while循环 用的是for循环

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

• 看来我已经会用continue语句了

明天继续:)