kjg's blog
0%

220208刷题

发表于 分类于
415.字符串相加(Easy) 43.字符串相乘(Mid) 1115.交替打印 FooBar(Mid) 1438.绝对差不超过限制的最长连续子数组(Mid) 面试题59-II.队列的最大值(Mid)

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 ：

输入：num1 = "11", num2 = "123"
输出："134"

提示：

  • 1 <= num1.length, num2.length <= 104
  • num1 和num2 都只包含数字 0-9
  • num1 和num2 都不包含任何前导零

C++

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
        string res = "";
        while(i >= 0 || j >= 0 || carry){
            int a = i >= 0 ? (num1[i] - '0') : 0;
            int b = j >= 0 ? (num2[j] - '0') : 0;
            int c = (a + b + carry)%10;
            res += c + '0';
            carry = (a + b + carry)/10;
            i --;
            j --;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零，除了数字0本身。

C++

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        string res = "0";
        int i = num1.size() - 1, j = num2.size() - 1;
        int cnt = 0;
        while(j >= 0){
            int times = num2[j] - '0';
            string temp = "0";
            while(times -- >0)
                temp = addStrings(temp, num1);
            temp.append(cnt++, '0'); // 第一次后每次要在 中间结果补0
            res = addStrings(res, temp);
            j--;
        }
        return res;
    }


    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
        string res = "";
        while(i >= 0 || j >= 0 || carry){
            int a = i >= 0 ? (num1[i] - '0') : 0;
            int b = j >= 0 ? (num2[j] - '0') : 0;
            int c = (a + b + carry)%10;
            res += c + '0';
            carry = (a + b + carry)/10;
            i --;
            j --;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

1115. 交替打印 FooBar

给你一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例：

  • 线程 A 将会调用 foo() 方法，而
  • 线程 B 将会调用 bar() 方法

请设计修改程序，以确保 "foobar" 被输出 n 次。

示例 1：

输入：n = 1
输出："foobar"
解释：这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2：

输入：n = 2
输出："foobarfoobar"
解释："foobar" 将被输出两次。

提示：

  • 1 <= n <= 1000

C++

  • 互斥锁
class FooBar {
private:
    int n;
    mutex m1, m2;
public:
    FooBar(int n) {
        this->n = n;
        m1.unlock();
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            m1.lock();
        	printFoo();
            m2.unlock();
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            m2.lock();
        	printBar();
            m1.unlock();
        }
    }
};
  • 信号量
#include<semaphore.h>
class FooBar {
private:
    int n;
    sem_t foo_done,bar_done;
public:
    FooBar(int n) {
        this->n = n;
        sem_init(&foo_done,0,0); // 中间变量为0 用在线程间，非0用在进程间
        sem_init(&bar_done,0,1); 
    }
    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            sem_wait(&bar_done); // P(bar_done)
            printFoo();
            sem_post(&foo_done); // V(foo_doneV)
        }
    }
    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            sem_wait(&foo_done); // P(foo_done)
            printBar();
            sem_post(&bar_done); // V(bar_done)
        }
    }
};
  • 原子操作
class FooBar {
private:
    int n;
    atomic<bool>foo_done=false;
public:
    FooBar(int n) {
        this->n = n;
    }
    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            while(foo_done) this_thread::yield();       
            printFoo();
            foo_done=true;
        }
    }
    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            while(foo_done==false) this_thread::yield();        
            printBar();
            foo_done=false;
        }
    }
};

1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：

输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

示例 2：

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

C++

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> st; // cpp中 map和set都自带红黑树,可排序 begin()最小, rbegin()最大
        int l = 0, r = 0;
        int res = 0;
        while(r < nums.size()){
            st.insert(nums[r ++]);
            while(*st.rbegin() - *st.begin() > limit) st.erase(st.find(nums[l++]));
            res = max(res, r - l);
        }
        return res;
    }
};

面试题59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5

C++

class MaxQueue {
public:
    multiset<int> st;
    queue<int> q;
    MaxQueue() {
        
    }
    
    int max_value() {
        return st.empty() ? -1 : *st.rbegin();
    }
    
    void push_back(int value) {
        q.push(value);
        st.insert(value);
    }
    
    int pop_front() {
        if(q.empty()) return -1;
        int res = q.front();
        q.pop();
        st.erase(st.find(res));
        return res;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */