Category: Easy

Posted 2022-04-30Updated 2022-04-29LeetCode / Easy / 复习a minute read (About 203 words)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

分别将数据保存在一个Priority Queue和一个栈中。
pop方法pop掉stack的内容，然后将其从优先队列中移除。
top方法返回stack的栈顶。
getMin方法返回优先队列的顶。

class MinStack {
    Queue<Integer> pq;
    Stack<Integer> stack;
    public MinStack() {
        pq = new PriorityQueue<>();
        stack = new Stack<>();
    }
    
    public void push(int val) {
        pq.add(val);
        stack.add(val);
    }
    
    public void pop() {
        int i = stack.pop();
        pq.remove(i);
        
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return pq.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Posted 2022-04-26Updated 2022-04-26LeetCode / Easy2 minutes read (About 353 words)

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

计算两个链表的长度。将长的链表向下移动两者长度的差，对齐两个链表的长度。
同时向下移动两个链表，如果两个节点的内存地址相同，则返回节点。否则返回null。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0, sizeB = 0;
        ListNode l1 = headA, l2 = headB;
            
        while(l1 != null){
            l1 = l1.next;
            sizeA++;
        }
        while(l2 != null){
            l2 = l2.next;
            sizeB++;
        }
        if(sizeA > sizeB){
            int size = sizeA - sizeB;
            while(size != 0){
                headA = headA.next;
                size--;
            }
        }
        else{
            int size = sizeB - sizeA;
            while(size != 0){
                headB = headB.next;
                size--;
            }
        }
        while(headA != null){
            if(headA == headB) return headA;
                headA = headA.next;
                headB = headB.next;
        }
        return null;
    }
}

遍历移动一个链表，将其加入哈希集合。
然后移动另一个链表，如果哈希集合中有重复节点，则返回该节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

Posted 2022-04-22Updated 2022-04-21LeetCode / Easy2 minutes read (About 256 words)

572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

帮助方法isEqual，DFS搜索判断两个节点的子节点是否完全相同。
DFS搜索，如果两个根节点的值相等则返回，且调用isEqual方法，如果子节点都相同则返回。

/**
 * 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 boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot) != null;
    }
    
    private TreeNode dfs(TreeNode root, TreeNode subRoot){
        if(root == null) return null;
        if(root.val == subRoot.val && isEqual(root, subRoot)) return root;
        if(dfs(root.left, subRoot) != null ) return dfs(root.left, subRoot);
        else return dfs(root.right, subRoot);
    }
    
    private boolean isEqual(TreeNode root, TreeNode subRoot){
        if(root == null || subRoot == null) return root == subRoot;
        if(root.val != subRoot.val) return false;
        return isEqual(root.left, subRoot.left) && isEqual(root.right, subRoot.right);
    }
}

Posted 2022-04-21Updated 2022-04-21LeetCode / Easy / 复习2 minutes read (About 299 words)

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

先将s分割成数组。
如果words的长度和pattern的长度不同则返回false。
用长度为26的数组储存pattern的字符。
同时遍历words和pattern，将pattern的字符换算成数字作为index，将words[i]填入数组。
如果数组中已经有word存在，则检查新的word和数组内的word是否相等。
如果不相等，则返回false。

最后遍历数组，比对各个字符中对应的word是否相等，如果有相等的，则返回false。由于数组长度固定，因此这个操作的时间复杂度是O(1)。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        String[] alphabet = new String[26];
        
        if(words.length != pattern.length()){
            return false;
        }
        
        for(int i = 0; i < pattern.length(); i++){
            
            if( alphabet[pattern.charAt(i) - 'a'] != null){
                if(!alphabet[pattern.charAt(i) - 'a'].equals(words[i])){
                    return false;
                }
            }
            else{
                alphabet[pattern.charAt(i) - 'a']  = words[i];
            }
        }
        
        for(int i = 0; i < alphabet.length; i++){
            for(int j = i+1; j < alphabet.length; j++){
                if(alphabet[i] == null || alphabet[j] == null){
                    continue;
                }
                if(alphabet[i].equals(alphabet[j])){
                    return false;
                }
            }
        }
        
        return true;
    }
}

Posted 2022-04-21Updated 2022-04-20LeetCode / Easya minute read (About 159 words)

415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

按照正常加法计算方法即可。
先将指针设置在两个String的末尾。
每次计算位置上加和的结果。
最后需要将字符串翻转过来。

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        
        StringBuffer ans = new StringBuffer();
        
        while( i >= 0 || j >= 0 || carry > 0){
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + carry;
            
            ans.append(result % 10);
            carry = result / 10;
            
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }
}

Posted 2022-04-21Updated 2022-05-04LeetCode / Easy / 复习a minute read (About 210 words)

409. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

回文字符串除了中心一个元素，其他的字符必须成对出现。因此可以直接统计字符串里有几组成对的字符。

用数组记录字符出现的次数。
如果数组中某个字符出现了两次，则可以将其归零。然后可以组成的最长回文数字加2。
如果字符串还剩下其他字符未选择，则最长回文数可以加一。

class Solution {
    public int longestPalindrome(String s) {
        int[] alphabet = new int['z' - 'A' + 1];
        int count = 0;
        int total = s.length();
        
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'A';
            alphabet[index]+=1;
            if( alphabet[index] == 2 ){
                total -= 2;
                count += 2;
                alphabet[index] = 0;
            }
        }
        
        if(total != 0){
            count++;
        }

        return count;
    }
}

Posted 2022-04-21Updated 2022-05-02LeetCode / Easya minute read (About 181 words)

705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

void add(key) Inserts the value key into the HashSet.

bool contains(key) Returns whether the value key exists in the HashSet or not.

void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

计算哈希值，使用数组实现Hash Set。

class MyHashSet {
    int PRIME = 1009;
    List<Integer>[] data;
    
    public MyHashSet() {
        data = new List[PRIME];
        for(int i = 0; i < PRIME; i++){
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        if(!contains(key)){
            int h = getHash(key);
            data[h].add(key);
        }
    }
    
    public void remove(int key) {
        int h = getHash(key);
        data[h].remove(new Integer(key));
    }
    
    public boolean contains(int key) {
        int h = getHash(key);
        for( int num : data[h] ){
            if( num == key ){
                return true;
            }
        }
        return false;
    }
    
    private int getHash(int o){
        return o % PRIME;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

Posted 2022-04-18Updated 2022-04-18LeetCode / Easya minute read (About 137 words)

119. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

根据杨辉三角形的规则递归。
每次递归行数-1。
根据上一行的返回值，生成新行的列表，然后返回。
如果生成行数为0则返回{1}。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        if(rowIndex == 0){
            List<Integer> ret = new ArrayList();
            ret.add(1);
            return ret;
        }
        
        List<Integer> arr = getRow(rowIndex - 1);
        List<Integer> ret = new ArrayList();
        
        for(int i = 0; i < arr.size()+1; i++){
            if(i == 0 || i == arr.size()){
                ret.add(1);
            }
            else{
                ret.add(arr.get(i) + arr.get(i-1));
            }
        }
        return ret;
    }
}

Posted 2022-04-18Updated 2022-04-19LeetCode / Easy / 复习3 minutes read (About 431 words)

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

哈希表，先设置一个素数Prime作为map的尺寸。
（这里设置成素数是为了减少可能的碰撞。）
创建一个Pair类记录key和value。

map初始化时需要生成一个LinkedList数组。

hash方法计算哈希值。用key % Prime并返回。
put方法，根据key计算其哈希值h。如果列表中有则重新设置当前Pair的value。
get方法，根据哈希值h搜索并查找链表中的Pair，如果找到则返回Pair，否则返回-1。
remove方法，根据哈希值h搜索并remove链表中的Pair。

class MyHashMap {
    final int PRIME = 1009;
    List<Pair>[] map;
    public MyHashMap() {
        map = new LinkedList[PRIME];
        for(int i = 0; i < PRIME; i++){
            map[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                p.setValue(value);
                return;
            }
        }
        Pair p = new Pair(key, value);
        map[h].add(p);
    }
    
    public int get(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                return p.value;
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                map[h].remove(p);
                return;
            }
        }
    }
    
    private int hash(int key){
        return key % PRIME;
    }
}

class Pair {
    int key;
    int value;
    public Pair(int k, int v){
        key = k;
        value = v;
    }
    
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
    public void setValue(int v){
        value = v;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Posted 2022-04-17Updated 2022-04-17LeetCode / Easya minute read (About 210 words)

897. Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

DFS搜索，在递归时将in-order遍历节点，并将其加入队列。
从队列中挤出节点，将上一个节点的右子节点设置为下一个节点。
同时需要将下一个节点的左子节点设置为null。
`

/**
 * 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 {
    Queue<TreeNode> q;
    public TreeNode increasingBST(TreeNode root) {
        q = new LinkedList();
        dfs(root);
        TreeNode head = q.poll();
        TreeNode curr = head;
        while(!q.isEmpty()){
            curr.left = null;
            curr.right = q.poll();
            curr = curr.right;
        }
        curr.left = null;
        return head;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        q.offer(root);
        dfs(root.right);
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy / 复习2 minutes read (About 311 words)

190. Reverse Bits

问题
Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

创建返回值ans。
每次向左移动一位ans，然后取n的尾数进行二进制或运算（相当于在尾部进行不进位的加和）。
然后将n向左移动一位。

二进制下的或运算只保留两数间较大的位。(0011 | 0110 = 0111)
二进制下的与运算只保留两数间皆为1的位。(0011 & 0110 = 0010)
掩码（Mask）是在二进制下进行与运算。以1作为掩码时，前面的31为皆为0，因此进行与运算后只保留最后一位。

因此(n & 1)相当于n的二进制与000…001运算，只保留n的尾数。
然后(ans << 1)向左移动一位，用 | 操作将n的尾数加入ans。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans = (ans << 1) | (n & 1);
            n >>= 1;
        }
        return ans;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy4 minutes read (About 526 words)

169. Majority Element

问题
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore投票算法
基本思想：
众数的值为+1，非众数的值为-1。其加和作为投票值。
遍历整个数组，由于众数数量大于非众数，因此最后结果一定为正数。

设置count记录票数，遍历数组。
当count为0时，则将当前的数组设为众数。当之后的数字与其相等，则count+1，反之则-1。
遍历完成后返回当前的众数。

根据以上规则，每次我们选择的众数，都是已遍历数组范围内出现最多次数的数值之一。
由于给定的数组的众数超过半数，因此遍历到最后的众数，一定是整个数组中出现最多次的数值。

核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        
        for(int num : nums){
            if(count == 0){
                major = num;
            }
            if(major == num){
                count++;
            }
            else{
                count--;
            }
        }
        return major;
    }
}

遍历数组，并将各个数值出现的次数记录在哈希表中。
当出现的次数大于数组的一半，则该数值是众数。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
            if(map.get(num) > nums.length/2){
                return num;
            }
        }
        return -1;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy / 复习a minute read (About 154 words)

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

位运算，对所有数值做二进制异或运算。
两个同样的值异或运算会等于0，最后和与单独的数字相等。

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int num : nums){
            ans = ans ^ num;
        }
        return ans;
    }
}

排序，然后遍历数组，如果第i个值不等于第i+1个则返回。

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; i+=2){
            if(nums[i] != nums[i+1]){
                return nums[i];
            }
        }
        return nums[nums.length-1];
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easya minute read (About 197 words)

653. Two Sum IV - Input is a BST

问题
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

DFS搜索，每次递归时检查HashSet中是否有当前节点的值。如没有则将目标值减去当前节点的值加入HashSet。如有则返回true。
递归左侧节点和右侧节点，并返回二者的或运算。

/**
 * 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 {
    HashSet<Integer> set;
    public boolean findTarget(TreeNode root, int k) {
        set = new HashSet();
        return dfs(root,k);
    }
    
    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return false;
        }
        if(set.contains(root.val)){
            return true;
        }
        set.add(k - root.val);

        return dfs(root.left,k) || dfs(root.right,k);
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easya minute read (About 221 words)

235. Lowest Common Ancestor of a BST

问题
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

DFS搜索，如果当前节点为null，则返回null。
如果当前节点小于p和q的值，则递归其左子节点。
反之递归其右子节点。
如果当前节点在p与q之间，则返回当前节点。
该节点是p与q的Lowest Common Ancestor。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

Recents

Archives

Links