善用Android设置技巧 摆脱第三方管理App
　　手机系统管理类的应用，多是一些将流量查询、防骚扰、清理垃圾、手机寻回等功能集成与一身App，其特点是可以便利的将一些分散到Android系统内部的功能整合到一起，供用户便捷的进行使用。但是很多用户对这些应用都较为反感，源起应用窥探用户数据，那么既然这些功能在Android系统中都具备，那么何不使用系统原生的共能解决问题呢?　　　　数据流量监控　　Android系统从很早开始就已经拥有了流量管理这个功能，只不过因为这个功能隐藏在用户不太常用的二级菜单中，所以没有得到重视。在“无线和网络”分类下，一般是在“更多”条目当中，有一个名为“使用情况”或是“数据使用”的项目，总之是点开之后有一个“曲线图”的界面。　　　　数据使用监测功能　　在这里用户可以设定自己的网络套餐限额，提醒界限以及禁用界限，系统会根据用户使用情况自动进行记录，用户也能通过下方的曲线图和应用流量使用情况清新的看到自己的流量消耗情况，同时也能找出吃流量的应用。　　　　通话时间以及短信条数限额　　除了网络流量的监测外，Android系统的这个界面中还提供了电话数据使用和短信条数的记录，这样不但方便用户对于包月短信条数和通话时间进行管理，还能有效的避免话费超支情况。可以说是Android系统中最为实用的被忽略的功能。　　程序后台服务与缓存管理　　在2012年以前的Android手机当中，如果想要删除一个应用，大多情况需要进入系统设置中的“应用程序”才能进行删除，而随着桌面删除功能的加入，程序管理似乎被很多用户遗忘了，但是在这里不仅可以删除应用，还可以对于后台服务以及缓存应用进行管理。　　　　后台服务与缓存占用　　值得一说的是Android系统将服务与缓存做到了同一个页面下，用户需要使用菜单按钮才能进行切换，掩藏的这么深一般用户恐怕是找不到的。在这里可以清楚的看到应用所使用的后台服务数量以及该服务的启动时常、占用内存情况等，并允许用户手动进行停止等操作。　　　　二级设置页面　　相比第三方应用所提供的数据Android自身所提供的数据可谓是非常详细了，但是缺点就是需要用户逐一进行操作，没有一键清理的功能。　　Android设备寻回工具　　继iOS和WP之后，Android系统终于在今年7月发布了Android设备管理器，用途在于手机丢失后的寻回。当然前提是这个手机不是被盗而是遗失。不过理性的说虽然市面上手机寻回应用比较多，但是对于被窃后的寻回效果似乎都差强人意。　　　　Android设备管理器的寻回功能　　想要使用Android手机的寻回系统首先需要更新的最新的Google服务框架，在Google设置中可以看到Android设备管理器的条目，在其中启两项服务，并在“设置”、“安全”、“设备管理器”当中激活Android设备管理器这项共功能的权限，全部设置完毕了就可以在“/android/devicemanager”网址中寻回手机了。　　　　Web端的寻回网页　　当然首先手机要登录Google账号，如果行货手机没有Google服务框架需要自行进行安装，最好找不需要卡刷的直装版本，另外网页端也要登录相应的账号。通过Web端的控制可以清空手机中的数据以及以最大音量响铃报警等。　　应用权限验证功能　　Android4.2.2将应用权限管理功能再次强化，不但在安装应用时将应用的全部使用权限展示给用户，还真对可能会产生资费的权限进行了高亮标注。只要用户在安装时细心查看一般情况下可以规避吸费应用。　　　　应用验证功能　　除了对于应用权限的改进，在“设置”、“安全”当中，还可以开启Google市场的验证功能，针对“盗版”应用在安装时，会通过网络与GooglePlay中的应用进行比对，如果发现用户正在安装的为盗版应用，还可以及时进行制止。　　随着Android手机版本的不断提升，可以说用户对其“设置”中的功能越来越陌生，往往用户进入设置页面后，有50%左右的功能是不知道有什么用处的，这使得Android系统中许多新功能被深埋，而实际上如果妥善使用这些功能是可以让手机实现自我管理的，本文也只是抛砖引玉，更多的实用功能还在等待着用户自己去发现。Android起步早于系统应用的第三方应用，杀不死自动重启的第三方应用_cocos2d-x之道~制造第一款文字游戏（一）_leetCode答题报告5道题(八)__脚本百事通
稍等，加载中……
^_^请注意，有可能下面的2篇文章才是您想要的内容：
Android起步早于系统应用的第三方应用，杀不死自动重启的第三方应用
cocos2d-x之道~制造第一款文字游戏（一）
leetCode答题报告5道题(八)
Android起步早于系统应用的第三方应用，杀不死自动重启的第三方应用
Android启动早于系统应用的第三方应用，杀不死自动重启的第三方应用1．为什么第三方应用能早于System的app启动？
Android应用的启动顺序网上有一大堆资料可以查阅了，这里就不细述了，这里不阐述ROM启动还有bootloader，软件启动的大致流程应该是
启动kernel
运行servicemanager 把一些native的服务用命令启动起来（包括wifi, power, rild, surfaceflinger, mediaserver等等)
启动Dalivk中的第一个进程Zygote -& 启动java 层的系统服务system_server（包括PowerManagerService, ActivityManagerService , telephony.registry, DisplayManagerService等等）该服务中的这些部件跟native的那些服务关联在一起
启动Luncher和Persistent的App，该程序是系统级的在AndroidManifest.xml里声明android:persistent="true"
发出ACTION_BOOT_COMPLETED广播给其他应用。
在这里需要注意的是声明android:persistent属性为true的APP被kill掉后还是会自动重启的。系统中我们已知android:persistent属性为true的APP肯定有Phone App，也就是说第三方应用应当至少晚于Phone APP启动，如何判断呢？最简单的办法看其PID的大小，PID值越小越先启动。有其第三方应用可以先于Phone APP启动。我们探其应用的AndroidManifest.xml (PS：如何看APK的代码，网上有你懂的apktool等)，发现其在AndroidManifest里定义的静态Receiver的intent-filter的属性如下：
&receiver android:name="com.anguanjia.safe.AAAReceiver"&
&span style="color:#FF0000;"&&intent-filter android:priority=""&&/span&
&action android:name="android.bluetooth.adapter.action.STATE_CHANGED" /&
&action android:name="android.net.wifi.WIFI_STATE_CHANGED" /&
&action android:name="android.net.conn.CONNECTIVITY_CHANGE" /&
&action android:name="android.intent.action.ANY_DATA_STATE" /&
&action android:name="android.net.wifi.STATE_CHANGE" /&
&/intent-filter&
&intent-filter android:priority=""&
&action android:name="android.intent.action.MEDIA_UNMOUNTED" /&
&action android:name="android.intent.action.MEDIA_MOUNTED" /&
&action android:name="android.intent.action.MEDIA_REMOVED" /&
&action android:name="android.intent.action.MEDIA_CHECKING" /&
&action android:name="android.intent.action.MEDIA_EJECT" /&
&data android:scheme="file" /&
&/intent-filter&
<span style="color:#FF3647 这个值是什么？好大，哦，原来是int的最大值！我们来看下google 文档
android:priority
The priority that should be given to the parent component with regard to handling intents of the type described by the filter. This attribute has meaning for both activities and broadcast receivers:
It provides information about how able an activity is to respond to an intent that matches the filter, relative to other activities that could also respond to the intent. When an intent could be handled by multiple activities with different priorities,
Android will consider only those with higher priority values as potential targets for the intent.
It controls the order in which broadcast receivers are executed to receive broadcast messages. Those with higher priority values are called before those with lower values. (The order applies only to
it's ignored for asynchronous
messages.)
Use this attribute only if you really need to impose a specific order in which the broadcasts are received, or want to force Android to prefer one activity over others.
The value must be an integer, such as "100". Higher numbers have a higher priority. The default value is 0. The value must be greater than -1000 and less than 1000.
这个值是receiver的优先级，值越大优先级越高，按优先顺序执行，但是文档介绍优先级值大小是-. 该应用的是int的最大值， 但android平台没有对android:priority值进行检查。在开机后该应用Receiver的intent-filter的优先级最高，在该filter里的intent被系统发送出来(android.intent.action.MEDIA_MOUNTE,
android.net.wifi.WIFI_STATE_CHANGED等等），这个时候App会根据这个intent而被启动起来。
这里需要注意的是该Receiver是个静态的，一定是要注册在AndroidManifest里。当Wifi成功注册后会发出WIFI_STATE_CHANGED的消息， 或者其他的部件完成一些事件后也会发出类似的消息，而这些消息的发出又早于属性为persistent的系统级APP的启动， 由此就会发生第三方应用早于系统级APP的启动的情况。
2. 在Android手机上为什么我想完全关闭的程序关不了？
有一种理论是Android手机为了有更好的用户体验，会后台自动启动一些程序， 这样我们前台在操作的时候会感觉手机更流畅平滑。但是如果程序运行过多，对CPU 内存的开销过大，往往会导致系统越用越慢，乃至手机挂掉的问题，在内存管理这快Android有两种机制去解决这个问题，一个是在framework层在 trimApplication方法中去实现，另外一个就是在kernel里的lowmemorykiller， 这里不再细述。
但是对于用户来说，我就是想完全关闭第三方程序，以免过多使用我的流量或者偷偷的做一些我不希望的操作。貌似没有办法去关闭，那为什么呢？ 我这里先讲述其中一种情况。
Service顾名思义是服务，运行在前后台后都可以，即可以运行在当前进程也可以运行在其他的进程里，Service可以为多个APP共享使用，是通过binder机制来实现的。当我Kill掉一个带有服务的进程(没有调用stopService())， 过一会该应用会自动重启。下面是代码的调用顺序，自下往上查看。com.android.server.am.ActiveServices.scheduleServiceRestartLocked(ActiveServices.java)
com.android.server.am.ActiveServices.killServicesLocked (ActiveServices.java)
com.android.server.am.ActivityManagerService.cleanUpApplicationRecordLocked(ActivityManagerService.java)
com.android.server.am.ActivityManagerService.handleAppDiedLocked(ActivityManagerService.java)
com.android.server.am.ActivityManagerService.appDiedLocked(ActivityManagerService.java)
com.android.server.am.ActivityManagerService$AppDeathRecipient.binderDied(ActivityManagerService.java)
从代码流程上我们看出该service被restart，进程也根据该service启动起来, service就运行在重启的进程里。
在这种情况下是不是就真没办法了呢，当然不是，如果我们在service中覆盖onStartCommand这个函数并且返回值为START_NOT_STICKY，在我们kill该进程后则不会自动重启，我们想关闭的应用也可以完全关闭了，不会再自动重启了。
public int &span style="color:#FF0000;"&&strong&onStartCommand&/strong&&/span&(Intent intent, int flags, int startId) {
return &span style="color:#FF0000;"&&strong&START_NOT_STICKY&/strong&&/span&;
Framwork实现代码
frameworks/base/services/java/com/android/server/am/ActiveServices.java
case Service.START_NOT_STICKY: {
// We are done with the associated start arguments.
r.findDeliveredStart(startId, true);
if (r.getLastStartId() == startId) {
// There is no more work, and this service
// doesn't want to hang around if killed.
r.&span style="color:#FF0000;"&stopIfKilled&/span& =
// 该变量设置为true
if (sr.startRequested && (sr.&span style="color:#FF0000;"&stopIfKilled&/span& || canceled)) {
//进入到该条件中
if (sr.pendingStarts.size() == 0) {
sr.startRequested =
if (sr.tracker != null) {
sr.tracker.setStarted(false, mAm.mProcessStats.getMemFactorLocked(),
SystemClock.uptimeMillis());
if (!sr.hasAutoCreateConnections()) {
// Whoops, no reason to restart!
bringDownServiceLocked(sr);
//执行在这里，不会重启App
重写onStartCommand方法且返回值为START_NOT_STICKY的代码调用顺序，自下而上查看。
com.android.server.am.ActiveServices.bringDownServiceLocked(ActiveServices.java)
com.android.server.am.ActiveServices.killServicesLocked(ActiveServices.java)
com.android.server.am.ActivityManagerService.cleanUpApplicationRecordLocked(ActivityManagerService.java)
com.android.server.am.ActivityManagerService.handleAppDiedLocked(ActivityManagerService.java)
com.android.server.am.ActivityManagerService.appDiedLocked(Activi tyManagerService.java)
com.android.server.am.ActivityManagerService$AppDeathRecipient.binderDied(ActivityManagerService.java)
附上Google doc 对于onStartCommand返回值的说明For started services, there are two additional major modes of operation they can decide to run in, depending on the value they return from onStartCommand():START_STICKY
is used for services that are explicitly started and stopped as needed, whileSTART_NOT_STICKY orSTART_REDELIVER_INTENT
are used for services that should only remain running while processing any commands sent to them. See the linked documentation for more detail on the semantics.
在这里对这个返回值做下解释：
当服务进程因某种原因(内存不够，强制关闭等)被kill掉时，START_STICKY在系统有充足的内存后重新创建service， 在onStartCommand中handle的是null intent.
START_NOT_STICKY通知系统不在重新创建该service. 还有一个返回值START_REDELIVER_INTENT重新创建service并且伴随着原来intent的去处理。
cocos2d-x之道~制造第一款文字游戏（一）
cocos2d-x之道~制作第一款文字游戏（一）前言
回想去年，也是在三、四月时开发出自己的第一款游戏，正是这款游戏，令我决定踏上独立开发者之路。一年过去了，第一款游戏达到它应有的盈利水平。然而这款游戏开发后的时间里，都没再取得另一款令自己满意的作品。直到今年的三、四月，我使用cocos2d-x开发出我的第一款文字游戏。
第一款游戏的传送门
第一款文字游戏的传送门
自从使用cocos2d-x后，发现自己爱上了这个引擎。它或许还不够强大和完善，但是使用它，可以体验编码的乐趣，还可以为我重拾C++这门技术（到底对C++有多么的执着啊），还能增进NDK和JNI的学习。恰恰满足我各种各样的追求。
这个第一款文字游戏，名字我取作Anagram Puzzle，其实这款游戏是参照RayWenderlich上的这篇教程来改写的，教程里使用的是iOS的UIKit编写，虽说原理相通，但是在改写过程中还是遇到不少折腾的地方。由于初次编写cocos2d-x游戏，所以错误难免百出，希望阅读者们高抬贵手，点到即止……废话不多说，马上开始coco2d-x之道~如何制作第一款文字游戏！
Anagram简介
Anagram是一种把单词或短语的字母顺序打乱，重新排列后变成一个新单词或短语的游戏。例如，单词cinema可以重新排列成iceman。游戏中就要求玩家进行你所提供单词或短语的重新排列。完成游戏的画面会如图所示：
在开发这个游戏过程中，会接触到以下这些知识：
MVC型的游戏结构
如何从文件配置加载级别
加载第三方字体
简单使用音乐音效
分离HUD层与游戏层
手势拖动及动画
Particle的效果
还有其他的一些cocos2d-x的基础知识，都会在开发过程中接触到。
初始化工程
首先最重要的当然是使用命令行来创建cocos2d-x工程，当然也有其他方法也可以创建工程，但是我认为掌握命令行来创建是必须的基本功。创建方法可以在这里找到。创建完成后各个平台的工程文件夹都有了。我们的主要工程文件夹是proj.android和proj.ios两个。整个开发过程，我使用Mac OS来开发，所以编码是在XCode上进行，而Android工程的编译则使用命令行，详细教程可以参考这里。
建立好工程后，先把所需的资源文件拷贝到Resource文件夹中。打开Xcode工程，目前Resource文件夹下还是原来的资源文件，通过右击Resource文件夹 -& Add Files to ...，把资源文件都加到工程里。编辑后工程会如图
1）加载级别配置文件
打开level1.plist，可以看到里面内容
有三个最顶端的key，分别是：
pointsPerTile: 每个单词填对后获得的分数。
timeToSolve: 解决这一关的时间（秒）。
anagrams: 是题目的列表，包含两个item，分别是原始的短语以及最后要拼出的短语。
level文件的介绍就到此为止，下面开始编写Level类，在Level.h中添加以下内容
class Level:public CCObject{
static Level * levelWithNum(int levelNum);
int mPointPerT
int mTimeToS
CCArray * pA
其中，三个变量对应level文件里的三个最顶端的item。还有一个初始化函数，是给外部调用初始化level文件。
现在，打开Level.cpp，实现levelWithNum函数
Level * Level::levelWithNum(int levelNum){
char fileName[50];
char fullPath[150];
sprintf(fileName,"level%d.plist",levelNum);
CCFileUtils::sharedFileUtils()-&fullPathFromRelativeFile(fileName,fullPath);
CCDictionary * pListDict = CCDictionary::createWithContentsOfFile(fileName);
if(pListDict == NULL){
CCLog("level config not found");
Level * l = new Level();
CCString * tempS
tempStr = dynamic_cast&CCString*&(pListDict-&objectForKey("pointsPerTile"));
l-&mPointPerTile = tempStr-&intValue();
tempStr = dynamic_cast&CCString*&(pListDict-&objectForKey("timeToSolve"));
l-&mTimeToSovle = tempStr-&intValue();
l-&pAnagrams = dynamic_cast&CCArray*&(pListDict-&objectForKey("anagrams"));
l-&pAnagrams-&retain();
这里首先用CCDictionary读出level文件中数值，然后就是读取出对应key里的值，并存储起来。
现在，打开主界面文件，默认是HelloWorldScene类，但是我改写成MainScene，其中MainScene.h是这样的
class MainScene : public cocos2d::CCLayer
~MainScene();
// Here's a difference. Method 'init' in cocos2d-x returns bool, instead of returning 'id' in cocos2d-iphone
virtual bool init();
// there's no 'id' in cpp, so we recommend returning the class instance pointer
static cocos2d::CCScene* scene();
// implement the "static node()" method manually
CREATE_FUNC(MainScene);
Level * pL
可见，增加了Level变量。在MainScene.cpp中的init函数，编写
pLevel = Level::levelWithNum(1);
当然，这里可以通过CCLog来打印出pLevel里的内容来看看，会得到如图所示
在MainScene里添加个新的函数
void dealRandomAnagram();
具体实现要这样
void MainScene::dealRandomAnagram(){
Common::random(0, pLevel-&pAnagrams-&count() - 1);
int randomIndex =
Common::random(0, pLevel-&pAnagrams-&count() - 1);
CCAssert((randomIndex &= 0 && randomIndex & pLevel-&pAnagrams-&count()),"error random index!");
CCArray * anagram = (CCArray*)pLevel-&pAnagrams-&objectAtIndex(randomIndex);
CCString * ana1 = (CCString*)anagram-&objectAtIndex(0);
CCString * ana2 = (CCString*)anagram-&objectAtIndex(1);
int ana1len = ana1-&length();
int ana2len = ana2-&length();
Common::random是我自己编写的，生成两个数值之间的随机数
int Common::random(int s,int e){
float i = CCRANDOM_0_1()*(e-s+1)+s;
return (int)i;
}这样就把初始状态的短语和最终状态的短语获取到了，把dealRandomAnagram函数添加到MainScene的init函数里，
pLevel = Level::levelWithNum(1);
dealRandomAnagram();
2）创建单词的View
在工程中新增一个继承于CCNode的类，名字叫做TileView，在TileView.h中添加以下代码
static TileView * initWithLetter(const char * l,float sideLen);
CCSprite * pS
其中initWithLetter是初始化函数，pSprite是显示的精灵，mLetter是对应的字母，mIsMatch表示结果是否已经配对上（就是找到字母所应该在的位置）。
在TileView.cpp里，添加以下代码
#include "TileView.h"
TileView * TileView::initWithLetter(const char * l, float sideLen){
TileView * tile = new TileView();
CCSprite * bg = CCSprite::create("tile.png");
tile-&addChild(bg);
tile-&pSprite =
float scale = sideLen / bg-&getContentSize().
bg-&setScale(scale);
char chLetter[2];
sprintf(chLetter,"%c",l[0] - 32);
CCLabelTTF * letter = CCLabelTTF::create(chLetter,"Arial",75 * scale);
letter-&setColor(ccWHITE);
tile-&addChild(letter);
tile-&mIsMatch =
tile-&mLetter = chLetter[0];
函数中，首先的是创建一个以tile.png为图案的精灵，然后创建图案上的字母
接下来就要在界面中显示出来了，在MainScene中添加
Level * pL
CCArray * pT
CCArray * pT
pTiles是TileView的数组，pTargets是TargetView的数组，其中TileView是放在底部给出的短语的各个单词，TargetView是目标短语的各个单词。在MainScene.cpp的dealRandomAnagram函数中继续添加代码
int ana1len = ana1-&length();
int ana2len = ana2-&length();
float tileSide = ceilf( Common::getCameraWith()*0.9 / (float)std::max(ana1len, ana2len) ) - kTileM
float xOffset = (Common::getCameraWith() - std::max(ana1len,ana2len) * (tileSide + kTileMargin)) / 2;
xOffset += tileSide/2;
此时，开始计算各个TileView的位置。首先，比较得出原始短语和目标短语中长度最长的，然后算出各个View所需的宽度tileSide，以及各个View之间的间隔xOffset
对了，不要忘了定义全局的空隙
#define kTileMargin 20
接着，就要创建我们的TileView了
pTiles = CCArray::createWithCapacity(ana1len);
const char * ana1Letter = ana1-&getCString();
for(int i = 0;i & ana1 i++){
char letter[3];
sprintf(letter,"%c",ana1Letter[i]);
if(letter[0] != ' '){
TileView * tile = TileView::initWithLetter(letter,tileSide);
tile-&setPosition(ccp(xOffset + i * (tileSide + kTileMargin),Common::getCameraHeight() / 4));
this-&addChild(tile);
pTiles-&addObject(tile);
pTiles-&retain();
创建方法比较简单，但是要注意的是，原始短语中可以会有空字符，空字符的地方需要留空。如图所示
3)单词View优化
方方正正的TileView看着有些拘谨，下面进行一些优化来让它们生动一些。在TileView中添加randomize函数
void TileView::randomize(){
float rotation = Common::random(0,50) /(float)100 - 0.2;
this-&setRotation(rotation * 10);
int yOffset = Common::random(0,10);
this-&setPositionY(this-&getPositionY() + yOffset);
让TileView稍作旋转和偏移，然后在MainScene的dealRandomAnagram函数中的 this-&addChild(tile); 语句后添加下面语句
tile-&randomize();
4）添加TargetView
有了原始短语，下面就要开始创建目标短语的View了。对比TileView，TargetView要相对简单一些。因为它是固定位置及不需要显示字母。TargetView.h中添加以下代码：
class TargetView : public CCNode
TargetView(void);
~TargetView(void);
static TargetView * initWithLetter(const char * l,float sideLen);
CCSprite * pS
与TileView相类似的，一个初始化函数，三个私有变量。与TileView的是一一对应。
TargetView * TargetView::initWithLetter(const char * l, float sideLen){
TargetView * tile = new TargetView();
CCSprite * bg = CCSprite::create("slot.png");
tile-&addChild(bg);
tile-&pSprite =
float scale = sideLen / bg-&getContentSize().
bg-&setScale(scale);
char chLetter[2];
sprintf(chLetter,"%c",l[0] - 32);
CCLabelTTF * letter = CCLabelTTF::create(chLetter,"Arial",78 * scale);
letter-&setColor(ccWHITE);
tile-&addChild(letter);*/
tile-&mIsMatch =
tile-&mLetter = chLetter[0];
TargetView的initWithLetter函数中，注释的语句是为显示一下结果，但是在实际游戏中是不显示TargetView上的字母。
接下来，就要把TargetView显示到场景上了，找到MainScene的dealRandomAnagram方法，在末尾处添加上以下代码
pTargets = CCArray::createWithCapacity(ana2len);
const char * ana2Letter = ana2-&getCString();
for(int i = 0;i & ana2 i++){
char letter[3];
sprintf(letter,"%c",ana2Letter[i]);
if(letter[0] != ' '){
TargetView * target = TargetView::initWithLetter(letter,tileSide);
target-&setPosition(ccp(xOffset + i * (tileSide + kTileMargin),Common::getCameraHeight() / 4 * 3));
this-&addChild(target);
pTargets-&addObject(target);
pTargets-&retain();
是否可看到TargetView也出来，这里，我们就完成了AnagramPuzzle的第一部分开发工作，最后上个截图
感觉还不错吧，轻松的把所需要的游戏界面展示出来。这次接触到cocos2d-x知识还是比较少，主要是怎样往主场景中添加内容，怎样创建精灵。下一次，我们就要编写一些有点挑战性的东西了，比如怎么拖动精灵，怎么判断是否摆在正确的位置，怎么进行倒计时等等，真正的Code乐趣快要上场！请听下回分解。
leetCode答题报告5道题(八)
leetCode解题报告5道题(八)
Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *
TreeLinkNode *
TreeLinkNode *
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
After calling your function, the tree should look like:
2 -& 3 -& NULL
4-&5-&6-&7 -& NULL
题意给我们一棵“完全二叉树”，让我们把二叉树中每个结点的next域根据如例子那样给它赋值。
看到这个题目，我们的第一反应可能是
1、层次遍历二叉树（这样要用到一个queue队列，并不满足题意的对空间的要求）
2、递归方法(这个是可以的)
但因为这道题目很特殊，二叉树是一棵完全二叉树，所以我们现在要用循环迭代的方法来求解这道题。
具体看代码中的注释
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
TreeLinkNode left, right,
TreeLinkNode(int x) { val = }
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
//每一层的最左边的那个结点
TreeLinkNode leftNode =
while (leftNode != null){
//把同一层的结点用next串起来
TreeLinkNode nowNode = leftN
while (nowNode != null){
//左孩子的next域指向右孩子
if (nowNode.left != null){
nowNode.left.next = nowNode.
//如果一个结点nowNode的右孩子不为空，却这个结点nowNode还有兄弟的话
//那么结点nowNode的右孩子的next域要指向兄弟结点的left域
if (nowNode.right != null && nowNode.next != null){
nowNode.right.next = nowNode.next.
//处理结点nowNode的右兄弟(如果为null则不处理)
nowNode = nowNode.
leftNode = leftNode.
Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
You may only use constant extra space.
For example,
Given the following binary tree,
After calling your function, the tree should look like:
2 -& 3 -& NULL
4-& 5 -& 7 -& NULL
这题跟上面那个题目的区别在于条件“所给二叉树并不一定是完全二叉树”了，这样子，在上一题的基础上，我们需要去找到每一层的第一个结点，找到这个第一个满足的结点，其他的思路跟上一题是一样的。
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
TreeLinkNode left, right,
TreeLinkNode(int x) { val = }
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
//每一层的第一个结点
TreeLinkNode firstNode =
while (firstNode != null){
TreeLinkNode nowNode = firstN
//找到第一个不为null的结点.
TreeLinkNode tempNode =
while (nowNode != null){
if (nowNode.left != null){
tempNode = nowNode.
if (nowNode.right != null){
tempNode = nowNode.
nowNode = nowNode.
//下一层要开始的第一个parent结点
firstNode = tempN
//把这一层的所有结点用next域串起来
while (nowNode != null){
if (nowNode.left != null && nowNode.left != tempNode){
tempNode.next = nowNode.
tempNode = nowNode.
if (nowNode.right != null && nowNode.right != tempNode){
tempNode.next = nowNode.
tempNode = nowNode.
nowNode = nowNode.
Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
[1,3,3,1],
[1,4,6,4,1]
public class Solution {
public ArrayList&ArrayList&Integer&& generate(int numRows) {
ArrayList&ArrayList&Integer&& arrays = new ArrayList&ArrayList&Integer&&();
for(int i=0; i&numR ++i){
ArrayList&Integer& list = new ArrayList&Integer&();
for (int j=0; j&=i; ++j){
if (j == 0 || j == i){
list.add(1);
ArrayList&Integer& temp = arrays.get(i-1);
int left = temp.get(j-1);
int right = temp.get(j);
list.add(left+right);
arrays.add(list);
题目四：Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Could you optimize your algorithm to use only O(k) extra space?
这道题目和上面那道题目的思路基本上是一样的arrays[i] = arrays[i] + arrays[i-1].
但是由于题目要求给我们的空间就O(k)，也就是说当我们想改变下一行的值arrays[i]的话我们必须从中间向左边改变，然后右边用r-i 来对称设置值，程序一开始我们先设置出k个位置的值，每个值都为1。
比如 我们要求的K=4 则
[1,1,1,1,1]
r=1： [1,1,1,1,1];
r=2：[1,2,1,1,1];
r=3：[1,3,3,1,1];
k=4 ：[1,4,6,4,1]
大家看看我的代码，如果我们不用
“从中间向左边改变，然后右边用r-i 来对称设置值”这样的话，会出现什么问题！
public class Solution {
public ArrayList&Integer& getRow(int rowIndex) {
//csdn : http://blog.csdn.net/ljphhj
ArrayList&Integer& list = new ArrayList&Integer&();
for (int i=0; i&=rowI ++i){
list.add(1);
for(int i=0; i&=rowI ++i){
//从中间i/2往左移动设置
//避免你从左向中间时，你计算的当前值会影响到下一个位的计算
for (int j=i/2; j&=0; --j){
if (j != 0 && j != i){
int left = list.get(j-1);
int right = list.get(j);
list.set(j, left+right);//设置值
list.set(i-j, left+right);//对称另一边的值
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 =
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
这题为典型的DP问题，求最短路径长度，也可以用递归的方法来求.
设用一个数组arr[i][j] 来存储这个三角形。
主要思想：动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。
则从三角形的最后一行向上求出每个点对应的最短路径，并把值存下来，最终arr[0][0]就为我们要得到的值
最后一行的arr[3][]
= {4,1,8,3};
则当到倒数第二行时，每个结点arr[2][i] 的最短路径为 arr[2][i] =
min{arr[2][i] + arr[2+1][i]
arr[2][i] + arr[2+1][i+1] };
这样我们就可以得到倒数第二行的所有点到叶子的最短路径长度了，一直往上，直到第一行就得到了最后的结果arr[0][0]
public class Solution {
public int minimumTotal(ArrayList&ArrayList&Integer&& triangle) {
int len1 = triangle.size();
//从倒数第二行起始
for (int i=len1-2; i&=0; i--){
ArrayList&Integer& listUp = triangle.get(i);//当前行
ArrayList&Integer& listDown = triangle.get(i+1);//当前行的下一行
for (int j=0; j&listUp.size(); ++j){
int left = listDown.get(j);
int right = listDown.get(j+1);
int min = left & right ? right+listUp.get(j) : left+listUp.get(j);
listUp.set(j, min);
return triangle.get(0).get(0);
如果您想提高自己的技术水平，欢迎加入本站官方1号QQ群：&&，&&2号QQ群：，在群里结识技术精英和交流技术^_^
本站联系邮箱：