力扣Hot100

力扣100题easy

1. 两数之和

���间空间复杂度为O(N)，思路是：创建一个哈希表，对于每一个 x，先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {    public int[] twoSum(int[] nums, int target) {        Map hashtable = new HashMap();        for(int i = 0; i  
21. 合并两个有序链表
 
用递归的思路：判断 l1 和 l2 哪一个链表的头节点的值更小，递归地决定下一个添加到结果里的节点。
 
class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) {            return l2;        } else if (l2 == null) {            return l1;        } else if (l1.val  
160. 相交链表
 
思路一：哈希集合存放不重复的元素，先将A链表的结点add后，再依次判断B链表的结点是否有相同的。
（） 
public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        Set set = new HashSet();        ListNode p = headA, q = headB;        while(p != null){            set.add(p);            p = p.next;        }        while(q != null){            if(set.contains(q)){                return q;            }            q = q.next;        }        return null;       }}
 
思路二：用双指针，先判断A、B链表是否为空，有空的则根本无法相交。都不为空则要同时更新p和q，p不为空就next，为空则指向headB。q同理，最后指向同一个结点或者null，返回即可。
 
public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if(headA == null || headB == null){            return null;        }        ListNode p = headA, q = headB;        while(p != q){            p = p == null ? headB : p.next;            q = q == null ? headA : q.next;        }        return p;    }}
 
234. 回文链表
 
要学的思路是把链表的值复制到数组中，再用双指针进行判断。
 
class Solution {    public boolean isPalindrome(ListNode head) {        List array = new ArrayList();        ListNode p = head;        while(p != null){            array.add(p.val);            p = p.next;        }        //用双指针判断是否是回文        int front = 0;        int back = array.size() - 1;        while(front  
283. 移动零
 
思路：分两次遍历，j用来记录当前数组中非0的元素，每遇到一个非0元素就往数组左边挪，遍历完后，j指向的是最后一个非0元素下标。第二次遍历就从j开始到结束，将其置为0。
 
class Solution {public void moveZeroes(int[] nums) {if(nums == null){            return;        }        int j = 0;        for(int i = 0; i  
101. 对称二叉树
 
要镜像对称，左右两边是相当的。递归的终止条件：两个结点为空；其中一个结点为空；两个结点不相等。随后再比较left.left, right.right和left.right, right.left
 
class Solution {    public boolean isSymmetric(TreeNode root) {        if(root == null){            return true;        }        return dfs(root.left, root.right);    }    public boolean dfs(TreeNode left, TreeNode right){        if(left == null && right == null){            return true;        }else if(left == null || right == null){            return false;        }else if(left.val != right.val){            return false;        }        return dfs(left.left, right.right) && dfs(left.right, right.left);    }}
 
543. 二叉树的直径
 
思路：求直径等同于求路径经过节点数的最大值 - 1。定义一个递归函数，返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 L 和 R，则该节点为根的子树的深度即为max(L, R) + 1。设置一个全局变量ans记录，最后返回ans - 1就是直径。
 
class Solution {    int ans;    public int diameterOfBinaryTree(TreeNode root) {        ans = 1;        depth(root);        return ans - 1;    }    public int depth(TreeNode node){        if(node == null){            return 0;        }        int L = depth(node.left);        int R = depth(node.right);        //ans是所有节点经过节点数的最大值        ans = Math.max(ans, L + R + 1);        //返回该节点为根的子树的深度        return Math.max(L, R) + 1;    }}
 
20. 有效的括号
 
class Solution {    public boolean isValid(String s) {       if(s.isEmpty()){           return true;       }        Stack stack = new Stack();       for(char c : s.toCharArray()){           if(c == '('){               stack.push(')');           }else if(c == '{'){               stack.push('}');           }else if(c=='['){               stack.push(']');           }else if(stack.empty() || c != stack.pop()){               return false;           }       }       if(stack.empty()){            return true;        }        return false;    }}
 
121. 买卖股票的最佳时机
 
两层循环超出时间，思路是：要在价格最低的那天买入用min来记录，那第i天的利益就是prices[i] - min，这样只需要一次循环。
 
class Solution {    public int maxProfit(int[] prices) {        int min = Integer.MAX_VALUE;        int max = 0;        for(int i = 0; i  max){                max = prices[i] - min;            }        }        return max;    }}
 
70. 爬楼梯
 
思路：跟斐波拉契数列思路很像，只是初始值不同。f(0) = 1，f(1) = 1，f(2) = 2。状态转移方程是：f(n) = f(n - 1) + f(n - 2)。如果是建立长度为n的dp数列，则空间复杂度是O(n)，可以用滚动数组的思想进行状态压缩。
 
class Solution {    public int climbStairs(int n) {        int sum = 1; //相当于f(n)，f(n - 1) + f(n - 2)        int i = 0, j = 0;         for(int k = 0; k  
118. 杨辉三角
 
思路：两层循环，i表示行数，第一个和最后一个都是1，即j == 0 || j == i。中间的数就是上一行左上角加右上角，即[i - 1][j] + [i - 1][j - 1]。
 
class Solution {    public List generate(int numRows) {        List ret = new ArrayList();        for(int i = 0; i