老师你好，买了你这门数据结构，算法和leetcode，我是转专业有工作经验的，为了补基础现在一边上课一边自己刷leetcode
来源：2-2 二次封装属于我们自己的数组
慕数据3866775
2018-07-21
我看到有人列了刷题的这几个阶段
1. 不知道怎么刷题，对很多概念比如Big O， DP都陌生。每天纠结到底是看那个算法书/资料入门快。
2. 在一个良好的IDE里，做Medium题目只要愿意想一般都能做出来，做不出来看答案也就懂了。Hard也能做出不少。除了有些复杂算法还在消化中，算法上基本已经入门。但脱离IDE写代码，就有点发怵。函数signature甚至函数名都老记错。搞个string操作还得Google一下API。非常依赖自动补全。很多新人以及多年经验的老人，可能都处于这个阶段。
3. 除了偶尔遇到个Hard题得想很久，基本平时刷LC非常comfortable。同时能非常comfortable的在白板或者LC等网站的网页简单IDE里写代码。写代码过程中不需要Google函数用法。不依赖自动补全。而且甚至觉着这么写比在IDE里还舒服。
4. 在3的基础上，一般题目都是20分钟一道，写完基本扫一下一检查就可以bug-free。Hard题噼里啪啦码一堆，不管逻辑再混乱，心里非常清楚自己码的是什么，复杂度多少，有没有优化潜力。且非常自信自己码的是对的。对于一次提交就AC是自己的基本要求。对参加LC contest（contest里都要求一次提交就AC，否则罚时）等业余竞赛比较comfortable。
我现在显然是2到3之间，现在在传统公司做码农，为了去一个一流互联网公司在努力；但是算法一直很虚，虽然不停地学习但是有好多基础的东西也不牢固，我上这个课的时候听你说可以来问你算法题的问题，于是就厚着脸皮来问了，这个我google了很多但是可能太基础了并没有有人说清楚：
leetcode第389题 - Find the Difference
你看我的解法
整个题用异或来找到多出来的那个字符，整体没问题；但我想不明白的是为什么第四行ch初始值一定要是多一个字符那个字符串的最后一个字符，为什么不能是倒数第二个或者就正数第一个（结果是错的），这个关键点在哪里？比如两个字符串"abcd"和"ebadc"，结果是'e'，那初始值为c到底起到了什么作用，不都是a^b^b=a这个原理吗？
同样的，这个做法把char可以用数字来表示，两个String的每个字符相减然后多余数字转换成char就是缺少的那个字符：
这个办法同样不明白为什么为什么charCode初始值得是较长字符串的最后一位字符，初始值是别的字符就会得到错误答案，我去IDE debug了还是没明白规律是怎么样的。
下面这种办法我就明白的，初始值为空白' '，然后直接从左到右异或就行了。
请老师解答一下前面两个解法的初始值应该怎么去理解，非常感谢！
1回答
-
哈哈：）不用觉得自己脸皮厚，这个可既然说可以答疑Leetcode的所有问题，就是可以：）尤其像你把问题描述的这么清晰，非常欢迎。可见素质极高，继续努力，前途无量：）
说回你的问题。
其实很简单，关键是下面的那重循环。以你给的第一个Solution为例，下面的循环是从0到len-1访问每一个s[i]和t[i]，注意：i这个索引同时作用在了s和t身上。
所以，想象一下，假设s有5个元素，t有6个元素：
index 0 1 2 3 4 s: s0 s1 s2 s3 s4 t: t0 t1 t2 t3 t4 t5
你给出的解法相当于就是首先让ch=t5，然后，就不用考虑t5了！之后，可以把s和t看作是两个同样长度为5的字符串。我们在for循环中，就是以for i from 0 to 4，每次同时处理s[i]和t[i]了：）
想象一下，如果你让ch初始为t0，为了把s和t的所有元素都扫描遍，就不能只写一个循环了，需要写两个循环：）因为这两个循环不统一。理解一下下面的代码，我让ch初始值为t0，也可以AC：）
class Solution { public char findTheDifference(String s, String t) { char ch = t.charAt(0); for(int i = 0; i < s.length(); i ++) ch ^= s.charAt(i); // 由于ch初始为t[0]，所以遍历t要从1开始，到t的结尾 // 因为遍历s从0开始，遍历t从1开始，所以两个循环不能合并 // 当然，也可以合并，在遍历t的时候做一个索引的偏移，但是我个人不推荐这样做，因为语意不清：） for(int i = 1; i< t.length(); i ++) ch ^= t.charAt(i); return ch; } }而如果对于你给出的第一个解法，只是简单地把ch设置成t[0]，其他逻辑不变。就会造成t[0]访问了两遍（初始时和循环时），而t的最后一个元素访问不到（因为循环长度到len-1）。
相信你已经理解了：）
你的第二个解法同理。不过注意，第二个解法中len的定义和第一个解法不同（第一个解法len是t的长度，第二个解法len是s的长度，造成边界不同）
加油！
112018-07-21
相似问题