算法

代码风格

命名

举例子 一般使用语言
小驼峰命名法(camel case) int myAge java，go，C++这些语言都会使用
下划线命名法 int my_age python和Linux环境下c/c++编程

代码空格

1.操作符左右一定有空格

  1. i = i + 1;

2.分隔符(,和;)的前一位没有空格，后一位保持空格，例如:

  1. int i, j;
  2. for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++)

3.花括号和函数保持同一行，并有一个空格

  1. while (n) {
  2.     n--;
  3. }

4.控制语句(while, if, for)后面都有一个空格，例如：

  1. while (n) {
  2.     if (k > 0) return 0;
  3.     n--;
  4. }

数组

数组的核心是要把所有的算法都能熟练的敲出来

1 二分法查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.1算法逻辑

  • 用我们给定要查找的目标值target去和nums[middle]的值做对比
    • middle是由左边的下标和最右边下标计算出来的中间值
  • 1.如果target大于nums[middle]
    • 说明target的下标应该再middle+1和right之间
    • left = middle+1
  • 2.如果target小于nums[middle]
    • 说明target的下标应该在left和middle-1之间
    • right = middle-1
  • 3.如果target等于nums[middle]的值
    • 返回middle，就为要求的下标，循环结束
  • 循环123的操作，直到找到target的值，或者left>right返回target=-1代表没有找到

1.2 用c++实现

  1. class Solution {
  2.     public:
  3.         int search(vector<int>& nums, int target) {
  4.             //定义left,right,和minddle
  5.             int left = 0;
  6.             int right = nums.size() - 1;
  7.             //如果在[left, right)区间内right = nums.size(),因为取不到
  8.             while (left <= right){
  9.                 //在[left, right)就为left < right
  10.                 int middle = left + (right - left) / 2;
  11.                 //注意，c++在使用/时，如果为小数，则会自动向下取整，但是python必须把相除的结果转化为整型
  12.                 if(target > nums[middle]){
  13.                     //1.如果target大于nums[middle]
  14.                     left = middle + 1;
  15.                 } else if (target < nums[middle]){
  16.                     //2.如果target小于nums[middle]
  17.                     right = middle - 1;
  18.                 } else{
  19.                     //3.如果target等于nums[middle]的值
  20.                     return middle;
  21.                 }
  22.             }
  23.             return -1;
  24.         }
  25. }

1.3 python实现

  2. class Solution(object):
  3.     def __init__(self):
  5.     def search(self, nums, target):
  6.         """
  7.         :type nums: List[int]
  8.         :type target: int
  9.         :rtype: int
  10.         """
  11.         left = 0
  12.         right = len(nums) - 1
  13.         while left <= right:
  14.             middle = int(left + (right - left)/2)
  15.             #注意，c++在使用/时，如果为小数，则会自动向下取整，但是python必须把相除的结果转化为整型
  16.             if target < nums[middle]:
  17.                 #如果target 小于下标为middle的值，那么right = middle-1
  18.                 right = middle - 1
  19.             elif target > nums[middle]:
  20.                 #如果target 小于下标为middle的值，那么left = middle + 1
  21.                 left = middle + 1
  22.             elif target == nums[middle]:
  23.                 return middle
  24.         return -1
  26. nums = [-1, 0, 3, 5, 9, 12]
  28. s1 = Solution()
  29. print(s1.search(nums, 0))

2 数组删除元素

题目地址：https://leetcode-cn.com/problems/remove-element/

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

2.1 双循环暴力解法

2.1.1 代码思路

  • 外围的大循环，把指针一次往后移动
    • 如果遇到了要删除的数字
      • 把后面的所有元素一次往前移动一个单位(小循环)

2.1.2 代码实现

  1. class Solution {
  2. public:
  3.     int removeElement(vector<int>& nums, int val) {
  4.         int size = nums.size();//定义变量size, 用来代表列表内有效元素的数量
  5.         for (int i = 0; i < size; i++) {
  6.             //i<size，不能写i < nums.size(),因为size在一直变小
  7.             //遍历的效率会更好，如果用第二种的话，会浪费很多时间
  8.             if (nums[i] == val) {
  9.                 for (int j == i + 1; j < nums.size(); j++) {
  10.                     nums[j - 1] = nums[j] 
  11.                 }
  12.                 i--;
  13.                 /**如果没有i--的话，i就会指向下一个元素，但是刚才指向的元素已经被后面的元素代替，
  14.                 但是又直接跳到了下一个元素，刚才替代的哪个元素就没有检查到，
  15.                 如果两个目标元素是连着的话，后面的元素就会被忽略了，检查不出来**/
  16.                 size--;//删除一个元素，size少一个
  17.             }
  18.         }
  19.         return size;
  20.     }
  21. };

2.2快慢指针解法

  1. class Solution {
  2.     public:
  3.         int removeElement(vector<int>& nums, int val) {
  4.             int slowIndex = 0;
  5.             for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
  6.                 if (val != nums[fastIndex]) {
  7.                     nums[slowIndex++] = nums[fastIndex]
  8.                 }
  9.             }
  10.             return slowIndex;
  11.         }
  12. }

3 滑动窗口

题目地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

3.1 暴力解法

3.1.1 代码逻辑

  • 定义一个整数类型的变量，用来记录最小子数组
  • 外面的大循环，从第一个元素开始遍历
    • 内层循环从一个元素开始遍历
      • 内循环每移动一个元素判断下目前子数组是否满足条件
      • 如果满足条件就和最小子数组做对比

3.1.2 代码实现c++

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums) {
  4.         int result = INT32_MAX;//最终结果
  5.         int sum = 0;//子序列的数值之和
  6.         int subLength = 0;//子序列长度
  7.         for (int i = 0; i < nums.size(); i++) {
  8.             sum = 0;//每次大循环都要让sum刷新为0
  9.              for (int j = i; j < nums.size(); j++) {
  10.                 sum += sums[j];
  11.                 if (sum >= target) {
  12.                     //如果有满足条件的：1.计算长度，2.和subLength比较长度，3.退出循环
  13.                     //1.计算长度
  14.                     subLength = j - i + 1;
  15.                     result = result < subLength ? result : subLength;
  16.                     //如果result<subLength满足，就返回result，否则就返回计算出来的长度subLength
  17.                     //最开始，result<subLength肯定是不满足的(除非整个数组中没有一个满足条件的子数组)
  18.                     break;
  19.                 }
  20.             }   
  21.         }
  22.         return result == INT32_MAX ? 0 : result;
  23.     }
  24. };

三目运算符

格式：<表达式1> ? <表达式2> : <表达式3>;

执行步骤：

  • 计算表达式1的值
  • 若表达式1为非0，则只计算表达式2，且表达式2的结果为整个表达式的结果
  • 若表达式1为0，则只计算表达式3，讲表达式3的结果作为整个表达式的结果

3.1.4 python实现

  1. class Solution:
  2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  3.         #定义最终结果，默认初始化为0
  4.         resutl = len(nums)+1
  5.         #定义子数组之和
  6.         sum = 0
  7.         #定义子数组长度
  8.         subLenght = 0
  9.         for i in len(nums):
  10.             #每次大循环结束后要刷新nums的值
  11.             sums = 0
  12.             for j in range(i, len(nums) + 1):
  13.                 #计算nums的大小
  14.                 nums += nums[j]
  15.                 #判断是否满足
  16.                 if sums >= target:
  17.                 #如果满足，就返回数组长度，且跳出循环
  18.                     subLength = j - i + 1
  19.                     if subLength < result:
  20.                         result = subLength
  21.                         break
  23.         if result == len(nums)+1:
  24.             return 0
  25.         else:
  26.             return result

问题：python用暴力解发总是回超过时间，和c++同样的逻辑，python效率是真的差。

3.2 滑动窗口

3.2.1 代码逻辑

  • 窗口里面是什么？
    • 窗口里是满足子数组元素之和大于target的数组
  • 两个指针，一个窗口开始指针i，一个窗口结束指针j
    • 结束指针j先向后移动，直到下标i到j之间的元素之和满足>=target
    • 满足以后，缩小窗口大小，开始指针i向后移动，j指针不变，直到窗口内的元素大小之和再次不满足>=target
  • 定义一个subLength保存窗口的长度，一个result保存最终答案
    • 每次满足的时候，计算子数组长度subLength，并与result做比较
      • 如果subLength<result
        • 更新result的值
  • 只要进行一轮循环，就可以找出最小窗口

3.2.2 c++代码实现

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums) {
  4.         //定义最终结果变量
  5.         int result = INT32_MAX;
  6.         //定义子数组大小
  7.         int sum = 0;
  8.         //定义窗口大小
  9.         int subLength = 0;
  10.         //滑动窗口起始位置
  11.         int i = 0;
  12.         for (int j = 0; j < nums.size(); j++) {
  13.             sum += nums[j]
  14.                 while(sum >= target) {
  15.                     //计算窗口的大小
  16.                     subLength = j - i + 1;
  17.                     //判断下看要不要更新result的值
  18.                     resutl = result < subLength ? result : subLength;
  19.                     //更新sum的值
  20.                     sum -= nums[i];
  21.                     i++;
  22.                     /**也可以写成下面这种形式
  23.                        shum -= nums[i++];
  24.                        先进行整个式子的运算，然后再进行i++
  25.                     */                    
  26.                 }
  27.         }
  28.         return result == INT32_MAX ? 0 : result;
  29.     }
  30. };

3.2.3 python代码实现

  1. class Solution:
  2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  3.         #定义一个无限大的数
  4.         res = float("ing")
  5.         Sum = 0
  6.         index = 0
  7.         for i in range(len(nums)):
  8.             Sum += nums[i]
  9.             while Sum > target:
  10.                 #这里直接用库函数min就行了
  11.                 res = min(res, i-index+1)
  12.                 Sum -= nums[index]
  13.                 index += 1
  14.         #下面是python的三目运算
  15.         return 0 if res==float("inf") else res

4 螺旋矩阵II

题目地址：https://leetcode-cn.com/problems/spiral-matrix-ii/

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

  1. class Solution {
  2. public:
  3.     vector<vector<int>> generateMatrix(int n) {
  4.         vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
  5.         int startx = 0, starty = 0;//定义开始循环的地方
  6.         int loop = n/2;//loop圈数，圈数是n/2(向下取整数)，没填写完以全，loop--
  7.         int mid = n/2;//如果是奇数的平方就会用到这个mid,可以直接给中间元素赋值
  8.         int count = 1;//从1开始技术
  9.         int offset = 1;//每转完一圈，偏移量就要增加2
  10.         int i,j;//循环变量
  11.         while (loop--) {
  12.             //一个while循环，就代表填写了这个正方行二维数组的以一圈(由外向内)，每次循环完圈数loop--
  13.             //把起始位置赋值给i,j
  14.             i = startx;
  15.             j = starty;
  17.             //上面一行，从左到右依次加一，一行的第一个元素包含了，最后一个元素没有包括，所以用了<
  18.             //二维数组的第二个[]代表内部的小数组
  19.             for (j = starty; j < starty + n - offset; j++) {
  20.                 res[start][j] = count++;
  21.             }
  23.             //右边一列，从上到下，一列的最上面的元素包括了，最下面的元素没有包括
  24.             //j就是上面for循环的位置，代表在这一列
  25.             for (i = startx; i < start + n - offset; i++) {
  26.                 res[i][j] = count++;
  27.             }
  29.             //下面一行，从右到左，j还是从上面的j的位置开始进行i--
  30.             for (; j > starty; j--) {
  31.                 res[i][j] = count++;
  32.             }
  34.             //左边一列，从下往上，i就是从上面i的位置，进行i--
  35.             for (; i > startx; i--) {
  36.                 res[i][j] = count++;
  37.             }
  39.             //每写完一圈，开始的位置就要往内移动一圈，即就是x,y都+1
  40.             startx++;
  41.             starty++;
  42.             //每写完一圈，offset+2，因为下一圈行列要写的元素都少两个
  43.             offset += 2;
  44.         }
  46.         //如果是奇数，要给最中间的元素单独赋值
  47.         if (n % 2) {
  48.             res[mid][mid] = count;
  49.         }
  50.         return res;
  51.     }
  52. };

链表

1.链表基础回顾

为什么要使用链表？

插入/删除(时间复杂度) 查询(时间复杂度) 适用场景
数组 O(n) O(1) 数量固定，频繁查询，删除元素少
链表 O(1) O(n) 数量不固定，频繁增删，查询比较少
  • 数组在定义的时候，空间大小就是给定义好的，要想改变数组大小的话，就要重新定义数组，非常麻烦
  • 链表的长度是不固定的，可以动态的增删元素增删的时间复杂度为O(1)

1.1 链表定义

  1. //单链表
  2. struct ListNode {
  3.     int val; // 节点上存储的元素
  4.     ListNode *next;// 指向下一个节点的指针
  5.     ListNode(int x) : val(x), next(NULL) () //节点的构造函数
  6. }

2.删除链表中的指定节点

题目链接203.删除指定节点

2.1 思路一，直接删除

直接删除指定节点

  • 对头节点做单独处理

  • 分两部分删除

    1. class Solution{
    2. public:
    3.   ListNode* removeElement(ListNode* head, int val) {
    4.       //删除头节点
    5.       while (head != NULL && head->val == val ) {
    6.           //这里为什么要用while不用if呢？
    7.           /**
    8.           1.后面的删除非头节点的代码不会去判断头节点。
    9.           所以，要是头节点后面的节点也是val的话。
    10.           如果用if只能删除一个，那head后面的新的head后面不会检测，所以肯定会剩下一个
    11.           2.用while的话，最后的结果可以保证head->val肯定不是val。
    12.           */
    13.           ListNode* tmp = head;
    14.           head = head->next;
    15.           delete tmp;
    16.       }
    18.       //删除非头节点
    19.       ListNode* cur = head;//定义一个临时指针：cur
    20.       while ( cur != NULL && cur->next != NULL) {
    21.           //当cur不指向头最后一个空指针NULL和自己本身不是空指针时执行
    22.           if (cur->next->val == val) {
    23.               ListNode* tmp = cur->next;
    24.               cur->next = cur->nex->next;
    25.               delete tmp;
    26.           }else {
    27.               cur = cur->next;
    28.           }
    29.       }
    30.       return head;
    31.   }
    32. }

    2.2 设置虚拟头节点

  • 添加一个虚拟头节点作为新的头节点

  • 最后return dummnNode->next;
    1. class Soltuion:
    2. public:
    3.   ListNode* removeElements(ListNode* head, int val) {
    4.       ListNode* dummyHead = new ListNode(0);//设置一个虚拟头节点，val为0
    5.       dummyHead->next = head;//让新指针指向head
    6.       ListNode* cur = dummyHead;
    7.       while (cur != NULL && cur->next != NULL) {
    8.           if (cur->next->val == val) {
    9.                  ListNode* tmp = cur->next;
    10.               cur->next = cur->next->next;
    11.               delete tmp;
    12.           }else{
    13.               cur = cur->next;
    14.           }
    15.       }
    16.       //删除定义的虚拟头节点
    17.       head = dummyHead->next;
    18.       delete dummyHead;
    19.       return head;
    20.   }

    3.链表设计

    题目链接707.设计链表
    1. get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。
    2. addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    3. addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
    4. addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
    5. deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点
  1. class MyLinkedList{
  2. public:
  3.     //定义链表结构体
  4.     struct LinkedNode {
  5.         int val;
  6.         LinkedNode* next;
  7.         LinkedNode(int val):val(val), next(nullptr){}
  8.     };
  10.     //初始化链表
  11.     MyLinkedList() {
  12.         _dymmyHead = new LinkedNode(0);//定义虚拟头节点，val值为0
  13.         _size = 0;
  14.     }
  16.     //函数1：获取到第index个节点的数值，如果index是非法数值，直接返回-1,(index从0开始的，第0个节点就是头节点)
  17.     int get(int index) {
  18.         //判断index是不是非法值
  19.         /**
  20.         1.要求的index不能大于链表的长度
  21.         2.要求的index不能小于0
  22.         */
  23.         if (index > (_size - 1) || index < 0) {
  24.             return -1;
  25.         }
  26.         LinkedNode* cur = _dummyHead->next;//定义一个临时变量指向虚拟头节点的下一个节点(原0号head节点)
  27.         while (index--) {
  28.             /*
  29.             执行顺序：
  30.             1.判断while (index)
  31.             2.执行index--
  32.             3.执行循环体代码
  34.             举例：index = 3
  35.             判断       3  2  1  判断不通过
  36.             index --   2  1  0
  37.             执行循环体 *1  *2  *3
  38.             */
  39.             cur = cur->next;
  40.         }
  41.         return cur->val;
  42.     }
  44.     //函数2：在链表最前面插入一个节点，插入完成以后，新插入的节点作为列表的新的头节点
  45.     void addAtHead(int val) {
  46.         LinkedNode* newNode = new LinkedNode(val);
  47.         newNode->next = _dummyHead->next;
  48.         _dummyHead->next = newNode;
  49.         _size++;
  50.     }
  52.     //函数3：在链表最后面添加一个节点
  53.     void addAtTail(int val) {
  54.         LinkedNode* newNode = new LinkedNode(val);
  55.         LinkedNode* cur = _dummyHead;
  56.         while(cur->next != nullptr){
  57.             cur = cur->next;
  58.         }
  59.         cur->next = newNode;
  60.         _size++;
  61.     }
  63.     //函数4：在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点
  64.     //如果index等于链表的长度， 则说明是新插入的节点为链表的尾节点
  65.     //如果index大于链表长度，则返回空
  66.     /**
  67.     参数1：插入在Index之前
  68.     参数2：插入的val
  69.     */
  70.     void addAtIndex(int index, int val) {
  71.         if (index > _size) {
  72.             //先判断inde是否合法
  73.             return;
  74.         }
  75.         //临时指针都先指向虚拟头节点
  76.         LinkedNode* cur = _dummyHead;
  77.         while(index--){
  78.             cur = cur->next;
  79.         }
  80.         newNode->next = cur->next;
  81.         cur->next = newNode;
  82.         _size++;
  83.     }
  85.     //函数5：删除第index个节点，如果index大于等于链表的长度，直接return,注意，index是从0开始的
  86.     void deleteAtIndex(int index) {
  87.         //先判断参数传入是否正确
  88.         if (index >= size || index < 0) {
  89.             return;
  90.         }
  91.         LinkedNode* cur = _dummyHead;
  92.         //找到目标位置
  93.         while(index--){
  94.             cur = cur->next;
  95.         }
  96.         LinkedNode* tmp = cur->next;
  97.            cur->next = cur->next->next;
  98.         delete tmp;
  99.         _size--;
  100.     }
  102.     //打印链表
  103.     void printLinkedList(){
  104.         LinkedNode* cur = _dummyHead;
  105.         while (cur->next != nullptr) {
  106.             cout << cur->next->val << " ";
  107.             cur = cur->next;
  108.         }
  109.         cout << endl;
  110.     }
  111. private:
  112.     int _size;
  113.     LinkedNode* _dummyHead;
  115. };

4.反转列表

4.1 双指针法

image.png

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* temp;
  5.         ListNode* cur = head;
  6.         ListNode* pre = NULL;
  7.         while(cur) {
  8.             temp = cur->next;
  9.             cur->next = pre;
  10.             pre = cur;
  11.             cur = temp;
  12.         }
  13.         return pre;
  14.     }
  15. }