所以說不要怕演算法，簡單的題反而出現的頻率最高，不一定非要寫個幾百道才面試

兩數之和

給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，

你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個陣列中同樣的元素，

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]

思路：

遇到的數字裝到hashmap中，遇到的新數字查找有沒有答案int dif = target - nums[i];

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int dif = target - nums[i];
            if (map.get(dif) != null) {
                res[0] = map.get(dif);
                res[1] = i;
                return res;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}

反轉鏈表

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞回地反轉鏈表，你能否用兩種方法解決這道題？

經典題，一i個回圈做那四個經典操作，自己拿紙筆畫一畫就懂啦，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

有效的括號

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串，判斷字串是否有效，

有效字串需滿足：

左括號必須用相同型別的右括號閉合，左括號必須以正確的順序閉合，注意空字串可被認為是有效字串，

示例 1:

輸入: "()"
輸出: true
示例 2:

輸入: "()[]{}"
輸出: true
示例 3:

輸入: "(]"
輸出: false
示例 4:

輸入: "([)]"
輸出: false
示例 5:

輸入: "{[]}"
輸出: true

思路：

初始化堆疊 ，一次處理運算式的每個括號，

1. 如果遇到開括號，我們只需將其推到堆疊上即可，這意味著我們將稍后處理它，
2. 如果我們遇到一個閉括號，那么我們檢查堆疊頂的元素，如果堆疊頂的元素是一個 相同型別的 左括號，那么我們將它從堆疊中彈出并繼續處理，否則運算式無效，

如果到最后我們剩下的堆疊中仍然有元素，那么運算式無效，

class Solution {
  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;
  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }
    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}

爬樓梯/跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法，

找遞推關系：

1）跳一階，就一種方法

2）跳兩階，它可以一次跳兩個，也可以一個一個跳，所以有兩種

3）三個及三個以上，假設為n階，青蛙可以是跳一階來到這里，或者跳兩階來到這里，只有這兩種方法，

它跳一階來到這里，說明它上一次跳到n-1階，

同理，它也可以從n-2跳過來

f（n）為跳到n的方法數，所以，f(n)=f(n-1)+f(n-2)

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

合并鏈表

將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：

輸入：l1 = [], l2 = []
輸出：[]
示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

提示：

兩個鏈表的節點數目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列

思路：歸并的思想，一直比較兩邊的大小并且插入，

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一個還未被合并完，我們直接將鏈表末尾指向未合并完的鏈表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}