LeetCode 探索-初级（总结）

一、数组

今天（18.04.14）搞定了LeetCode 探索-初级-数组部分，在此简单做个总结。

题型

• 从排序数组中删除重复项（移动元素）
• 买卖股票的最佳时机 II（数学，找客观规律）
• 旋转数组（数学，找客观规律）
• 存在重复（遍历，空间换时间 or 排序）
• 只出现一次的数字（数学）
• 两个数组的交集 II（遍历，空间换时间 or 排序）
• 加一（数学）
• 移动零（交换）
• 两数之和（遍历，空间换时间）
• 有效的数独（抽象，将实际问题转为数学模型-拟人+积木）
• 旋转图像（抽象，将实际问题转为数学模型-拟人+积木）

基本思路

1. 数学题：一般需要找到题目所隐含的数学规律。如旋转数字，本质是利用reverse实现。只出现一次的数字，利用的一个数亦或上自己为0的规律实现。这种题目一般技巧性比较强，如果没有接触过，想不到最优解，可以试着先用暴力法解决，尝试找寻客观规律。
2. 遍历：此类问题的解法是建立在对容器遍历的基础之上的。对于遍历，简单的思想是暴力法，优化手段一般是空间换时间、排序。遇到此类问题时可以往这两个方向思考。
3. 抽象：此类问题的描述一般比较抽象，需要通过将现象转换为数学模型进行编程。没什么花哨的技巧，对答题者的编程基础有一定的要求。一般没思路的时候采用“拟人+积木”的方法。将数组看做是一个个的积木，思考如果是人手动操作时一个怎样的过程，再次过程中抽象出计算机的实现逻辑。

二、字符串

拖了很多天的总结，赶紧补上（18.05.03）

题型

• 反转字符串（双指针，一头一尾向中间夹）
• 反转整数（数学，求余取低位，加乘变高位）
• 字符串中的第一个唯一字符（遍历，空间换时间）
• 有效的字母异位词（遍历，空间换时间&排序）
• 验证回文字符串（双指针，一头一尾向中间夹）
• 字符串转整数(atoi)（落地，从思想到代码）
• 实现strStr()（落地，从思想到代码）
• 数数并说（落地，从思想到代码）
• 最长公共前缀（落地，从思想到代码）

基本思路

1、双指针：涉及头尾操作的题目可以考虑采用双指针的解法，利用两个指针想中间夹。如反正、回文等。
2、数学：此类题目一般涉及的是数字型字符串，可以采用一些巧妙的数学公式来进行，最后返回的时候转换为字符串即可。
3、遍历：与数组遍历的相同，基本围绕空间换时间和排序两种思想。
4、落地：初级部分的字符串题型中设计较多此类题目。题目的描述比较简单，很容易相处核心算法，难点在于将思想落地成代码。比较考察代码的基本功，比较好的做法有最长公共前缀中的双重for，报数中i+j找起点遍历n步长的写法，具体如下：

// 报数
// 涉及找到一个起点遍历。然后在跳n个字符的做法可以参考这个实现
for (int i = 0; i < s.size(); i += j) {
  for (j = 0; j + i < s.size(); j++) {
    if (s[i] != s[i + j]) {
      break;
    }
  }
  now = now + int_to_string(j) + s[i];
}


// 从头开始遍历字符串数组
for (int i = 0; i < strs[0].length(); i++) {
  for (int j = 1; j < strs.size(); j++) {
    // 这里刚开始担心strs[j][i]有可能会越界，但实际上字符串最后一个字符是'\0'，肯定不等，所以不用去特意求最短的字符串
    if (strs[j][i] != strs[0][i]) {
      return prefix;
    }
  }
  prefix += strs[0][i];
}