LeetCode刷题笔记2（Easy题）

题目来源：力扣（LeetCode）https://leetcode-cn.com

本人水平较低，整理供个人学习回顾

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

class Solution {
    public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> list = new ArrayList<>();
       int[][] arr = new int[numRows][numRows];
       for(int i = 0;i<numRows;i++){
        List<Integer> subList = new ArrayList<>();
           for(int j =0;j<=i;j++){
               if(j==0||j==i){
                   arr[i][j] = 1;
               }else{
                   arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
               }
               subList.add(arr[i][j]);
           }
           list.add(subList);
       }
       return list;
    }
}

119. 杨辉三角 II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

解题思路：如何查找数组中两个相同的元素遍历数组每一个元素存入到set集合中，根据key的唯一性，来判断是否重复

class Solution {
    public boolean containsDuplicate(int[] nums) {
     Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }
        return false;
  }
}

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

解题思路：如何查找数组中两个相同的元素遍历数组每一个元素存入到map中，此时要将nums[i]的值作为key，而下标i作为value。方便后续处理

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
      Map<Integer,Integer> map = new HashMap<Integer,Integer>();
      for(int i = 0;i<=nums.length-1;i++){
          int num = nums[i];
          if(map.containsKey(num)&&i-map.get(num)<=k){
              return true;
          }else{
              map.put(num,i);
          }
      }
      return false;
    }
}

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

解题思路：可以直接使用String内置函数indexOf()来检索t串中是否有s串，也可以使用双指针的思路求解

使用内置IndexOf()函数

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.equals("")||null==s) return true;
        if(s.length()>t.length()) return false;
         int index = -1;
        for (char c : s.toCharArray()){
            index = t.indexOf(c, index+1);
            if (index == -1) return false;
        }
        return true;
    }
}

使用双指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() > t.length()) return false;
        if(s.equals("")||s==null) return true;
        int n = s.length();
        int m = t.length();
        int i = 0,j = 0;
        while(i < n && j < m){
            if(s.charAt(i)==t.charAt(j))
            {i++;}
            j++;
            if(i==n) return true;
        }
        return false;
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路：用map集合。首先将magazine字符串存储到map中。 key=字符。value=该字符出现的次数。然后对ransomNote遍历，每遍历一个字符去map中找。如果找不到或者该字符的使用次数已经用完。直接return false；如果找到并且有效，说明当前字符可以被组成。当能够遍历完毕ransomNote字符串，说明magazine可以组成ransomNote。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
      Map<Character,Integer> map = new HashMap<>();
      for(int i = 0;i<magazine.length();i++){
          char key = magazine.charAt(i);
          map.put(key,map.get(key)==null ? 1 : map.get(key)+1);
      }
      for(int i = 0;i<ransomNote.length();i++){
          char key = ransomNote.charAt(i);
          Integer value = map.get(key);
          if(value==null||value<1) return false;
          map.put(key,value-1);
      }
      return true;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
    StringBuilder stringbuilder = new StringBuilder(magazine);
    int index;
    for(char c : ransomNote.toCharArray()){
        index = stringbuilder.indexOf(String.valueOf(c));
        if(index>=0){
            stringbuilder.deleteCharAt(index);
        }else{
            return false;
        }
    }
    return true;
}
}

389. 找不同

给定两个字符串 s 和 t ，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

解题思路：将字符串 s 中每个字符的 ASCII 码的值求和得到sums，同样对t求和得到sumt，sumt-sums就是增加的字符的Ascii码。

class Solution {
    public char findTheDifference(String s, String t) {
       int sums = 0;
       int sumt = 0;
       for(int i = 0;i<s.length();i++){
           sums+=s.charAt(i);
       }
        for(int i = 0;i<t.length();i++){
           sumt+=t.charAt(i);
       }

      return (char)(sumt-sums); 
    }
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

解题思路： dp[i]表示达到第i级（停止在第i级）台阶上，最小的cost，到达第i级，可以由i-2级跨2步，或者i-1级跨1步，其实最终到达第n级，或者第n-1级（大不了再跨2步，不增加cost）都可以。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 到达第1级的cost
     int pre = cost[0];
         // 到达第2级cost
     int cur = cost[1];
         // 到达第3级到第n级（最后一级）
     for(int i = 3;i<=cost.length;i++){
         int temp = cur;
         cur = Math.min(pre,cur) + cost[i-1];
         pre = temp;
     }
     return Math.min(cur,pre);
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则,返回 false 。

解题思路：我们可以定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，快指针也在位置 head。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast) return true;
        }
        return false;
    }
}

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

解题思路：小于min时push了两个，先push原min再push新min。

即最小值下存放一个次小值，弹出最小值时会连同次小值一起弹出。这时次小值变最小值，从而确保min一直都是最小的

class MinStack {
    private int min = Integer.MAX_VALUE;
    private Stack<Integer> stack;
    public MinStack() {
      stack = new Stack<>();
    }
    
    public void push(int val) {
      if(min >= val){
          stack.push(min);
          min = val;
      }
      stack.push(val);
    }
    
    public void pop() {
     if(stack.pop()==min){
         min = stack.pop();
     }
    }
    
    public int top() {
     return stack.peek();
    }
    
    public int getMin() {
      return min;
    }
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。

解题思路：1.可以使用hashmap解决问题，但有一种更巧妙的办法，利用两个链表的长度差第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)，两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA==null ? headB : pA.next;
            pB = pB==null ? headA : pB.next;
        }
        return pA;
  } 
}

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：排序后，返回数组中间的元素即可

   class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

或者采用map

class Solution {
    private Map getMap(int[] nums){
       Map<Integer,Integer> hashmap = new HashMap<>();
       for(int num:nums){
          if(hashmap.containsKey(num)){    
           hashmap.replace(num,hashmap.get(num) + 1);   
          }else{
             hashmap.put(num,1); 
          }
       }
       return hashmap;
    }
    public int majorityElement(int[] nums) {
    Solution sl = new Solution();
     Map<Integer,Integer> hashmap = sl.getMap(nums);
      Set<Integer> set = hashmap.keySet();
      for(int key:set){
          if(hashmap.get(key) > nums.length/2){
              return key;
          }
      }
      return 0;
    }
}

还有一种投票法因此我们可以假设数组的第一个数字为target，然后遍历数组，我们尝试用计数count模拟这个抵消的过程，规则如下：

1）当数组中的元素与假设的target不相等时，计数count减1，即模拟不同数字相互抵消；

2）假设数组中的元素与假设的target相等时，计数count加1；

3）当计数count等于0时，说明在当前遍历到的数组元素中，当前假设的target与其他数字相互抵消（个数相同），所以我们重新假设下一个遍历的数组元素为target,继续上面过程。

4）当遍历完数组后，target为所求数字。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int target = 0;

        for (int num : nums) {
            if (count == 0) {
                target = num;
            }
            count += (num == target) ? 1 : -1;
        }

        return target;
    }
}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution {
    public ListNode reverseList(ListNode head) {
       if(head == null) return null;
       ListNode pre = null;
       ListNode cur = head;
       while(cur != null){
           ListNode next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       return pre; 
    }
}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路：简单递归即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
      if(root==null) return null;
      TreeNode temp = root.left;
      root.left = root.right;
      root.right = temp;
      invertTree(root.left);
      invertTree(root.right);
      return root; 
    }
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解题思路: 整个解题思路可以分为以下五个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否为回文链表。
恢复原有链表。
返回结果。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        ListNode preHalfEnd = findPreHalfList(head).next;
        ListNode behindHalfReverseStart = behindHalfReverse(preHalfEnd);
        // 判断是否是回文的 
        ListNode p1 = head;
        ListNode p2 = behindHalfReverseStart;
        boolean result = true;
        while(result && p2!=null){
            if(p1.val != p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
       //再翻转回后一半链表拼接回去
       preHalfEnd = behindHalfReverse(behindHalfReverseStart);
       return result;
    }
     //找到前半部分链表的尾节点
     private ListNode findPreHalfList(ListNode head){
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
                slow = slow.next;  
            }
            return slow;
        }
        // 翻转后半部分链表
        private ListNode behindHalfReverse(ListNode head){
          ListNode cur = head;
          ListNode pre = null;
          while(cur != null){
            ListNode next = cur.next;
              cur.next = pre;
              pre = cur;
              cur = next;
          }
          return pre;
        }
}