有效的字母异位词
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
思路：这个题怎么说呢，审题审明白了做就很好做了。什么叫字母异位词？就是由相同的字母组成，只不过是位置不同。比如abcc和ccab就是异位词。abdca 和aadce就不是。知道了题目其实这道题很简单的。一个map就搞定。我先用能想出来的方法做，优化什么的做出来以后再说。
按照刚刚的想法做出来了，别说性能可不可怜，起码进阶要求应该满足了吧？
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
Map<String,Integer> map = new HashMap<String,Integer>();
for(int i=0;i<s.length();i++){
if(map.containsKey(s.charAt(i)+"")){
map.put(s.charAt(i)+"",map.get(s.charAt(i)+"")+1);
}else{
map.put(s.charAt(i)+"",1);
}
}
for(int j=0;j<s.length();j++){
if(!map.containsKey(t.charAt(j)+"")){
return false;
}else{
int val = map.get(t.charAt(j)+"");
if(val>1){
map.put(t.charAt(j)+"",map.get(t.charAt(j)+"")-1);
}else{
map.remove(t.charAt(j)+"");
}
}
}
return true;
}
}
然后开始正正经经的想思路了。看了题解，很无脑的char排序就ok了：
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length())return false;
char[] as=s.toCharArray();
char[] ts=t.toCharArray();
Arrays.sort(as);
Arrays.sort(ts);
return Arrays.equals(as,ts);
}
}
剩下的大同小异，是char比较还是换成int比较都可以，不过实际测了下，int比较性能好一点。
class Solution {
public boolean isAnagram(String s, String t) {
int[] sCounts = new int[26];
int[] tCounts = new int[26];
for (char ch : s.toCharArray()) {
sCounts[ch - 'a']++;
}
for (char ch : t.toCharArray()) {
tCounts[ch - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (sCounts[i] != tCounts[i]) {
return false;
}
}
return true;
}
}
这道题其实很简单，但是我最后优化也没到0ms的程度，就这样吧。下一题。
二叉树的所有路径
题目：给定一个二叉树，返回所有从根节点到叶子节点的路径。
image.png
思路：怎么说呢，我一直以来的经验：树，链表之类的题，不是迭代就是递归。而迭代树我又不是很擅长（链表的迭代容易点）所以这里的思路是递归。至于怎么递归，判断条件先确定，就是当前节点是不是叶子节点。想好了大体思路我要去撸代码了
回来了，遇到几个坑，做的比想象的慢得多。首先就是递归点问题，一开始我倒是很容易的把每一条线跑出来了。但是一条条件怎么加在一个集合里？所以又往递归方法中加了一个参数。就是习以为常的觉得递归方法参数不会多，一般也就一两个，所以这个让我卡了一会，因为这个里要有三个参数：一个是当前节点，一个是总的结果集，一个是当前的线性字符串。
这个方法确定好了下一步就简单了，逻辑什么的在"->"符号加在哪里也琢磨了半天，加载每一个数值前面结果一开始就有个这个，加在每一个数值后面最后没数值也有这个。试了三次才提出来单独追加。情况就是这么个情况。我直接贴代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<String>();
treePaths(root,result,"");
return result;
}
public void treePaths(TreeNode root,List<String> result,String path){
if(root!=null) {
path += root.val;
//叶子节点。直接存到结果集就行
if(root.left==null && root.right==null){
result.add(path);
}else{
path += "->";
//这不用额外判断左右节点是不是null，因为进去了是null直接返回了，总比判断省事
treePaths(root.left,result,path);
treePaths(root.right,result,path);
}
}
}
}
其实这个代码性能一般，我不知道把这个String换成可变类型会不会好点，比如StringBuffer或者StringBuilder之类的。
好了，现在回来了，我确定把这个字符串类型换成可变长的不行。应该是值传递引用传递的关系？反正如果换成StringBuffer或者StringBuilder数据不对，是在哪之后的追加。是我想当然了。
这道题应该用迭代的办法也能做，不过我就不做一遍了。下一题吧。
个位相加
题目：给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
思路：这个题目有点懵啊。懵的点在于这个进阶条件。不用循环或者递归?单纯题目来讲简单的不得了不得了，以前的某一道题其中一步就是这个。设置一个循环里原数%10.不断获得的各位数字相累加。累加值大于10继续这么循环累加。但是前提都是循环或者递归实现的。可是这个进阶条件。。。暂时想不到出了这两种还有什么解法了，我先想想
!!!!卧槽？？？这道题我用眼睛看出来的你敢信？
截个图上传得瑟下
讲一下心路流程:首先题目说能常量范围解决。所以证明一定是有点规律。然后就是死盯着题，看例子:38 3+8 =11 1+1 = 2 这是怎么来的？
因为 3+8 = 10 + 1 10变成了1。也就是满10减9。
或者换言之有几个10就减几个9。让后不够10的就该是多少是多少。
这一句话得出两个结论：
- 首先n小于9 n是几返回值是几。
- n大于10以后 有几个9减几个九。剩下的结果就对了。
而这个有几个9就减去几个九可以变种为n%9的余数。
这两句写完我就提交了，结果不出意外的错了。测试案例18，结果是9 我却输出0。
看了这个测试案例我就觉察出自己的问题了。非0数怎么相加也不会出0啊，绝对是错了，18是九的倍数。正好包含两个9.但是其实她本质上只有一个10能去9.最后剩下的1+8不够十。所以不能再减去9了。由此得出结论，当最后是9的时候是不能减去的。而最后是9说明这个数是9的倍数。
最后的最后还要添加一条：n%9==0 ，返回的结果就是9.
至此，三行代码完成！
因为这个循环和递归都很容易做，我就不实现了。这道题就这样了，下一题。
丑数
题目:编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。
说明：
1 是丑数。
输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
思路：这个题怎么说呢。感觉跟判断奇数偶数是一样的，不过是可判断的多了一点而已。我去直接撸代码了。
直接贴代码：
class Solution {
public boolean isUgly(int num) {
if(num<1) return false;
while(num!=1){
if(num%2!=0 && num%3!=0 && num%5!=0){
return false;
}
if(num%2==0){
num /= 2;
}else if(num%3==0){
num /= 3;
}else{
num /= 5;
}
}
return true;
}
}
逻辑简单清楚，没啥可讲解的。就这样吧。下一题。
第一个错误的版本
题目：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
**思路：这个题怎么说呢。简而言之就是有这么一个数：isBadVersion(n) 等于true，而isBadVersion(n-1)等于false。这个数在1-给定的参数之间。求这个数是多少。这么一说题目应该逻辑清晰多了，而且有没有似曾相识？熟的不得了对不对？以前也做过类似的题的。最暴力的就是从1开始遍历，到给定数字的时候肯定是会存在这么一个数的。但是题目说了尽量少判断。所以就要想算法了。巧了，我是彻彻底底的学渣，知道的也就是双指针和二分法。感觉双指针不太合适，毕竟万一是最后一个版本错了，快慢指针毫无用处。二分法可能是比直接从头遍历好点？反正我也只会这个。我去撸代码。 **
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
if(isBadVersion(n) && !isBadVersion(n-1)) return n;
return mid(0,n);
}
public int mid(long start,long end){
long version = 1;
while(!(isBadVersion((int)version) && !isBadVersion((int)version-1))){
version = (start+end)/2;
if(!isBadVersion((int)version)){
start = version;
}
if(isBadVersion((int)version-1)){
end = version;
}
}
return (int)version;
}
}
我只能说实现了，性能什么的，反正没从头调用，应该不是最差的。我还是直接去看大神思路吧：
回来了，首先可喜可贺，大神的思路也就是二分法。但是我这里的不足是我的start和end还有version都是long，至于这么设置的原因就是可能会涉及到溢出问题。所以要来回来去long int 的强转。而大神这里用了一个巧妙的算法避免了这种可能。就是start+（end-start）/2。另外我的左右节点其实比较的不好，归根结底只能缩小范围，并且判断条件很墨迹。说了这么多，直接上整改以后的代码：
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
if(isBadVersion(n) && !isBadVersion(n-1)) return n;
return mid(1,n);
}
public int mid(int start,int end){
int version = 1;
while(start<end){
version = start + (end-start)/2;
if(isBadVersion(version)){
end = version;
}else{
start = version+1;
}
}
return start;
}
}
好了，今天就学到这里，又是一个周末。真的有光阴似箭的感觉了。哈哈，祝大家周末愉快，另外工作顺顺利利！如果稍微帮到你了记得点个喜欢点个关注哟~~另外我哪些写的不太明白可以私聊或者留言交流！
网友评论