前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >除自身累乘算法题,又有创意解法了

除自身累乘算法题,又有创意解法了

作者头像
double
发布2018-07-31 17:25:10
7500
发布2018-07-31 17:25:10
举报
文章被收录于专栏:算法channel
2018 06 16

除自身相乘

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1).

举个例子:

输入:2, 3, 5, 1

输出:15, 10, 6, 30

分析:

15 = 3 * 5 *1; 10 = 1 * 5 * 1; 6 = 2 * 3 * 1;30 = 2 * 3 * 5

1 算法代码

昨晚,公号内推送了这道题的两版算法代码。推出后,又有小伙伴@地球村长 精心整理这道题详细的分析过程,如何一步一步解决除自身相乘问题。

今天凌晨近4点,@zero 估计观看西班牙和葡萄牙比赛中,给我发了一版堪称C罗神一般的电梯球那样的解法---深度优先搜索求解。

十分感谢@地球村长,@zero. 大家继续领悟这道:除自身相乘的算法题,彻底分析透,感受算法的魅力所在。

这道题主要难度在于时间复杂度和空间复杂度的要求,下面由浅入深的分析这道题:

v1 时间复杂度 O(n^2), 空间复杂度 O(1)

代码语言:javascript
复制
def product_except_self1(lst):

    n = len(lst)

    if n == 0:
        return 0

    if n == 1:
        return lst[0]

    res = [1 for i in range(n)]


    for i in range(n):
        for j in range(n):
            if j == i:
                continue
            else:
                res[i] *= lst[j]

    return res

print(product_except_self1([1,2,3,4]))

v2 时间复杂度 O(n), 空间复杂度 O(n)

代码语言:javascript
复制
def product_except_self2(lst):
    n = len(lst)
    if n == 0:
        return 0
    if n == 1:
        return lst[0]

    res = [1 for i in range(n)] # 保存结果的数组
    fwd = [1 for i in range(n)]
    bwd = [1 for i in range(n)]


    for i in range(1,n):
        fwd[i] = fwd[i-1] * lst[i-1]

    for i in range(n-2, -1, -1):
        bwd[i] = bwd[i+1] * lst[i+1]


    for i in range(n):
        res[i] = fwd[i] * bwd[i]

    return res

print(product_except_self2([1,2,3,4]))
代码语言:javascript
复制

v3 时间复杂度 O(n), 空间复杂度 O(1)

代码语言:javascript
复制
def product_except_self3(lst):
代码语言:javascript
复制
    n = len(lst)
    if n == 0:
        return 0

    if n == 1:
        return lst[0]

    res = [1 for i in range(n)] # 保存结果的数组


    for i in range(1,n):
        res[i] = res[i-1] *lst[i-1] # 从前往后遍历,以每个元素为界,之前元素累乘

                                    # 每次利用lst累乘一个结果(主要考虑空间复杂度)

    temp = lst[n-1] # 保存最后一个元素
    for i in range(n-2, -1, -1): # 从后往前遍历,以每个元素为界,之后元素累乘
        res[i] = res[i] * temp # 每次利用lst累乘一个结果(主要考虑空间复杂度)
        temp = temp * lst[i]
    return res

print(product_except_self3([1,2,3,4]))

v4 时间复杂度 O(n), 空间复杂度 O(1),直接拿输入数组保存结果,深度优先搜索,往下递推更新前缀积,回溯时更新后缀积。

代码语言:javascript
复制
using namespace std;
const int N = 1e4 + 5;
int f[N], n;
void dfs(int pre, int now, int& suf) {
    if(now == n + 1)
           return;
 dfs(pre * f[now], now + 1, suf);
    int t = f[now];
    f[now] = pre * suf;
    suf *= t;
}
int main() {
 cin >> n;
 for(int i = 1; i <= n; i++)
     cin >> f[i];
 int x = 1;
 dfs(1, 1, x);
 for(int i = 1; i <= n; i++)
     cout << f[i] << " ";
}

2 解题小结

数据结构与算法的优化主要有两个方面:

  1. 数据结构上的优化: 如:2与1相比得到常用:以空间换时间。

还有其他常用的是以字典来代替数组,这是数据结构上的优化

2. 算法上的优化:

如3与2相比得到:迭代和分治的思想。

还有常用的二分法与暴力法查找的比较这是算法上的优化

3. 面试经验小结:

  • 一般大公司面试都有比较规范的流程
  • 数据结构与算法写代码一般从易到难,逐步深入
  • 第一题,如果没有思路,尝试用 “二分+快排”(能解决70%的问题),所以不要说你不知道怎么准备面试,二分、快排及变形会了吗?
  • 算法难度到动态规划吧,校招一般过了较难的动态规划题,很可能要你了,算法基本思想会了吗?
  • 最后希望多刷题 leetcode,中文链接(省去英文读题):https://leetcode-cn.com/problemset/all/

4. 以上只是本人经验总结,不可绝对化,谢谢支持。

5. 感谢群组郭大哥的支持、鼓励与分享!

作为奖励,@地球村长,@zero ,欢迎与我联系,领取 Gitchat 动态规划邀请卡(2.99元)。本场 chat 的入口:

http://gitbook.cn/gitchat/activity/5b173ce1e4e6d50625638322

3 邀请进群

以上错误之处,有疑问的地方,或者待优化改进之处,欢迎公号内留言、微信群内提问作者。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-06-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档