Category: Easy

Posted 2022-06-21Updated 2022-06-21LeetCode / Easya minute read (About 142 words)

Question

You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Solution

数组统计，先遍历宝石，记录宝石的位置。
然后遍历石头，如果对应的位置已被记录则计数加一。

Code

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int ret = 0;
        int[] bin = new int[58];
        for(char c : jewels.toCharArray()){
            bin[c-'A']++;
        }
        
        for(char c : stones.toCharArray()){
            if(bin[c-'A'] != 0) ret++;
        }
        return ret;
    }
}

Posted 2022-06-21Updated 2022-06-21LeetCode / Easya few seconds read (About 72 words)

1108. Defanging an IP Address

Question

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Solution

迭代每个字符，用StringBuffer类来组成新的字符串。

Code

class Solution {
    public String defangIPaddr(String address) {
        StringBuffer sb = new StringBuffer();
        for(char c : address.toCharArray()){
            if(c == '.'){
                sb.append("[.]");
            }
            else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-06-12Updated 2022-06-11LeetCode / Easy2 minutes read (About 255 words)

2299. Strong Password Checker II

Question

A password is said to be strong if it satisfies all the following criteria:

It has at least 8 characters.

It contains at least one lowercase letter.

It contains at least one uppercase letter.

It contains at least one digit.

It contains at least one special character. The special characters are the characters in the following string: "!@#$%^&*()-+".

It does not contain 2 of the same character in adjacent positions (i.e., "aab" violates this condition, but "aba" does not).

Given a string password, return true* if it is a strong password*. Otherwise, return false.

Solution

直接遍历，记录四个真值对应四个符号，初始化为false，和上一个字符last。
每次遍历检查当前字符，如果等于上个字符则直接返回false。
根据字符范围来改变四个真值，最后返回四个真值的和运算。

Code

class Solution {
    public boolean strongPasswordCheckerII(String password) {
        if(password.length() < 8) return false;
        char last = ' ';
        boolean hasLower = false, hasUpper = false, hasDigit = false, hasSpecial = false;
        char[] word = password.toCharArray();
        
        for(int i = 0; i < password.length(); i++){
            char cur = word[i];
            if(last == cur) return false;
            if(cur >= 'a' && cur <= 'z') hasLower = true;
            else if(cur >= 'A' && cur <= 'Z') hasUpper = true;
            else if(cur >= '0' && cur <= '9') hasDigit = true;
            else hasSpecial = true;
            last = cur;
        }
        
        return hasLower && hasUpper && hasDigit && hasSpecial;
    }
}

Posted 2022-06-09Updated 2022-06-10LeetCode / Easy2 minutes read (About 246 words)

1332. Remove Palindromic Subsequences

Question

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Solution

当字符为空时，返回0。
注意本题中的子序列不需要连续。
由于只有’a’与’b’两个字符，因此最多两步即可将字符串清空。

辅助方法判断字符串是否为回文字符串。
如果为真则返回1，只需要删除一次。

如果为假则返回2，需要先删除所有的’a’，再删除所有的’b’。

Code

class Solution {
    public int removePalindromeSub(String s) {
        if(s.length() == 0) return 0;
        return isPalindrome(s) ? 1 : 2;
    }
    
    private boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(j > i){
            if(s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

Posted 2022-06-02Updated 2022-06-01LeetCode / Easya few seconds read (About 107 words)

867. Transpose Matrix

Question

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Solution

记录一个新数组res[][]。

双重循环，交换下标将matrix[i][j]复制到res[j][i]，最后返回。

Code

class Solution {
    public int[][] transpose(int[][] matrix) {
        int[][] res = new int[matrix[0].length][matrix.length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }
}

Posted 2022-06-01Updated 2022-06-01LeetCode / Easya few seconds read (About 85 words)

1480. Running Sum of 1d Array

Question

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Solution

类似动态规划，遍历数组，并将当前位置的元素和上一个位置的元素进行加和。

Code

class Solution {
    public int[] runningSum(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i-1];
        }
        return nums;
    }
}

Posted 2022-05-28Updated 2022-05-27LeetCode / Easya minute read (About 220 words)

268. Missing Number

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution 1

采用数学方法，从0到n的和减去从nums中的每个元素的和，得到的即是缺失的数字。
循环所有下标，每次在结果上加上下标的值，并减去下标对应的元素。最后需要再加上nums内元素数量+1的值。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum -= nums[i];
            sum += i;
        }
        
        return sum;
    }
}

Solution 2

遍历，采用一个数组found[]记录是否访问过。
再次遍历，如果存在未访问过的位置，则返回下标。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        int[] found = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++){
            found[nums[i]] = 1;
        }
        
        for(int i = 0; i <= nums.length; i++){
            if(found[i] == 0) res = i;
        }
        return res;
    }
}

Posted 2022-05-27Updated 2022-05-27LeetCode / Easya few seconds read (About 97 words)

1342. Number of Steps to Reduce a Number to Zero

Question

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Solution

循环，当num不等于零时，如果为奇数则减一，如果为偶数则除以2。
每次循环记录次数。

Code

class Solution {
    public int numberOfSteps(int num) {
        int count =0;
        while(num != 0){
            count++;
            if((num & 1) == 0){
                num/=2;
            }
            else{
                num--;
            }
        }
        return count;
    }
}

Posted 2022-05-22Updated 2022-05-21LeetCode / Easya few seconds read (About 90 words)

2278. Percentage of Letter in String

Question

Given a string s and a character letter, return* the percentage of characters in s that equal letter rounded down to the nearest whole percent.*

Solution

一次遍历，计算字符出现的次数。
返回字符出现的次数除以字符长度乘以100。

Code

class Solution {
    public int percentageLetter(String s, char letter) {
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == letter){
                count++;
            }
        }
        return count * 100 / s.length();
    }
}

Posted 2022-05-15Updated 2022-05-14LeetCode / Easy2 minutes read (About 319 words)

2273. Find Resultant Array After Removing Anagrams

Problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Solution

由于只用查看上一个元素。
记录一个prev[]数组记录上一个元素的字符情况。
遍历words，用数组bin[]统计每个字母出现的次数，同时减去prev数组的统计数字。
如果数组中的每个统计结果都为0，则是上一个字符串的Anagram。
否则是一个新的字符串，将其加入结果。
然后将上一个数组prev更新为当前的统计数组bin[]。

Code

class Solution {
    public List<String> removeAnagrams(String[] words) {
        int[] prev = new int[26];
        
        List<String> ans = new ArrayList<>();
        
        for(String word : words){
            int[] bin = new int[26];
            char[] chars = word.toCharArray();
            for(int i = 0; i < chars.length; i++){
                prev[chars[i]-'a']--;
                bin[chars[i]-'a']++;
            }
            if(!allZero(prev)){
                ans.add(word);
            }
            prev = bin;
        }
        return ans;
    }
    
    private boolean allZero(int[] bin){
        for(int num : bin){
            if(num != 0) return false;
        }
        return true;
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Easy / 复习2 minutes read (About 353 words)

202. Happy Number

Question

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Solution

首先证明，快乐数的计算不会趋近于无穷大。
我们可以考虑每一个位数的最大数字（9999…999）。
其下一个数值等于(81*n)。
对于三位数以下，其最大的值得下一个结果不会大于243。
对于四位数以上，下一个结果会快速收缩到三位数。
因此计算结果不会趋近于无穷。

当我们计算快乐数的值时，形成了一个隐式链表。
因此我们可以用快慢指针的方式，查询链表上是否有环。
快指针比慢指针初始值快1个单位，且移动速度为慢指针的一倍。
如果链表中有环，则两者终能相遇。
如果fast指针先走到1，等于走到了链表的终点。

Code

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while(fast != 1 && fast != slow){
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        return fast == 1;
    }
    
    private int getNext(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += (digit * digit);
            n = n / 10;
        }
        return sum;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Easy2 minutes read (About 366 words)

225. Implement Stack using Queues

Question

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.

int pop() Removes the element on the top of the stack and returns it.

int top() Returns the element on the top of the stack.

boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Solution

用两个队列实现栈。一个队列存放压入的元素。

push()

将当前元素加入到第一个队列。

top() & pop()

当需要挤出或者查看栈顶时，第一个队列只保留一个元素，其余元素加入第二个队列。最后一个元素就是栈顶。当第一个队列为空时，交换第一个队列与第二个队列。

empty()

返回两个队列是否均为空。

Code

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
        
    }
    
    public void push(int x) {
        q1.add(x);
    }
    
    public int pop() {
        move();
        return q1.poll();
    }
    
    public int top() {
        move();
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    
    private void move(){
        if(q1.isEmpty()){
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        while(q1.size() != 1){
            q2.add(q1.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

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

997. Find the Town Judge

Question

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.

Everybody (except for the town judge) trusts the town judge.

There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Solution

题目可以转换为计算各个顶点的入度和出度。

遍历每条边，并计算边上两个顶点的出度和入度。
如果某个节点的入度为n-1，出度为0，则符合有法官的条件。
否则没有法官，返回-1。

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n];
        int[] outDegrees = new int[n];
        
        for(int[] edge : trust){
            outDegrees[edge[0]-1]++;
            inDegrees[edge[1]-1]++;
        }
        for(int i = 0; i < n; i++){
            if(outDegrees[i] == 0 && inDegrees[i] == n-1) return i+1;
        }
        return -1;
    }
}

Posted 2022-05-02Updated 2022-05-01LeetCode / Easya minute read (About 148 words)

905. Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

双指针，右侧指针之后存放奇数项。
当左侧指针的元素为奇数时，交换left和right上的元素。然后将右侧指针左移。
当左侧指针的元素为偶数时，左侧指针左移。

class Solution {
    int[] arr;
    public int[] sortArrayByParity(int[] nums) {
        arr = nums;
        int left = 0;
        int right = nums.length-1;
        
        while(left < right){
            if(nums[left] % 2 == 1){
                swap(left, right);
                right--;
            }
            else{
                left++;
            }
        }
        return arr;
    }
    
    private void swap(int left, int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

Posted 2022-05-02Updated 2022-05-01LeetCode / Easy / 复习2 minutes read (About 237 words)

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

以中序遍历的顺序创建节点（代码实现时先序遍历），每次选择范围的中间值mid为根节点。
根节点的左子节点递归左侧left直到mid-1的位置。
根节点的右子节点递归mid+1直到右侧right的位置。
当left > right时，返回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 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
    
    private TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid-1);
        root.right = build(nums, mid+1, right);
        
        return root;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Problem

Solution

Code

Question

Solution

Code

Question

Solution

push()

top() & pop()

empty()

Code

Question

Solution

Code

Recents

Archives

Links