回溯算法

贪心算法的基础理论及实践

class Solution { // 面积 //矩形的长度:两条垂直线的距离 //矩形的宽度:两条垂直线其中较短一条的长度 public int maxArea(int[] height) { //设置两个指针 left 和 right,分别指向数组的最左端和最右端。 此时,两条垂直线的距离是最远的, in...

java.lang.Integer

Integer

缓存

先看一段代码

Integer a = 1;
Integer b = 1;
Integer c = 500;
Integer d = 500;
System.out.print(a == b);//true
System.out.print(c == d);//false

Integer a = 1;
Integer a = new Integer(1);
System.out.print(a == b);//false

Integer类型在-128—>127范围之间是被缓存了的,也就是每个对象的内存地址是相同的,赋值就直接从缓存中取,不会有新的对象产生,而大于这个范围,将会重新创建一个Integer对象,也就是new一个对象出来,当然地址就不同了,也就!=;

dp矩阵数组优化、滚动数组、线性数组

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? //输入:m = 3, n = 2 //输出:3 //解释: //从左上角开始,总共有 3 条路径可以到达右下角。 //1. 向右 -> 向下 -> 向下 ...

随机权值选择算法

按权值随机选择算法

给你一个 下标从 0 开始 的正整数数组 w ,其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ,它可以 随机地 从范围 [0, w.length - 1] 内(含 0 和 w.length - 1)选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

例如,对于 w = [1, 3],挑选下标 0 的概率为 1 / (1 + 3) = 0.25 (即,25%),而选取下标 1 的概率为 3 / (1 + 3) = 0.75(即,75%)。

输入:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出:
[null,1,1,1,1,0]
解释:
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1,返回下标 1,返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0,返回下标 0,返回该下标概率为 1/4 。

由于这是一个随机问题,允许多个答案,因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

来源:力扣(LeetCode)

离散图论2:邻接矩阵

假设节点为[a,b,c,d],在邻接矩阵中,

  • 无向图:如果v1到v2有边,则邻接矩阵M[v_1][v_2]=M[v_2][v_1]=1,否则=0.

    M[0]中的值为1的元素的个数为a(节点0)的度,M[i][0]中的值为1的元素的个数也为a(节点0)的度,因为在无向图中,邻接矩阵是以对角线对称的。

  • 有向图:M[0]中的值为1的元素的个数为a(节点0)的出度,M[i][0]中的值为1的元素的个数也为a(节点0)的入度

  • 带权图:如果v1到v2有边,则邻接矩阵M[v_1][v_2]=W_1_2, 否则为正无穷

优点:

  • 快速判断两顶点是否有边
  • 方便计算各顶点的度

缺点

离散图论3:边集数组

如果要对边进行排序,或按边的权重进行排序,推荐使用边集数组

java.lang.String

String

String类表示字符串。 Java 程序中的所有字符串文字,例如”abc” ,都是作为此类的实例实现的。
字符串是常量; 它们的值在创建后无法更改。 字符串缓冲区支持可变字符串。 因为 String 对象是不可变的,所以它们可以共享。 例如:

String str = "abc";

相当于:

char data[] = {'a', 'b', 'c'};
String str = new String(data);

离散图论1:基础

基础理论

度:

对于无向图

  • 度指的是该节点与相邻节点的总边数

对于有向图:

01背包算法

背包问题(Knapsack problem)是一种组合优化的NP完全(NP-Complete,NPC)问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的,但是利用动态规划,我们可以以伪多项式时间复杂度求解背包问题。

背包问题有以下几种分类:

  1. 01背包问题
  2. 完全背包问题
  3. 多重背包问题

01背包问题:

一共有N件物品,第i(i从1开始)件物品的重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?