精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
一网友投了华为的软件工程师，投了之后就没有反应了，联系HR也不回复，后来通过打听得知该网友所在学校不是华为的目标院校。原来大厂招聘都有目标院校，如果不是目标院校是不是简历都过不了？
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第238题：除自身以外数组的乘积。
问题描述
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内
问题分析
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] res = new int[length];
res[0] = 1;
// 先计算当前位置左边所有元素的乘积。
for (int i = 1; i < length; i++)
res[i] = res[i - 1] * nums[i - 1];
int right = 1;// 当前位置右边所有元素的乘积。
// 左边和右边的乘积就是当前位置的值。
for (int i = length - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
vector<int> res(length);
res[0] = 1;
// 先计算当前位置左边所有元素的乘积。
for (int i = 1; i < length; i++)
res[i] = res[i - 1] * nums[i - 1];
int right = 1;// 当前位置右边所有元素的乘积。
// 左边和右边的乘积就是当前位置的值。
for (int i = length - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)
res = [0] * length
res[0] = 1
# 先计算当前位置左边所有元素的乘积。
for i in range(1, length):
res[i] = res[i - 1] * nums[i - 1]
right = 1 # 当前位置右边所有元素的乘积。
# 左边和右边的乘积就是当前位置的值。
for i in range(length - 1, -1, -1):
res[i] *= right
right *= nums[i]
return res
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
