0%

2021-5-26 LeetCode记录

2021-5-26 LeetCode记录

难度 数量
总计 6
Easy 5
Medium 1

​ 今天做的都是剑指Offer里面的题目。

  1. 10-I.斐波那契数列10-II.青蛙跳台阶问题

    两题都是类似于斐波那契数列的动态规划类题目,比较好的方法是通过常数级别的变量存储动态规划需要的数据并循环求解。

    时间复杂度:$O(n)$

    空间复杂度:$O(1)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    int fib(int n) {
    int first = 0, second = 1, res = 0;
    if (n == 0){
    return 0;
    }
    else if (n == 1){
    return 1;
    }
    else{
    for (int i = 2;i <= n;i++){
    res = first + second;
    res %= 1000000007;
    first = second;
    second = res;
    }
    }
    return res;
    }
    };
  2. 03.数组中的重复数字

    这道题有两种解法。一是利用额外空间建立哈希表来记录元素重复情况,二是利用题目中的数字分布规律(所有数字在0~n-1的范围内)性质来在不用额外空间的情况下求解。

    第二种方法的思路是:遍历数组并将元素其值代表的下标位置进行交换,若其中已存放该值的话则说明有重复。

    时间复杂度:$O(n)$

    空间复杂度:$O(1)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
    int findRepeatNumber(vector<int>& nums) {
    for (int i = 0;i<nums.size();i++){
    if (nums[i] == i){
    continue;
    }
    // 出现重复
    if (nums[i] == nums[nums[i]]){
    return nums[i];
    }
    swap(nums[i], nums[nums[i]]);
    }
    return -1;
    }
    };
  3. 04.二维数组中的查找

    本题是在一个每一行左-右递增、每一列上-下递增的二维数组中进行元素查找。

    理想的方法是将其视作以右上角或左下角为根的二叉查找树。

    时间复杂度:$O(M+N)$

    空间复杂度:$O(1)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if (matrix.size() == 0) return false;
    // 以右上角为根结点
    int x = 0, y = matrix[0].size() - 1;
    while (x < matrix.size() && y >= 0){
    // 大于当前结点则右移
    if (matrix[x][y] > target) y--;
    // 小于当前结点则下移
    else if (matrix[x][y] < target) x++;
    // 等于则退出
    else return true;
    }
    return false;
    }
    };
  4. 11.旋转数组的最小数字

    利用旋转数组的性质,进行二分查找。

    具体方法是维护左右指针,每次将中点与末尾对比,随后更新左右指针。

    时间复杂度:$O(log_2N)$

    空间复杂度:$O(1)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
    int minArray(vector<int>& numbers) {
    int i = 0, j = numbers.size()-1;
    while (i != j){
    int m = (i+j)/2;
    //
    if (numbers[m]>numbers[j]) i = m + 1;
    else if (numbers[m]<numbers[j]) j = m;
    else j = j - 1;
    }
    return numbers[i];
    }
    };
  5. 09.用两个栈实现队列

    用两个栈来实现队列,一个栈用于入队操作、一个栈用于出队操作。

    入队时加在栈尾,出队时将入队栈翻转并出队栈顶。

    时间复杂度:添加$O(1)$、删除$O(n)$

    空间复杂度:$O(N)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class CQueue(object):
    def __init__(self):
    self.stack_add = []
    self.stack_del = []

    def appendTail(self, value):
    self.stack_add.append(value)

    def deleteHead(self):
    if self.stack_del:
    return self.stack_del.pop()
    if not self.stack_add:
    return -1
    while self.stack_add:
    self.stack_del.append(self.stack_add.pop())
    return self.stack_del.pop()