力扣100题easy
1. 两数之和
时间空间复杂度为O(N)，思路是：创建一个哈希表，对于每一个 x，先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
if(hashtable.containsKey(target - nums[i])){ //存在target - x
return new int[]{i, hashtable.get(target - nums[i])};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
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 < l2.val) {
l1.next = mergeTwoLists(l1.next, l2); //选了此时的l1，再l1.next与l2比小
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
160. 相交链表
思路一：哈希集合存放不重复的元素，先将A链表的结点add后，再依次判断B链表的结点是否有相同的。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<ListNode>();
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<Integer> array = new ArrayList<Integer>();
ListNode p = head;
while(p != null){
array.add(p.val);
p = p.next;
}
//用双指针判断是否是回文
int front = 0;
int back = array.size() - 1;
while(front < back){
if(!array.get(front).equals(array.get(back))){
return false;
}
front++;
back--;
}
return true;
}
}
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 < nums.length; i++){
if(nums[i] != 0){
nums[j++] = nums[i];
}
}
for(int i = j; i < nums.length; i++){
nums[i] = 0;
}
}
}
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<Character> stack = new Stack<Character>();
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 < prices.length; i++){
if(prices[i] < min){
min = prices[i];
}else if(prices[i] - min > 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 < n; k++){
//数组向前移动
i = j;
j = sum;
sum = i + j;
}
return sum;
}
}
118. 杨辉三角
思路：两层循环，i表示行数，第一个和最后一个都是1，即j == 0 || j == i。中间的数就是上一行左上角加右上角，即[i - 1][j] + [i - 1][j - 1]。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for(int i = 0; i < numRows; i++){ //代表当前行数
List<Integer> list = new ArrayList<Integer>();
for(int j = 0; j <= i; j++){
if(j == 0 || j == i){
list.add(1);
}else{
list.add(ret.get(i - 1).get(j) + ret.get(i - 1).get(j - 1));
}
}
ret.add(list);
}
return ret;
}
}
136. 只出现一次的数字
思路：用异或运算。num与0异或还是num，num与num异或是0，并且符合交换律吧。将数组中所有数字异或，出现两次的数异或后均为0，最后剩下的数就是只出现一次的数。
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int num : nums){
single ^= num;
}
return single;
}
}
169. 多数元素
思路：先将数组排序，既然多数元素出现次数大于⌊ n/2 ⌋，那排序后它一定在nums[length / 2]的位置。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}