1 链表反转
Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
//从后往前走
public ListNode reverseList(ListNode head) {
ListNode cur = head,pre=null;
while(head!=null){
head = head.next;
cur.next = pre;
pre = cur;
cur = head;
}
return pre;//最后cur和head都是NULL
}
}
2 链表两两反转
public ListNode swapPairs(){
ListNode h = new ListNode(0);
ListNode next = h;
for (int i = 1; i < 4; i++) {
next.next = new ListNode(i);
next = next.next;
}
head = h;
ListNode dump = new ListNode(-1);//新的头结点
dump.next = head；//新头结点指向h
ListNode f,s,p = dump;
while (head != null && head.next!=null) {
//设置交换节点
f = head;
s = head.next;
//交换节点
f.next = s.next;
s.next = f;
p.next = s;
//重置head位置和pre位置
head = f.next;
p=f;
}
print(dump);
return dump.next;
}
3 判断链表是否有环
3.1 头结点开始遍历，直到位NULL（卡时间，避免死循环）
3.2 Set存储走过的结点，判断是否有重复，复杂的O(N)
3.3 快慢指针，快走两步，慢指针走一步，O(N)
public boolean hasCycle(ListNode head) {
if(head==null || head.next == null)
return false;
ListNode s=head,f=head.next;
while(f!=null && f.next!=null){
if(s.equals(f)){
return true;
}
f = f.next.next;
s = s.next;
}
return false;
}
4 有效的括号
1 用栈存储左括号([{，Map存储括号对{},[],()
2 遍历字符串，左括号入栈，右括号的话从Map中拿到对于的左括号与栈顶值对比是否相等，相等继续遍历字符串，否则返回false
3 遍历完毕字符，最后判断栈是否为空，空即为有效括号
class Solution {
public boolean isValid(String s) {
Map<String,String> map = new HashMap<String, String>(){
{
put(")","(");
put("]","[");
put("}","{");
}
};
Stack<String> stack = new Stack<>();
for (int i=0;i<s.length();i++){
String c = s.charAt(i)+"";
if (!map.containsKey(c)){//左括号（[{,入栈
stack.push(c);
continue;
}
//右括号）]}，栈顶值是否==map.get(c)
if (map.containsKey(c) && !stack.isEmpty() && stack.pop().equals(map.get(c))){
continue;
}else {
return false;
}
}
return stack.isEmpty();
}
}
5 用栈实现队列
1 两个栈实现，一个输入栈一个输出栈
2 push操作只操作输入栈
3 pop和peek操作只操作输出栈，并且先判断输出栈是否为空，若为空，需要将输入栈的元素依次转移到输出栈
class MyQueue {
Stack<Integer> input = new Stack<>();
Stack<Integer> ouput = new Stack<>();
/**
* Initialize your data structure here.
*/
public MyQueue() {
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
input.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
trimToSize();
return ouput.pop();
}
/**
* Get the front element.
*/
public int peek() {
trimToSize();
return ouput.peek();
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
return input.isEmpty() && ouput.isEmpty();
}
private void trimToSize(){
if (!ouput.isEmpty())
return;
while (!input.isEmpty()){
ouput.push(input.pop());
}
}
}
6 用队列实现栈
重点操作Push，在push元素的时候需要将先前的元素依次出队并且再次添加到队列里头，直至刚入队的元素在队里第一位
class MyStack {
private LinkedList<Integer> queue = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
int size = queue.size();
while (size > 1) {
queue.add(queue.remove());
size--;
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
7 优先队里
小顶堆
截屏2020-07-24 上午1.29.06.png
从图中可以看出斐波拉契堆和严格的斐波拉契堆性能比较好
截屏2020-07-24 上午1.31.37.png
大顶堆
截屏2020-07-24 上午1.29.41.png
8 数据流中的第K大元素
8.1 用一个数组将前K个最大的数保存起来，每次插入判断当前数值是否大于第K大的数，如果大于，将第K大元素移除，并将当前值插入数组中,时间复杂度为NKlogK
8.2 用优先队里Priority队列存前K大的元素，元素小的数值处于堆顶，当要插入的数值大于堆顶元素时，删除堆顶元素，并将当前值入队到优先队列中，时间复杂度为N*Log(2)K
class KthLargest {
//小顶堆 pop为最小的 offer操作入队
private PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int i : nums){
add(i);
}
}
public int add(int val) {
if (priorityQueue.size()<k){//个数小于K，直接放到优先队列（小顶堆）
priorityQueue.offer(val);
}else if (priorityQueue.peek()<val){
//个数大于K，而且val大于K个最大数值中的最小数（大于第K大数），先移除堆顶元素再插入
priorityQueue.poll();
priorityQueue.offer(val);
}
return priorityQueue.peek();
}
}
9 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
1 暴力方法，有N-K+1个窗口，每次遍历查找最大值K，复杂度为 O(Nk)
2 最大堆中 heap[0] 永远是最大的元素。在大小为 k 的堆中插入一个元素消耗 log(k)时间，因此算法的时间复杂度为 O(Nlog(k))
2 双端队里，
处理前 k 个元素，初始化双向队列。
遍历整个数组。在每一步 :
清理双向队列 :
- 只保留当前滑动窗口中有的元素的索引。
- 移除比当前元素小的所有元素，它们不可能是最大的。
将当前元素添加到双向队列中。
将 deque[0] 添加到输出中。
返回输出数组。
class Solution {
private ArrayDeque<Integer> deque = new ArrayDeque<>();
private int[] nums;
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
if (length==0 || k ==0)
return new int[0];
if (k==1)
return nums;
this.nums = nums;
//记录结果数组
int[] output = new int[length-k+1];
//标记前K个值最大元素下标
int maxIndex = 0;
for (int i=0;i<k;i++){
cleanDeque(i,k);
deque.addLast(i);
if (nums[i]>nums[maxIndex])
maxIndex = i;
}
output[0] = nums[maxIndex];
for (int i=k;i<length;i++){
cleanDeque(i,k);//先清理队里里头的元素，比nums[i]小的都移除
deque.addLast(i);//插入第I个元素下标
output[i-k+1] = nums[deque.getFirst()];//记录保存最大值
}
return output;
}
//清理队列里的值k：插入值的下标 windowSize：窗口大小
private void cleanDeque(int index,int windowSize){
if (deque.isEmpty()) return;
if (index-deque.getFirst()==windowSize)//队列里有K个元素，则将第一个移除
deque.removeFirst();
while (!deque.isEmpty()&&nums[index]>nums[deque.getLast()])
//如果要插入的值nums[index]大于window里头的值，删除移动窗口里头的元素，因为有nums[index]在，index前边的元素没有出头之日
deque.removeLast();
}
}
10 有效的字母异位词
1 排序，将字符排序，然后再比较是否相等,时间复杂度为 O(nlogn)
2 hash表存储当前字母个数，key为字母的值，时间复杂度O(N)
class Solution {
public boolean isAnagram(String s, String t) {
if (s==null || t==null)
return false;
if (s.length() != t.length())
return false;
int[] rst = new int[26];
for (int i = 0; i < s.length(); i++) {
rst[s.charAt(i)-'a']++;
rst[t.charAt(i)-'a']--;
}
for (int i : rst) {
if (i == 0) {
continue;
}else {
return false;
}
}
return true;
}
}
11 1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1 暴力求解发，遍历两次数组，时间复杂度：O(n^2)
2 哈希表存储数组【值,下标】键值对，遍历数组元素，哈希表查找（target-当前元素）是否存在，存在则返回查找对象下标以及当前值下标，否则将当前值和下标存储到哈希表中
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int rst = target - nums[i];//计算hashmap的key值
if (map.containsKey(rst)) {//存在直接返回
return new int[]{map.get(rst),i};
}
map.put(nums[i],i);//存储当前值和下标到hashmap中
}
throw new IllegalArgumentException("null tow sum solution");
}
}
12 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组
1 暴力求解法，时间复杂度是 O(n3)。
2 在凑齐两人以后，他们可以找主持人登记需求的第三人，而不需要在茫茫人海中去找队友。这样，我们就把问题优化成了每个人都要找其他每个人，即时间复杂度 O(n2)
3 双指针，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N2)减少至 O(N)。为什么是 O(N)呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList();
Arrays.sort(nums);
for (int first = 0; first < nums.length - 2; first++) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int third = nums.length - 1;
int target = -nums[first];
for (int second = first + 1; second < nums.length - 1; second++) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while (second < third && nums[second] + nums[third] > target) {
--third;
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list1 = new ArrayList<>();
list1.add(nums[first]);
list1.add(nums[second]);
list1.add(nums[third]);
list.add(list1);
}
}
}
return list;
}
}
13 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 所有左子树和右子树自身必须也是二叉搜索树。
- 递归：递归函数 helper(root, lower, upper) 来递归判断root.val的值是否在（lower，upper）中，若不在则返回false；在的话递归遍历左结点helper(root.left, lower, root.val) 和右子树helper(root.right, root.val, upper)
- 中序遍历:中序遍历二叉搜索树一定是升序的，中序遍历的时候实时检查当前值是否大于前一个中序遍历到的结点的值，如果均大于说明是升序的。
递归方法
private boolean help(TreeNode node,Integer low,Integer up){
if (node==null) return true;
int val = node.val;//当前结点的值
if ((up!=null && val >= up)//当前结点的值大于最大值
|| (low!=null && val <= low)) //当前结点值小于最小值
return false;//说明不是一颗二叉搜索树
if (!help(node.left, low, val))//更新左子树值的最大值
return false;
if (!help(node.right, val, up)) {//更新右子树值的最小值
return false;
}
return true;//左子树和右子树均满足条件，是一颗二叉搜索树
}
中序遍历
if (root==null)//特殊情况
return true;
double value = -Double.MAX_VALUE;//value保存当前左子树的最大值（前一个中序遍历到的结点的值），初始化为最小值
Stack<TreeNode> stack = new Stack<>();//保存中序遍历结点
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);//当前结点不为空，将当前结点入栈
root = root.left;//继续将当前结点的左孩子入栈,中序遍历先遍历左子树
}
root = stack.pop();//*得到中序遍历的结点
if (root.val<=value) return false;//*当前结点值必须大于左子树的值
value = root.val;//更新中序遍历左子树最大值
root = root.right;//*继续判断右子树
}
return true;
简单点中序遍历
List<Integer> nodeVal = new ArrayList<>();//保存中序遍历结点的值
public boolean isValidBST(TreeNode root) {
input(root);
//中序遍历升序
for (int i = 0; i < nodeVal.size()-1; i++) {
if (nodeVal.get(i) >= nodeVal.get(i + 1)) {
return false;
}
return true;
}
private void input(TreeNode node){
if (node.left != null) {//先遍历左子树
input(node.left);
}
nodeVal.add(node.val);//当前结点
if (node.right != null) {//在遍历右子树
input(node.right);
}
}
14 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
要点：两个结点值都比根节点大，则两个结点都在右子树，继续在右子树查找
两个结点值都比跟结点小，则两个结点都在左子树，继续在左子树查找
两个结点一大一小在根节点左右两颗子树中，则当前结点就是最近公共祖先
- 递归方法
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int pVal = p.val;
int qVal = q.val;
TreeNode parent = root;
if (parent.val < pVal && parent.val < qVal) {//两个结点值都在右子树
return lowestCommonAncestor(parent.right, p, q);
}
if (parent.val > pVal && parent.val >qVal) {//两个结点值都在左子树
return lowestCommonAncestor(parent.left, p, q);
}
return parent;
}
- 迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int pval = p.val;
int qval = q.val;
TreeNode parent = root;
while (parent != null) {
int parentVal = parent.val;
if (pval < parentVal && qval < parentVal) {//两个结点值都在左子树
parent = parent.left;
continue;
}
if (pval > parentVal && qval > parentVal) {//两个结点值都在右子树
parent = parent.right;
continue;
}
return parent;
}
}
15 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
- 递归：递归遍历整棵二叉树，定义 fxf表示 xxx 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false
class Solution {
TreeNode ans = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root,p,q);
return ans;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root==null) return false;
boolean lson = dfs(root.left, p, q);//递归左子树查找p或者q的值
boolean rson = dfs(root.right, p, q);//递归右子树查找p或者q的值
//如果左右子树均包含其中一个结点，则找到公共祖先
if ((lson && rson)
//若果当前结点为其中一个值，并且左子树或者右子树包含另外一个值，则说明找到公共祖先
|| ((root.val == p.val || root.val == q.val) && (lson || rson)))
{
ans = root;
}
return root.val == p.val || root.val == q.val || lson || rson;
}
}
iShot2020-07-27上午01.54.07.png
16 Pow(x, n)
1 库函数
2 暴力求解，循环N次
3 X的N次幂转成X的N/2的平方
- 递归写法
public double myPow(double x, int n) {
int N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
private double quickMul(double x, int n) {
if (n == 0) {
return 1;
}
double half = quickMul(x, n / 2);
return n % 2 == 0 ? half * half : half * half * x;
}
- 迭代
iShot2020-07-29上午12.48.49.png
iShot2020-07-29上午12.49.04.png
iShot2020-07-29上午12.49.20.png
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
17 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
- 暴力方法，两重循环，第一层循环元素，第二层循环查找数组中元素的个数时间复杂度N的平方
- 哈希法 用Map存储key表示元素数值，value表示元素的个数
-排序 用Arrays.sort对数组排序，复杂度N*logN，取元素中间值就是所要找的值nums[nums.length/2] - 分治 如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
哈希Map
int majorityElement_2(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
//每次记录最多元素的个数和值，避免再次遍历map数组
int maxCount = 0;//记录当前最多元素的个数
int majority = 0;//记录当前最多个数的值
for (int i = 0; i < nums.length; i++) {
int count = map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1;
map.put(nums[i], count);
if (maxCount < count) {
maxCount = count;
majority = nums[i];
}
}
return majority;
}
排序
int majorityElement_1(int[] nums) {
//排序
Arrays.sort(nums);
return nums[nums.length / 2];//众超过n/2个，中间的那个数肯定是最多的
}
分治
class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int lo, int hi) {
// 只有一个元素，返回即可
if (lo == hi) {
return nums[lo];
}
// 分别查找左半部分和右半部分的最多元素
int mid = (hi-lo)/2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid+1, hi);
// 左半部分与右半部分一样，返回其中一个即可
if (left == right) {
return left;
}
// 查找元素最多的值
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
}
18 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
- 贪心算法，有股票升值的时候就买入
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
//第二天的股票比第一天的股票价值高，第一天买入，第二天卖出
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
19 广度优先遍历
用队列保存根节点元素，每次从队列里头拿第一个结点访问，并将该结点的子结点添加到队里尾部，如此循环直到队列为NULL
//广度优先搜索，队列实现
public void BFS(TreeNode root){
if (root == null) {
return;
}
ArrayDeque<TreeNode> nodeArrayDeque = new ArrayDeque<>();
nodeArrayDeque.offer(root);
while (!nodeArrayDeque.isEmpty()){
TreeNode treeNode = nodeArrayDeque.pop();
//TODO
//visitor(treeNode);
if (treeNode.left != null) {
nodeArrayDeque.offer(treeNode.left);
}
if (treeNode.right != null) {
nodeArrayDeque.offer(treeNode.right);
}
}
}
- 深度优先搜索
递归方法本身就是用栈的形式维护一个方发栈，遍历的方式的用Stack维护，访问了之后再将该结点入栈
//深度优先搜索，队列实现
public void DFS(TreeNode root) {
if (root == null) {
return;
}
//TOOD
//visit(root);
DFS(root.left);
DFS(root.right);
}
20 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
iShot2020-07-31上午12.17.00.pngiShot2020-07-31上午12.17.11.png
- 广度搜索BFS，每次搜索一层
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
Deque<TreeNode> deque = new LinkedList();
deque.add(root);//每次while循环存储下一层结点的值
while (!deque.isEmpty()) {
List<Integer> levelList = new ArrayList<>();
int size = deque.size();
for (int i = 0; i < size; i++) {//每次循环遍历一层结点
TreeNode cur = deque.pollFirst();
levelList.add(cur.val);
if (cur.left != null) {
deque.add(cur.left);//添加下一层结点的左儿子结点
}
if (cur.right != null) {
deque.add(cur.right);//添加下一层结点的右儿子结点
}
}
results.add(levelList);
}
return results;
}
- 深度优先搜索DFS，递归调用的时候传入level值，更加level值判断当前元素存储在哪一层（也就是list<list>的第一个元素）
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
_dfs(results,root,0);
return results;
}
private void _dfs(ArrayList<ArrayList<Integer>> rst, TreeNode node, int level) {
if (rst.size() - 1 < level) {
rst.add(new ArrayList<>());//添加当前层的数据结构
}
rst.get(level).add(node.val);//将当前值存储在对应层的数组中
if (node.left!=null)//遍历下一层元素
_dfs(rst,node.left,level+1);
if (node.right!=null)
_dfs(rst,node.right,level+1);
}
21 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
- 递归：分别查找左子树和右子树最大的深度加一即可
public int maxDepth(TreeNode root) {
if (root==null)//叶子节点返回0
return 0;
int leftdepth = maxDepth(root.left);//计算左子树的最大深度
int rightdepth = maxDepth(root.right);//计算右子树的最大深度
return 1 + Math.max(leftdepth, rightdepth);//左右子树最大深度+1
}
- 广度优先搜索 广度优先搜索树，直到扫描完整棵树
public int maxDepth(TreeNode root) {
if (root==null)
return 0;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
int depth = 0;
while (!list.isEmpty()){
int size = list.size();
for (int i = 0; i < size; i++) {
TreeNode cur = list.poll();
if (cur.left != null) {
list.add(cur.left);
}
if (cur.right != null) {
list.add(cur.right);
}
}
depth++;
}
return depth;
}
22 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
- 广度优先搜索树，遇到的第一个叶子节点，当前深度即为这棵树的最小深度
public int minDepth(TreeNode root) {
if (root==null)
return 0;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
int depth = 0;
while (!list.isEmpty()){
int size = list.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode cur = list.poll();
if (cur.left == null && cur.right == null) {
return depth;//广度优先搜索的第一个叶子节点就是当前树的最小深度
}
if (cur.left != null) {
list.add(cur.left);
}
if (cur.right != null) {
list.add(cur.right);
}
}
}
return depth;
}
- 深度优先搜索
对于每个节点，按照深度优先搜索的策略访问，同时在访问到叶子节点时更新最小深度。
class Solution {
public int minDepth(TreeNode root) {
LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root == null) {
return 0;
}
else {
stack.add(new Pair(root, 1));
}
int min_depth = Integer.MAX_VALUE;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pollLast();
root = current.getKey();
int current_depth = current.getValue();
if ((root.left == null) && (root.right == null)) {
min_depth = Math.min(min_depth, current_depth);
}
if (root.left != null) {
stack.add(new Pair(root.left, current_depth + 1));
}
if (root.right != null) {
stack.add(new Pair(root.right, current_depth + 1));
}
}
return min_depth;
}
- 递归
public int minDepth(TreeNode root) {
if (root==null)//节点为空返回0
return 0;
if (root.left == null && root.right == null) {
return 1;//叶子节点返回1
}
int minDepth = Integer.MAX_VALUE;
if (root.left != null) {
minDepth = minDepth(root.left);//计算左子树的最小深度
}
if (root.right != null) {
minDepth = Math.min(minDepth(root.right), minDepth);//计算右子树的最小深度并和左子树比较得到子树最小深度
}
return minDepth + 1;//左右子树的最小深度+当前节点深度1
}
23 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
- 暴力法，生成包含长度为2*n的字符组合，每个都可能为左括号或者右括号，总共有2的n次方种组合方式，然后再判断每个组合是否有效
- 递归方法，长度为2*n，只有当左括号小于n的时候可以插入左括号，当左括号大于右括号个数的时候可以插入右括号，当左括号和右括号个数都为n时即生成一组有效组合
public List<String> generateParenthesis(int n) {
List<String> results = new ArrayList<>();//存储有效组合的list
_gen(results, n,0, 0, "");
return results;
}
/**
* @param results 存储有效组合的list
* @param n n个左/右括号
* @param left 左括号使用了几个
* @param right 左括号使用了几个
* @param s 当前使用了左右括号的组合
*/
private void _gen(List<String> results,int n, int left, int right, String s) {
if (left == n && right == n) {
results.add(s);
return;
}
if (left < n) {//左括号个数小于n都可以填入左括号
_gen(results,n,left+1,right,s+"(");
}
if (left > right) {//只有当右括号个数小于左括号的时候才可以填入右括号
_gen(results,n,left,right+1,s+")");
}
}
24 N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
-
剪支发 递归每一行row，遍历每一个列是否满足条件，符合条件继续递归下一行（row+1),否则清理当前放置的Q，继续下一列的判断
iShot2020-08-04上午12.55.13.png
List<List<Integer>> results = new ArrayList<>();//记录结果的list
Set<Integer> cols = new HashSet<>();//记录放置皇后Q的列，其他列就不能放置了用于剪支
Set<Integer> pie = new HashSet<>();//记录和放置的Q处于同一对角线的元素（col+row=常亮）
Set<Integer> na = new HashSet<>();//记录和放置的Q处于同一对角线的元素（col-row=常亮）
public List<List<String>> solveNQueens(int n) {
_queen(n,0,new ArrayList<>());
return covert(n,results);
}
/**
* @param nQueen 皇后的个数
* @param rows 递归遍历到第几行
* @param state 记录0~rows皇后的位置
*/
private void _queen(int nQueen, int rows, List<Integer> state) {
if (rows == nQueen) {
//深拷贝一份出来记录，避免下一次递归修改list数组
List<Integer> list = new ArrayList<>();
list.addAll(state);
results.add(list);
return;
}
//遍历当前行的每一列是否满足条件
for (int col = 0; col < nQueen; col++) {
//剪支，不能和之前的同处于同一类，同一对角线
if (cols.contains(col) || pie.contains(col+rows) || na.contains(col-rows)){
continue;
}
//满足条件，添加限制条件，列和对角线
cols.add(col);
pie.add(col + rows);
na.add(col - rows);
state.add(col);
//继续递归下一行
_queen(nQueen, rows + 1, state);
//回退寻找更多可能的结果，移除当前Q并移除对应的限制条件
cols.remove(col);
pie.remove(col + rows);
na.remove(col - rows);
state.remove(state.size()-1);
}
}
private List<List<String>> covert(int n,List<List<Integer>> sources) {
List<List<String>> rst = new ArrayList<>();
for (int i = 0; i < sources.size();i++) {
List<String> sub = new ArrayList<>();
for (int row = 0; row < n; row++) {
sub.add(getStr(n, sources.get(i).get(row)));
}
rst.add(sub);
}
return rst;
}
private String getStr(int n, int pos) {
String rst = "";
for (int i = 0; i < n; i++) {
if (i == pos) {
rst += "Q";
}else {
rst += ".";
}
}
return rst;
}
25 解数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
- 递归+剪支 遍历整个9x9的找出没有被填入的位置，每次尝试放入一个数，判断其合法性，假如不合法继续尝试下一个数
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0) {
return;
}
_solve(board);
}
/**
* 遍历整个board，找出没有确定的值并尝试放入1-9
* @param board
* @return
*/
private boolean _solve(char[][] board) {
for (int i = 0; i < board.length; i++) {//row遍历
for (int j = 0; j < board[0].length; j++) {//col遍历
if (board[i][j] == '.') {//没有被确认的值
for (char v = '1'; v <= '9'; v++) {//尝试放入的值
if (_isValid(board, i, j, v)) {//验证该位置是否可以放入v
board[i][j] = v;//验证通过，填入该值
if (_solve(board))//递归判断其他位置是否满足条件
return true;//满足返回true
else
board[i][j] = '.';//不满足回退，继续尝试下一个值
}
}
return false;
}
}
}
return true;
}
/**
* 检查该位置是否可以放入值
* @param board 整个9x9格式
* @param row 放入值的列
* @param col 放入值的列
* @param v 尝试放入的值
* @return
*/
private boolean _isValid(char[][] board, int row, int col, char v) {
for (int i = 0; i < 9; i++) {
if (board[row][i]!='.'&&board[row][i]==v)return false;//检查行是否包含该数
if (board[i][col]!='.'&&board[i][col]==v) return false;//检查列是否包含该数
if (board[3*(row/3)+i/3][3*(col/3)+i%3]!='.'
&& board[3*(row/3)+i/3][3*(col/3)+i%3]==v)//检查3x3的格子是否包含v
return false;
}
return true;
}
26 二分查找
有序+有上下界+索引可以找到到目标值
int left=0,right = len(array)-1
while(left<right){
mid = (left+right)/2;
if(array[mid]==target)
break or return;
if(array[mid]<target)
left = mid+1;
else
right = mid-1;
}
- 应用 x 的平方根
x的平方递增函数，每次使用二分查找方法逼近目标值
/**
* 开平方，二分查找（x的平方递增）
* @param tartget
* @return
*/
public double sqrt(double tartget) {
if (tartget==0 || tartget ==1)
return tartget;
double left = 1.0,right = tartget,result=0;
while (right - left > 1e-10) {//精确值1e-10
double mid = left/2+right/2;
if (mid>tartget/mid)//避免mid的平方越界
right = mid;
else
left = mid;
}
Log.i("FKY_SQRT", Math.sqrt(tartget) + " " + left);
return left;
}
牛顿迭代法
图片.png
牛顿法的思想：
在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，
求直线与 xxx 轴的交点，重复这个过程直到收敛。
public class Solution {
public int mySqrt(int a) {
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return (int) x;
}
}
27 实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
public class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
public TrieNode(char c){
val = c;
}
}
class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode trieNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (trieNode.children[c - 'a'] == null) {
trieNode.children[c - 'a'] = new TrieNode(c);
}
trieNode = trieNode.children[c-'a'];
}
trieNode.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c-'a']==null) return false;
node = node.children[c - 'a'];
}
return node.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (node.children[c-'a']==null) return false;
node = node.children[c - 'a'];
}
return true;
}
}
28 单词搜索 II
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
iShot2020-08-05下午11.18.26.png
- 将要所搜的word放入字典树trie，遍历二维网格board，将遍历到的字符累加到一起strCur，每次累加字符的时候标记已经访问过该位置，并在字典上trie上查找strCur字符，如果不是前缀，放弃搜索，如果是，判断当前字符strCur是否为单词word，是的话添加到结果集Set中，并继续遍历当前结点上下左右结点值继续递归
public class Solution {
Set<String> res = new HashSet<>();
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();//1 将搜索words放入到字典树中
for (String word:words) {
trie.insert(word);
}
int row = board.length;
int col = board[0].length;
boolean[][] visited = new boolean[row][col];//标记已经被访问的位置结构visited
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
find(visited,board, i, j, "",trie);//遍历查找board中所有位置的字符
}
}
return new ArrayList<>(res);
}
/**
*
* @param visited 标记被访问字符二维数组，大小和board一样
* @param board 搜索的board
* @param x 当前搜索的行号
* @param y 当前搜索的列号
* @param strCur 已经搜索到的结果
* @param trie 字典树，存储了所有需要查找的字符
*/
private void find(boolean[][] visited, char[][] board, int x, int y, String strCur,Trie trie) {
if (x<0||y<0 || x>=board.length || y>=board[0].length) return;//边界判断
if (visited[x][y]) return;//当前位置是否被访问
strCur+=board[x][y];//没有被访问开始访问该位置的元素
if (!trie.startsWith(strCur))return;//字典树中查找是否是前缀，没有前缀放弃查找
if (trie.search(strCur)) {//字典树中查找是否存在strCur单词，找到了假如结果集中
res.add(strCur);
}
visited[x][y]=true;//标记该位置已经被访问
find(visited,board,x-1,y,strCur,trie);//递归当前位置左边的元素
find(visited,board,x+1,y,strCur,trie);//递归当前位置右边的元素
find(visited,board,x,y-1,strCur,trie);//递归当前位置上边的元素
find(visited,board,x,y+1,strCur,trie);//递归当前位置下边的元素
visited[x][y]=false;//移除标记，继续循环
}
}
29 位运算
iShot2020-08-05下午11.45.18.png
1、x & 1 == 1 OR ==0 判断奇数偶数(& 只有两个同时为1结果才为1)
2、x=x&(x-1)清理最低位的1 如6&5=4
6---->1 1 0
5---->1 0 1
结果为1 0 0 --> 4
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数
1 循环每次模2结果为1计数加一，并将输入数值除以2
while(target!=0){
if(target%2==1) count++;
target = target/2;
}
2 每次进行x=x&(x-1)移除最低位的1，并count++,直到为0
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
假如是2的幂次方，二进制位只有一个1
public boolean isPowerOfTwo(int x) {
//数据范围为-2147483648 ~ 2147483647[-2^31 ~ 2^31-1]
//用long存储，避免只有所有都为1的情况-2147483648，再-1越界
long n = x;
return n!=0&&((n&(n-1))==0);
}
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
1 遍历每个数分别计算1的个数
2 x&(x-1) 去除x最低位的1，可以得到关系：x二进制位1的个数等于x&(x-1)二进制位1的个数+1，而且x&(x-1)的值小于x，所有递推即可 P(x)=P(x&(x−1))+1;
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int i = 1; i <= num; ++i)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
}
}
30 N 皇后问题的二进制解法
public int totalNQueue(int n){
if (n<1) return -1;
_dfs(n,0,0,0,0);
return countNQueues;
}
private void _dfs(int n,int row,int cols,int pie,int na) {
if (row>=n){
countNQueues++;
return;
}
//如：第一行方了第3个位置
// cols 1--> 0 0 1 0
// pie 1--> 0 1 0 0
// na 1--> 0 0 0 1
//cols|pie|na --> 0 1 1 1
//~cols|pie|na --> 1 0 0 0 只有第一个位置可以放
int bits = (~(cols|pie|na))&((1<<n)-1);// 得到当前所有空位
while (bits > 0) {
//如 bits 5 0000 ... 0101
// -5 1000 ... 0101
// -5反码 1111 ... 1010（负数反码 =除去最高位之外其他位取反
// -5补码 1111 ... 1011（负数的补码=反码+1）
//计算机中负数的表示形式是以补码表示
//int a a&(-a)表示取低位1
int bit = bits & -bits;//取得到最后（低位）一个1，需要放置的位置，放置一个皇后 Q，继续递归遍历
_dfs(n, row + 1, cols | bit, (pie | bit) << 1, (na | bit) >> 1);
// bits 5 --> 0000 ... 0101
// bits 5-1 --> 0000 ... 0100
//bits&(bits-1)--> 0000 ... 0100
bits = bits & bits-1;//移除最后(低位)一个1继续遍历其他可能情况
}
}
31 动态规划
理解:递归+记忆化------>递推
状态定义：op[n],dp[n],fib[n]
状态转移方程：op[n]=best_of(opt[n-1],opt[n-2],...)
最优子结构
DP VS 回溯 VS 贪心
回溯（递归）--》重复计算
贪心-----------》永远局部最优
DP------------》记录局部最优子结构/多种记录值
- 斐波拉契
iShot2020-08-07上午12.27.33.png
iShot2020-08-07上午12.28.39.png
public int fblq(int n){
int[] F = new int[n+1];
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++) {
F[i] = F[i-1] + F[i-2];
}
return F[n];
}
33 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
- 动态规划解法 定义f(k)表示爬到第k阶楼梯有f(k)种不同方法，每次可以爬1或者2个台阶，所以爬到k阶台阶的走法=爬到k-1阶台阶的总数(再爬一步)+爬到k-2阶楼梯台阶总数(再爬两步)，即f(n)=f(n-1)+f(n-2)
class Solution {
public int climbStairs(int n) {
if(n<=1) return 1;
int rst[] = new int[n+1];
rst[0] = 1;
rst[1] = 1;
for(int i=2;i<=n;i++){
rst[i]=rst[i-1]+rst[i-2];
}
return rst[n];
}
}
34 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
- 递归方法 深度优先搜索方法dfs(triangle,i,j)表示结点trangle[i][j]最小路径和，则
dfs(triangle,i,j)=min(dfs(triangle,i+1,j),dfs(triangle,i+1,j+1))+triangle[i][j]
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
return dfs(triangle, 0, 0);
}
private int dfs(List<List<Integer>> triangle, int i, int j) {
if (i == triangle.size()) {
return 0;
}
return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
}
}
- 35 动态规划+空间优化 定义DP状态方程DP(i,j)表示从底部走到i,j结点最小和，DP状态转移方程DP(i,j)=min(DP(i+1,j),DP(i+1,j+1))+triangle[i][j],由于每次只需要保存上一层DP状态即可，所以只用以为数组保存DP结果即可
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n + 1];//存储i+1行DP状态值
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
//dp[i,j]=min(dp[i+1,j],dp[i+1][j+1])+triangle[i,j]
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
35 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
- 因为有负数，所以需要记录最大最小值两个元素
DP状态定义：dp[k][0|1] 选取表示第k个数字最大值和最小值
DP状态转移：
当nums[i]大于0时->
最大值DP[i][0]=DP[i-1][0]nums[i];
最小值DP[i][1]=DP[i][1]nums[i];
当nums[i]小于0时->
最大值DP[i][0]=DP[i-1][1]nums[i];
最小值DP[i][1]=DP[i][0]nums[i];
class Solution {
/**
* dp[k][2] 表示选择第k个数的最大值和最小值，因为要有负数，所以需要保存两个追
* @param nums
* @return
*/
public int maxProduct(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
//定义dp状态，dp[][0] 最大值
//定义dp状态，dp[][1] 最小值
int[][] dp = new int[nums.length][2];
int rst = nums[0];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > 0) {
//第k个数值大于0
//最大值为num[i]*dp[i-1][0]
dp[i][0] = dp[i-1][0]*nums[i];
dp[i][0] = Math.max(dp[i][0],nums[i]);//取nums[i]本身和dp[i][0]最大值
//最小值为num[i]*dp[i-1][1]
dp[i][1] = dp[i-1][1]*nums[i];
dp[i][1] = Math.min(dp[i][1],nums[i]);
} else {
//第k个数值小于0
//最大值为num[i]*dp[i-1][1]
dp[i][0] = dp[i-1][1]*nums[i];
dp[i][0] = Math.max(dp[i][0],nums[i]);//取nums[i]本身和dp[i][0]最大值
//最小值为num[i]*dp[i-1][0]
dp[i][1] = dp[i-1][0]*nums[i];
dp[i][1] = Math.min(dp[i][1],nums[i]);
}
rst = Math.max(rst, dp[i][0]);
}
return rst;
}
}
36 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
- 动态规划
public int lengthOfLIS(int[] nums) {
if (nums.length==0) return 0;
//状态定义:dp[k]表示选取nums[k]时最长子序列
int[] dp = new int[nums.length];
dp[0] = 1;
int lis = 1;//记录最长子序列长度
for (int i = 1; i < nums.length; i++) {
int maxi = 1;//记录包含nums[i]时最长子序列长度
for (int j = 0; j < i - 1; j++) {
//只有当nums[i]>nums[j]时候才是递增
if (nums[i] > nums[j] && dp[j]+1 > maxi) {
maxi = dp[j] + 1;
}
}
dp[i] = maxi;
if (lis < maxi) {
lis = maxi;
}
}
return lis;
}
- 另一种思路
/**
* 10 11 12 13 14 1 2 3 4 5 6
* --> 10 0 0 0 ...
* --> 10 11 0 0 ...
* ...
* -->10 11 12 13 14 0 0 0 ...
* -->1 11 12 13 14 0 0 ... 替换第一个比 1 大的数
* -->1 2 12 13 14 0 0 ... 替换第一个比 2 大的数
* -->1 2 3 13 14 0 0 ...
* -->1 2 3 4 14 0 0 ...
* -->1 2 3 4 5 0 0 0 ...
* -->1 2 3 4 5 6 ....
* @param nums
* @return
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;//记录最长子序列长度
for (int k = 0; k < nums.length; k++) {
int left = 0;
int right = len;
print(dp);
while (left < right) {//二分查找找到第一个比nums[k]大的数
int mid = (left + right) / 2;
if (dp[mid] < nums[k]) {
left = mid + 1;
} else {
right = mid;
}
}
dp[left] = nums[k];//替换或者插入nums[k]到递增队列
if (right==len)
len++;
}
print(dp);
return len;
}
37 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1.
原理：与爬楼梯原理一样，爬到第k阶楼梯方法dp[k]总数=爬到k-coins[0...n]中方法，取最小值值即可
/**
* 与爬楼梯一样
* coins = [1, 2, 5], amount = 11
* 暴力法：最多可以去2个5元，5个2元，11个一元
* 递归调用（或者循环）选2个5元，0个2元，1个一元，成功，
* 假如不成功则继续选1一个五元，剩余4，选3个2元，成功，如果不成功继续递归
* @param coins
* @param amount
* @return
*/
public int coinChange(int[] coins, int amount) {
//DP状态定义：dp[k]表示爬到k阶楼梯最小值步数（在这里表示数值amount最小的组合方式）
int[] dp = new int[amount+1];
for (int i = 0; i < amount+1; i++) {
dp[i] = amount+1;//初始化，方便取最小值
}
dp[0] = 0;//0元没有方案
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j]<=i) {//保证数组不越界
//取最小值 DP状态转移方程
//dp[11] = min{dp[11-1],dp[11-2],dp[11-5]}+1
dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
38 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
题目给定了两个单词，设为 A 和 B，这样我们就能够六种操作方法。
注意：如果我们有单词 A 和单词 B：
对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为 dog 时，
我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，
得到相同的doge；
同理，对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的；
对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，
我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。
这样以来，本质不同的操作实际上只有三种：
在单词 A 中插入一个字符；
在单词 B 中插入一个字符；
修改单词 A 的一个字符。
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if (n * m==0) {
return n+m;
}
//DP状态定义：DP[i][j]表示word1前i个字符和word2前j个字符匹配需要操作的最少步数
int[][] DP = new int[m + 1][n + 1];
//初始化边缘值：表示word1前i个字符匹配word2前0个字符，删除word1前i个字符即可
for (int i = 0; i < m + 1; i++) {
DP[i][0] = i;
}
//初始化边缘值：表示word1前0个字符匹配word2前i个字符，插入word2前i个字符即可
for (int i = 0; i < n + 1; i++) {
DP[0][i] = i;
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {//当两个字符相等，躺赢，不要操作步数
DP[i][j] = DP[i - 1][j - 1];
} else {//不相等：可以有3中操作，对word1进行删除，插入，替换
//DP[i][j]=DP[i-1][j]+1:表示删除word1第i个字符删除，
// 即word1[i]!=word2[j],删除word[i]字符，等效于求解DP[i-1][j]+1(删除word1第i个字符操作)
//DP[i][j]=DP[i][j-1]+1:word1删除第1个字符等效于word2插入一个字符
//DP[i][j]=DP[i-1][j-1]+1:表示将word1第i个字符替换成word2第j个字符
DP[i][j] = Math.min(DP[i-1][j-1],Math.min(DP[i-1][j],DP[i][j-1]))+1;
}
}
}
return DP[m][n];
}
39 岛屿数量
给你一个由
'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
- 暴力染色法思路：遍历二维网格，当发现陆地‘1’的时候岛屿数+1，并递归上下左右结点，将为陆地结点染色为水‘0’。
int numIslands = 0;
int row;
int col;
public int numIslands(char[][] grid) {
if (grid.length==0 || grid[0].length==0) {
return 0;
}
row = grid.length;
col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
numIslands++;
ranse(grid,i,j);
}
}
}
return numIslands;
}
private void ranse(char[][] grid,int i,int j){
if (i < row && j < col && j >= 0 && i >= 0 && grid[i][j]=='1') {
grid[i][j] = '0';//开始染色
}else {
return;//数组越界或者为水'0'退出递推
}
//递归遍历上下左右结点
ranse(grid,i,j+1);
ranse(grid,i,j-1);
ranse(grid,i+1,j);
ranse(grid,i-1,j);
}
- 查并集
class UnionFind {
int[] roots;//查并集
int[] ranks;//查并集的层次（树的深度）
int count;
public UnionFind(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
roots = new int[row * col];
ranks = new int[row * col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
roots[i*col+j] = i*col+j;//初始化查并集，各自为营（自己指向自己）
ranks[i*col+j] = 0;//初始化层次为0
count++;
}
}
}
}
/**
* 递归查找自己的老大（老大的特点自己指向自己）
* @param i
* @return
*/
public int find(int i) {
if (roots[i] != i) {
return find(roots[i]);
}else {
return roots[i];
}
}
/**
* 合并结点p和q（p的老大是q老大的parent或者q的老大是p老大的parent）
* @param p
* @param q
*/
public void union(int p, int q) {
//查找各自的老大parent
int rootP = find(p);
int rootq = find(q);
if (rootP == rootq) {
return;
}
//根据深度来决定谁来做老大
if (ranks[rootP] < ranks[rootq]) {
roots[rootP] = rootq;
} else if (ranks[rootP] > ranks[rootq]) {
roots[rootq] = rootP;
} else {
roots[rootP] = rootq;
ranks[rootq]++;
}
--count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int row= grid.length;
int col = grid[0].length;
UnionFind unionFind = new UnionFind(grid);
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
//将上下左右的结点指向自己，作为一个岛屿
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
unionFind.union(i*col+j,(i-1)*col+j);
}
if (i + 1 < row && grid[i + 1][j] == '1') {
unionFind.union(i*col+j,(i+1)*col+j);
}
if (j + 1 < col && grid[i][j + 1] == '1') {
unionFind.union(i * col + j, i* col + j+1);
}
if (j - 1 >=0 && grid[i][j - 1] == '1') {
unionFind.union(i * col + j, i* col + j-1);
}
}
}
}
return unionFind.count;
}
40 LRU&LFU算法
LRU Least Resently Used
LFU Least Frequrently Used
-LRU Cache将最近使用的放到链表前段，由于空间有限，假如队列已满，将队尾元素移除，数据结构使用双向链表实现
iShot2020-08-16上午12.06.43.png
iShot2020-08-16上午12.07.24.png
-
LFU Cache 将访问频次最多的元素放到队列头部，假如队列满了，访问的元素没有空间存储，将队尾元素移除，将要访问的元素放到队列里(放置到哪里按照频次优先次序排列)
iShot2020-08-16上午12.07.51.png
41 布隆过滤器 Bloom Filter
一个很长的二进制向量和一个映射函数
布隆过滤器可以用于检索一个元素是否存在一个集合中
优点：空间效率和查询时间远远超过一般的算法
缺点：有一定的误识别率（存在的时候可能误识别，不存在的时候是100%准确）和删除困难
iShot2020-08-16下午11.47.39.png
iShot2020-08-16下午11.51.04.png
- 附带自定义LRU Cache
public class LRUCache {
class DLinkedNode {
int key;//hashcode
int value;//值
DLinkedNode prev;//前序结点
DLinkedNode next;//后续结点
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();//key对应的Node结点映射
private int size;//当前cache元素的个数
private int capacity;//容量
private DLinkedNode head, tail;//链表的头结点和尾结点
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
