第十周算法题
1、437. 路径总和 III
class Solution {
fun pathSum(root: TreeNode?, targetSum: Int): Int {
val prefixSumMap = HashMap<Int, Int>();
prefixSumMap[0] = 1;
return recursionPathSum(root, prefixSumMap, targetSum, 0);
}
fun recursionPathSum(node: TreeNode?, prefixSumMap: HashMap<Int, Int>, target: Int, currSum: Int): Int {
var varCurrSum = currSum
if (node == null) {
return 0
}
var res = 0
varCurrSum += node.`val`
res += prefixSumMap.getOrDefault(varCurrSum - target, 0)
prefixSumMap[varCurrSum] = prefixSumMap.getOrDefault(varCurrSum, 0) + 1
res += recursionPathSum(node.left, prefixSumMap, target, varCurrSum)
res += recursionPathSum(node.right, prefixSumMap, target, varCurrSum)
prefixSumMap[varCurrSum] = prefixSumMap[varCurrSum]!! - 1
return res
}
}
2、| 889. 根据前序和后序遍历构造二叉树 |
class Solution {
fun constructFromPrePost(pre: IntArray, post: IntArray): TreeNode? {
if (pre.isEmpty()) {
return null
}
val root = TreeNode(pre[0])
if (pre.size == 1) {
return root
}
var l = 0
post.forEachIndexed { index, i ->
if (pre[1] == i) {
l = index + 1
}
}
root.left = constructFromPrePost(pre.copyOfRange(1, l + 1), post.copyOfRange(0, l))
root.right = constructFromPrePost(pre.copyOfRange(l + 1, pre.size), post.copyOfRange(l, pre.size - 1))
return root
}
}
第九周算法题
1、剑指 Offer 34. 二叉树中和为某一值的路径
class Solution {
var ans = ArrayList<LinkedList<Int>>()
var path = LinkedList<Int>()
fun pathSum(root: TreeNode?, sum: Int): List<List<Int>> {
pst(root, sum)
return ans
}
fun pst(node: TreeNode?, sum: Int) {
if (node == null) return
path.add(node.`val`)
val s = sum - node.`val`
if (s == 0 && node.left == null && node.right == null) {
ans.add(LinkedList(path))
}
pst(node.left, s)
pst(node.right, s)
path.removeLast()
}
}
2、面试题 04.03. 特定深度节点链表
class Solution {
fun listOfDepth(tree: TreeNode?): Array<ListNode?> {
val res = ArrayList<ListNode?>()
val nodes = ArrayList<LinkedList<TreeNode>>()
tree?.let {
nodes.add(LinkedList<TreeNode>().apply {
add(tree)
})
}
var deep = 0
while (nodes.size > deep) {
val parentList = nodes[nodes.size - 1]
val childList = LinkedList<TreeNode>()
parentList.forEach {
it.left?.let {
childList.add(it)
}
it.right?.let {
childList.add(it)
}
}
if (childList.size > 0) {
nodes.add(childList)
}
deep++
}
nodes.forEach {
var value: ListNode? = null
var rootValue: ListNode? = null
it.forEach {
if (value == null) {
value = ListNode(it.`val`)
rootValue = value
} else {
value?.next = ListNode(it.`val`)
value = value?.next
}
}
res.add(rootValue)
}
return res.toTypedArray()
}
}
第八周算法题
1、面试题 16.25. LRU 缓存https://leetcode-cn.com/problems/lru-cache-lcci/
class LRUCache(var capacity: Int) {
var map = LinkedHashMap<Int, Int>()
fun get(key: Int): Int {
val value = map[key]
return if (value == null) {
-1
} else {
map.remove(key)
map[key] = value
value
}
}
fun put(key: Int, value: Int) {
if (map.containsKey(key)) {
map.remove(key)
map[key] = value
return
}
map[key] = value
if (map.size > capacity) {
map.remove(map.entries.iterator().next().key)
}
}
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
HashMap<TreeNode,TreeNode> map = new HashMap<TreeNode,TreeNode>();
HashSet<TreeNode> set = new HashSet<TreeNode>();
solve(map,root);
TreeNode parent = p;
while(parent!=null){
set.add(parent);
parent = map.get(parent);
}
parent = q;
while(parent!=null){
if(set.contains(parent)){
return parent;
}
parent = map.get(parent);
}
return null;
}
public void solve(HashMap<TreeNode,TreeNode> map,TreeNode node){
if(node==null) return;
if(node.left!=null){
map.put(node.left,node);
}
if(node.right!=null){
map.put(node.right,node);
}
solve(map,node.left);
solve(map,node.right);
}
}
第七周算法题
1、162. 寻找峰值 https://leetcode-cn.com/problems/find-peak-element/
class Solution {
fun findPeakElement(nums: IntArray): Int {
return search(0, nums.size - 1, nums)
}
fun search(l: Int, r: Int, nums: IntArray): Int {
if (l == r) {
return l
}
val mid = (r + l) / 2
if (nums[mid] > nums[mid + 1]) {
return search(l, mid, nums)
} else {
return search(mid + 1, r, nums)
}
}
}
2、153. 寻找旋转排序数组中的最小值https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
class Solution {
fun findMin(nums: IntArray): Int {
var l = 0
var r = nums.size - 1
if (r == 0) {
return nums[r]
}
if (nums[l] < nums[r]) {
return nums[l]
}
while (l != r) {
val mid = (l + r) / 2
if (nums[l] < nums[mid]) {
l = mid
} else {
r = mid
}
}
return nums[l+1]
}
}
第六周算法题
01、42. 接雨水https://leetcode-cn.com/problems/trapping-rain-water/
class Solution {
fun trap(height: IntArray): Int {
var left = 0
var right = height.size - 1
var res = 0
var leftMax = 0
var rightMax = 0
while (left < right) {
leftMax = Math.max(leftMax, height[left])
rightMax = Math.max(rightMax, height[right])
if (height[left] < height[right]) {
res += leftMax - height[left++]
} else {
res += rightMax - height[right--]
}
}
return res
}
}
02、面试题 03.06. 动物收容所 https://leetcode-cn.com/problems/animal-shelter-lcci/
class AnimalShelf() {
var queueCat = LinkedList<IntArray>()
var queueDog = LinkedList<IntArray>()
fun enqueue(animal: IntArray) {
if (animal[1] == 0) {
queueCat.addLast(animal)
} else {
queueDog.addLast(animal)
}
}
fun dequeueAny(): IntArray {
if (queueCat.isNotEmpty() && queueDog.isNotEmpty()) {
if (queueCat.first[0] <= queueDog.first[0]) {
return queueCat.removeFirst()
} else {
return queueDog.removeFirst()
}
}
if (queueCat.isNotEmpty()) {
return queueCat.removeFirst()
}
if (queueDog.isNotEmpty()) {
return queueDog.removeFirst()
}
return intArrayOf(-1, -1)
}
fun dequeueDog(): IntArray {
if (queueDog.isNotEmpty()) {
return queueDog.removeFirst()
}
return intArrayOf(-1, -1)
}
fun dequeueCat(): IntArray {
if (queueCat.isNotEmpty()) {
return queueCat.removeFirst()
}
return intArrayOf(-1, -1)
}
}
第五周算法题
01、面试题 08.06. 汉诺塔问题https://leetcode-cn.com/problems/hanota-lcci/ 递归
class Solution {
fun hanota(A: MutableList<Int>, B: MutableList<Int>, C: MutableList<Int>): Unit {
move(A.size, A, B, C)
}
fun move(num: Int, a: MutableList<Int>, b: MutableList<Int>, c: MutableList<Int>) {
if (num == 1) {
c.add(a.removeAt(a.size - 1))
return
}
move(num - 1, a, c, b)
c.add(a.removeAt(a.size - 1))
move(num - 1, b, a, c)
}
}
02、148. 排序链表https://leetcode-cn.com/problems/sort-list/ 排序
class Solution {
fun sortList(head: ListNode?): ListNode? {
if (head == null) {
return null
}
var length = 0
var node = head
while (node != null) {
length++
node = node.next
}
val preNode = ListNode().apply { next = head }
var subLength = 1
while (subLength < length) {
var pre: ListNode? = preNode
var cur = preNode.next
while (cur != null) {
var head1 = cur
var i = 1
while (i < subLength && cur?.next != null) {
cur = cur.next
i++
}
var head2 = cur?.next
cur?.next = null
cur = head2
i = 1
while (i < subLength && cur?.next != null) {
cur = cur.next
i++
}
var next: ListNode? = null
if (cur != null) {
next = cur.next
cur.next = null
}
val merge = merge2List(head1, head2)
pre?.next = merge
while (pre?.next != null) {
pre = pre.next
}
cur = next
}
subLength = subLength shl 1
}
return preNode.next
}
fun merge2List(l1: ListNode?, l2: ListNode?): ListNode? {
var ll1: ListNode? = l1
var ll2: ListNode? = l2
var head = ListNode()
var sort: ListNode? = head
while (ll1 != null && ll2 != null) {
if (ll1.`val` > ll2.`val`) {
sort?.next = ll2
ll2 = ll2.next
} else {
sort?.next = ll1
ll1 = ll1.next
}
sort = sort?.next
}
if (ll1 == null) sort?.next = ll2
if (ll2 == null) sort?.next = ll1
return head.next
}
}
第四周算法题
1、剑指 Offer 59 - II. 队列的最大值https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
class MaxQueue() {
var maxQueue = PriorityQueue<Int>(Comparator<Int> { o1, o2 ->
o1 - o2
})
var queue = LinkedList<Int>()
fun max_value(): Int {
return maxQueue.peek() ?: -1
}
fun push_back(value: Int) {
queue.add(value)
maxQueue.offer(value)
}
fun pop_front(): Int {
if (queue.size == 0) {
return -1
}
val value = queue.pop() ?: return -1
maxQueue.remove(value)
return value
}
}
2、剑指 Offer 59 - I. 滑动窗口的最大值https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
class Solution {
fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
if(nums.size==0){
return IntArray(0)
}
val ans = IntArray(nums.size - k + 1)
for (i in (k - 1) until nums.size) {
var max = Int.MIN_VALUE
for (j in 0 until k) {
max = Math.max(max, nums[i - j])
}
ans[i - (k - 1)] = max
}
return ans
}
}
第一周算法题
1、面试题 01.03. URL化：https://leetcode-cn.com/problems/string-to-url-lcci/
class Solution {
fun replaceSpaces(S: String, length: Int): String {
val array = S.toCharArray()
var i = S.length - 1
var j = length - 1
while (j >= 0) {
val tmp = array[j--]
if (tmp == ' ') {
array[i--] = '0'
array[i--] = '2'
array[i--] = '%'
} else {
array[i--] = tmp
}
}
return String(array).substring(i+1)
}
}
2、1528. 重新排列字符串：https://leetcode-cn.com/problems/shuffle-string/
class Solution {
fun restoreString(s: String, indices: IntArray): String {
val res = CharArray(s.length)
indices.forEachIndexed { index, i ->
res[i] = s[index]
}
return String(res)
}
}
第二周算法题
1、两数相加：https://leetcode-cn.com/problems/add-two-numbers/
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
var ll1 = l1
var ll2 = l2
var head: ListNode? = null
var tail: ListNode? = null
var addNum = 0
while (ll1 != null || ll2 != null) {
val tmp = (ll1?.`val` ?: 0) + (ll2?.`val` ?: 0) + addNum
addNum = tmp / 10
if (head == null) {
head = ListNode().apply {
`val` = tmp % 10
}
tail = head
} else {
val node = ListNode().apply {
`val` = tmp % 10
}
tail?.next = node
tail = node
}
ll1 = ll1?.next
ll2 = ll2?.next
}
if (addNum > 0) {
tail?.next = ListNode().apply {
`val` = addNum
}
}
return head
}
}
2、反转链表：https://leetcode-cn.com/problems/reverse-linked-list/
class Solution {
fun reverseList(head: ListNode?): ListNode? {
var cur: ListNode? = head
var pre: ListNode? = null
while (cur != null) {
val next = cur.next
cur.next = pre
pre = cur
cur = next
}
return pre
}
}
第三周算法题
1、面试题 16.26. 计算器 https://leetcode-cn.com/problems/calculator-lcci/
class Solution {
fun calculate(s: String): Int {
var i = 0
var num = 0
var numStack = LinkedList<Int>()
var symStack = LinkedList<Char>()
while (i < s.length) {
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
if (symStack.peek() == '*') {
symStack.pop()
numStack.push(numStack.pop() * num)
} else if (symStack.peek() == '/') {
symStack.pop()
numStack.push(numStack.pop() / num)
} else {
numStack.push(num)
}
num = 0
symStack.push(s[i])
} else if (s[i] == ' ') {
} else {
num = num * 10 + (s[i] - '0')
}
i++
}
if (symStack.peek() == '*') {
symStack.pop()
numStack.push(numStack.pop() * num)
} else if (symStack.peek() == '/') {
symStack.pop()
numStack.push(numStack.pop() / num)
} else {
numStack.push(num)
}
while (symStack.isNotEmpty()) {
if (symStack.pollLast() == '-') {
numStack.add(numStack.pollLast() - numStack.pollLast())
} else {
numStack.add(numStack.pollLast() + numStack.pollLast())
}
}
return numStack.pop()
}
}
2、739. 每日温度 https://leetcode-cn.com/problems/daily-temperatures/
class Solution {
fun dailyTemperatures(T: IntArray): IntArray {
out@ for (i in 0 until T.size) {
for (j in i + 1 until T.size) {
if (T[j] > T[i]) {
T[i] = j - i
continue@out
}
}
T[i] = 0
}
return T
}
}
class Solution {
fun dailyTemperatures(T: IntArray): IntArray {
val stack = Stack<Int>()
val res = IntArray(T.size)
T.forEachIndexed { index, it ->
while (stack.isNotEmpty() && T[stack.peek()] < it) {
val pre = stack.pop()
res[pre] = index - pre
}
stack.push(index)
}
return res
}
}
网友评论