FragmentTransaction的commit的异步操作

FragmentTransaction是异步的,commit()仅是相当于把操作加入到FragmentManager的队列,然后FragmentManager会在某一个时刻来执行,并不是立即执行。所以,真正开始执行commit()时,如果Activity的生命周期发生了变化,比如走到了onPause,或者走到了onStop,或者onDestroy都走完了,那么就会报出IllegalStateException。

这个地方确实是很坑的,我在做一个功能,需要从FragmentA跳转到FragmentB,然后调用FragmentB的刷新方法,那我的思路是从FragmentA和B的MainActivity中将A隐藏,将B显示,然后调用刷新。
于是我先将A隐藏B显示

private void switchFragment(Fragment newFragment) {

        FragmentManager fm = getSupportFragmentManager();
        FragmentTransaction transaction = fm.beginTransaction();

        LogCat.i("newFragment isAdded=" + newFragment.isAdded());
        if (newFragment.isAdded()) {
            transaction.hide(mCurrentFragment).show(newFragment).commitAllowingStateLoss();
        } else {
            transaction.hide(mCurrentFragment).add(R.id.main_content, newFragment).commitAllowingStateLoss();
        }
        mCurrentFragment = newFragment;
    }

然后,再switchFragment之后调用FragmentB的刷新功能,但是问题出现了,发现FragmentB里面的一些空间没有初始化,打了log之后发现,初始化在我的初始化在我的刷新功能后面执行,查了资料发现,FragmentTransaction的commit方法是异步的,难怪~

解决方法:executePendingTransactions

这里写图片描述

在用FragmentTransaction.commit()方法提交FragmentTransaction对象后,会在进程的主线程中,用异步的方式来执行。如果想要立即执行这个等待中的操作,就要调用这个方法(只能在主线程中调用)。要注意的是,所有的回调和相关的行为都会在这个调用中被执行完成,因此要仔细确认这个方法的调用位置。

于是我重写switchFragment方法

FragmentManager fm = getSupportFragmentManager();
        FragmentTransaction transaction = fm.beginTransaction();

        if (fragment.isAdded()) {
            transaction.hide(mCurrentFragment).show(fragment).commitAllowingStateLoss();
        } else {
            transaction.hide(mCurrentFragment).add(R.id.main_content, fragment).commitAllowingStateLoss();
        }
        mCurrentFragment = fragment;


        fm.executePendingTransactions();

        ((DiscoverFragment) fragment).refresh(searchWord);

多加了一句fm.executePendingTransactions();
就OK了

遇到的问题,特此记录

Activity启动流程–Activity启动的概要流程

概述

Android中启动某个Activity,将先启动Activity所在的应用。应用启动时会启动一个以应用包名为进程名的进程,该进程有一个主线程,叫ActivityThread,也叫做UI线程。

本系列博客将详细阐述Activity的启动流程,这些博客基于Cm 10.1源码研究。

  • 深入理解Activity启动流程(二)–Activity启动相关类的类图
  • 深入理解Activity启动流程(三)–Activity启动的详细流程1
  • 深入理解Activity启动流程(三)–Activity启动的详细流程2
  • 深入理解Activity启动流程(四)–Activity Task的调度算法

Activity启动时的概要交互流程

用户从Launcher程序点击应用图标可启动应用的入口Activity,Activity启动时需要多个进程之间的交互,Android系统中有一个zygote进程专用于孵化Android框架层和应用层程序的进程。还有一个system_server进程,该进程里运行了很多binder service,例如ActivityManagerService,PackageManagerService,WindowManagerService,这些binder service分别运行在不同的线程中,其中ActivityManagerService负责管理Activity栈,应用进程,task。

Activity启动时的概要交互流程如下图如下所示(点击图片可看大图):

activity_start_flow

用户在Launcher程序里点击应用图标时,会通知ActivityManagerService启动应用的入口Activity,ActivityManagerService发现这个应用还未启动,则会通知Zygote进程孵化出应用进程,然后在这个dalvik应用进程里执行ActivityThread的main方法。应用进程接下来通知ActivityManagerService应用进程已启动,ActivityManagerService保存应用进程的一个代理对象,这样ActivityManagerService可以通过这个代理对象控制应用进程,然后ActivityManagerService通知应用进程创建入口Activity的实例,并执行它的生命周期方法。

后续博客将介绍Activity的详细启动流程。

Activity启动流程–Activity启动相关类的类图

在介绍Activity的详细启动流程之前,先为大家介绍Activity启动时涉及到的类,这样大家可以有大概的了解,不至于在细节中迷失。

  • 深入理解Activity启动流程(一)–Activity启动的概要流程
  • 深入理解Activity启动流程(三)–Activity启动的详细流程1
  • 深入理解Activity启动流程(三)–Activity启动的详细流程2
  • 深入理解Activity启动流程(四)–Activity Task的调度算法

Activity启动时涉及到的类有IActivityManager相关类, IApplicationThread相关类, ActivityManagerService相关类。

IActivityManager相关类

点击图片可看大图

IActivityManager

Activity的管理采用binder机制,管理Activity的接口是IActivityManager. ActivityManagerService实现了Activity管理功能,位于system_server进程,ActivityManagerProxy对象是ActivityManagerService在普通应用进程的一个代理对象,应用进程通过ActivityManagerProxy对象调用ActivityManagerService提供的功能。应用进程并不会直接创建ActivityManagerProxy对象,而是通过调用ActiviyManagerNative类的工具方法getDefault方法得到ActivityManagerProxy对象。所以在应用进程里通常这样启动Activty:

1
ActivityManagerNative.getDefault().startActivity()

IApplicationThread相关类

点击图片可看大图

IApplicationThread

应用进程需要调用ActivityManagerService提供的功能,而ActivityManagerService也需要主动调用应用进程以控制应用进程并完成指定操作。这样ActivityManagerService也需要应用进程的一个Binder代理对象,而这个代理对象就是ApplicationThreadProxy对象。

ActivityManagerService通过IApplicationThread接口管理应用进程,ApplicationThread类实现了IApplicationThread接口,实现了管理应用的操作,ApplicationThread对象运行在应用进程里。ApplicationThreadProxy对象是ApplicationThread对象在ActivityManagerService线程 (ActivityManagerService线程运行在system_server进程)内的代理对象,ActivityManagerService通过ApplicationThreadProxy对象调用ApplicationThread提供的功能,比如让应用进程启动某个Activity。

ActivityManagerService相关类

点击图片可看大图

ActivityManagerService

ActivityManagerService管理Activity时,主要涉及以下几个类:

  • 1)\tActivityManagerService,它是管理activity的入口类,聚合了ProcessRecord对象和ActivityStack对象
  • 2)\tProcessRecord,表示应用进程记录,每个应用进程都有对应的ProcessRecord对象
  • 3)\tActivityStack,该类主要管理回退栈
  • 4)\tActivityRecord,每次启动一个Actvity会有一个对应的ActivityRecord对象,表示Activity的一个记录
  • 5)\tActivityInfo,Activity的信息,比如启动模式,taskAffinity,flag信息(这些信息在AndroidManifest.xml里声明Activity时填写)
  • 6)\tTaskRecord,Task记录信息,一个Task可能有多个ActivityRecord,但是一个ActivityRecord只能属于一个TaskRecord

注意:

ActivityManagerService里只有一个ActivityStack对象,并不会像Android官方文档描述的一样,每个Task都有一个activity stack对象。ActivityStack管理ActivityRecord时,不是下面这样组织ActivityRecord的:

1
2
List<TaskRecord> taskList; //ActivityStack类
List<ActivityRecord> recordList;// TaskRecord类

而是像下面这样组织ActivityRecord:

1
2
ArrayList<ActivityRecord> mHistory = new ArrayList<ActivityRecord>(); //ActivityStack类里
TaskRecord task; // ActivityRecord类里

也就是说ActivityManagerService组织回退栈时以ActivityRecord为基本单位,所有的ActivityRecord放在同一个ArrayList里,可以将mHistory看作一个栈对象,索引0所指的对象位于栈底,索引mHistory.size()-1所指的对象位于栈顶。

但是ActivityManagerService调度ActivityRecord时以task为基本单位,每个ActivityRecord对象都属于某个TaskRecord,一个TaskRecord可能有多个ActivityRecord。

ActivityStack没有TaskRecord列表的入口,只有在ActivityManagerService才有TaskRecord列表的入口:

1
final ArrayList<TaskRecord> mRecentTasks

ActivityStack管理ActivityRecord时,将属于同一个task的ActivityRecord放在一起,如下所示:

backstack

回退栈里可看到两个task,假设上面的task为task1,下面的task为task2,task1包含D,E两个Activity Record,task2包含3个ActivityRecord。task1位于回退栈的栈顶,task2位于task1下面,task1中E位于栈顶,task2中C位于栈顶。需注意两个task的Activity不会混在一起,也就是说task2的B不能放在task1的D和E中间。

因为回退栈是栈结构,所以此时不断按返回键,显示的Activity的顺序为E–>D–>C–>B–>A。

下一篇博客为大家讲述Activity的详细启动流程。

IOS逆向分析—终*详细(一)

文章目录
前言
一、逆向分析是什么?
二、越狱
1.所有方法
2.尝试的方法
3.成功的方法
三、mac终端连接iPhone
总结
前言
本文是个人完成对IOS上APP分析的整个过程,当然对于不同的机型还会遇到不同的情况,谨以此文供大家参考,如有错误,望大佬们多多指教
一、逆向分析是什么?
逆向工程(又称反向工程),是一种技术过程,即对一项目标产品进行逆向分析及研究,从而演绎并得出该产品的处理流程、组织结构、功能性能规格等设计要素,以制作出功能相近,但又不完全一样的产品。逆向工程源于商业及军事领域中的硬件分析。 上面是正儿八经的介绍。我做这个就是为了工作需要,要分析其它的视频类APP,所以就开始了苦逼的折腾iPhone的过程。
二、越狱
1.所有方法
我知道的方法大致分为以下两种

在windows下使用爱思助手一键越狱(目前我就找到这个软件可以一键越狱);对于安卓手机的话,PP助手也可以,但是不幸的是在2021年的2月28日,PP助手下架了ios上的所有商品。(我特么的就是这个之后开始做的,搜资料的时候就觉得自己特别水逆,大家好多就直接用PP助手都搞定了)。另外我为什么要说在windows下使用呢?因为我尝试过在mac上用爱思助手,可是版本不支持,就越狱不了(估计是这玩意经常更新的就是windows平台上的,个人感觉mac上的就是辣鸡)
直接下载越狱软件,经常用的是unc0ver,当然还有checkra1n、红雪、绿毒、Absinthe等等。后面说的有些是很古老的版本了,这些里面从谷歌搜索出来的结果来看,目前unc0ver还是用的多一些,因为它已经支持到了越狱14.3(截止发稿时)
2.尝试的方法
共尝试了三种方案unc0ver、checkra1n以及爱思助手(windows下)。 写这些主要是给大家把我踩的坑告诉大家,一方面一起开心一下,另一方面如果其它方式都不行必须用这些方法的时候,说不定有用。如果不想看这个苦逼过程的可以直接跳过到下一节。
unc0ver:根据官网提示给出了三种使用unc0ver的越狱方法。altstore方式,该方式安装完全能够成功,越狱显示也是成功了,我是用的iPhoneXs(ios14.0)进行的越狱。首先根据官网提示安装altsotre,安装成功后,在iPhone上登陆unc0ver的官网,然后点击open in altstore按钮(官网上也有写这一步,只不过我当时看懵逼了,我以为是在mac上操作,死活找不到这个按钮,因此特此说明)。
在这个过程种出现了一个问题:
cannot activate more than 3 apps and app extensions. Make sure “Offload Unused Apps” is disabled in Settings > iTunes & App Stores, then install or delete all offloaded apps.
解决方案:
删除app,主要是需要ios设置信任的app,如果之前有安装,那么就要删除完全。另外还要设置disable offloaded unused app。就可以了
安装成功后,点击越狱按钮就可以了,进行到这一步我十分的开心,以为这个好easy,结果后面在连接手机成功,并且开始砸壳app的时候,这个过程给我好好上了一课。个人感觉还是越狱没有很成功(当然手机的机型以及系统型号应该都有关系,由于手头上的手机比较少,未作比较,所以这只是个人主观猜测),所以导致越狱后的手机的Developer文件夹是没法使用的,这个文件夹下面有很重要的东西。所以只能到此作罢,尝试别的方法。
checkra1n:这个对设备有要求,要求12.0以上的系统,而且它还破解不了14.0。我手头是一台14.0的手机和一台11.1的手机,这就相当尴尬。不过这个软件下载下来之后,mac连接手机是能直接识别的,感觉做的还不错,可以尝试一下。
在windows下下载爱思助手,越狱了两台手机,se1以及Xs,两台都成功了,但是由于se1太过老旧,因此越狱后的效果并不好,且后续的砸壳操作也无法执行。
3.成功的方法
重点来了!!!
重点往往十分朴素
Windows下下载爱思助手,将手机使用usb连接电脑,一键越狱。
没错,有时候越狱就是这么简单
越狱成功的标志一般情况下是cydia商店可以使用,但从我的这几天折磨的经历来看,不光要可以使用,还要其它的各种情况均正常,才能后达到我们越狱的目的。
成功以后记得安装Apple File Conduit “2”以及AppSync Unifiled,另外在Mac端安装iFunBox,以此查看iphone中的文件

三、mac终端连接iPhone
使用OpenSSH
安装OpenSSH,安装完成后,尝试连接同一个wifi,但是并不能ping通而且也不能够ssh连接成功。*终使用了不同的wifi,就能够ping通而且连接成功,初始密码是alpine。

ssh root@手机ip
1
这个手机ip就是点击iphone的设置-》无线局域网,然后点击你连接的wifi的名称后面跟着的圈i,往下滑动就能看到ip地址
另外一种方式通过usb连接。首先下载usbmuxd工具包,然后用usb线连接手机。进入python-client目录,执行以下命令将本地22222端口转发到远程22端口。

python tcprelay.py -t 22:22222
1
出现下面这句就说明成功了:

Forwarding local port 22222 to remote port 22
1
*后,执行

ssh root@localhost -p 22222
1
特别提示:千万记得使用python3以下进行调用,因为用python3试过,真的是不行,主要是里面的py文件是按照3一下的标准写的。另外千万不要听那些网页说了P一定要大写,我用大写尝试了也不行,小写才可以。

总结
下一章讲解破壳以及分析过程,敬请期待!!!
好好学习,天天向上!!!
喜欢的给个三连!!!
感谢大家!!!

iOS10.2下的IPA砸壳

前言

从App Store上下载的ipa里面的二进制文件是经过加密的,class-dump和Hopper Disassembler都需要用到未加密的二进制文件,需要通过砸壳得到。网上敲壳教程还是挺多的,几乎都差不多,但都太旧了都没有更新,例如在iOS10.2下,传统的dumpdecrypted砸壳就会有问题,需要加点其它操作才能敲成功。

查看二进制文件是否加密

使用可以otool来查看,otool -l 二进制文件路径 | grep -B 2 crypt

  1. $ otool -l WeChat.app/WeChat | grep -B 2地穴
  2. cmd LC_ENCRYPTION_INFO
  3. cmdsize 20
  4. cryptoff 16384
  5. cryptsize 49463296
  6. cryptid 1
  7. cmd LC_ENCRYPTION_INFO_64
  8. cmdsize 24
  9. cryptoff 16384
  10. cryptsize 53149696
  11. cryptid 1
  12. 复制代码

cryptid为1时说明被加密,为0时则是未加密。可以看到微信已经被加密了,*个对应的是较老的armv7架构,后者则是arm64架构。被加密的二进制文件直接拿起来就撸是没用的,需要先敲壳。

准备敲壳

ssh连上的iPhone

确保iPhone和Mac在同一个网段,我的iPhone的IP地址为192.168.1.22.OpenSSH的root密码默认为alpine

  1. $ ssh root@192.168.1.22
  2. root@192.168.1.22的密码:
  3. Dankal-Device-5s:~root#
  4. 复制代码

这个时候已经顺利获取了iPhone的root权限,root相当于Windows中的管理员,权限*高,可读写。

ssh相关的问题请看之前写过的“iOS10.2 SSH连接越狱设备”,这里就不多阐述。

获取设备当前的进程

iPhone打开微信,后台结束其他APP进程,控制台输入ps ax 或者ps -e

  1. Dankal-Device-5s:~root#ps -e
  2. PID TTY TIME CMD
  3. 1 ?? 0:26.19 / sbin / launchd
  4. 21 ?? 0:01.77 / usr / sbin / syslogd
  5. 42 ?? 0:17.65 / usr / libexec / logd
  6. 44 ?? 0:00.08 /System/Library/PrivateFrameworks/MobileSoftwareUpdate.framework/Support/softwareupdated
  7. 1190 ?? 0:08.03 / 变种 /容器/捆绑/应用/ 46316B03 -5DC3- 4534 -8D40-A29FE9315E22 / WeChat.app /微信
  8. 1391 ?? ?? 0:00.17 / usr / local / bin / dropbear -F -R -p 22
  9. 1392 ttys000 0:00.04 -sh
  10. 1401 ttys000 0:00.01 ps -e
  11. 1020 ttys001 0:00.02 login -fp mobile
  12. 1021 ttys001 0:00.06 -SH
  13. 复制代码

找到微信的的进程,记住PID为1190,Bundle路径/var/containers/Bundle/Application/46316B03-5DC3-4534-8D40-A29FE9315E22/WeChat.app/WeChat

勾住进程

  1. Dankal-Device- 5 s: ~root #cygcript – p 1190
  2. CY#
  3. 复制代码

看到cy#的出现就说明,成功勾住了微信的进程。

获取沙盒路径

通过Cycript与进程交互动态获取应用的沙盒路径,输入以下任一行代码。

  • [NSHomeDirectory() stringByAppendingString:@"/Documents"]
  • NSSearchPathForDirectoriesInDomains(NSDocumentDirectory,NSUserDomainMask,YES)[0]
  1. cy#[NSHomeDirectory()stringByAppendingStrin g: @ “/ Documents” ]
  2. @ “/ var / mobile / Containers / Data / Application / E2ABB23B-EC66-4DA4-AD3E-E14E20D680B5 / Documents”
  3. 复制代码

出来显示的字符串即为沙盒品路径

dumpdecrypted.dylib

敲壳的*重要的东西就是dumpdecrypted.dylib,确保从Github上下载了*新的dumpdecrypted源码,解压后进入dumpdecrypted文件夹的跟目录,make编译dumpdecrypted.dylib。

  1. $ cd / Users / bingo / Downloads / dumpdecrypted-master
  2. $ make
  3. `xcrun –sdk iphoneos – find gcc` -Os -Wimplicit -isysroot`xcrun –sdk iphoneos –show-sdk-path` -F`xcrun –sdk iphoneos –show-sdk-path` / System /库/框架-F`xcrun –sdk iphoneos –show-sdk-path` / System / Library / PrivateFrameworks -arch armv7 -arch armv7s -arch arm64 – c – o dumpdecrypted。o dumpdecrypted。C
  4. `xcrun –sdk iphoneos – find gcc` -Os -Wimplicit -isysroot`xcrun –sdk iphoneos –show-sdk-path` -F`xcrun –sdk iphoneos –show-sdk-path` / System /库/框架-F`xcrun –sdk iphoneos –show-sdk-path` / System / Library / PrivateFrameworks -arch armv7 -arch armv7s -arch arm64 -dynamiclib – o dumpdecrypted.dylib dumpdecrypted。Ø
  5. 复制代码

结束后会在当前目录中生成dumpdecrypted.dylib,这里有坑,下面会说。

拷贝dumpdecrypted.dylib到沙盒路径下

scp拷贝贝文件到越狱设备的沙盒路径下,沙盒目录刚刚用Cycript动态获取到了,如果设备不支持scp或者出现问题,可以参考“让越狱设备支持scp文件传输”,或者使用iTools等工具实现文件传输,在此不再阐述。

  1. $ scp dumpdecrypted.dylib root@192.168.1.22:/ var / mobile / Containers / Data / Application / E2ABB23B-EC66-4DA4-AD3E-E14E20D680B5 / Documents
  2. root@192.168.1.22的密码:
  3. dumpdecrypted.dylib 100%193KB 242.3KB / s 00:00
  4. 复制代码

开始敲壳 以上都是准备工作,接下来可以正式砸壳了。

dumpdecrypted.dylib的具体用法是:DYLD_INSERT_LIBRARIES=to/Path/dumpdecrypted.dylib to/bundlePath

  1. Dankal-设备- 5个S: 〜根#CD的/ var /移动/容器/数据/应用/ E2ABB23B-EC66- 4 DA4-AD3E-E14E20D680B5 /文件
  2. Dankal-设备- 5个S:的/ var /移动/容器/数据/应用/ E2ABB23B-EC66- 4 DA4-AD3E-E14E20D680B5 /文档根#DYLD_INSERT_LIBRARIES = dumpdecrypted.dylib “的/ var /容器/捆绑/应用/ 46316B03-5DC3 -4534-8D40-A29FE9315E22 / WeChat.app /微信”
  3. dyld:无法加载插入的库‘dumpdecrypted.dylib’,因为找不到合适的图像。没有找到:
  4. dumpdecrypted.dyli B:所需的代码签名丢失了 “dumpdecrypted.dylib”
  5. 中止陷阱:6
  6. 复制代码

很明显砸壳失败了,这跟说好的不一样!为什么别人砸壳成功了,而我却砸失败了?重复试了几次都不成功。

于是开始找问题,首先怀疑我的设备的CPU架构不对,打开iTools可以明显看到是iPhone 5s,arm64,已越狱,没毛病,如果是32位处理器的话应该是越狱不成功的。

再找问题,怀疑是yalu02越狱的时候出了问题,重启再越狱了一遍,还是一样的问题。

继续寻找,设备不支持吗?网上搜索“iPhone5s砸壳失败”,很失望,没有相关的资料,搜到的全是真的手机壳的相关问题。

*后,怀疑是越狱本身就有问题,毕竟iOS 10.2是非完美越狱。于是搜“iOS 10.2 dumpdecrypted失败”,终于摸索到相关文章,真的不容易啊,卡了一天,终于找到了解决方案。学会定位问题与使用搜索引擎对于程序员来说还是很重要的!

正确砸壳

dumpdecrypted对系统ios 9.3.2以上的版本砸壳失败,会报错Killed: 9,解决方案

当然,我们现在是iOS 10.2,上面的解决方案可能还有问题,*后找到正确的解决方法,就是另外下载dumpdecrypted.dylib,链接来自上面解决方案的页面下的评论。

masbog

也许一些用户需要*新的.dylib与iOS 10.2 sdk … masbog.com/dumpdecrypt…和一些iOS 10.2教程:拥抱:

*终能找到问题所在我也感到非常神奇与幸运,为了预防站长的服务器挂掉或者链接失效,我已经将.dylib上传到了七牛云上,cdn加速下载链,以防不备之需。

使用方法

拷贝*新的dumpdecrypted.dylib到设备上的/usr/lib

  1. $ scp dumpdecrypted.dylib root@192.168.1.22:/ usr / lib
  2. root@192.168.1.22的密码:
  3. dumpdecrypted.dylib 100%193KB 410.8KB / s 00:00
  4. 复制代码

iOS 10+:

  1. Dankal-Device- 5 s: ldid -S /usr/lib/dumpdecrypted.dylib
  2. 复制代码

*终一砸

  1. Dankal-设备- 5个S:的/ var /移动/容器/数据/应用/ E2ABB23B-EC66- 4 DA4-AD3E-E14E20D680B5 /文档根#DYLD_INSERT_LIBRARIES = / usr / lib中/ dumpdecrypted.dylib “的/ var /容器/包/应用程序/ 46316B03-5DC3-4534-8D40-A29FE9315E22 / WeChat.app /微信”
  2. 马赫Ø解密自卸车
  3. 免责声明:此工具是 只意味着用于安全研究的目的,而不是用于应用饼干。
  4. [+] 在内存中检测到64位ARM二进制文件。
  5. 找到[+]偏移到 cryptid :@ 0 x1000a0ca8(从0 x1000a0000)= ca8
  6. [+]在地址00004000处找到长度为53149696字节的加密数据- 类型 1。
  7. [+]打开/私有的/ var /容器/捆绑/应用/ 46316 B03- 5 DC3- 4534 – 8 D40-A29FE9315E22 / WeChat.app /微信为读数。
  8. [+]阅读标题
  9. [+]检测标题类型
  10. [+]可执行是 一个 FAT图像-搜索为 右架构
  11. [+]正确拱是在偏移58195968中文件
  12. [+]开放WeChat.decrypted 用于写入。
  13. [+]复制文件的未加密开头
  14. [+]将解密的数据转储到文件中
  15. [+]复制未加密的文件剩余部分
  16. [+] 在偏移3780 ca8 处将LC_ENCRYPTION_INFO-> cryptid设置为 0
  17. [+]关闭原始文件
  18. [+]关闭转储文件
  19. Dankal-设备- 5个S:的/ var /移动/容器/数据/应用/ E2ABB23B-EC66- 4 DA4-AD3E-E14E20D680B5 /文件根#
  20. 复制代码

查看成果 砸壳完毕,会自动在当前目录生成砸壳后的二进制文件WeChat.decrypted

  1. $ ls
  2. 00000000000000000000000000000000 Ksid MMResourceMgr SafeMode.dat db.globalconfig
  3. 8 f9f003b02f320ae7f28b1250270eb48 LocalInfo.lst MMappedKV WeChat.decrypted mmupdateinfo.archive
  4. 复制代码

后话

终于砸壳完毕,说难也不难,从App Store上下载的ipa就这样被砸掉了壳,可见所谓的Apple Store给ipa穿上的战衣也不过如此,并没有多么安全。敲壳后的二进制文件就可以做一些好玩的东西了,比如dump出头文件等,接下来的文章会慢慢记录。

Activity启动流程–Activity启动的详细流程

本系列文章将详细阐述Activity的启动流程,这些基于Cm 10.1源码研究。

  • 深入理解Activity启动流程(一)–Activity启动的概要流程
  • 深入理解Activity启动流程(二)–Activity启动相关类的类图
  • 深入理解Activity启动流程(三)–Activity启动的详细流程1
  • 深入理解Activity启动流程(四)–Activity Task的调度算法

上篇文章介绍了Activity详细启动流程的前半部分:

  • 1. Activity调用ActivityManagerService启动应用
  • 2. ActivityManagerService调用Zygote孵化应用进程
  • 3. Zygote孵化应用进程

本篇文章主要介绍Activity详细启动流程的后半部分:

  • 4. 新进程启动ActivityThread
  • 5. 应用进程绑定到ActivityManagerService
  • 6. ActivityThread的Handler处理启动Activity的消息

4. 新进程启动ActivityThread

点击图片可看大图

zygote_activitythread

Zygote进程孵化出新的应用进程后,会执行ActivityThread类的main方法。在该方法里会先准备好Looper和消息队列,然后调用attach方法将应用进程绑定到ActivityManagerService,然后进入loop循环,不断地读取消息队列里的消息,并分发消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//ActivityThread类
public static void main(String[] args) {
    //... 
    Looper.prepareMainLooper();
    ActivityThread thread = new ActivityThread();
    thread.attach(false);

    if (sMainThreadHandler == null) {
        sMainThreadHandler = thread.getHandler();
    }
    AsyncTask.init();
    //...
    Looper.loop();

    //...
}

5. 应用进程绑定到ActivityManagerService

点击图片可看大图

application_amservice

在ActivityThread的main方法里调用thread.attach(false);attach方法的主要代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//ActivityThread类
private void attach(boolean system) {
    sThreadLocal.set(this);
    mSystemThread = system;
    if (!system) {
        //...
        IActivityManager mgr = ActivityManagerNative.getDefault();
        try {
        //调用ActivityManagerService的attachApplication方法
        //将ApplicationThread对象绑定至ActivityManagerService,
        //这样ActivityManagerService就可以
        //通过ApplicationThread代理对象控制应用进程
            mgr.attachApplication(mAppThread);
        } catch (RemoteException ex) {
            // Ignore
        }
    } else {
        //...
    }
    //... 
}

ActivityManagerService的attachApplication方法执行attachApplicationLocked(thread, callingPid)进行绑定。

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
//ActivityManagerService类
private final boolean attachApplicationLocked(IApplicationThread thread,
        int pid) { 
    ProcessRecord app;
    //...     
    app.thread = thread; 
    //...  
    try {
        //...
        thread.bindApplication(processName, appInfo, providers,
                app.instrumentationClass, profileFile, profileFd, profileAutoStop,
                app.instrumentationArguments, app.instrumentationWatcher, testMode,
                enableOpenGlTrace, isRestrictedBackupMode || !normalMode, app.persistent,
                new Configuration(mConfiguration), app.compat, getCommonServicesLocked(),
                mCoreSettingsObserver.getCoreSettingsLocked());
        //... 
    } catch (Exception e) {
       //...
    }
    //... 
    ActivityRecord hr = mMainStack.topRunningActivityLocked(null);
    if (hr != null && normalMode) {
        if (hr.app == null && app.uid == hr.info.applicationInfo.uid
                && processName.equals(hr.processName)) {
            try {
                if (mHeadless) {
                    Slog.e(TAG, "Starting activities not supported on headless device: " + hr);
                } else if (mMainStack.realStartActivityLocked(hr, app, true, true)) {
                //mMainStack.realStartActivityLocked真正启动activity
                    didSomething = true;
                }
            } catch (Exception e) {
                //...
            }
        } else {
            //...
        }
    }
    //... 
    return true;
}

attachApplicationLocked方法有两个重要的函数调用thread.bindApplication和mMainStack.realStartActivityLocked。thread.bindApplication将应用进程的ApplicationThread对象绑定到ActivityManagerService,也就是说获得ApplicationThread对象的代理对象。mMainStack.realStartActivityLocked通知应用进程启动Activity。

5.1 thread.bindApplication

thread对象其实是ActivityThread里ApplicationThread对象在ActivityManagerService的代理对象,故此执行thread.bindApplication,*终会调用ApplicationThread的bindApplication方法,该方法的主要代码如下所示:

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
//ActivityThread类
public final void bindApplication(String processName,
        ApplicationInfo appInfo, List<ProviderInfo> providers,
        ComponentName instrumentationName, String profileFile,
        ParcelFileDescriptor profileFd, boolean autoStopProfiler,
        Bundle instrumentationArgs, IInstrumentationWatcher instrumentationWatcher,
        int debugMode, boolean enableOpenGlTrace, boolean isRestrictedBackupMode,
        boolean persistent, Configuration config, CompatibilityInfo compatInfo,
        Map<String, IBinder> services, Bundle coreSettings) {
    //...  
    AppBindData data = new AppBindData();
    data.processName = processName;
    data.appInfo = appInfo;
    data.providers = providers;
    data.instrumentationName = instrumentationName;
    data.instrumentationArgs = instrumentationArgs;
    data.instrumentationWatcher = instrumentationWatcher;
    data.debugMode = debugMode;
    data.enableOpenGlTrace = enableOpenGlTrace;
    data.restrictedBackupMode = isRestrictedBackupMode;
    data.persistent = persistent;
    data.config = config;
    data.compatInfo = compatInfo;
    data.initProfileFile = profileFile;
    data.initProfileFd = profileFd;
    data.initAutoStopProfiler = false;
    queueOrSendMessage(H.BIND_APPLICATION, data);
}

这样调用queueOrSendMessage会往ActivityThread的消息队列发送消息,消息的用途是BIND_APPLICATION。

这样会在handler里处理BIND_APPLICATION消息,接着调用handleBindApplication方法处理绑定消息。

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
//ActivityThread类
private void handleBindApplication(AppBindData data) {
  //...  
  ApplicationInfo instrApp = new ApplicationInfo();
  instrApp.packageName = ii.packageName;
  instrApp.sourceDir = ii.sourceDir;
  instrApp.publicSourceDir = ii.publicSourceDir;
  instrApp.dataDir = ii.dataDir;
  instrApp.nativeLibraryDir = ii.nativeLibraryDir;
  LoadedApk pi = getPackageInfo(instrApp, data.compatInfo,
        appContext.getClassLoader(), false, true);
  ContextImpl instrContext = new ContextImpl();
  instrContext.init(pi, null, this);
    //... 
   
     

  if (data.instrumentationName != null) {
       //...
  } else {
       //注意Activity的所有生命周期方法都会被Instrumentation对象所监控,
       //也就说执行Activity的生命周期方法前后一定会调用Instrumentation对象的相关方法
       //并不是说只有跑单测用例才会建立Instrumentation对象,
       //即使不跑单测也会建立Instrumentation对象
       mInstrumentation = new Instrumentation();
  }
  //... 
  try {
     //...
     Application app = data.info.makeApplication(data.restrictedBackupMode, null);
     mInitialApplication = app;
     //...         
     try {
          mInstrumentation.onCreate(data.instrumentationArgs);
      }catch (Exception e) {
             //...
      }
      try {
           //这里会调用Application的onCreate方法
           //故此Applcation对象的onCreate方法会比ActivityThread的main方法后调用
           //但是会比这个应用的所有activity先调用
            mInstrumentation.callApplicationOnCreate(app);
        } catch (Exception e) {
           //...
        }
    } finally {
        StrictMode.setThreadPolicy(savedPolicy);
    }
}

5.2 mMainStack.realStartActivityLocked

realStartActivity会调用scheduleLaunchActivity启动activity,主要代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//ActivityStack类
final boolean realStartActivityLocked(ActivityRecord r,
        ProcessRecord app, boolean andResume, boolean checkConfig)
        throws RemoteException {

    //...  
    try {
        //...
        app.thread.scheduleLaunchActivity(new Intent(r.intent), r.appToken,
                System.identityHashCode(r), r.info,
                new Configuration(mService.mConfiguration),
                r.compat, r.icicle, results, newIntents, !andResume,
                mService.isNextTransitionForward(), profileFile, profileFd,
                profileAutoStop);
        
        //...
        
    } catch (RemoteException e) {
        //...
    }
    //...    
    return true;
}

同样app.thread也只是ApplicationThread对象在ActivityManagerService的一个代理对象而已,*终会调用ApplicationThread的scheduleLaunchActivity方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//ActivityThread类
public final void scheduleLaunchActivity(Intent intent, IBinder token, int ident,
        ActivityInfo info, Configuration curConfig, CompatibilityInfo compatInfo,
        Bundle state, List<ResultInfo> pendingResults,
        List<Intent> pendingNewIntents, boolean notResumed, boolean isForward,
        String profileName, ParcelFileDescriptor profileFd, boolean autoStopProfiler) {
    ActivityClientRecord r = new ActivityClientRecord();
    r.token = token;
    r.ident = ident;
    r.intent = intent;
    r.activityInfo = info;
    r.compatInfo = compatInfo;
    r.state = state;
    r.pendingResults = pendingResults;
    r.pendingIntents = pendingNewIntents;
    r.startsNotResumed = notResumed;
    r.isForward = isForward;
    r.profileFile = profileName;
    r.profileFd = profileFd;
    r.autoStopProfiler = autoStopProfiler;
    updatePendingConfiguration(curConfig);
    queueOrSendMessage(H.LAUNCH_ACTIVITY, r);
}

这里调用了queueOrSendMessage往ActivityThread的消息队列发送了消息,消息的用途是启动Activity,接下来ActivityThread的handler便会处理该消息。

6. ActivityThread的Handler处理启动Activity的消息

点击图片可看大图

activitythread_activity

ActivityThread的handler调用handleLaunchActivity处理启动Activity的消息,handleLaunchActivity的主要代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
//ActivityThread类
private void handleLaunchActivity(ActivityClientRecord r, Intent customIntent) {
    //... 
    Activity a = performLaunchActivity(r, customIntent);
    if (a != null) {
        //...
        handleResumeActivity(r.token, false, r.isForward,
                !r.activity.mFinished && !r.startsNotResumed);
        //...
    } else {
        //...
    }
}

handleLaunchActivity方法里有有两个重要的函数调用,performLaunchActivity和handleResumeActivity,performLaunchActivity会调用Activity的onCreate,onStart,onResotreInstanceState方法,handleResumeActivity会调用Activity的onResume方法.

6.1 performLaunchActivity

performLaunchActivity的主要代码如下所示:

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
51
52
53
54
55
//ActivityThread类
private Activity performLaunchActivity(ActivityClientRecord r, Intent customIntent) {
    //...
    Activity activity = null;
    try {
        java.lang.ClassLoader cl = r.packageInfo.getClassLoader();
        activity = mInstrumentation.newActivity(
                cl, component.getClassName(), r.intent);
        //...
    } catch (Exception e) {
        //...
    }
    try {
        //r.packageInfo.makeApplication实际并未创建Application对象,
        //因为bindApplication过程已经创建了Application对象,
        //makeApplication方法会返回已创建的Application对象
        Application app = r.packageInfo.makeApplication(false, mInstrumentation);
        //...         
        if (activity != null) {
            //...
            //将application对象,appContext对象绑定到新建的activity对象
            activity.attach(appContext, this, getInstrumentation(), r.token,
                    r.ident, app, r.intent, r.activityInfo, title, r.parent,
                    r.embeddedID, r.lastNonConfigurationInstances, config);
            //... 
            //会调用Activity的onCreate方法             
            mInstrumentation.callActivityOnCreate(activity, r.state);
            //...
            //...
            //调用Activity的onStart方法
            if (!r.activity.mFinished) {
                activity.performStart();
                r.stopped = false;
            }              
            if (!r.activity.mFinished) {
                if (r.state != null) {
                    //会调用Activity的onRestoreInstanceState方法
                    mInstrumentation.callActivityOnRestoreInstanceState(activity, r.state);
                }
            }
            if (!r.activity.mFinished) {
                activity.mCalled = false;
                mInstrumentation.callActivityOnPostCreate(activity, r.state);
                //...
            }
        }
        //...
    } catch (SuperNotCalledException e) {
        throw e;

    } catch (Exception e) {
        //...
    }
    return activity;
}

6.2 handleResumeActivity

handleResumeActivity的主要代码如下所示:

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
//ActivityThread类
final void handleResumeActivity(IBinder token, boolean clearHide, boolean isForward,
        boolean reallyResume) {
    //...
    //performResumeActivity*终会调用Activity的onResume方法 
    ActivityClientRecord r = performResumeActivity(token, clearHide);
    if (r != null) {
        final Activity a = r.activity;
        //... 
        //显示界面
        if (r.window == null && !a.mFinished && willBeVisible) {
            r.window = r.activity.getWindow();
            View decor = r.window.getDecorView();
            decor.setVisibility(View.INVISIBLE);
            ViewManager wm = a.getWindowManager();
            WindowManager.LayoutParams l = r.window.getAttributes();
            a.mDecor = decor;
            l.type = WindowManager.LayoutParams.TYPE_BASE_APPLICATION;
            l.softInputMode |= forwardBit;
            if (a.mVisibleFromClient) {
                a.mWindowAdded = true;
                wm.addView(decor, l);
            }
           //...         
        } else if (!willBeVisible) {
             //...
        }
        // Tell the activity manager we have resumed.
        if (reallyResume) {
            try {
                ActivityManagerNative.getDefault().activityResumed(token);
            } catch (RemoteException ex) {
            }
        }

    } else {
         //...
    }
}

performResumeActivity的主要代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//ActivityThread类
public final ActivityClientRecord performResumeActivity(IBinder token,
        boolean clearHide) {
    ActivityClientRecord r = mActivities.get(token);
    //...
    if (r != null && !r.activity.mFinished) {
         //...
        try {
            //... 
            //会调用Activity的onResume方法 
            r.activity.performResume();
            //...
        } catch (Exception e) {
            //...
        }
    }
    return r;
}

总结

Activity的概要启动流程:

用户在Launcher程序里点击应用图标时,会通知ActivityManagerService启动应用的入口Activity,ActivityManagerService发现这个应用还未启动,则会通知Zygote进程孵化出应用进程,然后在这个dalvik应用进程里执行ActivityThread的main方法。应用进程接下来通知ActivityManagerService应用进程已启动,ActivityManagerService保存应用进程的一个代理对象,这样ActivityManagerService可以通过这个代理对象控制应用进程,然后ActivityManagerService通知应用进程创建入口Activity的实例,并执行它的生命周期方法

现在也可以理解:

如果应用的组件(包括所有组件Activity,Service,ContentProvider,Receiver) 被启动,肯定会先启动以应用包名为进程名的进程,这些组件都会运行在应用包名为进程名的进程里,并且是在主线程里。应用进程启动时会先创建Application对象,并执行Application对象的生命周期方法,然后才启动应用的组件。

有一种情况比较特殊,那就是为组件设置了特殊的进程名,也就是说通过android:process设置进程名的情况,此时组件运行在单独的进程内。

ipa砸壳解析出头文件

说明

  • 在越狱的iOS设备上,解析UCWeb应用的头文件

直接将从苹果商店上下载的ipa导出头文件

class-dump -H UCWEB.app -o UCWEB

由于该ipa文件加了壳,不能解析出头文件。

砸壳

使用dumpdecrypted工具
下载地址:https://codeload.github.com/stefanesser/dumpdecrypted/zip/master
下载后解压,然后cd到该目录下,执行make命令进行编译

  1. `xcrun –sdk iphoneos –find gcc` -Os -Wimplicit -isysroot `xcrun –sdk iphoneos –show-sdk-path` -F`xcrun –sdk iphoneos –show-sdk-path`/System/Library/Frameworks -F`xcrun –sdk iphoneos –show-sdk-path`/System/Library/PrivateFrameworks -arch armv7 -arch armv7s -arch arm64 -c -o dumpdecrypted.o dumpdecrypted.c
  2. `xcrun –sdk iphoneos –find gcc` -Os -Wimplicit -isysroot `xcrun –sdk iphoneos –show-sdk-path` -F`xcrun –sdk iphoneos –show-sdk-path`/System/Library/Frameworks -F`xcrun –sdk iphoneos –show-sdk-path`/System/Library/PrivateFrameworks -arch armv7 -arch armv7s -arch arm64 -dynamiclib -o dumpdecrypted.dylib dumpdecrypted.o

显示如上内容,编译成功。
make命令执行完毕后,会在当前目录下生成一个dumpdecrypted.dylib文件,这就是我们等下砸壳所要用到的榔头。此文件生成一次即可,以后可以重复使用,下次砸壳时无须再重新编译。

上传文件

ssh连接到手机(我的手机ip地址是192.168.1.181)

ssh root@192.168.1.181

执行命令,找到所有进程

ps -e | grep var 

查找到uc的路径
/var/mobile/Containers/Bundle/Application/78241EAF-781C-475C-BA53-84EF7C4FE23D/UCWEB.app/UCWEB

进入/var/mobile/Containers/Bundle/Application/78241EAF-781C-475C-BA53-84EF7C4FE23D/UCWEB.app路径下
利用cycript工具勾住UCWEN应用

cycript -p UCWEB

执行代码

[[NSFileManager defaultManager] URLsForDirectory:NSDocumentDirectory inDomains:NSUserDomainMask][0]

获取当前应有的Document目录,然后进入到当前Document目录下。
将我们刚刚编译好砸壳工具dumpdecrypted.dylib上传到该文件夹下。

scp dumpdecrypted.dylib root@192.168.1.181:/var/mobile/Containers/Data/Application/72D29CE0-C288-4BEB-B319-41595DA3F64A/Documents/dumpdecrypted.dylib

提示输入密码,输入手机root密码,然后提示上传进度。

dumpdecrypted.dylib                                                               100%  193KB 192.9KB/s   00:00 

开始砸壳

  1. DYLD_INSERT_LIBRARIES=dumpdecrypted.dylib /var/mobile/Containers/Bundle/Application/78241EAF-781C-475C-BA53-84EF7C4FE23D/UCWEB.app/UCWEB
  2. mach-o decryption dumper

会生成app砸壳后的文件xx.decrypted. 这里就是 UCWEB.decrypted

文件导出到电脑

  1. root# scp UCWEB.decrypted root@192.168.1.105:/private/tmp
  2. Password:
  3. UCWEB.decrypted 100% 193KB 192.9KB/s 00:00

导出头文件

使用class-dump工具导出头文件

class-dump -H UCWEB.decrypted  -o output/

*好放一张解析成功的图片,可以看到右6502个文件(包含第三方sdk的类)。分析应用的头文件基本可以了解应用如何搭建。

 

%title插图%num

204. 计数质数(JS实现)

204. 计数质数(JS实现)
1 题目
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
2 思路
这道题即判断每个数是否为质数,题解中有个更巧妙的方法, Sieve of Eratosthenes算法,即某个若为质数,则其所有倍数都不可能是质数了
3代码
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    if (n <= 1) return 0;
    let count = 0;
    for (let i=2; i<n; i++) {
        if (i > 3 && (i % 2 === 0 || i % 3 === 0)) continue;
        if (isPrime(i)) count++;
    }
    return count;
    function isPrime(num) {
        let p = Math.sqrt(num);
        for (let i=2; i<=p; i++) {
            if (num % i === 0) return false;
        }
        return true;
    }
};

207. 课程表(JS实现)

207. 课程表(JS实现)
1 题目
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
链接:https://leetcode-cn.com/problems/course-schedule
2 思路
这道题就是考察拓扑排序,用于排查图里有没有环,首先建立图的邻接矩阵,然后再进行拓扑排序,逐步删除入度为0的节点
3代码
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    function Vex(value) {
        this.val = value;
        this.firstEdge = null;
        this.in = 0;
    }
    const vexs = [];
    for (let arr of prerequisites) {
        if (!vexs[arr[1]]) {
            vexs[arr[1]] = new Vex(arr[1]);
        }
        if (!vexs[arr[0]]) {
            vexs[arr[0]] = new Vex(arr[0]);
        }
        let firstEdge = vexs[arr[1]].firstEdge;
        vexs[arr[1]].firstEdge = {vex: vexs[arr[0]], next: firstEdge};
        vexs[arr[0]].in++;
    }
    const stack= [];
    let len = 0;
    for (let i=0; i<vexs.length; i++) {
        if (vexs[i]) {
            len++;
            if (vexs[i].in === 0) stack.push(vexs[i]);
        }
    }
    let count = 0;
    while(stack.length > 0) {
        let currentVex = stack.pop();
        count++;
        let currentEdge = currentVex.firstEdge;
        while(currentEdge) {
            if (–currentEdge.vex.in === 0) stack.push(currentEdge.vex);
            currentEdge = currentEdge.next;
        }
    }
    return len === count;
};

208. 实现 Trie (前缀树)(JS实现)

208. 实现 Trie (前缀树)(JS实现)
1 题目
实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree
2 思路
这道题就是实现前缀树这种数据结构,这种数据结构有个特点,就是每个节点存储一个元素为指针的数组,数组的索引就指明当前的字母,而数组值就指向下一个指针数组。
3代码
/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.startIndex = ‘a’.charCodeAt();
    this.root = new TreeNode();
};
/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let p = this.root;
    for (let i=0; i<word.length; i++) {
        let index = word[i].charCodeAt() – this.startIndex;
        if (!p.list[index]) {
            let newNode = new TreeNode();
            p.list[index] = newNode;
        }
        p = p.list[index];
    }
    p.type = ‘leaf’;
    p.word = word;
};
/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let p = this.root;
    for (let i=0; i<word.length; i++) {
        p = p.list[word[i].charCodeAt() – this.startIndex];
        if (!p && i<word.length-1) return false;
    }
    if (p && p.type === ‘leaf’ && p.word === word) return true;
    return false;
};
/**
 * Returns if there is any word in the trie that starts with the given prefix.
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let p = this.root;
    for (let i=0; i<prefix.length; i++) {
        p = p.list[prefix[i].charCodeAt() – this.startIndex];
        if (!p) return false;
    }
    return true;
};
function TreeNode() {
    this.type = ‘branch’;
    this.list = [];
    this.word = ”;
}
/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */