329. Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9]. Example 2:
Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
class Solution {
public int longestIncreasingPath(int[][] matrix) {
int ans = 0;
if(matrix==null||matrix.length==0){
return 0;
}
int[][] memory = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
ans = Math.max(ans, dfs(matrix, i, j, memory));
}
}
return ans;
}
private int[] dirx = {0, 0, 1, -1};
private int[] diry = {1, -1, 0, 0};
private int dfs(int[][] matrix, int x, int y, int[][] memory){
if(memory[x][y] !=0){
return memory[x][y];
}
for(int i=0;i<4;i++){
int xx = x + dirx[i];
int yy = y + diry[i];
if(xx>=0&&yy>=0&&xx<matrix.length&&yy<matrix[0].length&&matrix[xx][yy]>matrix[x][y]){
memory[x][y] = Math.max(memory[x][y], dfs(matrix, xx, yy, memory));
}
}
return ++memory[x][y];
}
}memory数组存储到当前这个点的最大递增长度，下次在执行的时候就不用重复计算了，所以用深度优先遍历的方式，找到最长的路径。
给你一个大小为n*m的矩阵，每个单元都有一个数字。现要求输出最长的数值严格上升的一条路径的长度。 从一点出发，只可上下左右地移动。
解题思路（1）: 最为常规的解法是，从每一点出发，然后向四个方向去寻找下一个可以移动的单元，即数值满足较当前单元大的条件，直到不可移动为止。这种情况下每个结点将会被多次访问，时间复杂度为O(n^2 * m^2)
解题思路（2）:
在解法1中，我们将会对一个单元进行多次搜索，而对当个单元而言。每次搜索所建立的搜索树都是相同的，而导致往后的搜索实质上是冗余的。因此考虑新开一数组memory[x][y]来记录，对坐标为(x,y)的点进行搜索，得到的最大的路径长度。该值另可解释为以(x,y)作为序列中第一个数值，可得到的最长上升序列的长度。 这种做法可保证对每个单元仅进行一次搜索，时间复杂度为O(n*m)
算法正确性:
由于从一单元可移动的下一点要严格大于当前单元，因此全局的搜索形成了一种拓扑结构，可保证最优情况下对每个单元进行一次搜索计算出全局最优值的正确性。而本题的数据时静态的，使从一点向下的搜索树恒定不变，使记忆化成为可能。 下面举一个例子以帮助理解算法:
[9,9,4]
[6,6,8]
[2,1,1]
(1,1)：无可移动结点，memory[1][1]=1
(1,2)：无可移动结点，memory[1][2]=1
(1,3): 可移动至(1,2)，(1,2)的值事先已被计算出来，因此若走(1,2)则最长路径长度为2;可移动至(2,3)，(2,3)无可移动点，f2=1，返回(1,3),因此若走(2,3)，最长路径长度为2；
(2,1): 可移动至(1,1)，(1,1)的值事先已被计算出来，因此若走(1,1)则最长路径长度为2;
(2,2): 可移动至(1,2)，(1,2)的值事先已被计算出来，因此若走(1,2)则最长路径长度为2;可移动至(2,3)，(2,3)的值事先已被计算出来，因此若走(2,3)则最长路径长度为2;
(2,3)：已被计算，最长路径长度为1;
(3,1): 可移动至(2,1)，(2,1)的值事先已被计算出来，因此若走(2,1)则最长路径长度为3;
(3,2): 可移动至(3,1)，(3,1)的值事先已被计算出来，因此若走(3,1)则最长路径长度为4; 可移动至(2,2)，(2,2)的值事先已被计算出来，因此若走(2,2)则最长路径长度为3;
(3,3): 可移动至(2,3)，(2,3)的值事先已被计算出来，因此若走(2,3)则最长路径长度为2;
Use dynamic properties and achieve flexibility of untyped languages while keeping type-safety.
The Abstract Document pattern enables handling additional, non-static properties. This pattern uses concept of traits to enable type safety and separate properties of different classes into set of interfaces.
Real world example
Consider a car that consists of multiple parts. However we don't know if the specific car really has all the parts, or just some of them. Our cars are dynamic and extremely flexible.
In plain words
Abstract Document pattern allows attaching properties to objects without them knowing about it.
Wikipedia says
An object-oriented structural design pattern for organizing objects in loosely typed key-value stores and exposing the data using typed views. The purpose of the pattern is to achieve a high degree of flexibility between components in a strongly typed language where new properties can be added to the object-tree on the fly, without losing the support of type-safety. The pattern makes use of traits to separate different properties of a class into different interfaces.
进程和线程的区别：
-
进程是系统资源分配的最小单位
-
线程是资源调度的最小单位
-
同一进程的线程共享本进程的地址空间，共享本进程的资源如内存、I/O、cpu等，但同一进程的每个线程拥有自己的栈空间；
-
进程之间则是独立的地址空间和资源。
-
同一进程的多个线程中，若一个线程死掉，则整个进程崩溃；
-
进程间执行相互独立，一个进程崩溃不影响其他进程运行。
-
进程切换比线程切换的开销大（进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据的，使用相同的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。）
包含关系：没有线程的进程可以看做是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。