EasyJsWebView 源码分析

最近在做hybrid相关的工作，项目中用到了EasyJsWebView,代码量不大，一直想分析一下它的具体实现，抽空写了这篇文章。

1.前言

原生代码＋h5页面＋甚至React Native(或其他) 的方式开发移动客户端已经成为当前的主流趋势，因此老生常谈的一个问题就是原生代码与js的交互。原生代码中执行js代码，没什么可讲的直接webView执行js代码即可，本文主要由安卓的js调用原生的方式切入，分析iOS端是如何实现类似比较方便的调用的。

2.安卓端（js -> native interface）

对安卓的开发不是很熟，只是列举一个简单的例子讲述这样一种方式。

  • native端
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void onCreate(Bundle savedInstanceState) {
    ...
    // 添加一个对象, 让JS可以访问该对象的方法, 该对象中可以调用JS中的方法
    webView.addJavascriptInterface(new Contact(), "contact");
}

private final class Contact {
    //Html调用此方法传递数据
    public void showcontacts() {
        String json = "[{\"name\":\"zxx\", \"amount\":\"9999999\", \"phone\":\"18600012345\"}]"; 
        // 调用JS中的方法
        webView.loadUrl("javascript:show('" + json + "')");
    }
}
  • h5端
1
2
3
4
5
6
7
8
9
10
11
<html>
<body onload="javascript:contact.showcontacts()">
   <table border="0" width="100%" id="personTable" cellspacing="0">
        <tr>
            <td width="30%">姓名</td>
            <td width="30%" align="center">存款</td>
            <td align="center">电话</td>
        </tr>
    </table>
</body>
</html>

当h5页面加载时，onload方法执行，对应的native端中的Contact类中的showcontacts方法被执行。因此核心思想就是通过webView将native原生的类与自定义的js对象关联，js就可以直接通过这个js对象调用它的实例方法。

3.iOS端（js -> native interface）

上述安卓的js调用native的方式是如此简单明了，不禁想如果iOS端也有如此实现的话，这样同时即保证安卓，iOS，h5的统一性也能让开发者只用关心交互的接口即可。因此便引出了EasyJSWebView的第三方的框架（基于说明2设计），下面从该框架的使用出发，分析框架的具体实现。

说明：

  • 1.iOS端虽然也可以通过JSContext注入全局的方法但是达不到与安卓端统一
  • 2.iOS端可以通过拦截h5请求的url，通过url的格式区分类或方法，但是这样不够直观，也达不到与安卓端统一

4.EasyJsWebView

4.1 EasyJsWebView使用

本文直接列举EasyJsWebView Github README例子

  • native端
1
2
3
4
5
6
7
8
9
10
11
12
13
14
@interface MyJSInterface : NSObject

- (void) test;
- (void) testWithParam: (NSString*) param;
- (void) testWithTwoParam: (NSString*) param AndParam2: (NSString*) param2;

- (NSString*) testWithRet;

@end

// 注入
MyJSInterface* interface = [MyJSInterface new];
[self.myWebView addJavascriptInterfaces:interface WithName:@"MyJSTest"];
[interface release];
  • js端
1
2
3
4
5
MyJSTest.test();
MyJSTest.testWithParam("ha:ha");
MyJSTest.testWithTwoParamAndParam2("haha1", "haha2");

var str = MyJSTest.testWithRet();

4.2 EasyJsWebView具体实现

4.2.1 EasyJsWebView初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
- (id)init{
	self = [super init];
    if (self) {
		[self initEasyJS];
    }
    return self;
}

- (void) initEasyJS{
	self.proxyDelegate = [[EasyJSWebViewProxyDelegate alloc] init];
	self.delegate = self.proxyDelegate;
}

- (void) setDelegate:(id<UIWebViewDelegate>)delegate{
	if (delegate != self.proxyDelegate){
		self.proxyDelegate.realDelegate = delegate;
	}else{
		[super setDelegate:delegate]; 
	}
}

初始化设置webView的delegate,实际的webView的回调的在EasyJSWebViewProxyDelegate中实现，因此我们主要关注EasyJSWebViewProxyDelegate中的webView的回调的实现即可。

4.2.2 EasyJSWebViewProxyDelegate webView回调实现

4.2.2.1 webViewDidStartLoad回调实现

代码片段一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
NSMutableString* injection = [[NSMutableString alloc] init];
	
//inject the javascript interface
for(id key in self.javascriptInterfaces) {
	NSObject* interface = [self.javascriptInterfaces objectForKey:key];
	
	[injection appendString:@"EasyJS.inject(\""];
	[injection appendString:key];
	[injection appendString:@"\", ["];
	
	unsigned int mc = 0;
	Class cls = object_getClass(interface);
	Method * mlist = class_copyMethodList(cls, &mc);
	for (int i = 0; i < mc; i++){
		[injection appendString:@"\""];
		[injection appendString:[NSString stringWithUTF8String:sel_getName(method_getName(mlist[i]))]];
		[injection appendString:@"\""];
		
		if (i != mc - 1){
			[injection appendString:@", "];
		}
	}
	
	free(mlist);
	
	[injection appendString:@"]);"];
	
	
	NSString* js = INJECT_JS;
	//inject the basic functions first
	[webView stringByEvaluatingJavaScriptFromString:js];
	//inject the function interface
	[webView stringByEvaluatingJavaScriptFromString:injection];
}
  • 遍历注入的接口的列表key
  • 通过key获取注入类的实例
  • 通过类的实例获取实例方法的列表
  • 依次拼接需要执行js函数的代码
  • EasyJS对象的加载，执行EasyJS.inject方法

例子：参考Demo调试结果如下

1
2
3
4
5
6
7
8
9
EasyJS.inject("MyJSTest", 
[
	"test",
	"testWithParam:", 
	"testWithTwoParam:AndParam2:", 
	"testWithFuncParam:",
	"testWithFuncParam2:", 
	"testWithRet"
]);

4.2.2.2 EasyJS对象

代码片段一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inject: function (obj, methods){
	window[obj] = {};
	var jsObj = window[obj];
	
	for (var i = 0, l = methods.length; i < l; i++){
		(function (){
			var method = methods[i];
			var jsMethod = method.replace(new RegExp(":", "g"), "");
			jsObj[jsMethod] = function (){
				return EasyJS.call(obj, method, Array.prototype.slice.call(arguments));
			};
		})();
	}
}

遍历注入的类的实例方法的列表，通过一个全局的window[obj]的字典维护对应方法的具体实现。下面我们具体看看EasyJS.call方法的实现。

代码片段二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
call: function (obj, functionName, args){
	var formattedArgs = [];
	for (var i = 0, l = args.length; i < l; i++){
		if (typeof args[i] == "function"){
			formattedArgs.push("f");
			var cbID = "__cb" + (+new Date);
			EasyJS.__callbacks[cbID] = args[i];
			formattedArgs.push(cbID);
		}else{
			formattedArgs.push("s");
			formattedArgs.push(encodeURIComponent(args[i]));
		}
	}
	
	var argStr = (formattedArgs.length > 0 ? ":" + encodeURIComponent(formattedArgs.join(":")) : "");
    alert(argStr);
	var iframe = document.createElement("IFRAME");
	iframe.setAttribute("src", "easy-js:" + obj + ":" + encodeURIComponent(functionName) + argStr);
	document.documentElement.appendChild(iframe);
	iframe.parentNode.removeChild(iframe);
	iframe = null;
	
	var ret = EasyJS.retValue;
	EasyJS.retValue = undefined;
	
	if (ret){
		return decodeURIComponent(ret);
	}
},

这段代码做了三件事：

  • 1.分别针对参数function类型与其他类型区分处理
  • 2.创建一个IFRAME标签元素,设置src
  • 3.将新建的IFRAME添加到root元素上

修改IFRAME的src默认会触发webView的回调的执行，因此便有了下面方法shouldStartLoadWithRequest的拦截。

4.2.2.3 shouldStartLoadWithRequest回调实现

代码片段一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
NSArray *components = [requestString componentsSeparatedByString:@":"];
//NSLog(@"req: %@", requestString);
	
NSString* obj = (NSString*)[components objectAtIndex:1];
NSString* method = [(NSString*)[components objectAtIndex:2]
					stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding];
	
NSObject* interface = [javascriptInterfaces objectForKey:obj];
	
// execute the interfacing method
SEL selector = NSSelectorFromString(method);
NSMethodSignature* sig = [[interface class] instanceMethodSignatureForSelector:selector];
NSInvocation* invoker = [NSInvocation invocationWithMethodSignature:sig];
invoker.selector = selector;
invoker.target = interface;
	
NSMutableArray* args = [[NSMutableArray alloc] init];
	
if ([components count] > 3){
	NSString *argsAsString = [(NSString*)[components objectAtIndex:3]
							  stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding];
	
	NSArray* formattedArgs = [argsAsString componentsSeparatedByString:@":"];
	for (int i = 0, j = 0, l = [formattedArgs count]; i < l; i+=2, j++){
		NSString* type = ((NSString*) [formattedArgs objectAtIndex:i]);
		NSString* argStr = ((NSString*) [formattedArgs objectAtIndex:i + 1]);
		
		if ([@"f" isEqualToString:type]){
			EasyJSDataFunction* func = [[EasyJSDataFunction alloc] initWithWebView:(EasyJSWebView *)webView];
			func.funcID = argStr;
			[args addObject:func];
			[invoker setArgument:&func atIndex:(j + 2)];
		}else if ([@"s" isEqualToString:type]){
			NSString* arg = [argStr stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding];
			[args addObject:arg];
			[invoker setArgument:&arg atIndex:(j + 2)];
		}
	}
}
[invoker invoke];
  • 1.拆分拦截到的requestString拆分为obj,method,formattedArgs三个部分
  • 2.获取类实例方法的签名，新建一个NSInvocation实例，指定实例与方法
  • 3.invoker设置参数，然后执行invoke，注意参数中function类型的区分，以下5中会分析回调function的处理过程。

代码片段二：

1
2
3
4
5
6
7
8
9
10
11
if ([sig methodReturnLength] > 0){
	NSString* retValue;
	[invoker getReturnValue:&retValue];
	
	if (retValue == NULL || retValue == nil){
		[webView stringByEvaluatingJavaScriptFromString:@"EasyJS.retValue=null;"];
	}else{
		retValue = (NSString *)CFBridgingRelease(CFURLCreateStringByAddingPercentEscapes(NULL,(CFStringRef) retValue, NULL, (CFStringRef)@"!*'();:@&=+$,/?%#[]", kCFStringEncodingUTF8));
		[webView stringByEvaluatingJavaScriptFromString:[@"" stringByAppendingFormat:@"EasyJS.retValue=\"%@\";", retValue]];
	}
}

获取invoker执行的结果通过webView执行js代码返回结果值。

5.EasyJSDataFunction 与 invokeCallback

以下主要分析EasyJsWebView是如何处理回调方法参数的。

代码片段一：

1
2
3
4
5
6
if (typeof args[i] == "function"){
	formattedArgs.push("f");
	var cbID = "__cb" + (+new Date);
	EasyJS.__callbacks[cbID] = args[i];
	formattedArgs.push(cbID);
}

js端call方法这样处理function参数，EasyJS对象一个全局的__callbacks字典存储方法实现对象

代码片段二：

1
2
3
4
5
6
if ([@"f" isEqualToString:type]){
	EasyJSDataFunction* func = [[EasyJSDataFunction alloc] initWithWebView:(EasyJSWebView *)webView];
	func.funcID = argStr;
	[args addObject:func];
	[invoker setArgument:&func atIndex:(j + 2)];
}

native端拦截到请求，执行方法

代码片段三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- (NSString*) executeWithParams: (NSArray*) params{
	NSMutableString* injection = [[NSMutableString alloc] init];
	
	[injection appendFormat:@"EasyJS.invokeCallback(\"%@\", %@", self.funcID, self.removeAfterExecute ? @"true" : @"false"];
	
	if (params){
		for (int i = 0, l = params.count; i < l; i++){
			NSString* arg = [params objectAtIndex:i];
			NSString* encodedArg = (NSString*) CFURLCreateStringByAddingPercentEscapes(NULL, (CFStringRef)arg, NULL, (CFStringRef) @"!*'();:@&=+$,/?%#[]", kCFStringEncodingUTF8);
			
			[injection appendFormat:@", \"%@\"", encodedArg];
		}
	}
	
	[injection appendString:@");"];
	
	if (self.webView){
		return [self.webView stringByEvaluatingJavaScriptFromString:injection];
	}else{
		return nil;
	}
}

回调方法执行，将回调方法执行参数解析封装js函数字符串，注意前两个参数第一个表示js函数的唯一ID方便js端找到该函数对象，第二个表示第一次回调完成是否移除该回调执行的函数对象的bool值，然后webView主动执行，这样就完成个整个的回调过程。

例子：Demo回调执行语句调试

1
EasyJS.invokeCallback("__cb1462414605044", true, "blabla%3A%22bla");

6.存在问题

见如下代码我们分析实现会发现jsObj全局字典方法区分的key是方法名的拼接，且去处了连接符号:,因此产生疑问这样可能还是会出现同一个key对应不同的方法。

1
2
3
4
5
6
7
(function (){
	var method = methods[i];
	var jsMethod = method.replace(new RegExp(":", "g"), "");
	jsObj[jsMethod] = function (){
		return EasyJS.call(obj, method, Array.prototype.slice.call(arguments));
	};
})();

鉴于以上的疑问我改了一下Demo工程，MyJSInterface增加一个实现的接口

1
2
3
4
- (void) testWithTwoParamAndParam2: (NSString*) param
{
    NSLog(@"testWithTwoParamAndParam2 invoked %@",param);
}

这样就会与以下方法冲突

1
2
3
- (void) testWithTwoParam: (NSString*) param AndParam2: (NSString*) param2{
	NSLog(@"test with param: %@ and param2: %@", param, param2);
}

Demo改成如下调用

1
MyJSTest.testWithTwoParamAndParam2("haha1", "haha2");

抛出异常,原因就是js方法全局字典的keytestWithTwoParamAndParam2所对应的方法被下一个方法覆盖。

1
*** WebKit discarded an uncaught exception in the webView:decidePolicyForNavigationAction:request:frame:decisionListener: delegate: <NSInvalidArgumentException> -[NSInvocation setArgument:atIndex:]: index (3) out of bounds [-1, 2]

解决：

  • 1.可以尽量避免重名问题
  • 2.也可以替换分隔符号”:”用其他特殊字符替换

本文结，本人还在不断学习积累中，如果对文章有疑问或者错误的描述欢迎提出。
或者你有hybrid iOS一块比较好的实现也欢迎分享大家一起学习，谢谢！！！

JSPatch源码解析(二)

上篇文章简单分析了修复部分的代码实现，本文直接开始由调用过程入手。

1.调用过程

1.1 JPForwardInvocation

1.1.1 入口

还是以上篇文章的handleBtn方法作为例子阐述整个的调用过程。

当点击模拟器的Push JPTableViewController按钮时，handleBtn的方法被调用，由上篇文章4.3.2中以下代码我们已经知道selector的实现实际走消息转发的流程。

1
2
IMP msgForwardIMP = _objc_msgForward;
class_replaceMethod(cls, selector, msgForwardIMP, typeDescription);

同样4.3.2中的以下代码我们知道消息转发的实现已经替换为静态方法JPForwardInvocation的具体实现，因此下面我们具体看看这里的实现。

1
2
3
4
if (class_getMethodImplementation(cls, @selector(forwardInvocation:)) != (IMP)JPForwardInvocation) {
        IMP originalForwardImp = class_replaceMethod(cls, @selector(forwardInvocation:), (IMP)JPForwardInvocation, "v@:@");
        class_addMethod(cls, @selector(ORIGforwardInvocation:), originalForwardImp, "v@:@");
    }

1.1.2 实现

代码片段一：

1
2
3
4
5
6
7
8
9
10
11
12
id slf = assignSlf;
NSMethodSignature *methodSignature = [invocation methodSignature];
NSInteger numberOfArguments = [methodSignature numberOfArguments];
    
NSString *selectorName = NSStringFromSelector(invocation.selector);
NSString *JPSelectorName = [NSString stringWithFormat:@"_JP%@", selectorName];
SEL JPSelector = NSSelectorFromString(JPSelectorName);
    
if (!class_respondsToSelector(object_getClass(slf), JPSelector)) {
    JPExcuteORIGForwardInvocation(slf, selector, invocation);
    return;
}

判断新的selector是否在该类中已经实现，否则就走原始方法的消息转发的流程。

代码片段二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
NSMutableArray *argList = [[NSMutableArray alloc] init];
if ([slf class] == slf) {
    [argList addObject:[JSValue valueWithObject:@{@"__clsName": NSStringFromClass([slf class])} inContext:_context]];
} else if ([selectorName isEqualToString:@"dealloc"]) {
    [argList addObject:[JPBoxing boxAssignObj:slf]];
    deallocFlag = YES;
} else {
    [argList addObject:[JPBoxing boxWeakObj:slf]];
}
...
if (_currInvokeSuperClsName) {
    Class cls = NSClassFromString(_currInvokeSuperClsName);
    NSString *tmpSelectorName = [[selectorName stringByReplacingOccurrencesOfString:@"_JPSUPER_" withString:@"_JP"] stringByReplacingOccurrencesOfString:@"SUPER_" withString:@"_JP"];
    if (!_JSOverideMethods[cls][tmpSelectorName]) {
        NSString *ORIGSelectorName = [selectorName stringByReplacingOccurrencesOfString:@"SUPER_" withString:@"ORIG"];
        [argList removeObjectAtIndex:0];
        id retObj = callSelector(_currInvokeSuperClsName, ORIGSelectorName, [JSValue valueWithObject:argList inContext:_context], [JSValue valueWithObject:@{@"__obj": slf, @"__realClsName": @""} inContext:_context], NO);
        id __autoreleasing ret = formatJSToOC([JSValue valueWithObject:retObj inContext:_context]);
        [invocation setReturnValue:&ret];
        return;
    }
}

把self与相应的参数都添加到一个集合中。

代码片段三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
NSArray *params = _formatOCToJSList(argList);
const char *returnType = [methodSignature methodReturnType];
...

#define JP_FWD_RET_CALL_JS \
JSValue *fun = getJSFunctionInObjectHierachy(slf, JPSelectorName); \
JSValue *jsval; \
[_JSMethodForwardCallLock lock];   \
jsval = [fun callWithArguments:params]; \
[_JSMethodForwardCallLock unlock]; \
while (![jsval isNull] && ![jsval isUndefined] && [jsval hasProperty:@"__isPerformInOC"]) { \
    NSArray *args = nil;  \
    JSValue *cb = jsval[@"cb"]; \
    if ([jsval hasProperty:@"sel"]) {   \
        id callRet = callSelector(![jsval[@"clsName"] isUndefined] ? [jsval[@"clsName"] toString] : nil, [jsval[@"sel"] toString], jsval[@"args"], ![jsval[@"obj"] isUndefined] ? jsval[@"obj"] : nil, NO);  \
        args = @[[_context[@"_formatOCToJS"] callWithArguments:callRet ? @[callRet] : _formatOCToJSList(@[_nilObj])]];  \
    }   \
    [_JSMethodForwardCallLock lock];    \
    jsval = [cb callWithArguments:args];  \
    [_JSMethodForwardCallLock unlock];  \
}

把包含self与调用的参数转换为js对象，getJSFunctionInObjectHierachy获取对应的js重写的函数，直接调用callWithArgument方法，执行函数。

以上部分我们发现handleBtn的实现部分实际上是_JPhandleBtn对应的方法的实现，调用的流程基本了解，而此时我们有疑问，Demo中handleBtn具体的替换实现(见代码)是如何执行的呢？

1
2
var tableViewCtrl = JPTableViewController.alloc().init()
self.navigationController().pushViewController_animated(tableViewCtrl, YES)

1.2 callSelector

1.2.1 入口

代码片段一：分析JSPatch.js的代码部分时我们发现会有如下一段代码,给js对象基类 Object 的 prototype 加上 c 成员，这样所有对象都可以调用到 c,为什么这么做可以查看原作者
wiki详解

1
2
3
4
Object.defineProperty(Object.prototype, "__c", {value: function(methodName) 
{
  ...
}, configurable:false, enumerable: false});

因此我们只需要关注__c方法的具体实现，分析发现它的核心实现是

1
2
3
4
return function(){
var args = Array.prototype.slice.call(arguments)
return _methodFunc(self.__obj, self.__clsName, methodName, args, self.__isSuper)
}

查看_methodFunc的代码，最终定位_OC_callI,_OC_callC两个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var _methodFunc = function(instance, clsName, methodName, args, isSuper, isPerformSelector) {
var selectorName = methodName
if (!isPerformSelector) {
  methodName = methodName.replace(/__/g, "-")
  selectorName = methodName.replace(/_/g, ":").replace(/-/g, "_")
  var marchArr = selectorName.match(/:/g)
  var numOfArgs = marchArr ? marchArr.length : 0
  if (args.length > numOfArgs) {
    selectorName += ":"
  }
}
var ret = instance ? _OC_callI(instance, selectorName, args, isSuper):
                     _OC_callC(clsName, selectorName, args)
return _formatOCToJS(ret)
}

由startEngine可知，_OC_callI,_OC_callC两个方法为注入到context的全局的方法，因此就定位到callSelector。以上分析了callSelector的入口，下面主要分析它的具体实现。

1
2
3
4
5
6
context[@"_OC_callI"] = ^id(JSValue *obj, NSString *selectorName, JSValue *arguments, BOOL isSuper) {
    return callSelector(nil, selectorName, arguments, obj, isSuper);
};
context[@"_OC_callC"] = ^id(NSString *className, NSString *selectorName, JSValue *arguments) {
    return callSelector(className, selectorName, arguments, nil, NO);
};

1.2.2 实现

代码片段一：

1
2
3
4
5
6
7
8
9
10
11
if (instance) {
        instance = formatJSToOC(instance);
        if (!instance || instance == _nilObj) return @{@"__isNil": @(YES)};
    }
    id argumentsObj = formatJSToOC(arguments);
    
    if (instance && [selectorName isEqualToString:@"toJS"]) {
        if ([instance isKindOfClass:[NSString class]] || [instance isKindOfClass:[NSDictionary class]] || [instance isKindOfClass:[NSArray class]] || [instance isKindOfClass:[NSDate class]]) {
            return _unboxOCObjectToJS(instance);
        }
    }

把js对象与参数转换为OC对象

代码片段二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if (isSuper) {
NSString *superSelectorName = [NSString stringWithFormat:@"SUPER_%@", selectorName];
SEL superSelector = NSSelectorFromString(superSelectorName);
    
Class superCls;
if (clsDeclaration.length) {
    NSDictionary *declarationDict = convertJPDeclarationString(clsDeclaration);
    NSString *defineClsName = declarationDict[@"className"];

    Class defineClass = NSClassFromString(defineClsName);
    superCls = defineClass ? [defineClass superclass] : [cls superclass];
} else {
    superCls = [cls superclass];
}
    
Method superMethod = class_getInstanceMethod(superCls, selector);
IMP superIMP = method_getImplementation(superMethod);
    
class_addMethod(cls, superSelector, superIMP, method_getTypeEncoding(superMethod));
    
NSString *JPSelectorName = [NSString stringWithFormat:@"_JP%@", selectorName];
JSValue *overideFunction = _JSOverideMethods[superCls][JPSelectorName];
if (overideFunction) {
    overrideMethod(cls, superSelectorName, overideFunction, NO, NULL);
}
    
selector = superSelector;
  }



判断是否是父类的方法，走父类的方法的实的实现

代码片段三:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
NSInvocation *invocation;
NSMethodSignature *methodSignature;
if (!_JSMethodSignatureCache) {
_JSMethodSignatureCache = [[NSMutableDictionary alloc]init];
}
if (instance) {
    ...
    invocation= [NSInvocation invocationWithMethodSignature:methodSignature];
    [invocation setTarget:cls];
}
[invocation setSelector:selector];
...
[invocation invoke]; 
...
return returnValue;

封装NSInvocation并执行,返回处理的结果

补充说明

上一篇博文中预留一个问题：4.3.1 中为什么需要加入参数个数的说明呢？
如下代码：

*typeDescStr = [@"@@:" mutableCopy];
1
for (int i = 0; i < numberOfArg; i ++) {
    [typeDescStr appendString:@"@"];
}
overrideMethod(currCls, selectorName, jsMethod, !isInstance, [typeDescStr cStringUsingEncoding:NSUTF8StringEncoding]);**

需要根据传递过来的参数的个数声称方法的签名。

JSPatch核心的代码分析的部分已经完成，可以参考我的两篇博文，
JSPatch源码学习(一)
JSPatch源码学习(二)部分细节问题未作具体的分析，例如内存，JPBoxing,JPExtension等，有兴趣可以关注我后期的该主题的博文。本人还在不断的学习积累中，有问题欢迎及时指出，谢谢！

JSPatch 源码解析(一)

1.前言

前一段时间在公司做了一个iOS热补丁的模块，就用到了JSPatch框架,期间有了解过一些关于框架的源码分析的博客：

1.JSPatch学习:JSPatch核心和实现原理分析

2.JSPatch defineProtocol部分实现详解

思考再三还是决定自己调试了解一下整体的实现机制。

2.准备工具

3.项目文件

3.1项目文件图

3.2具体文件分析

  • JPEngine.m 核心的Native端实现。
  • JSpatch.js 核心的js端实现。
  • Extensions 扩展的方法提供给js端调用，内部是OC实现。
  • Loader 一套热补丁动态更新补丁脚本的客户端实现，需要配合服务端才能实现整个更新框架。（本文不对此作多赘述）

4.调试分析

4.1调用代码

1
2
3
4
[JPEngine startEngine];
NSString *sourcePath = [[NSBundle mainBundle] pathForResource:@"demo" ofType:@"js"];
NSString *script = [NSString stringWithContentsOfFile:sourcePath encoding:NSUTF8StringEncoding error:nil];
[JPEngine evaluateScript:script];

4.2 JPEngine初始化

1
[JPEngine startEngine];

我们来看看具体的代码实现，

  • 代码片段一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
+ (void)startEngine
{
    if (![JSContext class] || _context) {
        return;
    }
    
    JSContext *context = [[JSContext alloc] init];
    
    context[@"_OC_defineClass"] = ^(NSString *classDeclaration, JSValue *instanceMethods, JSValue *classMethods) {
        return defineClass(classDeclaration, instanceMethods, classMethods);
    };

    context[@"_OC_defineProtocol"] = ^(NSString *protocolDeclaration, JSValue *instProtocol, JSValue *clsProtocol) {
        return defineProtocol(protocolDeclaration, instProtocol,clsProtocol);
    };
    
    /*.... 分块分析，暂时省略以下代码*/
}

_content 为JSContect的实例，根据苹果官方文档 :

我们知道JSContext为js的执行环境。因此例如：
context[@"_OC_defineProtocol"]=block实现这样的调用就很好的理解为为js的上下文注入了全局的_OC_defineProtocol方法，而具体的实现对应着Native端的block的实现。

  • 代码片段二：
1
2
3
4
5
6
7
8
9
NSString *path = [[NSBundle bundleForClass:[self class]] pathForResource:@"JSPatch" ofType:@"js"];
NSAssert(path, @"can't find JSPatch.js");
NSString *jsCore = [[NSString alloc] initWithData:[[NSFileManager defaultManager] contentsAtPath:path] encoding:NSUTF8StringEncoding];
    
 if ([_context respondsToSelector:@selector(evaluateScript:withSourceURL:)]) {
        [_context evaluateScript:jsCore withSourceURL:[NSURL URLWithString:@"JSPatch.js"]];
 } else {
        [_context evaluateScript:jsCore];
 }

加载核心的JSPatch.js代码完成初始化，具体js代码后续具体调用再作分析。

4.3具体修复代码

我们来看看Demo的修复代码：

1
2
3
4
5
6
defineClass('JPViewController', {
  handleBtn: function(sender) {
    var tableViewCtrl = JPTableViewController.alloc().init()
    self.navigationController().pushViewController_animated(tableViewCtrl, YES)
  }
})

调试看看执行步骤：

4.3.1 首先执行global.defineClass (js端)

1
global.defineClass = function(declaration, properties, instMethods, clsMethods)

我们断点到var ret = _OC_defineClass(declaration, newInstMethods, newClsMethods)处，查看局部变量表
会发现newInstMethods newClsMethods均被赋值，且其中每个实例或类方法的js对象被修改添加参数的个数的说明，只是好奇为什么需要加入参数个数的说明呢？？？

4.3.2 执行_OC_defineClass (js端 -> Native端)

1
2
3
context[@"_OC_defineClass"] = ^(NSString *classDeclaration, JSValue *instanceMethods, JSValue *classMethods) {
       return defineClass(classDeclaration, instanceMethods, classMethods);
   };

实际执行的是Native的 static NSDictionary *defineClass(NSString *classDeclaration, JSValue *instanceMethods, JSValue *classMethods) 方法,以下分代码片段解析。

  • 代码片段一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
NSScanner *scanner = [NSScanner scannerWithString:classDeclaration];
    
    NSString *className;
    NSString *superClassName;
    NSString *protocolNames;
    [scanner scanUpToString:@":" intoString:&className];
    if (!scanner.isAtEnd) {
        scanner.scanLocation = scanner.scanLocation + 1;
        [scanner scanUpToString:@"<" intoString:&superClassName];
        if (!scanner.isAtEnd) {
            scanner.scanLocation = scanner.scanLocation + 1;
            [scanner scanUpToString:@">" intoString:&protocolNames];
        }
    }
    
    if (!superClassName) superClassName = @"NSObject";
    className = trim(className);
    superClassName = trim(superClassName);
    
    NSArray *protocols = [protocolNames length] ? [protocolNames componentsSeparatedByString:@","] : nil;
    
    Class cls = NSClassFromString(className);
    if (!cls) {
        Class superCls = NSClassFromString(superClassName);
        if (!superCls) {
            NSCAssert(NO, @"can't find the super class %@", superClassName);
            return @{@"cls": className};
        }
        cls = objc_allocateClassPair(superCls, className.UTF8String, 0);
        objc_registerClassPair(cls);
    }

    if (protocols.count > 0) {
        for (NSString* protocolName in protocols) {
            Protocol *protocol = objc_getProtocol([trim(protocolName) cStringUsingEncoding:NSUTF8StringEncoding]);
            class_addProtocol (cls, protocol);
        }
    }

通过传递的classDeclaration解析相应的className,superClassName,protocols,

1
2
3
4
5
6
7
8
9
10
11
//1.
cls = objc_allocateClassPair(superCls, className.UTF8String, 0);
objc_registerClassPair(cls);
 
 //2.
 if (protocols.count > 0) {
        for (NSString* protocolName in protocols) {
            Protocol *protocol = objc_getProtocol([trim(protocolName) cStringUsingEncoding:NSUTF8StringEncoding]);
            class_addProtocol (cls, protocol);
        }
    }

1.运行期间创建一个新类，并完成注册. 2.遍历协议名，依此初始化并完成对类的协议的添加。

  • 代码片段二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
for (int i = 0; i < 2; i ++) {
        BOOL isInstance = i == 0;
        JSValue *jsMethods = isInstance ? instanceMethods: classMethods;
        
        Class currCls = isInstance ? cls: objc_getMetaClass(className.UTF8String);
        NSDictionary *methodDict = [jsMethods toDictionary];
        for (NSString *jsMethodName in methodDict.allKeys) {
            JSValue *jsMethodArr = [jsMethods valueForProperty:jsMethodName];
            int numberOfArg = [jsMethodArr[0] toInt32];
            NSString *selectorName = convertJPSelectorString(jsMethodName);
            
            if ([selectorName componentsSeparatedByString:@":"].count - 1 < numberOfArg) {
                selectorName = [selectorName stringByAppendingString:@":"];
            }
            
            JSValue *jsMethod = jsMethodArr[1];
            if (class_respondsToSelector(currCls, NSSelectorFromString(selectorName))) {
                overrideMethod(currCls, selectorName, jsMethod, !isInstance, NULL);
            } else {
                BOOL overrided = NO;
                for (NSString *protocolName in protocols) {
                    char *types = methodTypesInProtocol(protocolName, selectorName, isInstance, YES);
                    if (!types) types = methodTypesInProtocol(protocolName, selectorName, isInstance, NO);
                    if (types) {
                        overrideMethod(currCls, selectorName, jsMethod, !isInstance, types);
                        free(types);
                        overrided = YES;
                        break;
                    }
                }
                if (!overrided) {
                    if (![[jsMethodName substringToIndex:1] isEqualToString:@"_"]) {
                        NSMutableString *typeDescStr = [@"@@:" mutableCopy];
                        for (int i = 0; i < numberOfArg; i ++) {
                            [typeDescStr appendString:@"@"];
                        }
                        overrideMethod(currCls, selectorName, jsMethod, !isInstance, [typeDescStr cStringUsingEncoding:NSUTF8StringEncoding]);
                    }
                }
            }
        }
    }
  • 遍历传递过过来的实例方法，类方法的js实例，然后依次遍历方法字典，完成方法名js命名到native命名的转换。
  • 通过转换后的方法名，用class_respondsToSelector判断是否该类的方法列表中是否已经存在该方法的实现，存在即调用overrideMethod(currCls, selectorName, jsMethod, !isInstance, NULL);覆盖方法实现。

  • 如果类的方法列表中不存在该方法的实现，则通过实现的协议的列表查找，依次判断方法是否在协议的实现方法中,如果以上都不是说明是新添加的方法.

  • 代码片段三：

1
2
3
4
5
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"
    class_addMethod(cls, @selector(getProp:), (IMP)getPropIMP, "@@:@");
    class_addMethod(cls, @selector(setProp:forKey:), (IMP)setPropIMP, "v@:@@");
#pragma clang diagnostic pop

添加类的getProp:``setProp:forKey:的方法及实现。

  • 代码片段四：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
static void overrideMethod(Class cls, NSString *selectorName, JSValue *function, BOOL isClassMethod, const char *typeDescription)
{
    SEL selector = NSSelectorFromString(selectorName);
    
    if (!typeDescription) {
        Method method = class_getInstanceMethod(cls, selector);
        typeDescription = (char *)method_getTypeEncoding(method);
    }
    
    IMP originalImp = class_respondsToSelector(cls, selector) ? class_getMethodImplementation(cls, selector) : NULL;
    
    IMP msgForwardIMP = _objc_msgForward;
    #if !defined(__arm64__)
        if (typeDescription[0] == '{') {
            //In some cases that returns struct, we should use the '_stret' API:
            //http://sealiesoftware.com/blog/archive/2008/10/30/objc_explain_objc_msgSend_stret.html
            //NSMethodSignature knows the detail but has no API to return, we can only get the info from debugDescription.
            NSMethodSignature *methodSignature = [NSMethodSignature signatureWithObjCTypes:typeDescription];
            if ([methodSignature.debugDescription rangeOfString:@"is special struct return? YES"].location != NSNotFound) {
                msgForwardIMP = (IMP)_objc_msgForward_stret;
            }
        }
    #endif

    class_replaceMethod(cls, selector, msgForwardIMP, typeDescription);

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"
    if (class_getMethodImplementation(cls, @selector(forwardInvocation:)) != (IMP)JPForwardInvocation) {
        IMP originalForwardImp = class_replaceMethod(cls, @selector(forwardInvocation:), (IMP)JPForwardInvocation, "v@:@");
        class_addMethod(cls, @selector(ORIGforwardInvocation:), originalForwardImp, "v@:@");
    }
#pragma clang diagnostic pop

    if (class_respondsToSelector(cls, selector)) {
        NSString *originalSelectorName = [NSString stringWithFormat:@"ORIG%@", selectorName];
        SEL originalSelector = NSSelectorFromString(originalSelectorName);
        if(!class_respondsToSelector(cls, originalSelector)) {
            class_addMethod(cls, originalSelector, originalImp, typeDescription);
        }
    }
    
    NSString *JPSelectorName = [NSString stringWithFormat:@"_JP%@", selectorName];
    SEL JPSelector = NSSelectorFromString(JPSelectorName);

    _initJPOverideMethods(cls);
    _JSOverideMethods[cls][JPSelectorName] = function;
    
    class_addMethod(cls, JPSelector, msgForwardIMP, typeDescription);
}

核心的替换添加方法实现的方法：

  • 把原始的方法的实现替换为_objc_msgForward,即该方法的调用会走消息转发的路径.
  • 类的forwardInvocation:方法的实现被替换为JPForwardInvocation的实现
  • 添加的方法ORIGforwardInvocation指向原始的实现IMP.
  • 添加的方法ORIG+selector指向原始的实现的IMP.
  • 添加_JP+selector指向新的函数的实现.

上述代码只是讲解了替换添加方法的实现，而新的实现方法是一个个js的对象，如何关联到Native端的调用？后续会继续更新，分析 调用核心方法JPForwardInvocation,JPExtension等其他部分的实现，对于上述的分析有问题处欢迎及时指出，谢谢!

补充：4.3.1 中为什么需要加入参数个数的说明呢，与方法的签名有关，具体下次更新作分析！！！

LintCode Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

样例

Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] maxSquares = new int[n + 1];
        maxSquares[0] = 0;
        maxSquares[1] = 1;
        
        for(int i = 2;i <= n;i++){
            maxSquares[i] = Integer.MAX_VALUE;
            int sqrtNum = (int) Math.sqrt(i);
            if(sqrtNum * sqrtNum == i){
                maxSquares[i] = 1;
                continue;
            }
            
            for(int j = 1;j <= sqrtNum;j++){
                int minusNum = i - j * j;
                if(maxSquares[i] > maxSquares[minusNum] + 1){
                    maxSquares[i] = maxSquares[minusNum] + 1;
                }
            }
        }
        return maxSquares[n];
    }
}

LintCode 最小调整代价

给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

样例

对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> list, int target) {
		if(null == list || list.size() <= 0)
		{
			return 0;
		}
		
		int[][] minAdjustmentCosts = new int[list.size()][101];
		int result = Integer.MAX_VALUE;
		for(int i = 0;i <= 100;i ++) // 最大值100
		{
			minAdjustmentCosts[0][i] = Math.abs(i - list.get(0));
		}
		
		for(int i = 1;i < list.size();i++)
		{
			for(int j = 0;j <= 100;j++)
			{
				minAdjustmentCosts[i][j] = Integer.MAX_VALUE;
				int left = Math.max(j - target, 0);
				int right = Math.min(j + target, 100);
				int diff = Math.abs(j - list.get(i));
				for(int k = left;k <= right;k++)
				{
					minAdjustmentCosts[i][j] = Math.min(minAdjustmentCosts[i][j], minAdjustmentCosts[i - 1][k] + diff); 
				}
			}
		}
		
		for(int i = 0;i <= 100;i++)
		{
			if(minAdjustmentCosts[list.size() - 1][i] < result)
			{
				result = minAdjustmentCosts[list.size() - 1][i] ;
			}
		}
		
		return result;
	}
}

LintCode Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

样例

Given costs = [[14,2,11],[11,14,5],[14,3,10]] return 10

house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    /**
     * @param costs n x 3 cost matrix
     * @return an integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
		
		if(null == costs || costs.length <= 0)
		{
			return 0;
		}
		
		int minRedCost = costs[0][0];
		int minBlueCost = costs[0][1];
		int minGreenCost = costs[0][2];
		
		for(int i = 1;i < costs.length;i++)
		{
			int tempRedCost = minRedCost;
			int tempBlueCost = minBlueCost;
			int tempGreenCost = minGreenCost;
			minRedCost = Math.min(tempBlueCost + costs[i][0], tempGreenCost + costs[i][0]);
			minBlueCost = Math.min(tempRedCost+ costs[i][1], tempGreenCost + costs[i][1]);
			minGreenCost = Math.min(tempRedCost + costs[i][2], tempBlueCost+ costs[i][2]);
		}
		return Math.min(Math.min(minRedCost, minBlueCost), minGreenCost);
	}
}

LintCode Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

样例

Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.

Given an encoded message containing digits, determine the total number of ways to decode it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
   public int numDecodings(String s) {
		if(null == s || s.length() <= 0)
			return 0;
		
		if(s.length() == 1 && s.charAt(0) == '0')
			return 0;
		
		int[] numDecodings = new int[s.length() + 1];
		numDecodings[0] = 1;
		for(int i = 1;i <= s.length();i++)
		{
			if(s.charAt(i - 1) == '0')
			{
				if(i- 2 >= 0)
				{
					// 如果出现类似"50"这样的数字直接返回0
					if(s.charAt(i - 2) != '1' && s.charAt(i - 2) != '2')
					{
						return 0;
					}
					else
					{
						numDecodings[i] += numDecodings[i - 2];
						continue;
					}
				}
			}
			numDecodings[i] += numDecodings[i - 1];
			if(i - 2 >= 0)
			{
				if((s.charAt(i - 2) == '1') || (s.charAt(i - 2) == '2' 
						&& s.charAt(i - 1) >= '1' && s.charAt(i - 1) <= '6'))
				{
					numDecodings[i] += numDecodings[i - 2];
				}
			}
		}
		return numDecodings[s.length()];
	}
}

LintCode乘积最大子序列

找出一个序列中乘积最大的连续子序列（至少包含一个数）。

样例

比如, 序列 [2,3,-2,4] 中乘积最大的子序列为 [2,3] ，其乘积为6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
		if(null == nums || nums.length <= 0)
		{
			return 0;
		}
		
		int max = nums[0];
		int min = nums[0];
		int mostMax = max;
		
		for(int i = 1;i < nums.length;i++)
		{
			int tempMax = max;
			max = Math.max(Math.max(nums[i], tempMax * nums[i]),min * nums[i]);
			min = Math.min(Math.min(nums[i], tempMax * nums[i]),min * nums[i]);

			if(max > mostMax)
			{
				mostMax = max;
			}
		}
		return mostMax;
	}
}

LintCode 最长上升子序列

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

说明

最长上升子序列的定义：

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

样例

给出[5,4,1,2,3]，这个LIS是[1,2,3]，返回 3

给出[4,2,4,5,3,7]，这个LIS是[4,4,5,7]，返回 4

分析

第一种做法(常规做法):

时间复杂度:O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
		if(null == nums || nums.length <= 0)
			return 0;
		int[] logestSequences = new int[nums.length + 1];
		logestSequences[0] = 1;
		for(int i = 1;i < nums.length;i++)
		{
			logestSequences[i] = 1;
			for(int j = 0;j < i;j++)
			{
				if(nums[i] >= nums[j] && (logestSequences[j] + 1 > logestSequences[i])) // 核心代码
				{
					logestSequences[i] = logestSequences[j] + 1;
				}
			}
		}
		
		int longestIncreasingSubsequence = -1;
		for(int i = 0;i < nums.length;i++)
		{
			if(logestSequences[i] > longestIncreasingSubsequence)
			{
				longestIncreasingSubsequence = logestSequences[i];
			}
		}
		return longestIncreasingSubsequence;
    }
}

第二种做法(贪心策略)：

时间复杂度:O(n*lg(n))

分析：开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的’’潜力’’增大了。

举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
		if(null == nums || nums.length <= 0)
			return 0;
		if(nums.length == 1)
			return 1;
		int[] subsequenceStack = new int[nums.length + 1];
		int top = 0;
		subsequenceStack[0] = -1;
		
		for(int i = 0;i < nums.length;i++)
		{
			if(nums[i] >= subsequenceStack[top])
			{
				top++;
				subsequenceStack[top] = nums[i];
			}
			else
			{
				int low = 0;
				int high = top;
				while(low <= high)
				{
					int middle = (low + high) / 2;
					if(nums[i] < subsequenceStack[middle])
					{
						high = middle - 1;
					}
					else
					{
						low = middle + 1;
					}
				}
				subsequenceStack[low] = nums[i];
			}
		}
		return top;
    }
}

LintCode Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.

样例:

Given n=3, k=2 return 6

1
2
3
4
5
6
7
     post 1,   post 2, post 3
way1    0         0       1 
way2    0         1       0
way3    0         1       1
way4    1         0       0
way5    1         0       1
way6    1         1       0
分析：

影响第n种的颜色的是第n-1与第n-2种颜色的，因此可能性都为k-1种
因此得到如下递推式:maxWays[n] = (k - 1) * (maxWays[n - 1] + maxWays[n - 2]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    /**
     * @param n non-negative integer, n posts
     * @param k non-negative integer, k colors
     * @return an integer, the total number of ways
     */
   public int numWays(int n, int k) {
		if(n == 0 || k == 0)
			return 0;
		if(n == 1)
		    return k;
		
		int[] maxWays = new int[n + 1];
		maxWays[0] = 0;
		maxWays[1] = k;
		maxWays[2] = k * k;
		for(int i = 3;i <= n;i ++)
		{
			maxWays[i] = (k - 1) * (maxWays[i - 1] + maxWays[i - 2]);
		}
		
		return maxWays[n];
	}
}