Leetcode未分类
2019-08-10 本文已影响0人
浩泽Hauser
Leetcode 1147. Longest Chunked Palindrome Decomposition. 【Hard】【Blue】
题意：
class Solution {
public int longestDecomposition(String text) {
int res = 0;
int left = 0, right = text.length()-1;
String lStr = "", rStr = "";
while(left<right){
lStr = lStr + text.charAt(left);
rStr = text.charAt(right) + rStr;
if(lStr.equals(rStr)){
res+=2;
lStr = "";
rStr = "";
}
left++;
right--;
}
if(left>right && lStr.equals("")){ //特殊情况："ABAB",导致 left>right && lStr是empty
return res;
} else {
return res+1;
}
}
}
分析：什么情况下返回res而不是res+1？Special Case: "camelcamel",或者"avav".
notEmpty; empty
left==right res+1 res+1
left>right res+1 res
Leetcode 最佳解法：
遍历1次，若equals只+1。避免了left<right写法的res是否+1的判断。
public int longestDecomposition(String S) {
int res = 0, n = S.length();
String l = "", r = "";
for (int i = 0; i < n; ++i) {
l = l + S.charAt(i);
r = S.charAt(n - i - 1) + r;
if (l.equals(r)) {
++res;
l = "";
r = "";
}
}
return res;
}
Leetcode 937. Reorder Log Files. 【Easy】【Green】
class Solution {
//lexicographically: 字典的，按照字母排序的
public String[] reorderLogFiles(String[] logs) {
Comparator<String> comparator = new Comparator<String>(){ //这里的两个<>内部都必须写，而且都是Object类型如Integer，不能是int,long等
@Override
public int compare(String s1, String s2){
int space1 = s1.indexOf(' ');
int space2 = s2.indexOf(' ');
if(s1.charAt(space1+1)<='9'){
if(s2.charAt(space2+1)<='9') return 0;
else return 1;
} else {
if(s2.charAt(space2+1)<='9') return -1;
int letterCompare = s1.substring(space1+1).compareTo(s2.substring(space2+1));
if(letterCompare==0) letterCompare=s1.substring(0,space1).compareTo(s2.substring(0,space2));
return letterCompare;
}
}
}; //这里，需要加上 ; 符号
Arrays.sort(logs, comparator);
return logs;
}
}
Leetcode 1160. Find Words That Can Be Formed by Characters 【Easy】
class Solution {
public int countCharacters(String[] words, String chars) {
int[] alphabet = new int[26];
for(char c: chars.toCharArray()){
alphabet[c-'a']++;
}
int res = 0;
for(String word: words){
int[] copy = Arrays.copyOf(alphabet,alphabet.length);
//实际上是调用了System.arraycopy()方法，相当于执行了以下代码：
// int[] copy=new int[26];
// System.arraycopy(alphabet,0,copy,0,copy.length);
boolean legal =true;
int count=0;
for(char c: word.toCharArray()){
copy[c-'a']--;
count++;
if(copy[c-'a']<0) {
legal = false;
break;
}
}
if(legal) res+=count;
}
return res;
}
}
Leetcode 771. Jewels and Stones. 【Easy】【】
Tag：HashSet
题目简介：一个字符串代表珠宝，另一个字符串代表石头和珠宝的混合。求字符串2中含有多少个字符串1代表的珠宝。
解答过程：肯定是将字符串中的char存起来，然后搜索。HashMap的search需要O(n), 而HashSet的search需要O(1). 所以用HashSet来存储。
class Solution {
//I used hash set and it's O(1) to check if it contains an element.
//So the total time complexity will be O(M+N), instead of O(MN)
public int numJewelsInStones(String J, String S) {
int res = 0;
Set jewels = new HashSet();
for(char j: J.toCharArray()) jewels.add(j);
for(char s: S.toCharArray()) res = (jewels.contains(s))? res+1:res;
return res;
}
}
Leetcode 49. Group Anagrams. 【Green】【Medium】
Time: O(mn), strs个数字符串平均长度。或者说O(sum of all chars in strs).
Space: 同上，O(sum of all chars in strs)。
class Solution {
//anagram：易位构词游戏，是将组成一个词或短句的字母重新排列顺序，
//原文中所有字母的每次出现都被使用一次，这样构造出另外一些新的词或短句。
//比如，listen变为silnet。
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String str: strs){
int[] chars = new int[26];
for(char c: str.toCharArray()) chars[c-'a']++; //形成一个记录26个字母出现个数的数组
String key = "";
for(int i=0; i<26; i++){
if(chars[i]!=0){
key += String.valueOf(chars[i])+ (char)(i+'a'); //注意是String.valueOf() //从而形成"2a2b1c1r"形式的字符串
}
}
//String key = Arrays.toString(chars); //相当于字符串："[1,0,0,3,...]" time不如上面for循环(因为连同逗号都需要比较)，space也差,需要占据超过26个位置,而上面的for循环好很多
List<String> value = map.getOrDefault(key, new ArrayList<>());
value.add(str);
map.put(key,value);
}
return new ArrayList<>(map.values());
}
}
Leetcode 242. Valid Anagram.
class Solution {
public boolean isAnagram(String s, String t) {
int[] alphabet = new int[26];
if(s.length()!=t.length()) return false;
for(int i=0; i<s.length(); i++){
alphabet[s.charAt(i)-'a']++;
alphabet[t.charAt(i)-'a']--;
}
for(int i=0; i<26; i++){
if(alphabet[i] != 0) return false;
}
return true;
}
}
Leetcode 383. Ransom Note.
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] alphabet = new int[26];
for(int i=0; i<magazine.length();i++){
alphabet[magazine.charAt(i)-'a']++;
}
for(int i=0; i<ransomNote.length();i++){
alphabet[ransomNote.charAt(i)-'a']--;
if(alphabet[ransomNote.charAt(i)-'a']<0) return false;
}
return true;
}
}
Leetcode 387. First Unique Character in a String.
class Solution {
public int firstUniqChar(String s) {
int[] alphabet = new int[26];
for(int i=0; i<s.length(); i++){
alphabet[s.charAt(i)-'a']++;
}
for(int i=0; i<s.length(); i++){
if(alphabet[s.charAt(i)-'a']==1) return i;
}
return -1;
}
}
Leetcode 22. Generate Parentheses. 【Green】【Medium】
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if(n==0) return res;
helper(res, new String(), n, n);
return res;
}
public void helper(List<String> res, String cur, int open, int close){
if(open>close) return;
if(open==0 && close==0) res.add(cur);
if(open>0){
helper(res, cur+"(", open-1, close);
}
if(close>0){
helper(res, cur+")", open, close-1);
}
}
}
Leetcode 380. Insert Delete GetRandom O(1).
class RandomizedSet {
Map<Integer, Integer> map;
ArrayList<Integer> list;
Random rand;
//ArrayList可以在O(1)实现insert(值)，和getRandom()操作,但delete(val)需要O(n)。【注意,list remove(index)是O(1),但题目要求的是remove value值，需要遍历list所以是O(n)】。
//为了将remove的time降为O(1),可以将list内存放的val位置找到，调换到ArrayList的首/尾部，然后删除尾部即可
//由此，我们需要用HashMap来记录list中，val和val在list中的位置
/** Initialize your data structure here. */
public RandomizedSet() {
this.map = new HashMap<>();
this.list = new ArrayList<>();
this.rand = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) return false;
//a good hash algorithm will ensure map.containsKey() to be time O(1), but the worst case is O(n).在算法题中，基本都认为O(1)。
map.put(val,list.size()); //key是值，value是值的位置，从0开始
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
int index = map.remove(val); //返回的是value，即位置. //或者map.get(val),然后下一句map.remove(val)
//map.remove(val);
if(index != list.size()-1){
int lastInt = list.get(list.size()-1); //list的尾数的值
list.set(index,lastInt); //将准备删除的val所在list的位置设置为list最末尾的数的值，然后list.remove尾数即可
map.put(lastInt,index); //将 准备删除的val所在位置的值 修改为尾数值
}
list.remove(list.size()-1);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
Leetcode 381. Insert Delete GetRandom O(1) - Duplicates allowed. 【】
class RandomizedCollection {
Map<Integer, HashSet<Integer>> map;
List<Integer> list;
Random rand;
/** Initialize your data structure here. */
public RandomizedCollection() {
this.map= new HashMap<>();
this.list = new ArrayList<>();
this.rand = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
boolean oldVal = map.containsKey(val);
if(!oldVal) map.put(val,new HashSet<Integer>());
map.get(val).add(list.size());
list.add(val);
return !oldVal;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
int index = map.get(val).iterator().next();
map.get(val).remove(index); //位置[1], 避免影响后面add(index)
if(index < list.size()-1){
int lastInt = list.get(list.size()-1);
list.set(index,lastInt);
map.get(lastInt).remove(list.size()-1);
map.get(lastInt).add(index); //有可能lastInt==val.若是位置[2]，index已经在map里，add(index)没有任何作用，导致错误
}
list.remove(list.size()-1);
//map.get(val).remove(index); //位置[2],错误。尝试以下例子。
if(map.get(val).isEmpty()) map.remove(val); //map.isEmpty()方法调用了size()==0
return true;
}
//map.get(val).remove(index)，这句的位置，尝试这个例子：
//["RandomizedCollection","insert","insert","insert","remove","remove"]
//[[],[0],[3],[3],[3],[3]]
/** Get a random element from the collection. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
Leetcode 28. Implement strStr(). 【Easy】
class Solution {
public int strStr(String haystack, String needle) {
if(needle==null || needle.length()==0) return 0;
int h = haystack.length(), n = needle.length();
for(int i=0; i<=h-n; i++){
// for(int j=0; j<n && haystack.charAt(i+j)==needle.charAt(j); j++){
// if(j==n-1) return i;
// }
if(haystack.substring(i,i+n).equals(needle)){
return i;
}
}
return -1;
}
}
Leetcode 125. Valid Palindrome.
class Solution {
public boolean isPalindrome(String s) {
if(s==null || s.length()<=1) return true;
int start = 0, end=s.length()-1;
while(start<end){
Character startC = s.charAt(start);
Character endC = s.charAt(end);
if(!Character.isLetterOrDigit(startC)){
start++;
continue;
} else if(!Character.isLetterOrDigit(endC)){
end--;
continue;
} else {
if(Character.toLowerCase(startC) != Character.toLowerCase(endC)) return false;
start++;
end--;
}
}
return true;
}
}
Leetcode 344. Reverse String.
class Solution {
public void reverseString(char[] s) {
//若是传入的是String，需要用：
//1) char[] word = s.toCharArray();
//2) return new String(word);
int start = 0, end = s.length-1;
while(start<end){
if(s[start]!=s[end]){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
}
start++;
end--;
}
}
}
Leetcode 811. Subdomain Visit Count.
class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
Map<String,Integer> map = new HashMap<>();
for(String domain: cpdomains){
// int space = domain.indexOf(" ");
// int count = Integer.valueOf(domain.substring(0,space));
String[] s1 = domain.split(" ");
int count = Integer.valueOf(s1[0]);
map.put(s1[1],count+map.getOrDefault(s1[1],0)); //String dom = "."+s1[1];
String dom = s1[1];
for(int i=0; i<dom.length(); i++){
if(dom.charAt(i)=='.'){
String cur = dom.substring(i+1);
map.put(cur,count+map.getOrDefault(cur,0));
}
}
}
List<String> res = new ArrayList<>();
for(Map.Entry entry: map.entrySet()){
res.add(entry.getValue()+" "+entry.getKey());
}
// 可以用 for (String d : map.keySet()) res.add(map.get(d) + " " + d);
// 虽然leetcode跑数据是map.keySet()快，但在理论上，若是需要访问到value值(即既访问key又访问value)，
// keySet()需要用到map.get(),而entrySet()直接是getValue()所以更快更好
return res;
}
}
- Min Stack. 【Green】【Easy】
class MinStack {
/** initialize your data structure here. */
Deque<Integer> stack; //用 Stack<Integer> stack = new Stack<>(); 亦可
List<Integer> minList;
public MinStack() {
stack = new LinkedList<>();
minList = new ArrayList<>();
}
public void push(int x) {
stack.push(x);
if(minList.size()!=0 && minList.get(minList.size()-1)<=x){
minList.add(minList.get(minList.size()-1));
} else {
minList.add(x);
}
}
public void pop() {
stack.pop();
minList.remove(minList.size()-1);
}
public int top() {
return stack.peek();
}
public int getMin() {
return minList.get(minList.size()-1);
}
}
Leetcode 349. Intersection of Two Arrays.
Leetcode 350. Intersection of Two Arrays II.
三个 Follow up:
1）What if the given array is already sorted? How would you optimize your algorithm?
2）What if nums1's size is small compared to nums2's size? Which algorithm is better?
3）What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Leetcode 202. Happy Number.
用HashSet做：（这不是最优的）
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet();
int res = count(n);
while(res!=1){
if(set.contains(res)){
return false;
}
set.add(res);
res = count(res);
}
return true;
}
public int count(int n){
int res = 0;
while(n>0){
int mod = n%10;
res += mod*mod;
n = n/10;
}
return res;
}
}
最佳解法：参考Node的一道题，是否成环。
class Solution {
public boolean isHappy(int n) {
int x = n;
int y = x;
while(x!=1){
x = count(x); //x在原x基础上进一步
y = count(count(y)); //y在原y基础上进两步
if(x==1)return true;
if(y==1) return true;
if(x==y) return false;
}
return true;
}
public int count(int n){
int res = 0;
while(n>0){
int mod = n%10;
res += mod*mod;
n = n/10;
}
return res;
}
}
Leetcode 605. Can Place Flowers.
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int add = 0;
for(int i=0; i<flowerbed.length;){
if(flowerbed[i]==1){
i=i+2;
} else {
int pre = i==0? 0:flowerbed[i-1];
int next = i==flowerbed.length-1? 0:flowerbed[i+1];
if(pre==0 && next==0){
//flowerbed[i]=1; //we can delete it since we use i=i+2
add++;
i=i+2;
} else{
i=i+1;
}
}
}
return add>=n;
}
}
