27道题每天6道，本周刷完
要求时间复杂度50%以上，空间复杂度也要50%以上
1.两数之和
一个循环跑完：把差值需要的差值存在和当前坐标存在map里面
代码行数也会影响性能
Map对象也是空间换时间
hasOwnProperty
var twoSum = function(nums, target) {
const map = {};
for (let i = 0;i < nums.length;i++) {
const num = nums[i];
if (map.hasOwnProperty(num)) return [i, map[num]]
map[target - num] = i;
}
return [];
};100.相同的树
这里我曲解了原题的意思，我以为他的输入是[1,2,3]结果它是个对象
还是我的二叉树的概念有点忘记了
var isSameTree = function(p, q) {
return (!p && !q ) || (!(!p || !q) && p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
};104.二叉树的最大深度.
空间复杂度不行🙅
如果循环声明变量也会影响空间复杂度
要降低的话就要把depth拿掉
通过返回值保存变量
其实原因还在于你没有搞清楚递归的顺序
函数的递归是以栈的方式运行的，先进后出
区别在于，一个是在递归返回的时候加，一个是在递归传参的时候加，传参会声明新的变量，导致空间复杂度过高
var maxDepth = function(root) {
return !root ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};11.盛最多水的容器
对要乘的数进行排序比较
a b
A B
高是最小数
差是长
理想状况下 隔的越远 数越大越好
算出两个值 一个是差 一个是最小数 要保证这两个数是所有数里面最大的
差和最小数是有关联的吗？
就相当于要同时保证两个关联数最化
穷举肯定能解决
场景转化：
和最小数的差最大
找出最大的数，和一个离这个最大数最远的数
每个下标的值为1
7 * 7
5 * 8
双游标往中间移动
虽然差会变小但是值有可能会变大，往有利的方向移动
如果我反过来想，我移动大的元素而不是小的元素，区别在哪里
18
28
意味着2个数都比18小
27
1234576
16 5*1
26 4 * 2
17 1*6
思路的核心是排除小数
第一：图是可以帮助理解的，我之前的理解忽略了图的作用
第二：从图上可以很明显的看出来，区域的面积取决小数，不取决于大数
第三：所以我们查找的其实是最大的小数，和最远的距离
第四：所以双游标可以只移动小数
这道题的核心思路在于如果没有把数据转化为图，那几乎是很难得到解的，把抽象的数据具像化
循环什么时候结束？
要利用特性来解决问题，抓住核心矛盾
var maxArea = function(height) {
let start = 0;
let end = height.length - 1;
let max = 0;
while (start < end) {
max = Math.max(max, Math.min(height[start], height[end]) * (end - start))
if (height[start] > height[end]) {
end--;
} else {
start++;
}
}
return max;
};110.平衡二叉树
你不知道最小长度有多深
树的遍历是要遍历
TreeNode { val: 1, right: TreeNode { val: 2, right: TreeNode { val: 3, right: [TreeNode], left: null }, left: null }, left: TreeNode { val: 2, right: null, left: TreeNode { val: 3, right: null, left: [TreeNode] } } } 3 3
问题分析不足：问题在于差值等于1这个关键数字上面
利用递归一把到位
递归的核心在于把复杂的问题分解成为可以循环的简单问题 并定义好出口
关键点在于需要把所有的深度都计算出来
定义一个循环
先定义行为，你要做哪些动作
var isBalanced = function(root) {
if (!root) return true;
if (!isBalanced(root.left) || !isBalanced(root.right)) {
return false;
}
const getLen = node => node ? Math.max(getLen(node.left), getLen(node.right)) + 1 : 0;
const leftLen = getLen(root.left);
const rightLen = getLen(root.right);
return leftLen === rightLen || Math.abs(leftLen - rightLen) === 1;
};以上算法会产生重复计算，下面演示通过子节点深度计算父节点算法
不要担心递归，递归肯定是会触底的
深度从子节点开始计算 递归的时候返回个数组
但是变量声明过多导致占用内存比较高
用-1来代表不符合
const loop = node => {
if (!node) return 0
const left = loop(node.left)
if (left === -1) return -1
const right = loop(node.right)
if (right === -1) return -1
if (left !== right && Math.abs(left - right) !== 1) return -1
return Math.max(left, right) + 1
}
const isBalanced = root => loop(root) !== -1141.环形链表
我每次都不能一次性理解题意 这是最大的问题
环形链表的
pos根本不存在，它是要我判断链表是否发生循环就可以了先解一遍 尽管不是最优
双指针？？？？卧槽 这还是初学者 这也太打击人了吧
不要随便改原始数据
递归的空间复杂度会高一些 因为函数会创建新的函数作用域
var hasCycle = function(head) {
if (!head) return false
if (head.visited) return true;
head.visited = true;
return hasCycle(head.next);
};快慢指针
我对链表这种数据结构还是不熟悉
JS中且和或不一定会返回boolean
相当于是游标法
var hasCycle = function(head) {
let fast = head && head.next
let slow = head
while (fast !== slow) {
fast = fast && fast.next && fast.next.next
slow = slow.next
}
return !!slow
}142.环形链表-ii
这题没办法用快慢指针
- 不用额外空间
- 不能修改链表数据
双向链表？？但是它明确提到不能改链表属性
set = 哈希表
龟兔赛跑
这种算法题没有训练过的肯定是不知道的
像是通过公式推导出来的
追赶距离是5
一种是想象这个圈很大
第二种是解释为什么S不会绕圈
这题的关键解在于s=nb
B:环的长度;N:整数;S慢游标距离;F快游标距离;A起始点到环入口距离
o为起点，a为环入口点，b为相遇点
有以下两个恒等式：
F = 2S
F = S + NB
推导: S = NB
结论1：慢节点从o开始走了N个圈
推理：假设慢节点从a开始走，那么此时慢节点再走A就能返回到起始点（因为s=NB），然后再把慢节点的起始点从a回退到o，此时慢节点正好停在相遇点b，刚刚回退的距离正好就是b距离环入口的距离也就得到了
o到a的距离 = b到a的距离
var detectCycle = function(head) {
let slow = head && head.next
let fast = head && head.next && head.next.next
while (fast && slow !== fast) {
fast = fast.next && fast.next.next
slow = slow.next
}
if (!fast) return null
fast = head
while (fast !== slow) {
fast = fast.next
slow = slow.next
}
return fast
};144.二叉树的前序遍历
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
- 判断节点是否已经访问
- 判断节点是否遍历完成
- 获取当前节点的父节点
前序遍历
中序遍历
后序遍历
中序遍历
// var tree = {val: 1, left: null, right: { val: 2, right: null, left: { val: 3, left: null, right: null }}}
var tree = { val: 1, left: null, right: { val: 2, left: { val: 3 } } }
var centerTraversal = function(root) {
const res = []
const parentMap = new WeakMap()
let node = root
while (node) {
if (node.left && !parentMap.get(node.left)) {
parentMap.set(node.left, node)
node = node.left
continue
}
if ((!node.left || parentMap.get(node.left)) && (!node.right || !parentMap.get(node.right))) {
res.push(node.val)
}
if (node.right && !parentMap.get(node.right)) {
parentMap.set(node.right, node)
node = node.right
continue
}
// 这里最终会指向空节点
node = parentMap.get(node)
}
return res
};
preorderTraversal(tree)前序遍历
用栈会更节省空间，思路也更佳清晰
莫里斯算法、伪边
var preorderTraversal = function(root) {
const res = []
const parentMap = new WeakMap()
let node = root
while (node) {
if ((!node.left || !parentMap.get(node.left)) && (!node.right || !parentMap.get(node.right))) {
res.push(node.val)
}
if (node.left && !parentMap.get(node.left)) {
parentMap.set(node.left, node)
node = node.left
continue
}
if (node.right && !parentMap.get(node.right)) {
parentMap.set(node.right, node)
node = node.right
continue
}
// 这里最终会指向空节点
node = parentMap.get(node)
}
return res
};深度优先搜索（DFS）
前序、中序、后序
宽度优先搜索（BFS）
按照树的深度遍历
右节点会被压在栈底
递归本身是利用函数的调用栈，实际上利用数组也能实现
var preorderTraversal = function(root) {
const res = []
let node
const stacks = root ? [root] : []
while (stacks.length) {
node = stacks.pop()
res.push(node.val)
if (node.right) stacks.push(node.right)
if (node.left) stacks.push(node.left)
}
return res
}就好像在下象棋，在做第一步的时候已经为后面的第N步做好准备
伪链
先思考主流程
空间复杂度的降低和算法的执行链路有很大关系，代表链路不重复访问数据
伪链会被访问2次 右节点如果指向none则建立伪链 如果指向root则删除伪链
前驱节点向左走一步然后一直往右走
如何判断节点是否被二次访问
二次访问的特点是什么？
二次访问的前驱节点最终会指向自己本身，一旦发现指向自己本身，就移除伪链
遇到叶子左节点如何返回？
由于前驱节点会提前探测并在叶子结点上加上伪链所以一旦到叶子结点上，必然会有伪链返回，伪链的作用是在访问完右节点后，直接返回祖先的根节点
所以循环体中的逻辑是不同
既然是前驱节点就应该先判断前驱节点而不是本身
在我进入下一个节点的时候前驱节点同时重置好，而不是放在循环体里面
这也是双游标法的一种典型应用
之前的differ还有4游标法
关键在于游标的运用 前驱节点的更新时机问题 这里之前做了错误的判断
没有前驱往右走，有前驱前驱建立伪链然后往左走，如果出现伪链循环，则删除伪链并往右走
犯的错误，循环体边界的设计，应该已当前节点为准，而不是跑到下一个节点中
这个算法循环次数会多一些
var tree = { val: 1, right: { val: 2, left: { val: 3 } } };
var preorderTraversal = function(root) {
let node = root
const res = []
// 前驱节点
let predecessor = node && node.left
while (node) {
if (!predecessor) {
res.push(node.val)
node = node.right
predecessor = node && node.left
} else if(!predecessor.right) {
predecessor.right = node
res.push(node.val)
node = node.left
predecessor = node.left
} else if (predecessor.right === node) {
delete predecessor.right
node = node.right
predecessor = node && node.left
} else {
predecessor = predecessor.right
}
}
return res
}
preorderTraversal(tree)题解实现
我太强调一个循环解决了 把代码结构搞复杂了
var preorderTraversal = function(root) {
let node = root
let predecessor
const res = []
while (node) {
if (!node.left) {
res.push(node.val)
node = node.right
} else {
predecessor = node.left
while (predecessor.right && predecessor.right !== node) {
predecessor = predecessor.right
}
if (!predecessor.right) {
predecessor.right = node
res.push(node.val)
node = node.left
} else {
delete predecessor.right
node = node.right
predecessor = node && node.left
}
}
}
return res
}912.排序数组
随机快排
var list = [5,2,3,1]
var sortArray = function(arr, start = 0, end = arr.length - 1) {
if (!arr.length) return []
if (arr.length === 1) return arr
if (end <= start) return;
let temp = Math.floor(Math.random() * (end - start) + start)
let low = start
let high = end
let val
while (low <= high) {
if (temp >= low) {
if (arr[temp] < arr[low]) {
val = arr[temp]
arr[temp] = arr[low]
arr[low] = val
temp = low
}
low++
} else {
if (arr[high] < arr[temp]) {
val = arr[temp]
arr[temp] = arr[high]
arr[high] = val
temp = high
}
high--
}
}
sortArray(arr, start, temp - 1)
sortArray(arr, temp + 1, end)
return arr
}
sortArray(list)145.二叉树的后序遍历
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
栈
莫里斯的特点在于伪链，前序是：根左右，伪链联通的是左节点和根
出栈的时机很重要
前序一次性会压两个节点，但是一次性只出一个节点，以此来造成循环
绝对不是先全部入栈再出栈，而是一边入栈一
如果返回上一个节点，要阻止它重新向下
关键的问题在于怎么知道节点是否已经被访问
前驱节点？？
要不还是先用递归实现一遍 观察函数出栈入栈的方式
var tree = {val: 1 right: { val: 2, left: { val: 3 }}}
var postorderTraversal = function(root) {
const stacks = root ? [root] : []
const res = []
let node = root
while (stacks.length) {
node = node.left || node.right || stacks.pop()
if (node.right && '未被访问') stacks.push(node.right)
if (node.left && '未被访问') stacks.push(node.left)
// 是否被访问是是否入栈出栈的前置条件
if (!node.left && !node.right)
}
return res
}
postorderTraversal(tree)递归 - 分治法 O(N^2)
var postorderTraversal = function(root) {
return root ? postorderTraversal(root.left).concat(postorderTraversal(root.right), root.val) : []
}迭代（空间复杂度O(N)）需要判断节点是否访问过
判断的标志在于子节点是否全部访问完
但是高效率的算法必有一个特点，就是利用特性去解决问题
先自己通过迭代写一遍 先不管空间复杂度
因为没有parent指针，所以可以考虑通过栈的方式回溯
要不就抛弃之前的方式吧
把问题最小化
两个条件自由组合？？
先弹出来 然后检查 检查通过就pop 检查不通过继续入栈
var postorderTraversal = function(root) {
const stacks = root ? [root] : []
const res = []
const set = new WeakSet()
const hasVisited = node => !node || set.has(node)
while (stacks.length) {
const node = stacks.pop()
if (hasVisited(node.left) && hasVisited(node.right)) {
res.push(node.val)
set.add(node)
} else {
stacks.push(node)
}
if (!hasVisited(node.right)) stacks.push(node.right)
if (!hasVisited(node.left)) stacks.push(node.left)
}
return res
}逆向、反转
var postorderTraversal = function(root) {
const stacks = root ? [root] : []
const res = []
while (stacks.length) {
const node = stacks.pop()
res.unshift(node.val)
if (node.left) stacks.push(node.left)
if (node.right) stacks.push(node.right)
}
return res
}15.三数之和
先排序然后用游标法
先把考虑到的逻辑列出来 然后串起来
思考了这么久 先不管性能吧
排序的好处体现不出来
排序之前是需要22比较的
排序之后过滤了一些特殊情况
要处理极限情况
[-1,0,1,2,-1,-4]
[[-1,2,-1],[-1,1,0],[-1,1,0]]
顺序不同 代表不同的结果
[[-1,-1,2],[-1,0,1]]
去除重复
和如果刚好等于0 下标该怎么移动？
[-2,0,1,1,2]
[[-2,0,2]]
[[-2,0,2],[-2,1,1]]
[-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
[[-4,-2,6],[-4,0,4],[-4,1,3],[-2,0,2]]
[[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
排除的数据为什么会不影响结果？并没有穷举所有情况
最好是在遍历的时候就去重复，否则就要在遍历结束后暴力去重
利用特性去解决问题：0 和 已排序 先暴力去重复 验证有效性？？
相等的要素？
连续相等的数字
a b c
a + b、b + c、a + c
两种情况：和越来越小j--、和越来越大i++、和不变
访问到的数 被访问过
排序不好使啊
[-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]
[[-4,-2,6],[-4,0,4],[-4,1,3],[-2,0,2]]
[-4,2,2],[-2,-2,4]
直接判断和的大小来移动游标貌似会漏掉一些情况：就比如下面的-4 3 = -1
-4 -> -2会漏掉-4 2
两数相加再查找第三个数
如果所有的情况都穷举一遍肯定可以解决问题
反向思维
8点想不出来就看答案，思路是这样的
先选中-4
然后从[-2, 6]之间寻找和等于4的两个数
创建首末2个游标
如果两数之和大于4 则移动右节点 否则移动左节点
如何去重？
还会不会出现之前的连续重复情况？？
三个数的大小顺序是怎样的？？
遍历的时候需要排除自身
重复的数字是否需要重复遍历？？不需要
遍历到队友的情况也是重复？-4 [2,2] 2 [-4,2]
只管添加，添加之后不是直接是2维数组，因为长度是固定的，我保存3个set，分别存0,1,2的下标【空间复杂度高】
要利用0这个特性
大于0的是否可以不考虑，因为很有可能前面都被考虑进去了
-2 [1,3] 覆盖了 1[-2,3]
1 [-2,3]
如果只考虑右侧数组，如果当前的数大于0，则直接停止，如果我的和不是0，而是2呢？直接判断是否大于2
什么情况下和为0，必须要有一个大于等0的数，和一个小于等于0的数
两个大于2的数相加不可能等于-2
这是排序数组的特性
var numArr = [-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]
var threeSum = function(nums) {
if (nums.length < 3) return []
const sortList = nums.sort((acc, cur) => acc - cur)
const res = []
let low, high, val1, val2, val3
for (let i = 0; i < sortList.length;i++) {
if (sortList[i] > 0) break
if (sortList[i] === sortList[i - 1]) continue
low = i + 1
high = sortList.length - 1
while (low < high) {
if (sortList[i] + sortList[low] + sortList[high] === 0 && !(val1 === sortList[i] && val2 === sortList[low] && val3 === sortList[high])) {
val1 = sortList[i]
val2 = sortList[low]
val3 = sortList[high]
res.push([val1, val2, val3])
}
if (val >= 0) {
high--
} else {
low++
}
}
}
return res
};
threeSum(numArr)179.最大数
最简单的就是穷举
如果是字符串的话估计就没法比较了 一定要找规律
最大位比较
3
34
32
30
123
3433230123
位数是固定的
30000
12300
增数法
30
30
34
50
90
位运算？
比如：我比较3 30如何比较？
303
330
我觉得也是一种排序只是排序的规则不同
0可以不算
分解问题：拆成单个数字，条件是4必须后面跟在3后面
不能拆，因为会有多位的情况
var largestNumber = function(nums) {
return nums.every(num => !num) ? '0' : nums.sort((acc, cur) => `${cur}${acc}` - `${acc}${cur}`).join('')
};仅对首行进行判断，少一次循环，也就少用一个数组
var largestNumber = function(nums) {
const list = nums.sort((acc, cur) => `${cur}${acc}` - `${acc}${cur}`)
return list[0] === 0 ? '0' : list.join('')
};20.有效的括号
栈、要考虑极限情况，这是程序员要养成的职业习惯
var isValid = function(s) {
const map = {
'(': ')',
'[': ']',
'{': '}'
}
const stacks = []
for (let i = 0;i < s.length;i++) {
if (map[s[i]]) {
stacks.push(map[s[i]])
} else if (stacks.pop() !== s[i]) {
return false
}
}
return !stacks.length
};203.移除链表元素
不止一次没有考虑极限情况，说明不仔细，不严谨
算法题里的嵌套if else很难拆
var removeElements = function(head, val) {
let current = head
let res = null
let prev
while (current) {
if (current.val === val) {
if (prev) {
prev.next = current.next
}
} else {
if (!prev) {
res = current
}
prev = current
}
current = current.next
}
return res
};206.反转链表
迭代
var listNode = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 4
}
}
}
}
var reverseList = function(head) {
let current = head
let next
let prev
while (current) {
next = current.next
if (prev) {
current.next = prev
} else {
delete current.next
}
prev = current
current = next
}
return prev || head
};
reverseList(listNode)递归
递归的内存消耗会大于迭代‘
var reverseList = function(head, prev = null) {
if (!head) return prev
const next = head.next
if (!prev) {
delete head.next
} else {
head.next = prev
}
return reverseList(next, head)
};226.翻转二叉树
递归 同样是递归 但题解的递归要更好一些
var invertTree = function(root) {
if (root) {
const val = root.left
root.left = root.right
root.right = val
invertTree(root.left)
invertTree(root.right)
}
return root
};var invertTree = function(root) {
if (root) {
const right = invertTree(root.right)
const left = invertTree(root.left)
root.right = left
root.left = right
}
return root
};迭代 - 栈
var invertTree = function(root) {
const stacks = root ? [root] : []
while (stacks.length) {
const node = stacks.pop()
const val = node.left
node.left = node.right
node.right = val
if (node.left) stacks.push(node.left)
if (node.right) stacks.push(node.right)
}
return root
};235.二叉搜索树的最近公共祖先
栈 先出后入
深度优先遍历 获得同层级节点
后序遍历？
- 直接遍历每个节点看他的子节点里面是不是会同时存在p，q，从根节点开始，根节点必然，两步走，先搜索后比较，首先定义一个遍历的循环，然后看下怎么记录路径
如果他能够保证一定能找到，其实我就是要找到分叉口
正向找就是找不同
反向找就是找相同
深度反向遍历
二叉搜索树: 左子树比当前节点小，右子树比当前节点大
这是一道分析题，遍历时的三种情况，每次只需要处理一种节点
递归会产生回溯的成本
递归权值相加
递归
var lowestCommonAncestor = function(root, p, q) {
if (root.val > Math.max(p.val, q.val)) {
return lowestCommonAncestor(root.left, p, q)
}
if (root.val < Math.min(p.val, q.val)) {
return lowestCommonAncestor(root.right, p, q)
}
return root
};迭代
var lowestCommonAncestor = function(root, p, q) {
let node = root
while (node) {
if (node.val > Math.max(p.val, q.val)) {
node = node.left
continue
}
if (node.val < Math.min(p.val, q.val)) {
node = node.right
continue
}
return node
}
return node
};236.二叉树的最近公共祖先
先把它变成二叉搜索树 然后查找？
还是直接查找
这个算法内存消耗过大
递归查找路径然后比对
var lowestCommonAncestor = function(root, p, q) {
let pl, ql
const loop = (node, parentIds = []) => {
if (!node) return
const currentIds = parentIds.concat(node)
if (node === p) {
pl = currentIds
} else if (node === q) {
ql = currentIds
} else if (pl && ql) {
return
}
loop(node.left, currentIds)
loop(node.right, currentIds)
}
loop(root)
for (let i = 0;i < Math.max(pl.length, ql.length);i++) {
if (pl[i] !== ql[i]) return pl[i-1]
}
return null
};显示一颗树的路径
优化
值不重复这一点是否可以利用
遍历回溯
LCA
斜二叉树
栈图
递归
我对递归的理解还是不够深入
通过观察特质
深度递归是从根节点回溯的，此时记录节点的“积分”如果超过2就返回
虽然是递归，但是返回值是不同的
var lowestCommonAncestor = function(root, p, q) {
let res = null
const loop = node => {
if (!node) return false
const left = loop(node.left) ? 1 : 0
const right = loop(node.right) ? 1 : 0
const mid = (node === p || node === q) ? 1 : 0
if (left + right + mid >= 2) res = node
return left + right + mid > 0
}
loop(root)
return res
};父指针迭代
var lowestCommonAncestor = function(root, p, q) {
const map = new WeakMap()
let parents
const stacks = root ? [root] : []
const setParents = node => {
parents = new WeakSet()
while (node) {
parents.add(node)
node = map.get(node)
}
}
const getParent = node => {
while (node) {
if (parents.has(node)) return node
node = map.get(node)
}
return null
}
while (stacks.length) {
const node = stacks.pop()
if (node === p || node === q) {
if (!parents) {
setParents(node)
} else {
return getParent(node)
}
}
if (node.left) {
map.set(node.left, node)
stacks.push(node.left)
}
if (node.right) {
map.set(node.right, node)
stacks.push(node.right)
}
}
return null
};无父指针迭代
LD BD BP
用一个栈刚好弹出公共父节点
我脑子里面记住了它的循环体 也只能记住 要是能创新就好了
这是前序遍历？？
没有指针就必然存在一条可循环的路径（轨迹）
循环和条件判断
先定义 后实现
左根右
如果看了题解还不会，问题不在算法，而在技巧
会保留已访问过的父节点
记录节点的访问状态（关键）
BP:BOTH_PENDING
LD:LEFT_DONE
BD:BOTH_DEON
这个算法的过程现在脑子里面过一遍
先写循环体
把循环体和逻辑分开
好鸡贼啊
他没用有map。而是在stacks里面存了一对值
先设计循环体 然后再做条件判断
深度优先算法，先遍历左子树，根可能会被访问多次
var lowestCommonAncestor = function(root, p, q) {
let LCA, current
// 左节点已访问
const LEFT_DONE = 1
// 左右都没访问
const BOTH_PENDING = 2
// 左右节点都已访问
const BOTH_DONE = 3
const weakMap = new WeakMap()
weakMap.set(root, BOTH_PENDING)
const stacks = root ? [root] : []
const top = () => stacks[stacks.length - 1]
while (stacks.length) {
current = top()
if (current === p || current === q) {
if (!LCA) {
LCA = current
} else if (LCA !== current) {
return LCA
}
}
if (weakMap.get(current) === BOTH_PENDING) {
weakMap.set(current, LEFT_DONE)
if (current.left) {
stacks.push(current.left)
weakMap.set(current.left, BOTH_PENDING)
continue
}
}
if (weakMap.get(current) === LEFT_DONE) {
weakMap.set(current, BOTH_DONE)
if (current.right) {
stacks.push(current.right)
weakMap.set(current.right, BOTH_PENDING)
continue
}
}
if (weakMap.get(current) === BOTH_DONE) {
if (stacks.pop() === LCA) {
LCA = top()
}
}
}
return null
};
// const map = {};后面有没有分号有什么区别？
var testTree1 = (() => {
const map = {}
const createTree = val => ({ val });
[3,5,1,6,2,0,8,null,null,7,4].forEach(val => {
if (val != null) {
const node = createTree(val)
map[val] = node
}
})
const setVal = (val, left, right) => {
map[val].left = map[left]
map[val].right = map[right]
}
setVal(3, 5, 1)
setVal(5, 6, 2)
setVal(2, 7, 4)
setVal(1, 0, 8)
return [map[3], map[5], map[1]]
})
var testTree2 = (() => {
const map = {}
const createTree = val => ({ val });
[3,5,1,6,2,0,8,null,null,7,4].forEach(val => {
if (val != null) {
const node = createTree(val)
map[val] = node
}
})
const setVal = (val, left, right) => {
map[val].left = map[left]
map[val].right = map[right]
}
setVal(3, 5, 1)
setVal(5, 6, 2)
setVal(2, 7, 4)
setVal(1, 0, 8)
return [map[3], map[7], map[8]]
})
var node = lowestCommonAncestor(...testTree2())
console.log(node)26.删除排序数组中的重复项
不能用splice
var removeDuplicates = function(nums) {
nums.reduceRight((acc, cur, idx) => {
if (cur === acc) nums.splice(idx, 1)
return cur
}, null)
return nums.length
};题目只要求返回长度 所以可以简化
注意审题，你不需要考虑数组中超出新长度后面的元素，双指针法
var removeDuplicates = function(nums) {
if (!nums.length) return 0
let i = 0
for (let j = 1;j < nums.length;j++) {
if (nums[i] !== nums[j]) {
i++
nums[i] = nums[j]
}
}
return i + 1
};37.解数独
算法分析，.代表动态数字，每个数独都拥有一个可选池子，每一列也都拥有一个可选池，反推的话就是要一个坑要满足多个条件3个条件全满足
- 不停的循环扫每一个数据，直到所有的数都被填满
暴力破解法
多重条件取交集
约束编程
回溯
这个算法思路是完全错的，如果没有唯一条件就会进入死循环
const testData = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
var solveSudoku = function(board) {
// 判断是否结束
const isOver = arr => !arr.some(list => list.some(str => str === '.'))
const last = arr => {
const res = []
const set = new Set(arr)
let i = 1
while (i <= 9) {
const num = `${i}`
if (!set.has(num)) res.push(num)
i++
}
return res
}
const getValue = (...list) => {
const setList = list.map(arr => new Set(arr))
const listAll = list.reduce((acc, cur) => acc.concat(cur))
return [...new Set(listAll)].filter(str => setList.every(set => set.has(str)))
}
const getR = (i, j) => {
const res = []
let x = Math.floor(i / 3) * 3
let y = Math.floor(j / 3) * 3
let arr = []
const k = x + 3
while (x < k) {
arr = arr.concat(board[x].slice(y, y + 3))
x++
}
return arr
}
while (!isOver(board)) {
for (let i = 0;i < board.length;i++) {
for (let j = 0;j < board[i].length;j++) {
const x = board[i]
const y = board.map(list => list[j])
const r = getR(i, j)
if (board[i][j] === '.') {
const value = getValue(last(x), last(y), last(r))
if (value.length === 1) {
board[i][j] = value[0]
}
}
}
}
}
return board
};
solveSudoku(testData)约束、回溯、递归
backtrack
肯定要抽方法
他应该是指出现次数
用二维数组代替map
remove中有循环+递归
递归
删除
递归
递归调用栈
出口在这里couldPlace
判断sudokuSolved
remove
placeNextNumbers
回溯过程不是很清楚
全部remove岂不是进入死循环了？
递归一定要找出口
分析调用栈：递归调用栈
backtrack
placeNextNumbers
backtrack
placeNextNumbers + removeNumber + couldPlace
couldPlace none
placeNextNumbers 出去以后 remove
remove以后进入for next
一环接一环 太精妙了约束 回溯
不要老看题解，自主思考
要考虑字符串和数字的转换
var solveSudoku = function(board) {
// 是否已结束
let isOver
// box size
const n = 3
// row size
const N = n * n
// 生成二维数组
const getArray = () => {
const arr = []
while (arr.length < N) {
// 因为数字是1-9 其实也可以用其它数据结构来代替 比如map
arr.push(new Array(11).fill(0))
}
return arr
}
// 3个约束条件 横向 纵向 9宫格
// 他是直接创建空数组
const rows = getArray()
const cols = getArray()
// 按顺序存放9个boxs
const boxs = getArray()
// 根据row、col获取box的下标
const getBoxIdx = (row, col) => n * Math.floor(row / n) + Math.floor(col / n)
// 约束
const couldPlace = (d, row, col) => {
// 计算boxs位置
const idx = getBoxIdx(row, col)
return (rows[row][d] + cols[col][d] + boxs[idx][d]) === 0
}
// 放数字
const placeNumer = (d, row, col) => {
const idx = getBoxIdx(row, col)
rows[row][d]++
cols[col][d]++
boxs[idx][d]++
board[row][col] = `${d}`
}
// 移除数字
const removeNumber = (d, row, col) => {
const idx = getBoxIdx(row, col)
rows[row][d]--
cols[col][d]--
boxs[idx][d]--
board[row][col] = '.'
}
// 这里需要一个返回值 用于判断是否成功
function placeNext(row, col) {
// 循环结束
if (row === N - 1 && col === N - 1) {
isOver = true
return
}
// 遍历完一行之后换行
if (col === N - 1) {
trace(row + 1, 0)
} else {
trace(row, col + 1)
}
}
// 回溯
// 回溯算法的关键 还没有找到 核心还没有领悟
// 现在只有一个问题 什么时候remove???
function trace(row, col) {
if (board[row][col] === '.') {
// 这个循环体也是回溯的关键
for (let i = 1;i <= N;i++) {
if (couldPlace(i, row, col)) {
placeNumer(i, row, col)
placeNext(row, col)
if (!isOver) removeNumber(i, row, col)
}
}
} else {
placeNext(row, col)
}
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[i].length;j++) {
if (board[i][j] !== '.') {
placeNumer(board[i][j], i, j)
}
}
}
trace(0, 0)
return board
}回溯的关键就是利用递归一把走到底，如果没有走到底就回退到上一个值，继续尝试下一个结果，直到全部失败继续回溯，什么时候remove是关键，算法很精髓，比起暴力求解，同样是尝试，但不用列举所有情况，而是通过程序运行过程中不断调整！
但从这个算法来看，拆分逻辑的思想非常重要，我是学习了题解的拆分思想，然后实现了这样的算法，循环体和结构拆分是两大核心
leetcode里面除了算法的解题分析，还会教我们时间复杂度分析，这是一直被我们忽略的
我的问题：审题还是不够细心
374.猜数字大小
有把握再提交
二分法奇数永远取不到的问题
一个简单题目都要调半天
// guess
// 二分法
var guessNumber = function(n) {
let end = n
let start = 1
while (end >= start) {
let mid = Math.floor((end - start) / 2 + start)
let res = guess(mid)
if (res === 0) {
return mid
} else if (res === -1) {
end = mid - 1
} else {
start = mid + 1
}
}
return -1
};46.全排列
返回多少种排序可能，感觉像动态规划问题
数组长度为2 则为2
数组长度为3 123 213 231 321 312 132 123
数组长度为4 1234 2134 2314 2341 3241 3421 3412
矩阵
第一个数往后移动，直到被还原，跟数组长度的关系？？
每个数字的移动次数 = 数组长度
长度是n * (n - 1)
假设长度是3
3 * 3 - 1 = 8
假设为2 = 2 * 2 -1 =3
它要返回的不是次数，而是结果好吧
其实就是一个两重的循环就搞定
思路应该完全错了
[[5,4,6,2],[4,5,6,2],[4,6,5,2],[4,6,2,5],[6,4,2,5],[6,2,4,5],[6,2,5,4],[2,6,5,4],[2,5,6,4],[2,5,4,6],[5,2,4,6],[5,4,2,6]]
12
[[5,4,6,2],[5,4,2,6],[5,6,4,2],[5,6,2,4],[5,2,4,6],[5,2,6,4],[4,5,6,2],[4,5,2,6],[4,6,5,2],[4,6,2,5],[4,2,5,6],[4,2,6,5],[6,5,4,2],[6,5,2,4],[6,4,5,2],[6,4,2,5],[6,2,5,4],[6,2,4,5],[2,5,4,6],[2,5,6,4],[2,4,5,6],[2,4,6,5],[2,6,5,4],[2,6,4,5]]
24
没有5624
看他的结果，很像动态规划
其实就是个排列组合的问题呀
4个数的变化次数
4 * 4 的排列组合
而且这里是需要列举情况的
3 * 2
4 * 3 * 2 * 1
杨辉三角、动态规划（正序、缓存、倒序）
1
1 1
1111
动态规划，利用两次循环间的关系递归
f(n) = f(n - 1) * n
倒序动态规划应该还是递归的形式，回溯的思路是交换位置，而不是插空
// 插空
var permute = function(nums) {
const stacks = nums.length ? [[nums[0]]] : []
for (let i = 1;i < nums.length;i++) {
while (stacks[0].length <= i) {
const list = stacks.shift()
for (let j = 0;j <= list.length;j++) {
stacks.push(list.slice(0, j).concat(nums[i], list.slice(j)))
}
}
}
return stacks
};回溯法-搜索回溯
回溯本质上是一个递归
题解数组长并没有发生变化，他是怎样控制循环的 直接用[1,2,3]这个例子
0 0 [1,2,3];
1 0 [2,1,3];
2 0 [3,1,2];3 add [3,1,2] <- [2,1,3] 2 1 [2,3,1];3 add [2,3,1]<-[2,1,3] 2 2 [2,1,3]
i从first开始算
重新来
0 0 [1,2,3];
1 0 [2,1,3];
2 0 [3,1,2];3 add [3,1,2]
这个循环逻辑需要怎么联想？？
i一开始必然等于first
i是从first开始的，涉及到循环体和递归入口的地方一定要自信看
一般的递归就是想像成最小的可重复逻辑单元，但是回溯完全不同，因为递归与递归之间存在递进的关系
问题一：最先添加的数组是谁？
[1,2,3]
问题二：out更改的次序会不会被打乱？
[1,3,2]
for循环的第一步是废的
到2加1变成3，然后就会被添加
回溯算法的时间复杂度是指数级递增
深度优先算法是节约空间的
状态、状态重置 回溯搜索 选拔
递归不发生在外面，而是发生在自身
交换、递归、撤回
出口：递归次数=数组长度
起始位置和数组长度
每次递归进来到循环体都是无事发生
书读百遍，其义自现
回到循环体设计的本身中去，循环体是在做什么？建立印象，入参代表的
是起始位置first 和 first 互换位置，这一步产生的结果
疑惑在于和我理解的回溯是有差别的，我理解的回溯是会返回到上一次执行的值的
找算法执行路径，先变起始值，再变下标值，然后回溯起始值
确实会形成回溯
如何覆盖：先填第一个位置：再填第二个位置，最后第三个位置
var permute = function(nums) {
const res = []
const swap = (first , i) => {
const val = nums[first]
nums[first] = nums[i]
nums[i] = val
}
const n = nums.length
const backtrack = first => {
if (first === n) {
res.push([...nums])
}
for (let i = first;i < n;i++) {
console.log(first, i, [...nums])
swap(first, i)
backtrack(first + 1)
swap(i, first)
}
}
backtrack(0)
return res
};
permute([1,2,3])花了很长时间没有理解的话就写两遍吧，回溯的过程我是知道的，但是我没有弄明白，为什么能够覆盖所有情况
var permute = function(nums) {
const swap = (i, j) => {
const val = nums[i]
nums[i] = nums[j]
nums[j] = val
}
const n = nums.length
const res = []
const backTrack = first => {
if (first === n) {
res.push(...nums)
}
for (let i = first; i < n; i++) {
swap(first, i )
backTrack(first + 1)
swap(i, first)
}
}
backTrack(0)
return res
};509.斐波那契数
var fib = function(N) {
if (N === 0) return 0
if (N === 1) return 1
return fib(N - 1) + fib(N - 2)
};动态规划的三种模式：暴力递归、缓存结果、倒序递归
倒序递归
var fib = function(N) {
let first = 0, second = 1, res
if (N === 0) return first
if (N === 1) return second
for (let i = 2;i <= N; i++) {
res = first + second
first = second
second = res
}
return res
};51.n皇后
回溯算法
她横、竖、斜都可走一或七步
约束、回溯
回溯是基于递归的，之前是通过二维数组去标记数字的位置，现在可以通过某一种数据结构标记皇后的位置
返回值不一样 要输出所有结果，恐怕是要换个思路的
掌握的条件有哪些？n个皇后，我不需要把所有都遍历完，只需要把所有皇后都分配出去
解决方案是一套套的 要用一个数组去保存所有结果
1 不是1步或7步，而是横竖斜，那我的约束条件就是不对的
横竖斜（撇、捺）
约束、递归，空间换时间
一个递增、一个递减
怎么看对角线上有没有皇后，且不用经过太多遍历
思维应该反过来，仅保存皇后的集合，直接检查queens
用函数表示对角线y = nx y=(N-n)x
22
11、33
13
循环包裹有问题queens才是递归的主体
既然是n皇后，代表数组一中必然存在一种可能，我就直接一个数组一个数组的放然后检查就可以了，回溯肯定还是要回溯，但这个题比之前的解数独要简单，要返回不同的解决方案
空间换时间
回溯法 方法是对了 就是这里有一些额外的损耗 比如fill 比如对角线判断 题目中采用空间换时间的方式规避掉了
var solveNQueens = function(n) {
const res = []
const queens = []
const canPlace = (i, j) => queens.every((y, x) => x !== i && y !== j && Math.abs((y - j) / (x - i)) !== 1)
const genRes = () => new Array(n).fill(null).map((_, idx) => new Array(n).fill('.').map((str, j) => j === queens[idx] ? 'Q' : str).join(''))
function backTrack(i) {
for (let j = 0; j < n; j++) {
if (canPlace(i, j)) {
queens.push(j)
placeNext(i)
queens.pop()
}
}
}
function placeNext(i) {
const idx = i + 1
if (idx === n) {
res.push(genRes())
return
} else {
backTrack(idx)
}
}
backTrack(0)
return res
};有很多多余的判断
数组保存的是一个计数器
对角线判断
空间换时间
解题效率还需要大大提高
var solveNQueens = function (n) {
const rows = []
const dales = []
const hills = []
const res = []
const queens = []
// row - col + 2*n 是为了防止出现负数
const isNotUnderAttack = (row, col) => (rows[col] || 0 + dales[row - col + 2 * n] || 0 + hills[row + col] || 0) === 0
const placeQueen = (row, col) => {
queens[row] = col
rows[col] = 1
dales[row - col + 2 * n] = 1
hills[row + col] = 1
}
const removeQueen = (row, col) => {
queens[row] = 0
rows[col] = 0
dales[row - col + 2 * n] = 0
hills[row + col] = 0
}
const addSolution = () => {
res.push(new Array(n).fill(null).map((_, idx) => new Array(queens[idx]).fill('.').concat('Q', new Array(n - queens[idx] - 1).fill('.')).join('')))
}
function backtrack(row) {
for (let col = 0; col < n; col++) {
if (isNotUnderAttack(row, col)) {
placeQueen(row, col)
if (row === n - 1) addSolution()
else backtrack(row + 1)
removeQueen(row, col)
}
}
}
backtrack(0)
return res
}71.简化路径
要想办法提高解题的效率了，不能每天只刷一道题了，要不就全刷了提交然后一起对答案，不要刷一道看一道
用栈就可以解决
- 总感觉思路错了
- 做题速度太慢了
命令是有限的、后置执行
组合情况比较复杂
.. 后面拼数字，怎么样写才优雅
分析几种特殊情况吧 ../ .. 都是需要回退的
而..abc是不回退出的，我可以令空白='/'以后遇到../就回退
判断的是两个相近的命令，而不是两个字符串，JS没有枚举类型，可以一边收集一边判断，因为没有跨层级的影响，后置判断，合并多个path
写程序，先定结构，再写实现
last有可能不存在 我这里主要是处理last的情况
还有前后两段需要拼起来的情况，处理last会取到重复数据，因为存在后置追加..abc和前置判断两种情况../
感觉像一种首尾相连的函数体，我想把stacks给去掉
三种方式：
返回新函数；闭包next；直接封装对pre、current的操作。第三种最合适，前两种over design，特殊操作，判断前置和后置.. 和 / 只能判断一次，其实reduce最合适，要避免/..qww qww/.. 感觉像三级联动 /../sdd..能不能在收集阶段就解决这个问题？？
2019..
..2019
over design了，没有认真分析就动手了，/其实代表的就是分割符，. .. 代表的都是命令或操作，除此之外都是路径
var simplifyPath = function(path) {
const list = path.split('/').filter(str => !!str)
const stacks = []
list.forEach(path => {
if (path === '..') {
stacks.pop()
} else if (path !== '.') {
stacks.push(path)
}
})
return `/${stacks.join('/')}`
};79.单词搜索
感觉也像是回溯的一种形式尝试一个单词的上下左右4个方向
初始化是找第一个单词还是找任意单词？这一步其实时间复杂度是固定的
约束、回溯，先搞简单点 从第一个单词入手吧
一种是从第一个单词开始找是单向的，比较容易
另一种是从任意单词开始找，是双向的，复杂一点，理论上也是可行的，唯一不同的是约束（动态约束）
回溯的主体是谁？字符串；回溯的约束怎么产生？上下左右
回溯最终也只是递归的一种形式，把递归吃透，回溯不是问题，千万不要固步自封，变幻方向会影响约束条件
反过来想成是填数呢？
last只能判断一个，不足以判断所有
因为第一个数没有被我计算在内
backTrack placeNext canPlace remove
var exist = function(board, word) {
const wordList = new Array(board.length).fill(null).map((_, idx) => new Array(board[idx].length))
const backTrack = (i, j, idx) => {
if (idx === word.length) {
return true
}
const list = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]].filter(([x, y]) => x >= 0 && x < board.length && y >= 0 && y < board[x].length)
for (const current of list) {
const [x, y] = current
if (board[x][y] === word[idx] && !wordList[x][y]) {
wordList[x][y] = 1
if (backTrack(x, y, idx + 1, current)) return true
wordList[x][y] = 0
}
}
return false
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[i].length; j++) {
if (word[0] === board[i][j]) { // 从这里开始缩小约束范围
wordList[i][j] = 1
if (backTrack(i, j, 1)) return true
wordList[i][j] = 0
}
}
}
return false
};
var word = "ABCB"
var test = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]另一种解法是反过来的，可以理解为是在二维平面上搜索单词，其实题目已经说得很清楚了，可以尝试一下改原始数组
var exist = (board, word) => {
const wordList = new Array(board.length).fill(null).map((_, idx) => new Array(board[idx].length))
// 约束
const canPlace = (x, y, idx) => board[x][y] === word[idx] && !wordList[x][y]
// 状态重置
const remove = (x, y) => {
wordList[x][y] = 0
}
const add = (x, y) => {
wordList[x][y] = 1
}
function placeNext(i, j, idx) {
idx += 1
if (idx === word.length) return true
const list = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]].filter(([x, y]) => x >= 0 && x < board.length && y >= 0 && y < board[x].length)
for (const [x, y] of list) {
if (backTrack(x, y, idx)) return true
}
}
function backTrack(x, y, idx) {
if (canPlace(x, y, idx)) {
add(x, y)
if (placeNext(x, y, idx)) return true
remove(x, y)
}
}
for (let i = 0;i < board.length;i++) {
for (let j = 0;j < board[i].length;j++) {
if (backTrack(i, j, 0)) return true
}
}
return false
}
exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")94.二叉树的中序遍历
迭代 left right val，第二次访问时状态怎么办，压栈，是只需要访问一次，应该反推想要达到中序遍历应该以什么样的方式压栈，如果去记录已经访问的节点，那就很简单就能实现，用WeakSet，我的期望空间复杂度为0，且不改变原始数组，一定是从根上开始访问吗？？
// 栈
var inorderTraversal = function(root) {
const stacks = root ? [root] : []
const res = []
while (stacks.length) {
const node = stacks[stacks.length - 1]
if (node.left && !node.hasVisited) {
node.hasVisited = true
stacks.push(node.left)
continue
}
delete node.hasVisited
res.push(node.val)
stacks.pop()
if (node.right) {
stacks.push(node.right)
}
}
return res
};栈-不破坏原有结构-借助一个变量实现，仔细看它入栈的方式，有一层递归嵌套，不要回避循环嵌套，嵌套不等于时间复杂度高
cur其实代表状态，前push后pop，其实需要关联一个模型，其实我知道用栈，但我不知道如何写
var inorderTraversal = function(root) {
const stacks = []
const res = []
let cur = root
while (cur || stacks.length) {
if (cur) {
stacks.push(cur)
cur = cur.left
continue
}
cur = stacks.pop()
res.push(cur.val)
cur = cur.right
}
return res
}莫里斯算法-线索二叉树-莫里斯算法-前驱节点-会改变树的结构-相当于把左子树的最后一个节点和父节点连接起来，相当于自己建立了一条访问你的链路，只有当左子树没有的时候才会添加val，访问过了就把左子树清空
类似于穿针引线 是一种空间优化的策略
var inorderTraversal = function(root) {
let cur = root
let pre
const res = []
while (cur) {
if (!cur.left) {
res.push(cur.val)
cur = cur.right
} else {
let pre = cur.left
while (pre.right) {
pre = pre.right
}
pre.right = cur
const temp = cur
cur = cur.left
temp.left = null
}
}
return res
}98.验证二叉搜索树
递归么? 左边最大的数字和右边最小的数
递归
搜索二叉树含义可能不是很清楚
上界和下界的透传，就算你知道，你也不一定知道怎么写，这就是熟练度，循环体的设计永远是最关键的步骤
还是之前那个思路，先列点，然后串逻辑，这个思路是发过来的，我的想法局限于比较自身的左右节点，而这里不是，自身只跟上下届比较，然后通过递归更新上下界
var isValidBST = function(root) {
const isValid = (node, lower, higher) => {
if (!node) return true
return node.val > lower && node.val < higher && isValid(node.left, lower, node.val) && isValid(node.right, node.val, higher)
}
return isValid(root, -Infinity, +Infinity)
}中序遍历成递增数组 - 莫里斯算法性能会更高
栈
var isValidBST = function(root) {
const stacks = []
const res = []
let cur = root
let val = -Infinity
while (cur || stacks.length) {
while (cur) {
stacks.push(cur)
cur = cur.left
}
cur = stacks.pop()
if (cur.val > val) {
val = cur.val
} else {
return false
}
cur = cur.right
}
return true
}莫里斯算法 感觉把这个东西给记死了
var isValidBST = function(root) {
let pre
let val = -Infinity
let cur = root
while (cur) {
if (!cur.left) {
if (cur.val > val) {
val = cur.val
} else {
return false
}
cur = cur.right
} else {
pre = cur.left
while (pre.right) {
pre = pre.right
}
pre.right = cur
const temp = cur
cur = cur.left
temp.left = null
}
}
return true
}无理数，无限不循环小数
lgN = x 10^x = N