LeetCode-Easy

779 阅读8分钟

1.Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Input: "()"
Output: true
Input: "([)]"
Output: false
Input: "{[]}"
Output: true
class Solution {
    public boolean isValid(String s) {
        if(s==null || s.length()%2!=0){
            return false;
        }
        String r = "";
        for(int i=0;i<s.length();i++){
            char curr = s.charAt(i);
            //检查当前位置字符是 括号的开头还是结尾
            if(curr == ')' || curr == ']' || curr == '}'){
                //如果当前位置字符是 括号的结尾
                //检查拼接的字符串的上一个字符是否可对应消除
                if(r == ""){
                    //如果拼接的字符串为空:错
                    return false;
                }else if(curr == ')'&&r.charAt(r.length()-1)=='('){
                    r = r.substring(0,r.length()-1);
                }else if(curr == ']'&&r.charAt(r.length()-1)=='['){
                    r = r.substring(0,r.length()-1);
                }else if(curr == '}'&&r.charAt(r.length()-1)=='{'){
                    r = r.substring(0,r.length()-1);
                }else{
                    //如果拼接的字符串的上一个字符不可对应消除:错
                    return false;
                }
            }else{
                //如果当前位置 是括号的开头
                //无法消除,则继续拼接字符串
                r += curr;
            }
        }
        //最后检查拼接的字符串长度,长度!=0,说明有括号未对应消除掉:错
        return r.length()==0;
    }
}
class Solution {
    public boolean isValid(String s) {
        if(s.length() != 0 && s.length()%2 != 0){
            return false;
        }
        char[] c = new char[s.length()];
        char curr;
        int length = 0;
        for(int i = 0;i<s.length();i++){
            curr = s.charAt(i);
            if(length > 0 && (curr==')'||curr==']'||curr=='}') && match(curr,c[length-1])){
                length --;
            }else{
                c[length] = curr;
                length++;
            }
        }
        return length == 0;
    }
    public boolean match(char curr,char pre){
        if(curr == ')' && pre == '('){
            return true;
        }
        if(curr == ']' && pre == '['){
            return true;
        }
        if(curr == '}' && pre == '{'){
            return true;
        }
        return false;
    }
}

2.N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.
Return the element repeated N times.

Input: [1,2,3,3]
Output: 3
Input: [2,1,2,5,3,2]
Output: 2
思路:
1:
既然有1个数字占据了数组的1/2,我们将数组进行分割,2个元素1组,极端情况下用于看不到重复元素.
但是如果3个元素一组, 即使是极端情况,我们也可以在某一组3个元素中检查到重复对象,
如果检查不到,分组剩下的元素就一定是目标值.
2:
当然可以利用现成的API,使用Set.add每个元素,通过返回的boolean值来判断是否取到重复元素.
class Solution {
    public int repeatedNTimes(int[] A) {
        int count = A.length/3;
        for(int i=0;i<count;i++){
            if(A[i*3] == A[i*3 + 1] || A[i*3] == A[i*3 + 2]) return A[i*3];
            if(A[i*3 + 1] == A[i*3 + 2]) return A[i*3 + 1];
        }
        return A[3*count];
    }
}

3.Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn't matter what values are set beyond the returned length.
class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums==null||nums.length==0) return 0;
        //首先定义返回值length,默认为0
        int length = 0;
        for(int i=0;i<nums.length;i++){
            //如果遍历元素和给定值不同,则将length对应的索引指向当前元素,然后length+1
            if(nums[i]!=val) nums[length++]=nums[i];
        }
        return length;
    }
}

4.Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1==null ? l2 : l1;
        ListNode first = l1.val < l2.val ? l1 : l2;
        ListNode second = first == l1 ? l2 : l1;
        first.next = mergeTwoLists(first.next,second);
        return first;
    }
}

5.Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
思路:
既然是已经排好序的数组去除重复值,可以让 下一个元素/j 和 当前元素/i 作比较:
如果两者相等,则返回值不变.
如果两者不相等,将当前返回值索引指向当前元素/j,并将返回值+1
每次遍历,i和j都+1
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        if(nums.length==1) return 1;
        int length = 1;
        int i = 0;
        for(int j = 1;j<nums.length;j++){
            if(nums[j]!=nums[i]){
                nums[length] = nums[j];
                length++;
            }
            i++;
        }
        return length;
    }
}

6.Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            Integer targetKey = target - nums[i];
            if(map.containsKey(targetKey)){
                return new int[]{map.get(targetKey),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

7.Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Input: 123
Output: 321
Input: -123
Output: -321
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
class Solution {
    public int reverse(int x) {
        int result = 0;
        while(x != 0){
            int tail = x % 10;
            x /= 10;
            if(result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && tail > 7)){
                return 0;
            }
            if(result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && tail < -8)){
                return 0;
            }
            result = result * 10 + tail;
        }
        return result;
    }
}

8.Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Input: 121
Output: true
Input: -121
Output: false

Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
思路1:将整数从中间分隔,然后依次比较'首尾对应的2个数字'是否相等,出现不等说明不是回文数
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }
        if(x < 10){
            return true;
        }
        int length = (int)(Math.log10(x) + 1);
        for(int i = 0; i < length/2; i++){
            if(x/((int)Math.pow(10,i))%10 != x/((int)Math.pow(10,length-1-i))%10){
               return false; 
            }
        }
        return true;
    }
}
思路2:将整数直接反转,然后比较反转后数字和元数字是否相等,相等即为回文数
class Solution {
    public boolean isPalindrome(int x) {
        if(x<0 || (x!=0 && x%10==0)) return false;
        // if(x<10) return true;
        int reverse = 0;
        while(x > reverse){
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        return x==reverse || x==reverse/10;
    }
}

9.Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Input: "III"
Output: 3
Input: "IV"
Output: 4
Input: "IX"
Output: 9
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution {
    public int romanToInt(String s) {
        /*
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
        */
        int[] nums = new int[s.length()];
    for(int i=0;i<nums.length;i++){
        if(s.charAt(i)=='I'){
            nums[i]=1;
        }else if(s.charAt(i)=='V'){
            nums[i]=5;
        }else if(s.charAt(i)=='X'){
            nums[i]=10;
        }else if(s.charAt(i)=='L'){
            nums[i]=50;
        }else if(s.charAt(i)=='C'){
            nums[i]=100;
        }else if(s.charAt(i)=='D'){
            nums[i]=500;
        }else if(s.charAt(i)=='M'){
            nums[i]=1000;
        }
    }
    int result = 0;
    for(int i=0;i<nums.length-1;i++){
        if(nums[i]<nums[i+1]){
            result -= nums[i];
        }else{
            result += nums[i];
        }
    }
    result += nums[nums.length - 1];
    return result;
    }
}

10.Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length==0){
            return "";
        }
        StringBuilder sb = new StringBuilder("");
        for(int i=0;i<strs[0].length();i++){
            for(int j=1;j<strs.length;j++){
                if(strs[j].length()<(i+1) || strs[j].charAt(i) != strs[0].charAt(i)){
                    return sb.toString();
                }    
            }
            sb.append(strs[0].charAt(i));
        }
        return sb.toString();
    }
}

11.Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Input: haystack = "hello", needle = "ll"
Output: 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
class Solution {
    public int strStr(String haystack, String needle) {
        if(needle==null||needle.equals("")) return 0;
        if(needle.length()>haystack.length() || (needle.length()==haystack.length()&&!needle.equals(haystack))) return -1;
        for(int j=0;j<=haystack.length()-needle.length();j++){
            for(int i=0;i<needle.length();i++){
                if(needle.charAt(i) != haystack.charAt(j+i)) break;
                if(i == needle.length() - 1){
                    return j;
                }
            }
        }
        return -1;
    }
}

12.Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.
Input: [1,3,5,6], 5
Output: 2
Input: [1,3,5,6], 2
Output: 1
Input: [1,3,5,6], 7
Output: 4
Input: [1,3,5,6], 0
Output: 0
class Solution {
    public int searchInsert(int[] nums, int target) {
        if(target > nums[nums.length - 1]){
            return nums.length;
        }
        if(target < nums[0]){
            return 0;
        }
        for(int i = 0; i< nums.length; i++){
            if(target <= nums[i]){
                return i;
            }
        }
        return 0;
    }
}

13.Search Insert Position