近期准备抽出一点时间，刷一些题防止手生，毕竟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转List
ArrayList<Element> arrayList = new ArrayList<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;

    }

}

巴特西

LeetCode算法题菜鸟总结

PriorityQueue 具有优先级的基于优先级堆的极大优先级队列

技巧：

最新文章

热门文章

巴特西

LeetCode算法题 菜鸟总结

PriorityQueue 具有优先级的基于优先级堆的极大优先级队列

技巧：

最新文章

热门文章

LeetCode算法题菜鸟总结