202/12/09 基础算法每日5道详解

落日映苍穹つ 2024-03-31 17:07 52阅读 0赞

## 202/12/09 基础算法每日5道详解 ##

## 1.Two Sum 两数之和 ##

> Given an array of integers `nums` and an integer `target`, return *indices of the two numbers such that they add up to `target`*.
> 
> You may assume that each input would have \***exactly\* one solution**, and you may not use the *same* element twice.
> 
> You can return the answer in any order.
> 
> 给定一个整数数组 nums 和一个整数目标，返回两个数字的索引，使它们加起来等于目标。
> 
> 您可能会假设每个输入都只有一个解决方案，并且您可能不会两次使用相同的元素。
> 
> 您可以按任何顺序返回答案。

**Example 1:**

Input: nums = [2,7,11,15], target = 9
    Output: [0,1]
    Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

**Example 2:**

Input: nums = [3,2,4], target = 6
    Output: [1,2]

**Example 3:**

Input: nums = [3,3], target = 6
    Output: [0,1]

**代码实现：**

public class Twosum {
        
        public static void main(String[] args) {
        
            int[]a={
        3,2,4};
            int target= 6;
            int[] result = twoSum(a,6);
    
            for(int data:result){
        
                System.out.println(data);
            }
    
        }
        public static int[] twoSum(int[] nums, int target) {
        
            int [] result = new int[2];//cha
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();//用hash遍历数组，用target-数组当中的元素，差的值再遍历数组中是否有元素，不能存在相同的值
            for (int i = 0; i < nums.length; i++) {
        //遍历数组中的元素
                if (map.containsKey(target - nums[i])) {
         //map中是否有数值，如果没有，在map中插入数值，key为数值，i为索引
                    result[0] = map.get(target - nums[i]);//用taraget-map中已经输入的以i为索引的值
                    result[1] = i;
                    return result;//返回索引
                }
                map.put(nums[i], i);//添加i的值和索引
            }
            return result;
    
    
        }
    }

**结果：**

1
    2

**优化后代码：**

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            // 创建哈希表
            Map<Integer, Integer> map = new HashMap<>();
    
            // 遍历数组中的每个元素
            for (int i = 0; i < nums.length; i++) {
        
                // 计算该元素的差值
                int diff = target - nums[i];
    
                // 如果差值在哈希表中存在，则返回两个元素的下标
                if (map.containsKey(diff)) {
        
                    return new int[] {
        map.get(diff), i};
                }
    
                // 如果差值不存在，则将该元素插入哈希表中
                map.put(nums[i], i);
            }
    
            // 如果找不到两个组成目标整数的元素，则返回空数组
            return new int[0];
        }
     }
    
    //测试代码
    public class Main {
        
        public static void main(String[] args) {
        
            // 创建 Solution 对象
            Solution solution = new Solution();
    
            // 创建要测试的数组
            int[] nums = {
        2, 7, 11, 15};
    
            // 调用 twoSum 方法，并传入目标整数 9
            int[] result = solution.twoSum(nums, 9);
    
            // 输出结果
            System.out.println("下标1: " + result[0] + ", 下标2: " + result[1]);
        }
    }

**输出结果：**

下标1: 0, 下标2: 1

## 9.Palindrome Number 回文数 ##

> Given an integer x, return true if x is palindrome integer.
> 
> An integer is a palindrome when it reads the same backward as forward.
> 
> For example, 121 is a palindrome while 123 is not.
> 
> 给定一个整数 x，如果 x 是回文整数，则返回 true。
> 
> 当一个整数向后读和向前读一样时，它就是一个回文数。
> 
> 例如，121 是回文，而 123 不是。

**Example 1:**

Input: x = 121
    Output: true
    Explanation: 121 reads as 121 from left to right and from right to left.

**Example 2:**

Input: x = -121
    Output: false
    Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

**Example 3:**

Input: x = 10
    Output: false
    Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

代码实现：

class Solution {
        
        public boolean isPalindrome(int x) {
        
            // 如果 x 小于 0，则它不是回文数
            if (x < 0) return false;
    
            // 将 x 转换成字符串
            String s = Integer.toString(x);
    
            // 计算字符串的长度
            int n = s.length();
    
            // 从两端开始向中间逼近
            for (int i = 0; i < n / 2; i++) {
        
                if (s.charAt(i) != s.charAt(n - i - 1)) return false;
            }
    
            // 如果没有遇到任何不同的字符，则说明 x 是回文数
            return true;
        }
    }
    
    public class Main {
        
        public static void main(String[] args) {
        
            // 创建 Solution 对象
            Solution solution = new Solution();
    
            // 测试整数 121
            System.out.println(solution.isPalindrome(121));
    
            // 测试整数 -121
            System.out.println(solution.isPalindrome(-121));
    
            // 测试整数 10
            System.out.println(solution.isPalindrome(10));
        }
    }

运行结果：

true
    false
    false

leecode代码：

class Solution {
        
        public boolean isPalindrome(int x) {
        
            List<Integer> list = new ArrayList<>();
            if(x<0) return false;
            while(x/10 !=0){
        //排除小数 3/10=0 
                list.add(x%10);//数字最后一位
                x/=10;//循环除数到
            }
            list.add(x);//
            int i =0;
            int j = list.size()-1;
            while(i<j){
        
                if(list.get(i)!=list.get(j)) return false;
                i++;
                j--;
            }
            return true;
        }
    }
    
    //转为String之后进行倒数进行比较
    class Solution {
        
        public boolean isPalindrome(int x) {
        
           String a = (new StringBuilder(x+"")).reverse().toString();
            return (a.equals(x+""));
        }
    }
    
    //解法
    class Solution {
        
        public boolean isPalindrome(int x) {
        
            if(x<0) return false;
            int rst = 0;
            int y =x;
            while(y!=0){
        
                rst = rst * 10 + y%10;
                y=y/10;
                
            }
            return rst ==x;
        }
    }

## 13.Roman to Integer 罗马转整数 ##

> Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
> 
>     SymbolValue
>     I             1
>     V             5
>     X             10
>     L             50
>     C             100
>     D             500
>     M             1000
> 
> For example, `2` is written as `II` in Roman numeral, just two ones added together. `12` is written as `XII`, which is simply `X + II`. The number `27` 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.
> 
> 例如，“2”用罗马数字写成“II”，只是两个加在一起。 `12` 写成 `XII`，也就是 `X + II`。 数字“27”写成“XXVII”，即“XX + V + II”。
> 
> 罗马数字通常从左到右从大到小写。 但是，四的数字不是“IIII”。 相反，数字四写为“IV”。 因为一个在五个之前，所以我们减去它得到四个。 同样的原则也适用于数字九，它被写成“IX”。 有六个使用减法的实例：
> 
> I 可以放在 V (5) 和 X (10) 之前，组成 4 和 9。 X 可以放在 L (50) 和 C (100) 之前，组成 40 和 90。 C可以放在D（500）和M（1000）之前，组成400和900。 给定一个罗马数字，将其转换为整数。

**Example 1:**

Input: s = "III"
    Output: 3
    Explanation: III = 3.

**Example 2:**

Input: s = "LVIII"
    Output: 58
    Explanation: L = 50, V= 5, III = 3.

**Example 3:**

Input: s = "MCMXCIV"
    Output: 1994
    Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

**代码实现**

package com.xu.leecode.practise1;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class RomanToInt {
        
    
            public int romanToInt(String s) {
        
                // 建立一个HashMap，用来存储罗马数字与其对应的整数
                Map<Character, Integer> map = new HashMap<>();
                map.put('I', 1);
                map.put('V', 5);
                map.put('X', 10);
                map.put('L', 50);
                map.put('C', 100);
                map.put('D', 500);
                map.put('M', 1000);
    
                // 初始化结果
                int result = 0;
                // 从左往右遍历罗马数字
                for (int i = 0; i < s.length(); i++) {
        
                    // 获取当前位的罗马数字
                    int value = map.get(s.charAt(i));
                    // 如果当前位的值比右边的值小，则将其加入结果中
                    if (i + 1 < s.length() && value < map.get(s.charAt(i + 1))) {
        
                        result -= value;
                    } else {
        
                        result += value;
                    }
                }
                return result;
            }
    
            public static void main(String[] args) {
        
                // 测试用例
                String[] testCases = {
        "I", "III", "IV", "IX", "LVIII", "MCMXCIV"};
    //            int[] expectedResults = {1, 3, 4, 9, 58, 1994};
                RomanToInt romanToInt = new RomanToInt();
    
                for (int i = 0; i < testCases.length; i++) {
        
                    int result = romanToInt.romanToInt(testCases[i]);
                    System.out.println(result);
    //                assert result == expectedResults[i];
                }
            }
    
    
    }

**测试结果**

1
    3
    4
    9
    58
    1994

**leecode代码**

class Solution {
        
        public int romanToInt(String s) {
        
            // 建立一个HashMap，用来存储罗马数字与其对应的整数
            Map<Character, Integer> map = new HashMap<>();
            map.put('I', 1);
            map.put('V', 5);
            map.put('X', 10);
            map.put('L', 50);
            map.put('C', 100);
            map.put('D', 500);
            map.put('M', 1000);
    
            // 初始化结果
            int result = 0;
            // 从左往右遍历罗马数字
            for (int i = 0; i < s.length(); i++) {
        
                // 获取当前位的罗马数字
                int value = map.get(s.charAt(i));
                // 如果当前位的值比右边的值小，则将其加入结果中
                if (i + 1 < s.length() && value < map.get(s.charAt(i + 1))) {
        
                    result -= value;
                } else {
        
                    result += value;
                }
            }
            return result;
        }
    
    }

## 14.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 `""`.
> 
> 编写一个函数来查找字符串数组中最长的公共前缀字符串。  
> 如果没有公共前缀，则返回一个空字符串“”。

**Example 1:**

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

**Example 2:**

Input: strs = ["dog","racecar","car"]
    Output: ""
    Explanation: There is no common prefix among the input strings.

**代码实现：**

public class LongestCommonPrefix {
        
        public static void main(String[] args) {
        
            // 测试用例
            String[][] testCases = {
        {
        "flower", "flow", "flight"}, {
        "dog", "racecar", "car"}, {
        "aca", "cba"}};
            String[] expectedResults = {
        "fl", "", ""};
            LongestCommonPrefix longestCommonPrefix = new LongestCommonPrefix();
            for (int i = 0; i < testCases.length; i++) {
        
                String result = longestCommonPrefix.longest(testCases[i]);
                System.out.println(result);
                assert result.equals(expectedResults[i]);
            }
    
        }
        public String longest(String[] strs) {
        
            // 如果数组为空或者数组长度为0，则返回空字符串
            if (strs == null || strs.length == 0) {
        
                return "";
            }
            // 初始化最长公共前缀为数组的第一个字符串
            String prefix = strs[0];
            // 从第二个字符串开始，逐个和最长公共前缀比较
            for (int i = 1; i < strs.length; i++) {
        
                // 如果最长公共前缀不是当前字符串的前缀，则不断地缩小最长公共前缀的长度，直到它成为当前字符串的前缀
                while (strs[i].indexOf(prefix) != 0) {
        
                    prefix = prefix.substring(0, prefix.length() - 1);
                    // 如果最长公共前缀已经缩小为空串，则直接返回空串
                    if (prefix.isEmpty()) {
        
                        return "";
                    }
                }
            }
            // 如果所有的字符串都是以最长公共前缀开头的，则返回最长公共前缀
            return prefix;
        }
    
    
    }

**结果输出：**

**leecode：**

class Solution {
        
        public String longestCommonPrefix(String[] strs) {
        
    //        不存在
            if(strs.length==0) return "";
    //        数组中共同的设置为第一个
            String common =strs[0];
    //        数组的第二个开始，是否存在相同的元素
            for(int i=1;i<strs.length;i++){
        
                while(strs[i].indexOf(common)!=0){
        
    //                索引相同的元素不为0
    //                循环取出位置的共同的String
                    common = common.substring(0, common.length() - 1);
                }
            }
            return common;
    }

代码实现的思路是对的，但有一些细节问题需要修改。

首先，需要在类中定义一个longestCommonPrefix方法，这个方法接收一个字符串数组作为参数，并返回最长公共前缀。

其次，代码中没有处理数组为空的情况，如果数组为空，那么最长公共前缀就是空字符串，应该返回空字符串。

第三，代码可能会导致common字符串缩小到空字符串，这是不合法的，你需要在处理字符串的时候检查common是否为空，如果为空，则直接返回空字符串。

**leecode代码正确实现：**

public String longest(String[] strs) {
        
            // 如果数组为空或者数组长度为0，则返回空字符串
            if (strs == null || strs.length == 0) {
        
                return "";
            }
            // 初始化最长公共前缀为数组的第一个字符串
            String prefix = strs[0];
            // 从第二个字符串开始，逐个和最长公共前缀比较
            for (int i = 1; i < strs.length; i++) {
        
                // 如果最长公共前缀不是当前字符串的前缀，则不断地缩小最长公共前缀的长度，直到它成为当前字符串的前缀
                while (strs[i].indexOf(prefix) != 0) {
        
                    prefix = prefix.substring(0, prefix.length() - 1);
                    // 如果最长公共前缀已经缩小为空串，则直接返回空串
                    if (prefix.isEmpty()) {
        
                        return "";
                    }
                }
            }
            // 如果所有的字符串都是以最长公共前缀开头的，则返回最长公共前缀
            return prefix;
        }

## 20.Valid Parentheses 有效括号 ##

> Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.
> 
> An input string is valid if:
> 
> 1.  Open brackets must be closed by the same type of brackets.
> 2.  Open brackets must be closed in the correct order.
>     
>     给定一个仅包含字符 ‘(’, ‘)’, ‘\{’, ‘\}’, ‘\[’ 和 ‘\]’ 的字符串 s，确定输入字符串是否有效。
>     
>     输入字符串在以下情况下有效：
>     
>     开括号必须用相同类型的括号闭合。 开括号必须以正确的顺序闭合。

**Example 1:**

Input: s = "()"
    Output: true

**Example 2:**

Input: s = "()[]{}"
    Output: true

**Example 3:**

Input: s = "(]"
    Output: false

**解释为什么使用栈：**

> 用栈来判断括号是否匹配的原因是，栈具有先进后出的特点，可以保证括号在匹配时遵守先左后右的顺序。  
> 例如，对于字符串"(())"，首先遇到的是左括号，将其压入栈中，然后遇到右括号，从栈中弹出一个左括号，这两个括号匹配成功。接着遇到左括号，将其压入栈中，最后遇到右括号，从栈中弹出一个左括号，这两个括号也匹配成功。由于栈中没有剩余的左括号，因此该字符串是一个有效的括号字符串。  
> 如果不使用栈，则需要遍历整个字符串，对于每个遇到的括号，都要扫描剩余的字符串，看看是否存在与其匹配的括号。这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，明显不如使用栈来实现的 O ( n ) O(n) O(n)。  
> 此外，使用栈还有一个优点是，如果遇到的括号不匹配，可以立即返回错误，而不需要继续扫描剩下的字符串。  
> 因此，使用栈来实现括号匹配问题是一种高效和优雅的方法。

**代码实现：**

import java.util.Stack;
    
    public class ValidParentheses {
        
        public static void main(String[] args) {
        
            // 测试用例
            String[] testCases = {
        "(())", "()[]{}", "(]", "([)]"};
    //        boolean[] expectedResults = {true, true, false, false};
            ValidParentheses validParentheses = new ValidParentheses();
    
            for (int i = 0; i < testCases.length; i++) {
        
                boolean result = validParentheses.isValid(testCases[i]);
                System.out.println(result);
    //            assert result == expectedResults[i];
            }
    
        }
    
            public boolean isValid(String s) {
        
                // 如果字符串为空或者长度为奇数，则不可能是有效的括号字符串
                if (s == null || s.length() % 2 == 1) {
        
                    return false;
                }
                // 创建一个栈，用于存储左括号
                Stack<Character> stack = new Stack<>();
                // 遍历字符串中的每一个字符
                for (char c : s.toCharArray()) {
        
                    // 如果当前字符是左括号，则将其压入栈中
                    if (c == '(' || c == '[' || c == '{') {
        
                        stack.push(c);
                    }
                    // 否则，如果当前字符是右括号，则从栈中弹出一个左括号，并检查它们是否匹配
                    else if (stack.isEmpty() || c == ')' && stack.pop() != '(' || c == ']' && stack.pop() != '[' || c == '}' && stack.pop() != '{') {
        
                        // 如果栈为空或者括号不匹配，则返回false
                        return false;
                    }
                }
                // 如果栈为空，则返回true，否则返回false
                return stack.isEmpty();
            }
    
    
    }

**运行结果：**

true
    true
    false
    false

**Leecode：**  
**方法1：**

class Solution {
        
        public boolean isValid(String s) {
        
            if(s.isEmpty())
                return true;
    
    	Stack<Integer> stack = new Stack<>();
            String open = "({[";
            String close = ")}]";
    
            for (int i = 0; i < s.length(); i++) {
        
                char c = s.charAt(i);
                if (open.contains(c + "")) {
        
                    int id = open.indexOf(c);
                    stack.push(id);
                }
                else {
        
                    int id = close.indexOf(c);
                    if (stack.isEmpty() || id != stack.pop()) return false;
                }
            }
            return stack.isEmpty();
        }

> 以上代码可以执行，但是还需要优化  
> 首先，这段代码没有考虑字符串为空的情况，如果字符串为空，应该返回true，因为一个空字符串是一个有效的括号字符串。  
> 其次，这段代码使用了字符串的contains方法来判断当前字符是否是左括号，但是如果字符串的长度很大，这样的复杂度可能会很高。此外，使用字符串的indexOf方法来获取当前字符在open字符串中的位置，这样的复杂度也可能较高。可以考虑把这两个字符串改为数组或者映射来实现，这样复杂度会更低。  
> 第三，这段代码没有考虑字符串中存在非括号字符的情况，如果字符串中存在非括号字符，应该忽略这些字符。

**方法2：**

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(c != stack.pop()||stack.empty())
                  return false;
            }
            if(stack.empty())
               return true;
            return false;
            
        }
    }
    
    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.isEmpty() || stack.pop() != c)
    			return false;
    	}
    	return stack.isEmpty();