头像

acwing_5120




离线:7小时前



acwing_5120
7小时前

题目描述

给定一个数组A[0, 1, …, n-1],请构建一个数组B[0, 1, …, n-1],其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。

不能使用除法。

样例

样例
输入:[1, 2, 3, 4, 5]

输出:[120, 60, 40, 30, 24]
思考题:

能不能只使用常数空间?(除了输出的数组之外)

算法1

(暴力枚举) $O(n^2)$

C++ 代码

//暴力
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res;
        int n = A.size();
        for(int i  = 0; i < n; ++i){
            int ans = 1;
            for(int j = 0; j < n; ++j){
                if(j != i){
                    ans *= A[j];
                }
            }
            res.push_back(ans);
        }
        return res;

    }
};

算法2

(暴力枚举) $O(n)$

正向做一遍,存下 i 左侧的乘积
反向做一遍,在之前的结果上再次乘右侧的乘积

C++ 代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> res(n, 0);

        for(int i = 0, p = 1; i < n; ++i){
            res[i] = p;
            p *= A[i];
        }

        for(int i = n - 1, p = 1; i >= 0; --i){
            res[i] *= p;
            p *= A[i];
        }
        return res;
    }
};



题目描述

将一个骰子投掷 n 次,获得的总点数为 s,s 的可能范围为 n∼6n。

掷出某一点数,可能有多种掷法,例如投掷 2 次,掷出 3 点,共有 [1,2],[2,1] 两种掷法。

请求出投掷 n 次,掷出 n∼6n 点分别有多少种掷法。

样例

样例1
输入:n=1

输出:[1, 1, 1, 1, 1, 1]

解释:投掷1次,可能出现的点数为1-6,共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
样例2
输入:n=2

输出:[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

解释:投掷2次,可能出现的点数为2-12,共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。

      所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

算法1

(暴力枚举) $O(n^2)$

C++ 代码

class Solution {
public:
    vector<int> numberOfDice(int n) {
        //状态标识  投了i次,和为j的方案数,和的取值为 i - 6i
        vector<vector<int>> f(n + 1, vector<int>(6 * n + 1));  //为了好处理边界问题,多增加一个维度
        f[0][0] = 1;

        for(int i = 1; i <= n; ++i){ //第i次
            for(int j = i; j <= 6 * i; ++j){  //和为j
                for(int k = 1; k <= 6 && k <= j; ++k)//枚举最后一个的点数,计算方案数
                    f[i][j] += f[i - 1][j - k];       //这里有一个初始化的细节问题
            }
        }
        vector<int> res;
        for(int i = n; i <= 6 * n; ++i) res.push_back(f[n][i]);  //投n次,和最小为n
        return res;
    }
};




题目描述

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。

例如,如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口,它们的最大值分别为 [4,4,6,6,6,5]。

注意:

数据保证 k 大于 0,且 k 小于等于数组长度。

样例

输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

算法1

(暴力枚举) $O(n)$

1草图.png

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        int max_num = INT_MIN, index = 0;
        for(int i = 0; i < k; ++i){
            if(max_num < nums[i]){
                max_num = nums[i];
                index = i;
            }
        }
        res.push_back(index);

        for(int i = 1, j = k; j < n; ++i, ++j){
            if(i <= res.back()){
                if(nums[j] > nums[res.back()]) res.push_back(j);
                else res.push_back(res.back());
            }
            else{
                int pt = i;
                index = i;
                max_num = nums[i];
                while(pt <= j){
                    if(max_num < nums[pt]){
                        max_num = nums[pt];
                        index = pt;
                    }
                    ++pt;
                }
                res.push_back(index);
            }
        }

        for(int i = 0; i < res.size(); ++i){
            res[i] = nums[res[i]];
        }
        return res;
    }
};



题目描述

在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题:

如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

样例

输入:[1,1,1,2,2,2,3,4,4,4]

输出:3

算法1

(暴力枚举) $O(n^2)$

草图.png

C++ 代码

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for(int i = 31; i >= 0; --i){
            int tmp = 0;
            for(int j = 0; j < n; ++j){
                tmp += nums[j] >> i & 1;
            }
            x = x * 2 + tmp % 3;
        }
        return x;

    }
};



题目描述

在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。

输入一个数组,求出这个数组中的逆序对的总数。

样例

样例
输入:[1,2,3,4,5,6,0]

输出:6

算法1

(归并) $O(nlog(n))$

逆序对个数 = 左区间逆序对个数 + 右区间逆序对个数 + 两个区间中构成逆序对个数
因为左右区间内部排好序,逆序对计算出来之后,左右区间有序,不再存在逆序对,右区间 再和 左区间比较,之间不存在交集。

C++ 代码

class Solution {
public:
    //归并 1,找到中点. 2,递归  3归并
    int merge_sort(vector<int> &nums, int l, int r){
        if(l >= r) return 0;

        int mid = l + r >> 1, i = l, j = mid + 1;
        int res = merge_sort(nums, i, mid) + merge_sort(nums, j, r);

        vector<int> tmp(r - l + 1, 0);
        int k = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else{
                tmp[k++] = nums[j++];
                res += mid - i + 1;
            }
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];

        i = l, k = 0;
        for(;i <= r; ++i){
            nums[i] = tmp[k++];
        }

        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge_sort(nums, 0, nums.size() - 1);
    }
};



题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如,当从字符流中只读出前两个字符 go 时,第一个只出现一次的字符是 g。

当从该字符流中读出前六个字符 google 时,第一个只出现一次的字符是 l。

如果当前字符流没有存在出现一次的字符,返回 # 字符。

样例

样例
输入:"google"

输出:"ggg#ll"

解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。

算法1

(暴力枚举) $O(n)$

C++ 代码

class Solution{
public:
    //Insert one char from stringstream
    unordered_map<char, int> hash;
    queue<char> q;
    void insert(char ch){
        hash[ch]++;
        if(hash[ch] > 1){
            // while(q.size() && q.front() == ch) q.pop();// 这样写不行,因为可能队列中第二个字符当前时刻,数目也是大于1的。
            while(q.size() && hash[q.front()] > 1) q.pop();
        }
        else q.push(ch);
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if(q.empty()) return '#';
        else return q.front();

    }
};



题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。

例如 6、8 都是丑数,但 14 不是,因为它包含质因子 7。

求第 n 个丑数的值。

样例
输入:5

输出:5
注意:习惯上我们把 1 当做第一个丑数。


算法1

(暴力枚举) $O(n)$

草图.png
丑数序列 可以看作是2 3 5的倍数最后归并成的一个序列,去掉重复的元素

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        if(n == 1) return 1;
        int i = 0, j = 0, k = 0;  //i j k 3个因子,
        vector<int> num(1,1);

        while(num.size() < n){
            int min_num = min(num[i] * 2, min(num[j] * 3, num[k] * 5));   //找出3因子与对应数乘积的最小值
            num.push_back(min_num);
            if(num[i] * 2 == min_num) ++i;  //过滤掉相同的元素
            if(num[j] * 3 == min_num) ++j;
            if(num[k] * 5 == min_num) ++k;
        }
        return num[n - 1];

    }
};



题目描述

在一个 m×n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。

你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?

样例

注意:

m,n>0
样例:

输入:
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出:19

解释:沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

算法1

(dfs) $O(n^2)$

没写出来, TLE

C++ 代码

class Solution {
public:
    int res = 0, path = 0;
    int m= 0, n = 0;
    int getMaxValue(vector<vector<int>>& grid) {
        m = grid.size();
        if(m == 0) return 0;
        n = grid[0].size();

        dfs(grid, 0, 0);
        return res;
    }
    void dfs(vector<vector<int>> grid, int x, int y){
        if(x == m-1 && y == n-1){
            path += grid[x][y];
            res = max(res, path);
            path -= grid[x][y];
            return;
        }
        int dx[2] = {0, 1}, dy[2] = {1, 0};
        path += grid[x][y];
        for(int i = 0; i < 2; ++i){
            int x0 = x + dx[i], y0 = y + dy[i];

            if(x0 < m && y0 < n){
                dfs(grid, x0, y0);
            }
        }
        path -= grid[x][y];
    }
};

算法2

(dp) $O(n*m)$

C++ 代码

class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();

        vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                f[i][j] = max(f[i-1][j], f[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return f[m][n];   
    }
};



题目描述

给定一个数字,我们按照如下规则把它翻译为字符串:

0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z。

一个数字可能有多个翻译。

例如 12258 有 5 种不同的翻译,它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例
输入:”12258”

输出:5


算法1

(dfs) $O(n^2)$

C++ 代码


class Solution {
public:
    int n = 0, res = 0;
    int getTranslationCount(string s) {
        n = s.size();
        dfs(s,0);
        return res;
    }

    void dfs(string &s, int u){
        if(u == n){
            ++res;
            return;
        }

        int num = 0;
        for(int i = 0; i < 2 && u + i < n; ++i){
            int tmp = num;
            num = num * 10 + s[u + i] - '0';
            if(tmp==0 && i==1) continue; //会出现 04 01 02 这样的组合,但是这样的组合不符合规则。
                                        //05 这样的数,去掉,还可以if(i == 1 && num <10)
            if(num < 26){                
                dfs(s, u + 1 + i);
            }
        }
    }
};

算法2

(DP) $O(n)$

C++ 代码

class Solution {
public:
    int getTranslationCount(string s) {
        //状态划分  前i个数字的所有翻译方式
        int n = s.size();
        vector<int> f(n + 1, 0);
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i <= n; ++i){  //保证不越界
            f[i] = f[i - 1];
            int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if(num >=10 && num <=25) f[i] =f[i - 1] + f[i - 2];
        }
        return f[n];
    }
};



题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中,第 5 位(从 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。

请写一个函数求任意位对应的数字。

样例

样例
输入:13

输出:1


算法1

(暴力枚举) $O(logn)$

C++ 代码

class Solution {
public:
    int digitAtIndex(int n) {
        if(n == 0) return 0;

        //1 算出n是位于几位数中
        long long cnt = 9, i = 1, base = 1;
        // int cnt = 9, i = 1, base = 1;
        // cout<<n<<endl;
        while(n > cnt * i){
            n -=  i * cnt;
            ++i;
            cnt *= 10;
            base *= 10;
            // cout<<n<<endl;
            // cout<<"base"<<base<<endl;  //会出现 int 越界错误

        }

        //2 计算是i位数的第几个数
        int c = (n + i - 1) / i;         //上取整
        // cout<<"n"<<n<<endl;
        int num = base + c - 1;         //算出这个数是几
        // cout<<"num: "<<num<<endl;
        int j = n % i;                  

        //3计算那一位数字是几;
        if(j == 0) return num % 10;
        for(int k = j; k < i ; ++k){
            num /=10;
        }
        return num % 10;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla