丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
首先从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z，换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，每次比较三个丑数，取出最小的丑数，通过链表来存储丑数。
代码
import java.util.ArrayList;
/**
* 剑指offer一刷：丑数
*
* @author User
* @create 2019-05-26-14:58
*/
public class jzo33 {
public int GetUglyNumber_Solution(int index) {
if(index==0)
return 0;
ArrayList<Integer> res=new ArrayList<>();
res.add(1);
int i2=0,i3=0,i5=0;
while (res.size()<index){
int m2=res.get(i2)*2;
int m3=res.get(i3)*3;
int m5=res.get(i5)*5;
// 取出三个丑数最小的丑数
int min=Math.min(m2,Math.min(m3,m5));
res.add(min);
if (min==m2)
i2++;
if (min==m3)
i3++;
if (min==m5)
i5++;
}
return res.get(res.size()-1);
}
public static void main(String[] args){
jzo33 so=new jzo33();
System.out.println(so.GetUglyNumber_Solution(11));
}
}
第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
解题思路
方法一用HashMap来存储字符串，HashMap取值是O(1)，在判断是否只有一个数。
代码
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
/**
* 剑指offer一刷：第一个只出现一次的字符
*
* @author User
* @create 2019-05-26-15:15
*/
public class jzo34 {
public int FirstNotRepeatingChar(String str) {
LinkedHashMap<Character,Integer> map=new LinkedHashMap<>();
for (int i=0;i<str.length();i++){
if (map.containsValue(str.charAt(i))){
int time=map.get(str.charAt(i));
map.put(str.charAt(i),++time);
}else {
map.put(str.charAt(i),1);
}
}
int pos=-1;
for (int i=0;i<str.length();i++){
char c=str.charAt(i);
if (map.get(c)==1){
return i;
}
}
return pos;
}
public int FirstNotRepeatingChar1(String str) {
if(str==null||str.length()==0)
return -1;
List<Character> list=new ArrayList<>();
for(int i=0;i<str.length();i++){
char ch=str.charAt(i);
if (!list.contains(ch)){
list.add(Character.valueOf(ch));
}else {
list.remove(Character.valueOf(ch));
}
}
if (list.size()<=0)
return -1;
return str.indexOf(list.get(0));
}
public static void main(String[] args){
String str="aabbchdhudehdj";
jzo34 so=new jzo34();
System.out.println(so.FirstNotRepeatingChar(str));
System.out.println(so.FirstNotRepeatingChar1(str));
}
}
