剑指 Offer 50 题 Leetcode 版本（未完成）

二维数组中的查找

240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.

Integers in each column are sorted in ascending from top to bottom.

这题左上到右下就错了，主要问题在于到了边缘之后如果还找不到更大的边界，只能 i=0 回去重新遍历，复杂度和 for + break 是一样的。

优化的思路在于从左下到右上，如果 < target 就右移，如果 > target 就上移，直到找到或者越界退出。

从左上角走，往右或者往下都是递增，所以不确定往哪走，复杂度 N(nlogn)

从左下角走，往上的递减，往右是递增，越界终止，复杂度 N(m+n)

重建二叉树

105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Given preorder and inorder traversal of a tree, construct the binary tree.

You may assume that duplicates do not exist in the tree.

前序遍历的特点是 preorder[0] 就是 root，拿到这个 root 去 inorder 里寻找 root index，从而获取 left count 和 right count ，再去递归

用两个栈实现队列

232. Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.

pop() -- Removes the element from in front of queue.

peek() -- Get the front element.

empty() -- Return whether the queue is empty.

有两种方法。

第一种方法是时刻保持 s1 是满的 s2 的空的，这样 push 是 O(n)，pop 是 O(1)

第二种方法是需要 pop/peek 的时候再去 fill s2 ，这样 push 是 O(1) ，pop 是 O(1)

旋转数组的最小数字

153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

递归能做出最优解，但是性能不如 sort ，数组问题直接用 index 去 while 是效率最高的

斐波那契数列

509. Fibonacci Number

https://leetcode.com/problems/fibonacci-number/

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0,   F(1) = 1

F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

加个缓存即可，类似于 dp 问题，f(n) = f(n-1) + f(n-2)

二进制中 1 的个数

191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

比较慢的位运算，是 n&1 == 1 然后 n>>1 做计数，复杂度 O(n)

优化一下，是 n&n-1 做计数，有几个 1 就可以减几次

数值的整数次方

50. Pow(x, n)

https://leetcode.com/problems/powx-n/

Implement pow(x, n), which calculates x raised to the power n (xn).

和 for + r x 相比，可以通过 pow(x x, n//2) 来提高效率，O(n) 变 O(logn)

在 O(1) 时间删除链表节点

237. Delete Node in a Linked List

https://leetcode.com/problems/delete-node-in-a-linked-list/

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

把 next 值给自己，然后删掉 next ，在 val 上相当于删除了，内存上其实删除了 next node

链表中倒数第 k 个节点

19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/

Given a linked list, remove the n-th node from the end of list and return its head.

用一个 stack 来缓存最后 k+1 个 node，结束的时候把 q[1] 删了即可

边界情况：q length == n，意味着删的就是第一个 node，此时把 head = head.next 即可

反转链表

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

常规操作，俩指针即可

合并两个排序的链表

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/submissions/

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

先丢数组里，在初始化成链表比较简单

树的子结构

572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

主要问题在于 isEqual !+ isSubtree，容易导致一些边界情况的问题

二叉树的镜像

226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/

Invert a binary tree.

递归即可

顺时针打印矩阵

54. Spiral Matrix

https://leetcode.com/problems/spiral-matrix/

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

边界条件比较复杂，待二刷

包含 min 函数的栈

155. Min Stack

https://leetcode.com/problems/min-stack/

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

对应存个最小值数组做缓存即可

栈的压入弹出序列

946. Validate Stack Sequences

https://leetcode.com/problems/validate-stack-sequences/

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

当 pushed 中遇到 popped[0] 时，要记得把 i 往回拨一个，因为存在 push pop pop 这样的操作，所以要从 i-1 开始重新遍历。遍历之后对比剩余数组是否是 reverse 即可

从上往下打印二叉树

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

逐层遍历，用一个 queue 存一下每层的 node 即可，下个迭代清空后存 children

二叉搜索树的后序遍历序列

验证二叉搜索树的前序遍历序列 - lintcode 1307 // 相似题

二叉树中和为某一值的路径

113. Path Sum II

https://leetcode.com/problems/path-sum-ii/

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

递归就完事儿了

复杂链表的复制

138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

先遍历一边做 deep copy，再遍历一遍赋值 random ，难点在于 random 如何找到对应的 node，做法待优化

二叉搜索树与双向链表

TODO - leetcode 426 | lintcode 378

字符串的排列

46. Permutations

Given a collection of distinct integers, return all possible permutations.

选出一个数然后把剩下的数组迭代即可

数组中出现次数超过一半的数字

169. Majority Element

https://leetcode.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

set 计数 c > n/2 即可

最小的 k 个数

215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

简单粗暴的排序后 q[k] 可以得到 N(nlogn) 的解，用一共 list 缓存 top k 可以得到 N(n) 的解，不过要实时对 list 做排序

连续子数组的最大和

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

经典 DP 问题：Fn = n > 0 ? n + Fn-1 : F(n-1)

从 1 到 n 整数中 1 出现的次数

233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/submissions/

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

这题感觉没啥意思，纯粹的数学问题，和编程能力没啥关系，建议死背

丑数

264. Ugly Number II

https://leetcode.com/problems/ugly-number-ii/

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

按照传统的 2x 3x 5x 的方式往后填充 ugly number，最大的问题是不知道 length 应该是多少，如果发现 nth 达不到，就需要从头重新填充。

优化的思路是：ugly number 里的每一个数，都会被 235 乘一遍，所以存一下 235 分别乘到哪里了，然后每次取 3 个算出最小值后加入 ugly number 即可。

第一个只出现一次的字符

387. First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

word count 之后找到 value 为 1 的字符即可

数组中的逆序对

逆序对 | lintcode 532

两个链表的第一个公共节点

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

双指针从 AB 出发，先到终点后换一个起点继续，重合的时候就是第一个公共节点

数字在排序数组中出现的次数

34. Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

两边都进行二分查找即可。二分查找的边界处理是个问题，提前把贴边情况处理掉可能代码还会更简洁一些。

二叉树的深度

104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

递归即可

平衡二叉树

110. Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

计算出 height 之后，递归即可

数组中只出现一次的数字

260. Single Number III

https://leetcode.com/problems/single-number-iii/

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

简单的做法是用 set 计数，存在就 remove 不存在就 add。

正确的做法是位运算，先通过异或找到 a^b ，然后通过 n&~(n-1) 找到最后一位 1 的二进制数 m，然后通过 m 把数组分组，分别做异或运算，最后剩下的 n1 n2 就是结果

和为 s 的两个数字

167. Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

和 Two Sum I 一样用 set 解比较快。由于说 sorted 所以多了一个 left right 指针的做法，本来想可以二分更快，但是似乎还是得 O(n) 遍历

翻转单词顺序

151. Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/

Given an input string, reverse the string word by word.

可能说数组操作问题，不过用 split+reverse 比较简单

左旋转字符串

189. Rotate Array

https://leetcode.com/problems/rotate-array/

Given an array, rotate the array to the right by k steps, where k is non-negative.

O(1) 的空间复杂度就需要用轮换的方式来做

不用加减乘除做加法

371. Sum of Two Integers

https://leetcode.com/problems/sum-of-two-integers/

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

递归+进位加一

把字符串转成整数

8. String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/

没啥意思的题目，就是把字符串变成数字，做好最大最小值的边界判断，空格处理，正负处理即可

树中两个节点的最低公共祖先

236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

递归，两边都有最低公共祖先的时候就是 return root 的时候