Leetcode - Valid Palindrome

图片 1Paste_Image.png

图片 2

My code:

My code:

public class Solution { public boolean isPalindrome { if (s == null) return false; if (s.length return true; int head = 0; int tail = s.length() - 1; while (head < tail) { char tempHead = s.charAt; char tempTail = s.charAt; while (tempHead < 48 || (tempHead > 57 && tempHead < 65) || (tempHead > 90 && tempHead < 97) || tempHead > 122) { head++; if (head == s.length return true; else tempHead = s.charAt; } while (tempTail < 48 || (tempTail > 57 && tempTail < 65) || (tempTail > 90 && tempTail < 97) || tempTail > 122) { tail--; tempTail = s.charAt; } if (tempHead >= 65 && tempHead <= 90) { if (tempTail >= 65 && tempTail <= 90) { if (tempHead == tempTail) { head++; tail--; } else return false; } else if (tempTail > 90) { if (tempHead == tempTail - 32) { head++; tail--; } else return false; } else return false; } else if (tempHead > 90) { if (tempTail >= 65 && tempTail <= 90) { if (tempHead == tempTail + 32) { head++; tail--; } else return false; } else if (tempTail > 90) { if (tempHead == tempTail) { head++; tail--; } else return false; } else return false; } else { if (tempHead == tempTail) { head++; tail--; } else return false; } } return true; }}
public class Solution { public String getPermutation(int n, int k) { if (n <= 0) return null; int temp = n; int total = 1; while (temp > 0) { total *= temp; temp--; } if (k > total) return null; boolean[] isVisited = new boolean[n + 1]; return getResult(n, k, n, isVisited); } private String getResult(int n, int k, int curr, boolean[] isVisited) { if (curr <= 1) { int temp = 0; for (int i = 1; i <= n; i++) { if (!isVisited[i]) { temp = i; break; } } return Integer.toString; } int temp = curr - 1; int total = 1; while (temp > 0) { total *= temp; temp--; } int group =  / total + 1; // divide the group int count = 0; // count the group including the consideration of visited group int begin = 0; for (int i = 1; i <= n; i++) { if (!isVisited[i]) { count++; if (count == group) begin = i; } } isVisited[begin] = true; String beginStr = Integer.toString; k = k - (group - 1) * total; return beginStr + getResult(n, k, curr - 1, isVisited); } public static void main (String[] args) { Solution test = new Solution(); System.out.println(test.getPermutation; }}

My test result:

My test result:

图片 3

图片 4Paste_Image.png

那道难题相比简单。主要烦的两点。三个是她是大小写忽略的,要用if语句推断好这个情况。然后原有的字符串还应该有数字。不可能有toLowercase 那么些办法,太浪费时间了,每用叁遍都要遍历三次字符串!第三个是,忽略别的非字母数字的字符。所以供给中间用七个while过滤一下。同期,当head跑到字符串尾巴处时,表示该字符串不含数字字母,就直接回到true就行了。然后在tail里面无需思考这些corner case,因为一旦真是如此,才head里面早就看清结束重临了。

那道题目认为和 Next Permutation 有点事关。然后本身要好做出来了。首要正是,遵照顺序排列后,每一列,皆以遵照轻重缓急排列的。小编能够依据,k, 算出 那一个数字所属的块,小编称之为,group.然后,在走入那些group后,还也许会再分块,再进来group中的子group。然后,早先的假名,都以依据大小顺序排列的。小编能够总括出,先导字母,在这么些大group中的偏移地方group。然后,那一个职位只大概现身 ,1...n,中的三个,然后根据轻重缓急排列,第 group 个数字,便是本身要的开头字母。不过还亟需思考二个处境,就是某些数字已经在事先使用过了。所以要设置三个布尔数组 isVisited[], 访谈过了就设置为true,后一次遍历,就不再访问了。然后就人之常情了。

**总结: String, traversal**

**小结: backtracing, Array, 通过布尔数组 isVisted 来制止已经出现的动静再现。**

Anyway, Good luck, Richardo!

Anyway, Good luck, Richardo!

My code:

My code:

public class Solution { public boolean isPalindrome { if (s == null || s.length { return true; } s = s.toLowerCase(); int i = 0; int j = s.length() - 1; while  { while (i < s.length() && !isValid(s.charAt { i++; } while (j >= 0 && !isValid(s.charAt { j--; } if (i >= j) { break; } if (s.charAt != s.charAt { return false; } else { i++; j--; } } return true; } private boolean isValid { if (c >= '0' && c <= '9') { return true; } else if (c >= 'a' && c <= 'z') { return true; } else { return false; } }}
public class Solution { public String getPermutation(int n, int k) { if (n <= 0 || k <= 0) return null; /** calculate n! */ int total = n; for (int i = n - 1; i >= 1; i--) total *= i; StringBuilder ret = new StringBuilder(); boolean[] isVisited = new boolean[n]; helper(k, n, n, total, isVisited, ret); return ret.toString(); } private void helper(int k, int n, int level, int total, boolean[] isVisited, StringBuilder ret) { if (level == 1) { for (int i = 0; i < n; i++) { if (!isVisited[i]) { ret.append; break; } } return; } else { total = total / level; int group = k / total; if (k % total != 0) group++; int counter = 0; for (int i = 0; i < n; i++) { if (!isVisited[i]) { counter++; if (counter == group) { ret.append; isVisited[i] = true; break; } } } if (k % total == 0) k = total; else k = k % total; helper(k, n, level - 1, total, isVisited, ret); } }}

感觉那样一年下来,自个儿写的代码水平照旧多少提升的。。。在此以前怎么写的那么复杂。。这道难题最注重的是领略二个单词:阿尔法numeric文字数字的。

这是本人写的本子,相比较复杂冗杂。首要一个题目未能很好消除。就是抽取贰个数字进入字符串后,剩下的今后还得按序选,遵照算出来的撼动。所以本身设置了多少个boolean[] isVisited来进展那些操作,合作多个计数器,counter当 counter == 算出来的偏移量后,就抽出来放进字符串。同期,k的翻新也许有尊重的。反正全体是比较复杂的。下一次写依旧不可能担保一次经过。所以参谋了英特网的代码,以为很轻便,思路也很清楚。

于是笔者独立写了三个函数来检查是或不是valid

My code:

别的就基本上了。

public class Solution { public String getPermutation(int n, int k) { if (n <= 0 || k <= 0) return null; ArrayList<Integer> bag = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) bag.add; /** calculate n! */ int total = 1; for (int i = 1; i <= n; i++) total *= i; StringBuilder ret = new StringBuilder(); k--; // change k to be the index while  { total = total / n; int offset = k / total; ret.append(bag.get; bag.remove; k = k % total; n--; } return ret.toString(); } }

Anyway, Good luck, Good luck, Richardo! -- 09/17/2016

那道题木接触了多少个新东西。

老是收取来三个数后事后无法再取了。能够献身两个list里面,抽取来之后就把他删除了。那样今后就不会再用到了。然后前面包车型地铁element会移动到面前,所以能够满意如此一种效应。

k本来表示的是个数,比非常多地点用起来非常不便于!要求分类切磋。可是k-- 把她改成index之后,全体的都变方便了,无需再把代码写的和事先同一的复杂了。妙!

参考网页:

Anyway, Good luck, Richardo!

My code:

public class Solution { public String getPermutation(int n, int k) { List<Integer> bag = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { bag.add; } int total = 1; for (int i = 1; i <= n; i++) { total *= i; } StringBuilder ret = new StringBuilder(); k--; while  { total = total / n; int offset = k / total; int digit = bag.get; ret.append; bag.remove; k = k % total; n--; } return ret.toString(); }}

没做出来。尽管思路还是和从前同样。主要的多少个标题照旧 offset 和 真是的岗位一向分不清楚。即使笔者也想到了 k--

先是k--, 将它调换为index,之后再做。还会有个操作便是用list存 1-9,用二个去除三个,这样前面包车型地铁能够靠过来。就算如此做开采挺大,但思量到共计是 1-9,能够私下认可,成本为O

Anyway, Good luck, Richardo! -- 09/05/2016

本文由365bet体育在线官网发布于网络编程,转载请注明出处:Leetcode - Valid Palindrome

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。