【Android春招每日一练】（二十七） LeetCode Hot 5题+Android框架

文章目录

概览LeetCode Hot

2.41 二叉树的最大深度2.42 从前序与中序遍历序列构造二叉树2.43 二叉树展开为链表2.44 买卖股票的最佳时机2.45 二叉树中的最大路径和 Android框架

Retrofit解析总结

概览

LeetCode Hot：二叉树的最大深度、从前序与中序遍历序列构造二叉树、二叉树展开为链表、买卖股票的最佳时机、二叉树中的最大路径和
Android框架：Retrofit解析

LeetCode Hot 2.41 二叉树的最大深度

给定一个二叉树，找出其最大深度。

//DFS
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

2.42 从前序与中序遍历序列构造二叉树

同剑指offer第5题

2.43 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

    1
   / 
  2   5
 /    
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     
      2         5
     /          
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     
      2          
     /           
    3   4  
         
          5
           
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     
      2          
                 
        3       4  
                 
                  5
                   
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     
      2          
                 
        3      
         
          4  
           
            5
             
              6         
  
  ......

class Solution {
    public void flatten(TreeNode root) {
        while(root != null){
            //左子树为空，直接考虑右子树
            if(root.left == null) root = root.right;
            else{
                //找左子树最右边叶子节点
                TreeNode tmp = root.left;
                while(tmp.right != null){
                    tmp = tmp.right;
                }
                //将原来的右子树插入左子树最右边节点
                tmp.right = root.right;
                //将左子树插到原来右子树地方
                root.right = root.left;
                root.left = null;   //记得置null
                //考虑下一个节点
                root = root.right;
            }
        }
    }
}

2.44 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

//使用一个值记录当前最小值，每天和最小值计算利润，保存最大的利润，最后返回
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE,maxProfit = 0;
        for(int x:prices){
            if(minPrice > x) minPrice = x;
            if((x - minPrice) > maxProfit) maxProfit = x - minPrice;
        }
        return maxProfit;
    }
}

2.45 二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        } 
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);	//始终维护这个全局变量

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);	//二叉树中，从根出发，只能选择走右边还是左边
    }
}

Android框架 Retrofit解析

Retrofit 是 Square 推出的 HTTP 框架，主要用于 Android 和 Java。Retrofit 将网络请求变成方法的调用，使用起来非常简洁方便。

App应用程序通过Retrofit请求网络，实际上是使用Retrofit接口层封装请求参数，之后由OkHttp完成后续的请求操作。在服务端返回数据之后，OkHttp将原始的结果交给Retrofit，Retrofit根据用户的需求对结果进行解析。完成数据的转化(converterFactory)，适配(callAdapterFactory)，通过设计模式进行各种扩展。

基本用法：

public interface GitHubService {
  @GET("users/{user}/repos")
  Call> listRepos(@Path("user") String user);
}

在 GithubService 接口中有一个方法 listRepos，这个方法用了 @GET 的方式注解，这表明这是一个 GET 请求。在后面的括号中的 users/{user}/repos 是请求的路径，其中的 {user} 表示的是这一部分是动态变化的，它的值由方法的参数传递过来，而这个方法的参数@Path("user") String user 即是用于替换 {user} 。另外注意这个方法的返回值是 Call>。可以看出 Retrofit 用注解的方式来描述一个网络请求相关的参数。

发出这个网络请求：

Retrofit retrofit = new Retrofit.Builder()
.baseUrl("https://api.github.com/")
.addConverterFactory(GsonConverterFactory.create())
.build();

GitHubService service = retrofit.create(GitHubService.class);
Call> repos = service.listRepos("octocat");
repos.enqueue(new Callback>() {
    @Override
    public void onResponse(Call> call, Response> response) {
            
    }
    @Override
    public void onFailure(Call> call, Throwable t) {

    }
 });

先是构建了一个 Retrofit 对象，其中传入了 baseUrl 参数，baseUrl 和上面的 GET 方法后面的路径组合起来才是一个完整的 url。除了 baseUrl，还有一个 converterFactory，它是用于把返回的 http response 转换成 Java 对象，对应方法的返回值 Call> 中的 List>，其中 Repo 是自定义的类。有了Retrofit 对象，接着调用它的 create 方法创建了 GitHubService 的实例，然后就可以调用这个实例的方法来请求网络了。调用 listRepo 方法得到一个 Call对象，然后可以使用 enqueue 或者 execute 来执行发起请求，enqueue 是异步执行，而 execute 是同步执行。

源码分析：

Retrofit 的创建

从 Retrofit 的创建方法可以看出，使用的是 Builder 模式。Retrofit 中有如下的几个关键变量：

  //用于缓存解析出来的方法
  private final Map serviceMethodCache = new linkedHashMap<>();
  
  //请求网络的OKHttp的工厂，默认是 OkHttpClient
  private final okhttp3.Call.Factory callFactory;
  
  //baseurl
  private final HttpUrl baseUrl;
  
  //请求网络得到的response的转换器的集合 默认会加入 BuiltInConverters     
  private final List converterFactories;
  
  //把Call对象转换成其它类型
  private final List adapterFactories;
  
  //用于执行回调 Android中默认是 MainThreadExecutor
  private final Executor callbackExecutor;
  
  //是否需要立即解析接口中的方法
  private final boolean validateEagerly;

再看一下Retrofit 中的内部类 Builder 的 build 方法：

public Retrofit build() {
  if (baseUrl == null) {
    throw new IllegalStateException("base URL required.");
  }

  okhttp3.Call.Factory callFactory = this.callFactory;
  if (callFactory == null) {
    //默认创建一个 OkHttpClient
    callFactory = new OkHttpClient();
  }

  Executor callbackExecutor = this.callbackExecutor;
  if (callbackExecutor == null) {
     //Android 中返回的是 MainThreadExecutor
    callbackExecutor = platform.defaultCallbackExecutor();
  }

  // Make a defensive copy of the adapters and add the default Call adapter.
  List adapterFactories = new ArrayList<>(this.adapterFactories);
  adapterFactories.add(platform.defaultCallAdapterFactory(callbackExecutor));

  // Make a defensive copy of the converters.
  List converterFactories = new ArrayList<>(this.converterFactories);

  return new Retrofit(callFactory, baseUrl, converterFactories, adapterFactories,
      callbackExecutor, validateEagerly);
}

在创建 Retrofit 的时候，如果没有指定 OkHttpClient，会创建一个默认的。如果没有指定 callbackExecutor，会返回平台默认的，在 Android 中是 MainThreadExecutor，并利用这个构建一个 CallAdapter加入 adapterFactories。

create 方法

有了 Retrofit 对象后，便可以通过 create 方法创建网络请求接口类的实例，代码如下：

public  T create(final Class service) {
Utils.validateServiceInterface(service);
if (validateEagerly) {
  //提前解析方法
  eagerlyValidateMethods(service);
}
return (T) Proxy.newProxyInstance(service.getClassLoader(), new Class[] { service },
    new InvocationHandler() {
      private final Platform platform = Platform.get();

      @Override public Object invoke(Object proxy, Method method, Object... args)
          throws Throwable {
        // If the method is a method from Object then defer to normal invocation.如果是Object中的方法，直接调用
        if (method.getDeclaringClass() == Object.class) {
          return method.invoke(this, args);
        }
        //为了兼容 Java8 平台，Android 中不会执行
        if (platform.isDefaultMethod(method)) {
          return platform.invokeDefaultMethod(method, service, proxy, args);
        }
        //下面是重点，解析方法
        ServiceMethod serviceMethod = loadServiceMethod(method);
        OkHttpCall okHttpCall = new OkHttpCall<>(serviceMethod, args);
        return serviceMethod.callAdapter.adapt(okHttpCall);
      }
});

reate 方法接受一个 Class 对象，也就是我们编写的接口，里面含有通过注解标识的请求网络的方法。注意 return 语句部分，这里调用了 Proxy.newProxyInstance 方法，这个很重要，因为用了动态代理模式。

简单的描述就是，Proxy.newProxyInstance 根据传进来的 Class 对象生成了一个实例 A，也就是代理类。每当这个代理类 A 执行某个方法时，总是会调用 InvocationHandler(Proxy.newProxyInstance 中的第三个参数) 的 invoke 方法，在这个方法中可以执行一些操作(这里是解析方法的注解参数等)，通过这个方法真正的执行我们编写的接口中的网络请求。

方法解析和类型转换

下面具体看一下在 invoke 中解析网络请求方法的几行。首先是 ServiceMethod serviceMethod = loadServiceMethod(method);，其中 loadServiceMethod 代码如下：

ServiceMethod loadServiceMethod(Method method) {
    ServiceMethod result;
    synchronized (serviceMethodCache) {
      result = serviceMethodCache.get(method);
      if (result == null) {
        result = new ServiceMethod.Builder(this, method).build();
        serviceMethodCache.put(method, result);
      }
    }
    return result;
}

这里是先到缓存中找，缓存中没有再去创建。这里创建了 ServiceMethod 对象。ServiceMethod 用于把接口方法的调用转换成一个 HTTP 请求。其实，在 ServiceMethod 中会解析接口中方法的注解、参数等，它还有个 toRequest 方法，用于生成一个 Request 对象。这个 Request 对象就是 OkHttp 中的 Request，代表了一条网络请求(Retrofit 实际上把真正请求网络的操作交给了 OkHttp 执行)。下面是创建 ServiceMethod 的部分代码：

public ServiceMethod build() {
  //获取 callAdapter
  callAdapter = createCallAdapter();
  responseType = callAdapter.responseType();
  if (responseType == Response.class || responseType == okhttp3.Response.class) {
    throw methodError("'"
        + Utils.getRawType(responseType).getName()
        + "' is not a valid response body type. Did you mean ResponseBody?");
  }
  //获取 responseConverter 
  responseConverter = createResponseConverter();

  for (Annotation annotation : methodAnnotations) {
    //解析注解
    parseMethodAnnotation(annotation);
    //省略了一些代码
    ...
  }
}

在得到 ServiceMethod 对象后，把它连同方法调用的相关参数传给了 OkHttpCall 对象，也就是这行代码： OkHttpCall okHttpCall = new OkHttpCall<>(serviceMethod, args);。

下面介绍 OkHttpCall，OkHttpCall继承于 Call 接口。Call 是Retrofit 的基础接口，代表发送网络请求与响应调用，OkHttpCall 是 Call 的一个实现类，它里面封装了 OkHttp 中的原生 Call，在这个类里面实现了 execute 以及 enqueue 等方法，其实是调用了 OkHttp 中原生 Call 的对应方法。

接下来把 OkHttpCall 传给 serviceMethod.callAdapter 对象，这里的callAdapter又是什么？在上面创建 ServiceMethod 的代码中有一行代码： callAdapter = createCallAdapter()，这里创建了 calladapter，在这个代码内部是根据方法的返回类型以及注解去寻找对应的 CallAdapter，去哪里寻找？去 Retrofit 对象的 adapterFactories 集合中找。当我们创建 Retrofit 的时候，可以调用 addCallAdapter 向 adapterFactories 中添加 CallAdapter。在前面的基本用法里面，我们并没有添加任何 CallAdapter，但 adapterFactories 中默认会添加一个 ExecutorCallAdapterFactory，调用其 get 方法便可获得 CallAdapter 对象。

那么 CallAdapter 是干嘛的呢？上面调用了adapt 方法，它是为了把一个 Call 转换成另一种类型，比如当 Retrofit 和 RxJava 结合使用的时候，接口中方法可以返回 Observable，这里相当于适配器模式。默认情况下得到的是一个 Call 对象，它是ExecutorCallbackCall，代码如下：

public CallAdapter> get(Type returnType, Annotation[] annotations, Retrofit retrofit) {
if (getRawType(returnType) != Call.class) {
  return null;
}
final Type responseType = Utils.getCallResponseType(returnType);
return new CallAdapter>() {
  @Override public Type responseType() {
    return responseType;
  }

  @Override public  Call adapt(Call call) {
    return new ExecutorCallbackCall<>(callbackExecutor, call);
  }
};

个 ExecutorCallbackCall 接受一个 callbackExecutor(Android 中默认为 MainThreadExecutor，把返回的数据传回主线程) 和一个 call，也就是 OkhttpCall。看下 ExecutorCallbackCall 部分代码：

static final class ExecutorCallbackCall implements Call {
final Executor callbackExecutor;
final Call delegate;

ExecutorCallbackCall(Executor callbackExecutor, Call delegate) {
  this.callbackExecutor = callbackExecutor;
  this.delegate = delegate;
}

@Override public void enqueue(final Callback callback) {
  if (callback == null) throw new NullPointerException("callback == null");

  delegate.enqueue(new Callback() {
    @Override public void onResponse(Call call, final Response response) {
      callbackExecutor.execute(new Runnable() {
        @Override public void run() {
          if (delegate.isCanceled()) {
            // Emulate OkHttp's behavior of throwing/delivering an IOException on cancellation.
            callback.onFailure(ExecutorCallbackCall.this, new IOException("Canceled"));
          } else {
            callback.onResponse(ExecutorCallbackCall.this, response);
          }
        }
      });
    }

    @Override public void onFailure(Call call, final Throwable t) {
      callbackExecutor.execute(new Runnable() {
        @Override public void run() {
          callback.onFailure(ExecutorCallbackCall.this, t);
        }
      });
    }
  });
}

在 enqueue 方法中，调用了 OkHttpCall 的 enqueue，所以这里相当于静态的代理模式。OkHttpCall 中的 enqueue 其实又调用了原生的 OkHttp 中的 enqueue，这里才真正发出了网络请求，部分代码如下:

@Override public void enqueue(final Callback callback) {
    if (callback == null) throw new NullPointerException("callback == null");
    //真正请求网络的 call
    okhttp3.Call call;
    Throwable failure;

    synchronized (this) {
      if (executed) throw new IllegalStateException("Already executed.");
      executed = true;
      //省略了部分发代码
      ...
      call = rawCall;
      //enqueue 异步执行
    call.enqueue(new okhttp3.Callback() {
      @Override public void onResponse(okhttp3.Call call, okhttp3.Response rawResponse)
          throws IOException {
        Response response;
        try {
        //解析数据 会用到 conveterFactory，把 response 转换为对应 Java 类型
          response = parseResponse(rawResponse);
        } catch (Throwable e) {
          callFailure(e);
          return;
        }
        callSuccess(response);
      }

      @Override public void onFailure(okhttp3.Call call, IOException e) {
        try {
          callback.onFailure(OkHttpCall.this, e);
        } catch (Throwable t) {
          t.printStackTrace();
        }
      }

  private void callFailure(Throwable e) {
    try {
      callback.onFailure(OkHttpCall.this, e);
    } catch (Throwable t) {
      t.printStackTrace();
    }
  }

  private void callSuccess(Response response) {
    try {
      callback.onResponse(OkHttpCall.this, response);
    } catch (Throwable t) {
      t.printStackTrace();
    }
  }
 });
}

OkHttp 获取数据后，解析数据并回调 callback 响应的方法，一次网络请求便完成了。

总结:

Retrofit 整个框架的代码不算太多，还是比较易读的。主要就是通过动态代理的方式把 Java 接口中的解析为响应的网络请求，然后交给 OkHttp 去执行。并且可以适配不同的 CallAdapter，可以方便地与 RxJava 结合使用。
@然则
博文地址：https://segmentfault.com/a/1190000012656606

总结

1.最后Retrofit分析完，Android框架源码也暂且告一段落，至此总体知识已经初步整理学习完；
2.最后时间我选择先复习理解巩固前面所有整理的知识，然后再看面经查漏补缺，先把基础打牢。

【Android春招每日一练】（二十七） LeetCode Hot 5题+Android框架

Java相关栏目本月热门文章