简单题目

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6

输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6

输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

注意这种看似简单但不要暴力计算的题,拿一个数组或者哈希表,保存已经计算过的数据

这个题就是拿一个数组或者哈希表,要找target,就用list[nun-target]=index保存

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a={}
        for i,num in enumerate(nums):
            if target-num in a.keys():
                return [i,a[target-num]]
            a[num]=i
class Solution {
    public int[] twoSum(int[] nums, int target) {
         HashMap<Integer,Integer> hashMap=new HashMap<>();
            for(int i=0;i<nums.length;i++){
                if(hashMap.containsKey(target-nums[i])){
                    return new int[]{i,hashMap.get(target-nums[i])};
                }
                else{
                    hashMap.put(nums[i],i);
                }
            }
            return null;
    }
}

7、整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123

输出:321

示例 2:

输入:x = -123

输出:-321

示例 3:

输入:x = 120

输出:21

示例 4:

输入:x = 0

输出:0

class Solution {
    public int reverse(int x) {
        long n = 0;
        while(x != 0) {
            n = n*10 + x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }
}   

以下就是非常偷懒的做法,但是居然还挺快???

def reverse( x: int) -> int:
    a=x if x>0 else -x
    l=list(str(a))
    l.reverse()
    if x>0:
        ab=int("".join(l))
    else:
        ab=-1*int("".join(l))
    if ab>2147483647 or ab<-2147483648:
        return 0
image.png

9、回文数

给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。

示例 1:

输入:x = 121

输出:true

示例 2:

输入:x = -121

输出:false

解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入:x = 10

输出:false

解释:从右向左读, 为 01 。因此它不是一个回文数。

示例 4:

输入:x = -101

输出:false

提示:

  • -231 <= x <= 231 - 1

进阶:你能不将整数转为字符串来解决这个问题吗?

双指针,一个从头一个从尾,写就完了


13、罗马数字转整数

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值

I             1

V             5

X             10

L             50

C             100

D             500

M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 

C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"

输出: 3

示例 2:

输入: "IV"

输出: 4

示例 3:

输入: "IX"

输出: 9

示例 4:

输入: "LVIII"

输出: 58

解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"

输出: 1994

解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
  • 关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。

我的思路是,罗马数字中只有 IV,IX,XL,XC,CD,CM六中特殊情况,别的是多少加多少就行

所以先计算一个序列中这六种情况,计算完之后从序列中删除

class Solution {
    public int romanToInt(String s) {
        int r=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='I'&&(i+1)<s.length()&&s.charAt(i+1)=='V'){
                r+=4;
                i++;
            }
            else if(s.charAt(i)=='I'&&(i+1)<s.length()&&s.charAt(i+1)=='X'){
                r+=9;
                i++;
            }
            else if(s.charAt(i)=='X'&&(i+1)<s.length()&&s.charAt(i+1)=='L'){
                r+=40;
                i++;
            }
            else if(s.charAt(i)=='X'&&(i+1)<s.length()&&s.charAt(i+1)=='C'){
                r+=90;
                i++;
            }
            else if(s.charAt(i)=='C'&&(i+1)<s.length()&&s.charAt(i+1)=='D'){
                r+=400;
                i++;
            }
            else if(s.charAt(i)=='C'&&(i+1)<s.length()&&s.charAt(i+1)=='M'){
                r+=900;
                i++;
            }
            else if(s.charAt(i)=='I') r+=1;
            else if(s.charAt(i)=='V') r+=5;
            else if(s.charAt(i)=='X') r+=10;
            else if(s.charAt(i)=='L') r+=50;
            else if(s.charAt(i)=='C') r+=100;
            else if(s.charAt(i)=='D') r+=500;
            else if(s.charAt(i)=='M') r+=1000;
        }
        return r;
    }
}

14、最常公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入:strs = ["flower","flow","flight"]

输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]

输出:""

解释:输入不存在公共前缀。

提示:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

大概有这五种思路, 一般都会采用第四种, 但是耗时太多

1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准,把它的前缀串,与其他所有字符串进行判断,看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。

2、列出所有的字符串的前缀子串,将它们合并后排序,找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))

3、纵向扫描:从下标0开始,判断每一个字符串的下标0,判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。

4、横向扫描:前两个字符串找公共子串,将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。

class Solution {
    public String longestCommonPrefix(String[] strs) {
         if(strs.length==0){
            return "";
        }
        if(strs.length==1){
            return strs[0];
        }
        if(strs[0].length()==0){
            return "";
        }
        String r="";
        int p=0;
        int min=strs[0].length();
        for (String s:strs){
            if(s.length()<min){
                min=s.length();
            }
        }
        while (true){
            if(p>=min){
                r=strs[0].substring(0,p);
                break;
            }
            char temp=strs[0].charAt(p);
            for(int i=1;i<strs.length;i++){
                if(temp==strs[i].charAt(p)){
                    continue;
                }
                else {
                    r=strs[0].substring(0,p);
                    return r;
                }
            }
            p++;

        }
        return r;
    }
}

20、有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([)]"

输出:false

示例 5:

输入:s = "{[]}"

输出:true

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

单纯入栈出栈就行了,最简单的一类题目

class Solution {
    public boolean match(char a,char b){
        if((a=='('&&b==')')||(a==')'&&b=='(')) return true;
        if((a=='['&&b==']')||(a==']'&&b=='[')) return true;
        if((a=='{'&&b=='}')||(a=='}'&&b=='{')) return true;
        return false;
    }
    public boolean isValid(String s) {
        LinkedList<Character> heap=new LinkedList<Character>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{'||s.charAt(i)=='['||s.charAt(i)=='('){
                heap.add(s.charAt(i));
            }else {
                if(heap.size()==0){
                    return false;
                }
                char t=heap.getLast();
                heap.removeLast();
                if(match(s.charAt(i),t)){
                    continue;
                }else {
                    return false;
                }
            }
        }
        if(heap.size()!=0){
            return false;
        }
        return true;
    }
}

发布者

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

CAPTCHAis initialing...