-对特殊的具有某类题型针对性的算法的一些总结

数学模拟题

1、摩尔投票法

Leetcode 169.多数元素:

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

2、前缀积

Leetcode 238.除自身以外数组的乘积:

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

输入: [1,2,3,4] 输出: [24,12,8,6]

位运算

1、&运算符

剑指 Offer 15. 二进制中1的个数：

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。

2、进位和非进位实现加法

剑指 Offer 65. 不用加减乘除做加法：

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

3、&运算符和异或运算符运用:

剑指 Offer 56 - I. 数组中数字出现的次数：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

---

剑指 Offer 56 - II. 数组中数字出现的次数 II：

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

4、快速幂

Leetcode 50. Pow(x, n):

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

二叉树

1、分治:

Leetcode 105. 从前序与中序遍历序列构造二叉树:

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

---

剑指 Offer 33. 二叉搜索树的后序遍历序列:

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。