算法分析 [n值加法、平方加法] 2019-03-07
1. n值加法
167. 两数之和 II - 输入有序数组 Two Sum II - Input array is sorted medium
双指针（快fast 慢slow 指针），两数相加值大于目标值，e--，值小于目标值，s++，相等则返回
15. 获取数组中3个值相加等于目标值的组合(每个值只能用一次)，3Sum medium
[重要] 先排序
遍历第一次，需要考虑重复值if(i>0&&nums[i]==nums[i-1]) continue;
这种情况说明和前一个值相等，前一次算过了，不需要再计算了
减去值，得出剩下的值，然后用 2Sum 方式计算
2Sum返回所有集合，需要考虑值与前值相等无需重复计算，可以快速略过
while(lo<hi && nums[lo] == nums[lo+1]) lo++;
while(lo<hi && nums[hi] == nums[hi-1]) hi--;
lo++;
hi--;
16. 获取数组中3个值相加最接近于目标值 3Sum Closest medium
和3sum一样，只是要判断最接近值
private int max(int target, int src, int dst) {
return (Math.abs(dst - target) < Math.abs(src - target)) ? dst : src;
}
653. 二叉查找树查找两个节点相加值为目标节点 Two Sum IV - Input is a BST easy
法1. 时间复杂度O(n) 空间复杂度O(n)
使用中序遍历后保存列表，进行sum2计算
法2. 时间复杂度O(n) 空间复杂度O(n)
使用BFS，利用Queue和HashSet，每次遍历都出Queue，使用set.contains(k - node.val)判断是否存在目标值，如果不存在，将当前值入HashSet，并且入Queue
112. 是否根节点至叶子节点的路径存在一个等于目标值 Path Sum
法1. 时间复杂度O(n) 空间复杂度O(1)
使用递归，每次传入的sum=sum-root.val，每次递归node.left||node.right
113. 根节点至叶子节点的路径存在一个等于目标值所有节点 Path Sum II
法1. 时间复杂度O(n) 空间复杂度O(n)
使用backtrace，用一个list做记录，每次进一个节点都add，每次left||right完成后remove
129. 统计所有根节点至叶子节点的路径的总和 Sum Root to Leaf Numbers
法1. 时间复杂度O(n) 空间复杂度O(n)
用一个list做记录，每次进一个节点都add，每次left||right完成后remove
法2. 时间复杂度O(n) 空间复杂度O(1)
将之前的值 sum*10 + node.val 进行递归传递，这样可以减少空间复杂度
2. 平方加法
367. 校验是否存在最优的平方数直接等于目标值 Valid Perfect Square easy
法1. 时间复杂度O(1) 空间复杂度O(1)
使用平方公式对目标值求解，先得出一个double值，强转int，再通过int*int与目标值对比
法2. 时间复杂度O(logn) 空间复杂度O(1)
使用折半法，靠近目标值，但是由于m*m可能导致int的越界问题，可以考虑使用long来处理
法3. 时间复杂度O(sqrt(n)) 空间复杂度O(1)
平方的计算公式=A square number is 1+3+5+7+...，从1开始每次对其值+2，将目标值每次减去累加至，最后值如果减为0，说明是平方数
法4. 时间复杂度O(log(n)) 空间复杂度O(1)
newtoon 公式 => i = (i + x / i) / 2
69. 根号公式求解 Sqrt(x) easy
法1. 时间复杂度O(logn) 空间复杂度O(1)
使用折半法，靠近目标值，但是由于m*m可能导致int的越界问题，可以考虑使用long来处理，如果都没有找到，返回r或者l
法2. 时间复杂度O(log(n)) 空间复杂度O(1)
newtoon 公式 => i = (i + x / i) / 2
50. 值的n次方 Pow(x, n) medium
要考虑正整数和负整数边界问题，负整数比正整数多1
法1. 时间复杂度O(n) 空间复杂度O(1)
逐层进行n次累加，会出现Time Limit Exceeded
法1. 时间复杂度O(logn) 空间复杂度O(1)
采用 同值平方 具备 折半的特性, 如果 n次方的n是奇数, 需要独立*一次, 其余可以快速折半
633. 两数平方加法等于目标值 Sum of Square Numbers easy
法1. 时间复杂度O(sqrt(n)logn) 空间复杂度O(1)
使用Math.sqrt返回的double是否实是整形的方式来做判断
法2. 时间复杂度O(sqrt(n)logn) 空间复杂度O(logn)
减去第一个平方值后，剩下的值用折半来处理，考虑使用long来处理放置越界，因为 int*int 会导致越界
279. 最短的平方和加法等于目标值 Perfect Squares medium
法1. BFS 时间复杂度O(n^2) 空间复杂度O(n)
- 先求出构成值的所有平方和列表，下面是所有平方的构成方法
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while(square <= n) {
squares.add(square);
square += diff;
diff += 2;
}
return squares;
}
- 使用BFS，将值减去初始平方数开始，判断是否为0，余数加入queue
- 每次队列不为空最短路径都加1
- 然后再重新遍历平方和列表
- 需要标记已经使用过的余数，减少重复遍历
法2. dp
TODO
