近期准备抽出一点时间，刷一些题防止手生，毕竟codemonkey，吃饭的手艺不能忘。
·······································
基本的题目都是基于java语言解答的，周末最近喜欢上了比赛赢积分，要求时间和准确率。在具体题的前面，增加一下常用的
java数据结构，及快速解决方法。目标，快速AC简单问题
~~堆栈的使用
//字符串提取常用
s.charAt(i);
//大小写转换
s.toUpperCase()
s.toLowerCase()
s.substring(i,j);//截取[i，j]的子字符串
char[] arr = str.toCharArray();//转数组
String string =String.copyValueOf(arr); //转字符串
new String(arr);
String.trim() //去首尾空格
str.replace(" ", ""); .//去所有空格
String s[] = str.split(" ");//分割字符串为字符数组
StringBuffer sb = new StringBuffer();
sb.append(c);//string不存在append方法，借助 StringBuffer实现
sb.reverse();//字符串反转
sb.deleteCharAt(pos);//删除制定位置的字符
//字符串转int
Integer.parseInt（s）//默认十进制解析
Integer.parseInt (s,2)// 二进制解析字符串
//判断int数字是否溢出
Integer.MAX_VALUE
Integer.MIN_VALUE
//数组拷贝
//（原数组， 原数组的开始位置， 目标数组， 目标数组的开始位置， 拷贝个数）
int[] a1 = {1, 2, 3, 4, 5};
int[] a2 = new int[10];
System.arraycopy(a1, 1, a2, 3, 3);//// [0, 0, 0, 2, 3, 4, 0, 0, 0, 0] //Stack的简单使用
Stack<Character> stack = new Stack<Character>();
char b = stack.peek();
char c = stack.pop();
stack.add();
stack.empty();
//hashset使用
HashSet hs;
hs.add();//成功加入返回true
//快速表达式,简单的判断赋值，一行解决
a=b?b-a:a-b;
//计算函数是否符合为被二余数时，使用位操作更快
a&1 = 1; //Array转ListArrayList<Element> arrayList =newArrayList<Element>(Arrays.asList(array));
HashMap 使用键值对的时候可以使用，自带排序的TreeMap但是调用的时候稍微有点麻烦
TreeMap tp = new TreeMap();
Set<Integer> set = tp.keySet();
Interator<Integer> itor = set.interator();
int key = itor.next();
tp.get(key);
//快速遍历hashMap
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
tips：单链表查询有环问题，设计快慢指针，相遇则为有环。进一步，找到入环第一个节点，快慢指针相遇，路程差为头指针到交点距离。
简单队列：
Queue<String> q =new LinkedList<String>();
q.offer("a"); //添加元素
q.peek();//查看队首，不弹出
q.poll();//查看并弹出队首
q.element();//查看队首，不弹出，空时不报错
格雷编码快速生成：
格雷编码相邻数字仅有一位相差，可以通过位移方式快速形成
/**
关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
如 n = 3:
G(0) = 000,
G(1) = 1 ^ 0 = 001 ^ 000 = 001
G(2) = 2 ^ 1 = 010 ^ 001 = 011
G(3) = 3 ^ 1 = 011 ^ 001 = 010
G(4) = 4 ^ 2 = 100 ^ 010 = 110
G(5) = 5 ^ 2 = 101 ^ 010 = 111
G(6) = 6 ^ 3 = 110 ^ 011 = 101
G(7) = 7 ^ 3 = 111 ^ 011 = 100
**/
List<Integer> ret = new ArrayList<>();
for(int i = 0; i < 1<<n; ++i)
ret.add(i ^ i>>1);
public static void sort(int[][] ob, final int[] order) {
Arrays.sort(ob, new Comparator<Object>() {
public int compare(Object o1, Object o2) {
int[] one = (int[]) o1;
int[] two = (int[]) o2;
for (int i = 0; i < order.length; i++) {
int k = order[i];
if (one[k] > two[k]) {
return 1;
} else if (one[k] < two[k]) {
return -1;
} else {
continue; //如果按一条件比较结果相等，就使用第二个条件进行比较。
}
}
return 0;
}
});
}
二维数组排序
Deque实现队列，栈的操作。get，remove，peek，poll可选择first or last
package com.yulore.ex; import java.util.ArrayDeque;
import java.util.Deque; public class DequeTest { /**
* @param args
*/
public static void main(String[] args) {
Deque<Integer> mDeque = new ArrayDeque<Integer>(); for(int i=0;i<5;i++){
mDeque.offer(i);
} System.out.println(mDeque.peek()); System.out.println("***********集合方式遍历**********"); //集合方式遍历，元素不会被移除
for (Integer x : mDeque) {
System.out.println(x);
} System.out.println("**********遍历队列*************"); //队列方式遍历，元素逐个被移除
while (mDeque.peek() != null) {
System.out.println(mDeque.poll());
} System.out.println("***********进栈操作************"); mDeque.push(10);
mDeque.push(15);
mDeque.push(24);
print(mDeque); System.out.println("*********出栈操作*************"); System.out.println(mDeque.pop());
} public static void print(Deque<Integer> queue){
//集合方式遍历，元素不会被移除
for (Integer x : queue) {
System.out.println(x);
}
}
}
示例代码
PriorityQueue 具有优先级的基于优先级堆的极大优先级队列
public static void main(String[] args){
PriorityQueue<webs> pq = new PriorityQueue<webs>(3,new Comparator<webs>(){
@Override
public int compare(webs o1, webs o2) {
return o1.n - o2.n;
}
});
webs a = new webs(1);
webs b = new webs(2);
webs c = new webs(4);
webs e = new webs(0);
webs d = new webs(5);
pq.add(a);
pq.add(d);
pq.add(c);
pq.add(e);
pq.add(b);
while(!pq.isEmpty()){
Iterator<webs> ite = pq.iterator();
while(ite.hasNext()){
webs aa = ite.next();
System.out.println(aa.n);
}
webs tmp = pq.poll();
System.out.println(tmp.n+"-----------------");
}
优先级队列
-----分割线-----------
动态规划：
分解当前状态和之前状态的关系，基本通过二维数组迭代实现，进阶可使用一维数组
--------------------------------------分割线-----------------------------------------
简单记录下解题时的想法和遇到的坑，如果能坚持下来以后可能还会整理整理，sasa。
1，用链表计算计算加法 Add Two Numbers
对于科班出身的人对面向对象的概念都很简单，然而在实际的编程中，由于封装的原因，要考虑到各种奇葩的输入，防止你的程序异常崩溃。
回到题目，例子中给的是342+465 =807；在最开始要考虑链表是否为空的情况，在函数最开始进行判断。然后依次相加进位，输出结果。
注意：坑是在相加之后产生的进位可能会影响很多高位，例如1+999； 这种情况很容易被遗漏；
技巧：
对于本菜鸟来说，开始的时候在初始化队列头部时写的麻烦了。单独对头部进行相加之后才进入循环，因为直接进入循环处理不好实例化ListNode的时间。
然而在看过参考答案之后，为了不对头部单独进行判断，可以设置无意义的head节点，最终返回的时候return head.next；
还可以通过判断指针为空的方法，将不一样的长度的链表相加在一个while循环中计算，最后上代码：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
2,计算最长不重复子链长度 Longest Substring Without Repeating Characters
对于给定字符串，计算其中最长不重复子链的长度，比如abcabcbb，最长是abc，返回值是 3.
解决思想，字符串转字母数组，从头开始遍历，遍历到的字母最为key值加入map，value存储字母在字符串中的位置；如果key值重复，判断当前map的size是为max然后移除map中重复项及其前面的字母，加入新的字母，直到遍历结束。
易忽略点：1，当字符串为单个字母的情况容易判断错误，未及时更新max值
2，移除重复项的过程要记录上次移除到何处位置，否则会导致重复移除
public int lengthOfLongestSubstring(String s) {
int maxLongth = 0;
int startPosition = 0;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
char[] get = s.toCharArray();
for(int i=0;i<get.length;i++){
if (map.containsKey(get[i])) {
if (map.size()>maxLongth)
maxLongth =map.size();
int removeNum = map.get(get[i]);
for (int j = startPosition; j <= removeNum; j++)
map.remove(get[j]);
startPosition= removeNum+1;
}
map.put(get[i],i);
}
if (map.size()>maxLongth)
return map.size();
return maxLongth;
}
3,给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
提示：本题在于对时间复杂度和空间的限制，利用全部为正整数的性质，并且与数组下标对应，可以通过负数的形式，解决该问题。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list= new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
int val = Math.abs(nums[i])-1;
nums[val] =-Math.abs(nums[val]);
}
for(int i=0;i<nums.length;i++){
if(nums[i]>0)
list.add(i+1);
}
return list;
}
}