overview
LeetCode Hot: Full Permutation, rotating image, letter ectopic word grouping, maximum subarray and, jumping game
Design mode: adapter mode, decorator mode, agent mode, command mode and observer mode
LeetCode Hot
2.21 full arrangement
Given an array nums without duplicate numbers, all possible permutations are returned. You can return answers in any order.
Example 1: Input: nums = [1,2,3] Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//Backtracking method
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// All the numbers have been filled in
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// Dynamic maintenance array
Collections.swap(output, first, i);
// Continue to fill in the next number recursively
backtrack(n, output, res, first + 1);
// Undo operation
Collections.swap(output, first, i);
}
}
}
2.22 rotating images
Given an n × The two-dimensional matrix of N represents an image. Please rotate the image 90 degrees clockwise.
You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Do not use another matrix to rotate the image.
Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output:[[7,4,1],[8,5,2],[9,6,3]]
//In situ rotation
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; ++i) {//Guaranteed even rotation (n/2) × (n/2) positions, odd rotation ((n − 1) / 2) × ((n+1)/2) positions
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j]; //You only need to use a temporary variable to store a value
matrix[i][j] = matrix[n - j - 1][i]; //deduction
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
}
2.23 grouping of letter words
Here is an array of strings. Please combine the letters and words together. You can return a list of results in any order.
An alphabetic ectopic word is a new word obtained by rearranging the letters of the source word. The letters in all the source words are usually used just once.
Example 1: input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] output: [["bat"],["nat","tan"],["ate","eat","tea"]]
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
//hashmap.getOrDefault(Object key, V defaultValue)
//Gets the value corresponding to the specified key pair. If the key cannot be found, the set default value is returned
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
2.24 maximum subarray sum
Give you an integer array nums. Please find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum.
A subarray is a contiguous part of an array.
Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: continuous subarray [4,-1,2,1] The sum of is 6.
//DP
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0,maxSum = nums[0];
for(int x : nums){
pre = Math.max(pre + x,x);
maxSum = Math.max(pre,maxSum);
}
return maxSum;
}
}
2.25 jumping game
Given a nonnegative integer array nums, you are initially at the first subscript of the array.
Each element in the array represents the maximum length you can jump at that position.
Judge whether you can reach the last subscript.
Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: you can skip 1 step first, from subscript 0 to subscript 1, Then jump 3 steps from subscript 1 to the last subscript. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: in any case, you will always reach the position with subscript 3. However, the maximum jump length of this subscript is 0, so it is never possible to reach the last subscript.
//Greedy Algorithm
class Solution {
public boolean canJump(int[] nums) {
int max = nums[0],len = nums.length;
for(int i = 0;i < len;i++){
if(max >= i){
max = Math.max(max,i + nums[i]);
if(max >= len - 1)
return true;
}
}
return false;
}
}
Design mode
Structural mode
Adapter mode
Definition: the adapter pattern transforms the interface of a class into another interface expected by the client, so that two classes that cannot work together due to interface mismatch can work together.
Usage scenario:
- When we need to use an existing class, but the interface it provides is incompatible with the interface of our system, and we can't modify it
- When multiple teams independently develop the functional modules of the system and then combine them, but the interface cannot be determined in advance for some reasons.
Role:
-
Target role: This is the expected interface. Note: since the class adapter pattern is discussed here, the target cannot be a class.
-
Source (Adapee) role: now you need to adapt the interface.
-
Adapter role: the adapter class is the core of this pattern. The adapter converts the source interface into the target interface. Obviously, this role cannot be an interface, but must be a concrete class.
realization:
When the log system needs to use a third-party log interface, the interface is incompatible.
1. Determine the target interface
The original log interface of the system is as follows
public interface LogFactory {
void debug(String tag,String message);
}
2. Third party library interface and Implementation
public interface NewLogger {
void debug(int priority, String message, Object ... obj);
}
//Provide the implementation class of log function
public class NewLoggerImp implements NewLogger {
@Override
public void debug(int priority, String message, Object... obj) {
//...
}
}
3. Build adapter class
This class is the core of the adapter pattern. Through this class, the interface provided by the third-party library can be transformed into the target interface of the system
public class LogAdapter implements LogFactory {
private NewLogger newLogger;
public LogAdapter(NewLogger newLogger) {
this.newLogger = newLogger;
}
@Override
public void debug(String tag, String message) {
Objects.requireNonNull(newLogger);
newLogger.debug(1, message);
}
}
4. Client use
public class AdapterClient {
public void recordLog() {
LogFactory logFactory = new LogAdapter(new NewLoggerImp());
logFactory.debug("xxx");
}
}
Use of Android: ListView Adapter
By adding an Adapter layer to abstract the operation of Item View, ListView and other collection views obtain the number of items, data elements and Item views through the Adapter object, so as to achieve the effect of adapting various data and various Item views. Because Item View and data types are ever-changing, Android architects give these changed parts to users to deal with. They abstract them through getCount, getItem, getView and other methods, that is, they give the construction process of ItemView to users to deal with. They flexibly use the Adapter mode to achieve the purpose of unlimited adaptation and embracing change.
Decorator mode
Definition: Decoration mode is to dynamically extend the function of an object without changing the original class and using inheritance. It wraps the real object by creating a wrapper object, that is, decoration.
Usage scenario:
-
When you need to dynamically add additional responsibilities to an object at runtime
-
When you need to add responsibilities to an existing class, but you don't want to implement it through inheritance, or it's unrealistic to do so through inheritance.
realization:
There is an original coffee class. The current demand is to dynamically add some additional functions to some instances of this class. Here is to dynamically add new processes to some coffee making processes, such as adding milk and sugar, while some coffee remains the original flavor.
This demand is not easy to achieve through inheritance, because the coffee making process is dynamic. For example, some need plain coffee, some need milk coffee, some need sugar coffee, some need milk before sugar coffee, and some need sugar before milk coffee... This is a permutation and combination problem. If it is implemented by class inheritance, all possible combinations must be figured out in advance, and then the corresponding subclasses must be generated. With the increase of coffee taste and the change of addition order, it is almost non extensible and maintainable.
Step 1: first declare the interface of an original object
public interface ICoffee {
void makeCoffee();
}
Step 2: build our original object, here is the original coffee object, which implements the ICoffee interface.
public class OriginalCoffee implements ICoffee {
@Override
public void makeCoffee() {
System.out.print("Plain coffee ");
}
}
Step 3: build the decorator abstract base class, which implements the same interface ICoffee as the original object, and holds a reference of ICoffee type inside to receive the decorated object
public abstract class CoffeeDecorator implements ICoffee {
private ICoffee coffee;
public CoffeeDecorator(ICoffee coffee){
this.coffee=coffee;
}
@Override
public void makeCoffee() {
coffee.makeCoffee();
}
}
Step 4: build various decorator classes, which inherit to the decorator base class CoffeeDecorator. Two are generated here, one is the decorator with milk and the other is the decorator with sugar.
public class MilkDecorator extends CoffeeDecorator {
public MilkDecorator(ICoffee coffee) {
super(coffee);
}
@Override
public void makeCoffee() {
super.makeCoffee();
addMilk();
}
private void addMilk(){
System.out.print("Add milk ");
}
}
public class SugarDecorator extends CoffeeDecorator {
public SugarDecorator(ICoffee coffee) {
super(coffee);
}
@Override
public void makeCoffee() {
super.makeCoffee();
addSugar();
}
private void addSugar(){
System.out.print("Add sugar");
}
}
Step 5: client use
public static void main(String[] args) {
//Plain coffee
ICoffee coffee=new OriginalCoffee();
coffee.makeCoffee();
System.out.println("");
//Coffee with milk
coffee=new MilkDecorator(coffee);
coffee.makeCoffee();
System.out.println("");
//Coffee with milk before sugar
coffee=new SugarDecorator(coffee);
coffee.makeCoffee();
}
Use in Java: Design of Java I/O standard library
proxy pattern
Definition: provide a proxy for an object, and the proxy object controls the reference to the original object. Proxy mode is called proxy or Surrogate in English. It is an object structure mode.
Role:
-
Subject: abstract theme role
-
Proxy: proxy subject role
-
RealSubject: real theme role
realization:
Abstract object role
public abstract class AbstractObject {
//operation
public abstract void operation();
}
Target object role
public class RealObject extends AbstractObject {
@Override
public void operation() {
//Some operations
System.out.println("Some operations");
}
}
Proxy object role
public class ProxyObject extends AbstractObject{
RealObject realObject = new RealObject();
@Override
public void operation() {
//You can do related operations before calling the target object
System.out.println("before");
realObject.operation();
//After calling the target object, you can do related operations
System.out.println("after");
}
}
client
public class Client {
public static void main(String[] args) {
AbstractObject obj = new ProxyObject();
obj.operation();
}
}
Use in Android: Binder
Binder is a very typical Proxy mode. It is a remote Proxy. In fact, Proxy proxy Proxy is a Stub object in another process. The internal function is to mark the interface function to the corresponding ID, and then according to this ID to identify which function is currently invoked. The DESCRIPTOR is used as a Token to separate different interface calls. In addition, the function parameters and the return value of the accepted function are written through Parcel (the Stub end corresponds to the accepted parameters and the write result).
The Proxy class receives an ibinder parameter, which is actually the result of repackaging the Binder object returned by the onBind method in the server Service on the client. Because the client cannot directly communicate with the server through the packaged Binder, the client must communicate with the server through the Proxy class. Here, the role of Proxy is the role of Proxy, All requests of the client are represented by Proxy. The specific workflow is as follows: after receiving the request from the client, the Proxy will package the request parameters of the client into the Parcel object, and then transfer the Parcel object to the server through its internal ibinder object. After receiving the data and executing the method, the server will return the result to the Proxy of the client, The Proxy parses the data and returns it to the real caller of the client. Obviously, the above analysis is a typical agent model.
Behavioral model
Command mode
Definition: encapsulate a request into an object, so that users can parameterize the client with different requests; Queue or log requests, and support revocable operations.
Command mode is the encapsulation of commands. Command mode separates the responsibility of issuing commands from the responsibility of executing commands and delegates them to different objects.
Each command is an operation: the requesting party sends a request to perform an operation; The receiving party receives the request and performs the operation. The command mode allows the requesting party and the receiving party to be independent, so that the requesting party does not have to know the interface of the receiving party, let alone how the request is received, whether, when and how the operation is executed.
Usage scenario:
- When various actions need to be abstracted, different parameters are used to determine which object to execute
- When an operation or some operations need to support Undo
- When it is necessary to log the operation process so that the operation process can be repeated later through the log
- When an operation needs to support transaction operations
Role:
-
Client role: create requester, receiver and command object, and execute specific logic.
-
Command role: declares an abstract interface to all concrete command classes.
-
Concrete command role: define a weak coupling between receiver and behavior; Implement the execute() method, which is responsible for calling the corresponding operation of the receiver. The execute() method is often called the execute method.
-
Invoker role: it is responsible for calling the command object to execute the request. The related method is called action method.
-
Receiver role: responsible for implementing and executing a request. Any class can become a receiver. The method of implementing and executing the request is called action method.
realization:
Receiver role class
public class Receiver {
/**
* Actually execute the corresponding operation of the command
*/
public void action(){
System.out.println("Perform operations");
}
}
Abstract command role class
public interface Command {
/**
* Execution method
*/
void execute();
}
Specific command role class
public class ConcreteCommand implements Command {
//Holding the corresponding receiver object
private Receiver receiver = null;
public ConcreteCommand(Receiver receiver){
this.receiver = receiver;
}
@Override
public void execute() {
//Usually, the corresponding method of the receiver object will be transferred, so that the receiver can really perform the function
receiver.action();
}
}
Requester role class
public class Invoker {
/*
Hold command object
*/
private Command command = null;
public Invoker(Command command){
this.command = command;
}
/*
* Action method
*/
public void action(){
command.execute();
}
}
Client role class
public class Client {
public static void main(String[] args) {
//Create recipient
Receiver receiver = new Receiver();
//Create a command object and set its receiver
Command command = new ConcreteCommand(receiver);
//Create the requester and set the command object in
Invoker invoker = new Invoker(command);
//Execution method
invoker.action();
}
}
Observer mode
Definition: observer mode defines a one to many dependency, which allows multiple observer objects to listen to a topic object at the same time. When the subject object changes in state, it will notify all observer objects so that they can update themselves automatically.
Usage scenario: when the state of an object (target object) changes, all dependent objects (observer object) will be notified and broadcast.
- An abstract model has two aspects, one of which depends on the other. These aspects are encapsulated in independent objects so that they can be changed and reused independently.
- The change of one object will lead to the change of one or more other objects, and the coupling between objects can be reduced by not knowing how many objects will change.
- An object must notify other objects without knowing who they are.
- You need to create A trigger chain in the system. The behavior of object A will affect object B, and the behavior of object B will affect object C.. You can use the observer mode to create A chain trigger mechanism.
realization:
Output different hexadecimal numbers
Create the Subject class.
public class Subject {
private List<Observer> observers
= new ArrayList<Observer>();
private int state;
public int getState() {
return state;
}
public void setState(int state) {
this.state = state;
notifyAllObservers();
}
public void attach(Observer observer){
observers.add(observer);
}
public void notifyAllObservers(){
for (Observer observer : observers) {
observer.update();
}
}
}
Create the Observer class.
public abstract class Observer {
protected Subject subject;
public abstract void update();
}
Create an entity Observer class.
public class BinaryObserver extends Observer{
public BinaryObserver(Subject subject){
this.subject = subject;
this.subject.attach(this);
}
@Override
public void update() {
System.out.println( "Binary String: "
+ Integer.toBinaryString( subject.getState() ) );
}
}
public class OctalObserver extends Observer{
public OctalObserver(Subject subject){
this.subject = subject;
this.subject.attach(this);
}
@Override
public void update() {
System.out.println( "Octal String: "
+ Integer.toOctalString( subject.getState() ) );
}
}
public class HexaObserver extends Observer{
public HexaObserver(Subject subject){
this.subject = subject;
this.subject.attach(this);
}
@Override
public void update() {
System.out.println( "Hex String: "
+ Integer.toHexString( subject.getState() ).toUpperCase() );
}
}
Use Subject and solid observer objects.
public class ObserverPatternDemo {
public static void main(String[] args) {
Subject subject = new Subject();
new HexaObserver(subject);
new OctalObserver(subject);
new BinaryObserver(subject);
System.out.println("First state change: 15");
subject.setState(15);
System.out.println("Second state change: 10");
subject.setState(10);
}
}
summary
1. Design patterns have basically come to an end. You can often see these design patterns in Java and Android. You can also find a familiar feeling by reading the major open source frameworks.