工作中常用工具

1.DSYM 工具

1.查看 xx.app 文件的 UUID，terminal 中输入命令 ：

dwarfdump –uuid xx.app/xx (xx代表你的项目名)

2.查看 xx.app.dSYM 文件的 UUID ，在 terminal 中输入命令：
dwarfdump –uuid xx.app.dSYM

3.crash 文件内第一行 Incident Identifier 就是该 crash 文件的 UUID。

2.分析iOS Crash文件

先执行

1

sudo cp /Applications/Xcode.app/Contents/SharedFrameworks/DTDeviceKitBase.framework/Versions/A/Resources/symbolicatecrash /usr/local/bin/

再执行

1

symbolicatecrash appName.crash appName.app > appName.log

3.cocosPods主要命令

pod install --verbose --no-repo-update
pod update --verbose --no-repo-update

4.RN bundle 打包

react-native bundle
–entry-file index.ios.js
–platform ios
–dev true
–bundle-output ./output/index.ios.bundle
–assets-dest ./output/imgs

5.打包.a文件

lipo -create /Users/Travis/Desktop/libIMIUI.d.a /Users/Travis/Desktop/libIMIUI.s.a -output /Users/Travis/Desktop/libIMIUI.a

6 SSH 公钥生成

1
2

$ ssh-keygen
$ cat ~/.ssh/id_rsa.pub

7 显示隐藏文件(MAC)

1

defaults write com.apple.finder AppleShowAllFiles -bool true

git 命令

下面的$project_root代表工程根目录

• 进入工程目录 cd $project_root
• 初始化git仓库 git init
• 添加文件到仓库 git add .
• 提交代码到仓库 git commit -m 'init commit'
• 链接到 git server git remote add origin git@example.com:namespace/projectname.git
• push代码到服务器 git push origin master
• 我要把刚才的工程再clone到本地:git clone git@example.com:namespace/projectname.git

查看、添加、提交、删除、找回，重置修改文件

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

git help <command>  # 显示command的help  
git show            # 显示某次提交的内容  
git show $id  
   
git co  -- <file>   # 抛弃工作区修改  
git co  .           # 抛弃工作区修改  
   
git add <file>      # 将工作文件修改提交到本地暂存区  
git add .           # 将所有修改过的工作文件提交暂存区  
   
git rm <file>       # 从版本库中删除文件  
git rm <file> --cached  # 从版本库中删除文件，但不删除文件  
   
git reset <file>    # 从暂存区恢复到工作文件  
git reset -- .      # 从暂存区恢复到工作文件  
git reset --hard    # 恢复最近一次提交过的状态，即放弃上次提交后的所有本次修改  
   
git ci <file>  
git ci .  
git ci -a           # 将git add, git rm和git ci等操作都合并在一起做  
git ci -am "some comments"  
git ci --amend      # 修改最后一次提交记录  
   
git revert <$id>    # 恢复某次提交的状态，恢复动作本身也创建了一次提交对象  
git revert HEAD     # 恢复最后一次提交的状态

查看文件diff

1
2
3
4
5
6
7

git diff <file>     # 比较当前文件和暂存区文件差异  
git diff  
git diff <$id1> <$id2>   # 比较两次提交之间的差异  
git diff <branch1>..<branch2> # 在两个分支之间比较  
git diff --staged   # 比较暂存区和版本库差异  
git diff --cached   # 比较暂存区和版本库差异  
git diff --stat     # 仅仅比较统计信息

查看提交记录

1
2
3
4
5

git log  
git log <file>      # 查看该文件每次提交记录  
git log -p <file>   # 查看每次详细修改内容的diff  
git log -p -2       # 查看最近两次详细修改内容的diff  
git log --stat      #查看提交统计信息

取得Git仓库

1
2
3
4
5
6
7
8
9
10
11

#初始化一个版本仓库  
git init  
  
#Clone远程版本库  
git clone git@xbc.me:wordpress.git  
  
#添加远程版本库origin，语法为 git remote add [shortname] [url]  
git remote add origin git@xbc.me:wordpress.git  
  
#查看远程仓库  
git remote -v

提交你的修改

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

#添加当前修改的文件到暂存区  
git add .  
  
#如果你自动追踪文件，包括你已经手动删除的，状态为Deleted的文件  
git add -u  
  
#提交你的修改  
git commit –m "你的注释"  
  
#推送你的更新到远程服务器,语法为 git push [远程名] [本地分支]:[远程分支]  
git push origin master  
  
#查看文件状态  
git status  
  
#跟踪新文件  
git add readme.txt  
  
#从当前跟踪列表移除文件，并完全删除  
git rm readme.txt  
  
#仅在暂存区删除，保留文件在当前目录，不再跟踪  
git rm –cached readme.txt  
  
#重命名文件  
git mv reademe.txt readme  
  
#查看提交的历史记录  
git log  
  
#修改最后一次提交注释的，利用–amend参数  
git commit --amend  
  
#忘记提交某些修改，下面的三条命令只会得到一个提交。  
git commit –m "add readme.txt"  
git add readme_forgotten  
git commit –amend  
  
#假设你已经使用git add .，将修改过的文件a、b加到暂存区  
  
#现在你只想提交a文件，不想提交b文件，应该这样  
git reset HEAD b  
  
#取消对文件的修改  
git checkout –- readme.txt

查看、切换、创建和删除分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

git branch -r           # 查看远程分支  
git br <new_branch> # 创建新的分支  
git br -v           # 查看各个分支最后提交信息  
git br --merged     # 查看已经被合并到当前分支的分支  
git br --no-merged  # 查看尚未被合并到当前分支的分支  
   
git checkout <branch>     # 切换到某个分支  
git co -b <new_branch> # 创建新的分支，并且切换过去  
git co -b <new_branch> <branch>  # 基于branch创建新的new_branch  
   
git co $id          # 把某次历史提交记录checkout出来，但无分支信息，切换到其他分支会自动删除  
git co $id -b <new_branch>  # 把某次历史提交记录checkout出来，创建成一个分支  
   
git br -d <branch>  # 删除某个分支  
git br -D <branch>  # 强制删除某个分支 (未被合并的分支被删除的时候需要强制)

分支合并和rebase

1
2
3
4
5

git merge <branch>               # 将branch分支合并到当前分支  
git merge origin/master --no-ff  # 不要Fast-Foward合并，这样可以生成merge提交  
   
git rebase master <branch>       # 将master rebase到branch，相当于：  
git co <branch> && git rebase master && git co master && git merge <branch>

Git远程分支管理

1
2
3
4
5
6
7
8
9
10
11
12
13

git pull                         # 抓取远程仓库所有分支更新并合并到本地  
git pull --no-ff                 # 抓取远程仓库所有分支更新并合并到本地，不要快进合并  
git fetch origin                 # 抓取远程仓库更新  
git merge origin/master          # 将远程主分支合并到本地当前分支  
git co --track origin/branch     # 跟踪某个远程分支创建相应的本地分支  
git co -b <local_branch> origin/<remote_branch>  # 基于远程分支创建本地分支，功能同上  
   
git push                         # push所有分支  
git push origin master           # 将本地主分支推到远程主分支  
git push -u origin master        # 将本地主分支推到远程(如无远程主分支则创建，用于初始化远程仓库)  
git push origin <local_branch>   # 创建远程分支， origin是远程仓库名  
git push origin <local_branch>:<remote_branch>  # 创建远程分支  
git push origin :<remote_branch>  #先删除本地分支(git br -d <branch>)，然后再push删除远程分支

基本的分支管理

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

#创建一个分支  
git branch iss53  
  
#切换工作目录到iss53  
git chekcout iss53  
  
#将上面的命令合在一起，创建iss53分支并切换到iss53  
git chekcout –b iss53  
  
#合并iss53分支，当前工作目录为master  
git merge iss53  
  
#合并完成后，没有出现冲突，删除iss53分支  
git branch –d iss53  
  
#拉去远程仓库的数据，语法为 git fetch [remote-name]  
git fetch  
  
#fetch 会拉去最新的远程仓库数据，但不会自动到当前目录下，要自动合并  
git pull  
  
#查看远程仓库的信息  
git remote show origin  
  
#建立本地的dev分支追踪远程仓库的develop分支  
git checkout –b dev origin/develop

Git远程仓库管理

1
2
3
4
5

git remote -v                    # 查看远程服务器地址和仓库名称  
git remote show origin           # 查看远程服务器仓库状态  
git remote add origin git@ github:robbin/robbin_site.git         # 添加远程仓库地址  
git remote set-url origin git@ github.com:robbin/robbin_site.git # 设置远程仓库地址(用于修改远程仓库地址)  
git remote rm <repository>       # 删除远程仓库

创建远程仓库

1
2
3
4
5
6
7
8
9

git clone --bare robbin_site robbin_site.git  # 用带版本的项目创建纯版本仓库  
scp -r my_project.git git@ git.csdn.net:~      # 将纯仓库上传到服务器上  
   
mkdir robbin_site.git && cd robbin_site.git && git --bare init # 在服务器创建纯仓库  
git remote add origin git@ github.com:robbin/robbin_site.git    # 设置远程仓库地址  
git push -u origin master                                      # 客户端首次提交  
git push -u origin develop  # 首次将本地develop分支提交到远程develop分支，并且track  
   
git remote set-head origin master   # 设置远程仓库的HEAD指向master分支

git submodule的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

添加
为当前工程添加submodule，命令如下：

git submodule add 仓库地址 路径
即
git submodule add https://android.googlesource.com/platform/frameworks/volley extras
命令执行完成，会在当前工程根路径下生成一个名为“.gitmodules”的文件，其中记录了子模块的信息。添加完成以后，再将子模块所在的文件夹添加到工程中即可。

更新
如果过了一段时间volley库有更新，这时候我们的app也需要更新，命令如下：

git submodule update
删除
ubmodule的删除稍微麻烦点：首先，要在“.gitmodules”文件中删除相应配置信息。然后，执行“git rm –cached ”命令将子模块所在的文件从git中删除。

下载的工程带有submodule
当使用git clone下来的工程中带有submodule时，初始的时候，submodule的内容并不会自动下载下来的，此时，只需执行如下命令：

git submodule update --init --recursive
即可将子模块内容下载下来后工程才不会缺少相应的文件。

子模块拉取最新的代码

1

git submodule foreach --recursive git pull origin master

给出一个非负整数数组，你最初定位在数组的第一个位置。　　　

数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　　

判断你是否能到达数组的最后一个位置。

样例
A = [2,3,1,1,4]，返回 true.

A = [3,2,1,0,4]，返回 false.

注意
这个问题有两个方法，一个是贪心和 动态规划。

贪心方法时间复杂度为O（N）。

动态规划方法的时间复杂度为为O（n^2）。

我们手动设置小型数据集，使大家阔以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。

分析：

一：动态规划

1

canJumps[i] = (canJumps[j] && (j + maxSteps[j] >= i));(0 <= j < i)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
   public boolean canJump(int[] maxSteps) {
        if(null == maxSteps || maxSteps.length <= 0)
        	return false;
        
        boolean canJumps[] = new boolean[maxSteps.length];
        canJumps[0] = true; 
        for(int i = 1;i < maxSteps.length;i++)
        { 
        	for(int j = 0;j < i;j++)
        	{
        		if(canJumps[i])
        			break;
        		canJumps[i] = (canJumps[j] && (j + maxSteps[j] >= i));
        	}
        }
        return canJumps[maxSteps.length - 1];
    }
}

二：贪心做法

自上而下，依此寻找可以一步跳跃到该点的上一个点，且上个点离该点最远,由于是自上而下，所以当当满足最后meet_index == 0时，表示可以满足条件。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
  public boolean canJump(int[] maxSteps) {
        if(null == maxSteps || maxSteps.length <= 0)
        	return false;
        int meetIndex = maxSteps.length - 1;
        for(int i = maxSteps.length - 1;i >= 0;i--)
        {
        	if(i + maxSteps[i] >= meetIndex)
        	{
        		meetIndex = i;
        	}
        }
        return meetIndex == 0;
    }
}

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。

样例
给定 [3, 8, 4], 返回 8.

挑战
O(n) 时间复杂度 且 O(1) 存储。

分析:

定义dp[i]表示打劫第i个房间为止所获得的最大收益，而dp[i]的值只与dp[i-2] 和dp[i-3]有关 并且 dp[i] = A[i] + max(dp[i-2],dp[i-3])

当求解所有的A[i]后，需要对最后两个dp[len-1] dp[len-2] 取最大值作为最后的答案,因为存储的且 O(1) ,又dp关系仅限于4个数字之间，因此只用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

public class Solution {
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    public long houseRobber(int[] houseMoneys) {
		if(null == houseMoneys || houseMoneys.length <= 0)
			return 0;
		if(houseMoneys.length == 1)
			return houseMoneys[0];
		if(houseMoneys.length == 2)
		{
			return Math.max(houseMoneys[0], houseMoneys[1]);
		}
		
		if(houseMoneys.length == 3)
		{
			return Math.max(houseMoneys[1], houseMoneys[0] + houseMoneys[2]);
		}
		
		long[] max = new long[4];
		max[0] = houseMoneys[0];
		max[1] = houseMoneys[1];
		max[2] = Math.max(houseMoneys[1], houseMoneys[0] + houseMoneys[2]);
		
		for(int i = 3;i < houseMoneys.length;i++)
		{
			max[3] = houseMoneys[i] + Math.max(max[0], max[1]);
			if(i == houseMoneys.length - 1)
				continue;
			max[0] = max[1];
			max[1] = max[2];
			max[2] = max[3];
		}
		
		return Math.max(max[3], max[2]);
	}
}

1.监听加载jsbundle异常的处理

模拟情况：合并增量后jsbundle文件出现部分错误
调试发现当加载jsbundle出现异常时，RN模块RCTBatchedBridge.m中如下代码会执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

- (void)stopLoadingWithError:(NSError *)error
{
  RCTAssertMainThread();

  if (!self.isValid || !self.loading) {
    return;
  }

  _loading = NO;

  [[NSNotificationCenter defaultCenter] postNotificationName:RCTJavaScriptDidFailToLoadNotification
                                                      object:_parentBridge
                                                    userInfo:@{@"bridge": self, @"error": error}];
  RCTFatal(error);
}

因此native模块加入监听处理RCTJavaScriptDidFailToLoadNotification通知的方法即可:

1
2
3
4
5
6

[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(backToPreVersion) name:RCTJavaScriptDidFailToLoadNotification object:nil];

- (BOOL)backToPreVersion
{
 // rollback
}

2.存在加载jsbundle正常，但是RN代码执行就Crash的问题的处理方案（参考安卓的处理）

模拟情况：如果RN代码存在Crash bug
定位代码Crash时代码会执行到RCTAssert.m中如下语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void RCTFatal(NSError *error)
{
  _RCTLogNativeInternal(RCTLogLevelFatal, NULL, 0, @"%@", [error localizedDescription]);

  RCTFatalHandler fatalHandler = RCTGetFatalHandler();
  if (fatalHandler) {
    fatalHandler(error);
  } else {

#if DEBUG
    @try {
#endif
      NSString *name = [NSString stringWithFormat:@"%@: %@", RCTFatalExceptionName, [error localizedDescription]];
      NSString *message = RCTFormatError([error localizedDescription], error.userInfo[RCTJSStackTraceKey], 75);
      [NSException raise:name format:@"%@", message];
#if DEBUG
    } @catch (NSException *e) {
      
    }
#endif
  }
}

测试DEBUG模式下RN抛出异常后被catch，不会导致Crash,因此为保证RELEASE版本下程序不会Crash，依旧能更新增量包，因为可以将#if DEBUG的选项去掉，不让程序Crash。

前言

整理之前iOS开发中遇到的问题，集合一下。很大部分来自StackOverFlow。

问题1:Xcode release下调试报错[Project Name] was compiled with optimization - stepping may behave oddly; variables may not be available

解决：Build Setting中的optimization level release改为与debug一样的模式。

问题2:Xcode代码中类和方法等字体变黑文件失去关联symbol not found

解决：Xcode用得久了，代码中类和方法等字体变黑文件失去关联symbol not found，连智能提示有时候都没有，这里是因为工程索引文件被破坏导致，可通过以下方法解决：

一、Organizer -> Projects ->把所有工程中的Derived Data 删除Delete掉。

二、进入~/Library/Developer/Xcode/DerivedData 这个文件夹，把里面相关工程的文件夹删掉。

问题3:提交SVN Target没有显示出来

解决：需要勾选Autocreate schemes

问题4:property follows cocoa naming convention for returning ‘owned’ objects

注意：

• 代码中不能使用retain, release, retain, autorelease
• 不重载dealloc（如果是释放对象内存以外的处理，是可以重载该函数的，但是不能调用[super dealloc]）
• 不能使用NSAllocateObject, NSDeallocateObject
• 不能在C结构体中使用对象指针
• id与void *间的如果cast时需要用特定的方法（__bridge关键字）
• 不能使用NSAutoReleasePool、而需要@autoreleasepool块
• 不能使用“new”开始的属性名称 （如果使用会有下面的编译错误”Property’s synthesized getter follows Cocoa naming convention for returning ‘owned’ objects”）

问题5:”No previous prototype for function” warning警告错误

解决：warning:No previous prototype for function “randomPoint”。如何取消这个警告错误呢？方法尝试了这两种都可以：

• 1.方法上加修饰符static

• 2.或者Project-Info -> TARGETS ->Build Settings -> LLVM GCC4.2 - Warnings组 -> Missing Function Prototypes Yes->No

问题6:Code signing is required for product type ‘Application’ in SDK ‘iOS5.1’

解决:One possible solution which works for me:

Search “code sign” in Build settings
Change everything in code signing identity to “iOS developer”, which are “Don’t code sign” originally.

问题7:The common causes for “Undefined symbols for architecture armv7”

• You import a header and do not link against the correct library. This is common, especially for headers for libraries like QuartzCore since it is not included in projects by default. To resolve:

• Add the correct libraries in the Link Binary With Libraries section of the Build Phases.

• If you want to add a library outside of the default search path you can include the path in the Library Search Paths value in the Build Settings and add
  -l{library_name_without_lib_and_suffix} (eg. for libz.a use -lz) to the Other Linker Flags section of Build Settings.

• You copy files into your project but forgot to check the target to add the files to. To resolve:

• Open the Build Phases for the correct target, expand Compile Sources and add the missing .m files. If this is your issue please upvote Cortex’s answer below as well.

• You include a static library that is built for another architecture like i386, the simulator on your host machine. To resolve:

• If you have multiple library files from your libraries vendor to include in the project you need to include the one for the simulator (i386) and the one for the device (armv7 for example).

• Optionally, you could create a fat static library that contains both architectures.

问题8:’_compress2’, referenced from:+[UMANUtil deflatedDataPrefixedWith:level:source:] in libMobClickLibrary.a(UMANUtil.o)ld: symbol(s) not found for architecture x86_64clang: error: linker command failed with exit code 1 (use -v to see invocation)

解决：在Other Linker Flags里加入-lz

问题9:objc_msgSend()报错Too many arguments to function call ,expected 0,have3

解决：Build Setting–> Apple LLVM 6.0 - Preprocessing–> Enable Strict Checking of objc_msgSend Calls 改为 NO

问题10:dyld: Library not loaded: /System/Library/Frameworks/Social.framework/SocialReferenced from: /var/mobile/Applications/00D3E0A7-4FF6-451E-B11C-87D7A189F425/sample.app/sample Reason: image not found

解决：把Build Phases 里Social.framework后边的选项修改成为Optional就可以了

###问题11:Xcode release下调试报错[Project Name] was compiled with optimization - stepping may behave oddly; variables may not be available

解决：Build Setting中的optimization level release改为与debug一样的模式。

问题12：is invalid in c99

解决: build setting -> c language dialect -> GNU89

问题13: Xcode build .c文件失败

原因：对应的.pch文件中,没有针对Objecttive－C的特殊编译，是统一指定的，建议加入，

#ifdef OBJC

#endif

环绕 #import *

前言

近期在学习React Native 特开始着手遇到问题的解决方案，有问题及时留言，谢谢！！！

问题1：run 项目时遇到命令窗口出现：TypeError: Cannot read property ‘root’ of null

解决：打开终端，输入 brew update成功后再输入brew upgrade watchman关掉Xcode重新运行即可。

问题2:native 的(RCTResponseSenderBlock)callback注意回调的参数设置。

例如：callback(@[@”hello”]);

js端：

1
2
3
4
5

callback: function(ret) {
	if (ret[0]) {
		console.log(ret[0]);
	}
},

打印结果为：h,如果改为callback(@[@[@”hello”]])打印结果才为hello。

问题3:iOS项目jsbundle打包，release包的js代码是混淆的。可以更改/Users/arnold/HFRCTUpdaterDemo/node_modules/react-native/local-cli/bundle/buildBundle.js 下的minify的选项。

临时方案：直接更改../node_modules/react-native/packager/react-native-xcode.sh 中的–dev true即可,注意该命令的执行必须在ios的文件夹中。

问题4:iOS和安卓对图片处理的区别。

iOS:
this.setState({source}),更改Image的资源。

安卓:
this.setNativeProps({src:’’}),更改资源。

问题5:native 的(RCTResponseSenderBlock)callback注意回调的参数设置。

例如：callback(@[@”hello”]);

js端：

1
2
3
4
5

callback: function(ret) {
			if (ret[0]) {
				console.log(ret[0]);
			}
		},

打印结果为：h,如果改为callback(@[@[@”hello”]])打印结果才为hello。

问题6:react native 调用组件报错：invalid directory /Users/node_modules/

解决：注意@providesModule 的重要性

问题7:NPM throws error “couldn’t read dependencies”?

解决:sudo npm install -g npm

问题8: No compatible version found: react-native-viewpager@^1.2.1

解决:

1
2
3

sudo npm cache clean -f
sudo npm install -g n
sudo n stable

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法：

插入一个字符
删除一个字符
替换一个字符

样例
给出 work1=”mart” 和 work2=”karma”

返回 3

分析:minSteps[i][j]表示word1的前i个字符改为word2的前j个字符的最少操作数，因此有转移方程
minSteps[i][j] =
{
minSteps[i - 1][j - 1];(word1[i] == wrod2[j])
min(minSteps[i - 1][j - 1],minSteps[i][j - 1],minSteps[i - 1][j]);(word1[i] != wrod2[j])
}

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 {
	public int minDistance(String word1, String word2) {
		if(null == word1 || null == word2)
			return 0;
		
		int[][] minSteps = new int[word1.length() + 1][word2.length() + 1];
		for(int i = 0;i <= word1.length();i++)
		{
			minSteps[i][0] = i;
		}
		
		for(int i = 0;i <= word2.length();i++)
		{
			minSteps[0][i] = i;
		}
		
		for(int i = 1;i <= word1.length();i++)
		{
			for(int j = 1;j <= word2.length();j++)
			{
				if(word1.charAt(i - 1) == word2.charAt(j - 1))
				{
					minSteps[i][j] = minSteps[i - 1][j - 1];
				}
				else
				{
					minSteps[i][j] = Math.min(minSteps[i - 1][j - 1], Math.min(minSteps[i - 1][j], minSteps[i][j - 1])) + 1;
				}
			}
		}
		return minSteps[word1.length()][word2.length()];
	}
};

给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。

子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
样例
给出S = “rabbbit”, T = “rabbit”

返回 3

分析：这里我们可以用f(i,j)表示S中前i个字符串中，T的前j个字符出现的次数，不管S[i]和T[j]相不相等，首先f(i,j)=f(i-1,j)，其次要是S[i]==T[j]的话，f(i,j) = f(i-1,j)+f(i-1,j-1),可以看到，i的状态只与i-1有关，于是可以用滚动数组来进行优化。代码类似01背包。

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

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
   public int numDistinct(String S, String T) {
		if(null == S || null == T)
			return 0;
		// commons 表示S中的前i个字符包含T的前j个字符的个数
		int[][] commons = new int[S.length() + 1][T.length() + 1];
		for(int i = 0;i <= S.length();i++)
		{
			commons[i][0] = 1;
		}
		for(int i = 1;i <= S.length();i++)
		{
			for(int j = 1;j <= T.length();j++)
			{
				
				if(S.charAt(i - 1) != T.charAt(j - 1))
				{
					// 不包含S中的第i个
					commons[i][j] = commons[i - 1][j];
				}
				else
				{
					// dp思想，匹配结果分为包含S中的第i个与不包含第i个两种
					commons[i][j] = commons[i - 1][j - 1] +  commons[i - 1][j];
				}
			}
		}		
		return commons[S.length()][T.length()];
	}
}

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定 第一个玩家 是输还是赢？

样例
n = 1, 返回 true.

n = 2, 返回 true.

n = 3, 返回 false.

n = 4, 返回 true.

n = 5, 返回 true.

挑战
O(1) 时间复杂度且O(1) 存储。

分析：博弈的思想

1
2
3
4
5
6
7
8
9

public class Solution {
    /**
     * @param n: an integer
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        return !(n % 3 == 0);
    }
}