leetcode刷题_有一个包含 nn 个元素的整数数组 aa,对 aa 可以进行以下两种操作: 修改元素:modif

真的真的是菜鸟级的刷题，滴水穿石，加油加油加油！

目录

1. 两数之和

9.回文数

20.有效的括号

13.罗马数字转整数

27.移除元素

38 报数

118 杨辉三角

171 Excel表列序号

136 只出现一次的数字

---

1. 两数之和

【题目描述】

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
 
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

【Java1.0】

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] res = new int[2];
        int temp = 0;
        
        for(int i = 0; i < nums.length; i++){
            temp = target - nums[i];
            for(int j = 0; j < nums.length; j++){
                if(nums[j] == temp && j!=i)
                {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
    
}

时间复杂度o(n2)

【java2.0]

利用哈希表,将给出的数字作为键， 下标作为值，<2, 0><7, 1><11, 2><15, 3>

map.containsKey(键） ，判断某一个键是否在哈希表中

map.get(键）得到的是键为某数的value值

为什么不用下标作为键，给出的数字作为值呢？<0, 2><1, 7><2, 11><3, 15>

在判断target-nums[i]在不在哈希表中时，是判断哈希表中的值，v==map.get(?),用哪个下标才能找到值呢，不能，除非遍历，所以将给出的数字作为键，这样在判断的时候，map.containsKey(v)就可以判断给出的数字在不在哈希表中的键， 并且如果存在，要判断这个键对应的下标和i相不相同。其实这样利用哈希表，就是将数组中的下标和值反了过来，利用map.containsKey(v),相似于遍历数组中的值，这样减少了时间复杂度。嗯，脑子笨只能一点一点来了。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        
        for(int i = 0; i < nums.length; i++){
            int v = target - nums[i];
            
            if(map.containsKey(v) && i!=map.get(v)){
                result[0] = i;
                result[1] = map.get(v);
                return result;
            }
        }
        return result;
        
    }
}

9.回文数

【题目描述】

判断一个整数是否是回文数。回文数是指正序和倒序读都是一样的整数。

【java1.0】将整数转换为字符串，再转化为字符数组

class Solution{
    public boolean isPalindrome(int x){
        
        String s = Integer.toString(x);
        
        int length = x.length();
        
        char cs[] = s.toCharArray();
        
        for(int i = 0; i< length/2; i++){
            
            if(cs[i]!=cs[length-i-1]){
                return false;
            }
        }
        
        return true;
    }
}

【java2.0】将整数转换为字符串，然后反转字符串，与原字符串比较

class Solution {
    public boolean isPalindrome(int x) {
        String s = Integer.toString(x);
        int length = s.length();
        StringBuffer sb = new StringBuffer(sb);
        sb.reverse();  //sb字符串反转        
        for( int i = 0; i< length; i++){            
            if(s.charAt(i) != sb.charAt(i))
                return false;
        }
        return true;
}

【java3.0】将数字整除获得每一位数，相当于字符串反转。

值得注意的几个边界值是：

1. 整数小于0时，一定不是回文。
2. 整数为0时，是回文数。

（所以在代码时，一定要注意特殊的边界值，尽可能考虑全面）

class Solution {
    public boolean isPalindrome(int x) {
        int y = 0;
        int temp = x;
        if(x < 0){
            return false;
        }
        else{
            
            while( temp!=0 ){
                y = y * 10 + temp % 10;
                temp = temp / 10;
            }
            if ( x == y)
                return true;
            else
                return false; 
        }
 
    }
}

20.有效的括号

【题目描述】

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

【java 1.0】运用stack的操作进行判断，后续可以用switch-case改进，应该可以有更好的方法。

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for(int i = 0; i < s.length(); i++){
            
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.push(s.charAt(i));
            }
            else if(s.charAt(i) == ')'){
                if(stack.empty())
                    return false;
                else if((Character)stack.peek() == '('){
                    stack.pop();
                }
                else return false;
 
            }
            else if(s.charAt(i) == ']'){
                if(stack.empty())
                    return false;
                else if((Character)stack.peek() == '['){
                    stack.pop();
                }
                else return false;
            }
            else {
                if(stack.empty())
                    return false;
                else if((Character)stack.peek() == '{'){
                    stack.pop();
                }
                else return false;
            }
        }
        if(stack.empty())
            return true;
        else
            return false;
    }
}

13.罗马数字转整数

【java1.0】运用map存储罗马数字，然后根据给出的字符串判断加减

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> m = new HashMap<Character, Integer>();
        m.put('I', 1);
        m.put('V', 5);
        m.put('X', 10);
        m.put('L', 50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);
        
        int result = 0;
        char[] c = s.toCharArray();
        for(int i = 0; i < s.length(); i++ )
        {
            if(i == s.length()-1){  //如果是数组的最后一个，就没有和下一个数字比较了
                result += m.get(c[i]);
                return result;
            }
            else{
                if(m.get(c[i]) >= m.get(c[i+1])){
                result += m.get(c[i]);
                }
                else{
                    result -= m.get(c[i]);
                }
            }
            
        }
        return result;
    }
}

27.移除元素

【java1.0】将不是val值的元素往前移动，覆盖val值得元素

class Solution {
    public int removeElement(int[] nums, int val) {
        int lenTotal = 0;
        int lenRemove = 0;    
        for ( int i = 0; i< nums.length; i++){
            if(nums[i] == val){
                lenRemove+=1;           
            } 
            else{
                lenTotal++;
                nums[i-lenRemove] = nums[i];
                
            }
        } 
        return lenTotal;
        
    }
}

38 报数

刚拿到题目的时候审不懂题意，看其他的大牛们的解释才明白。

其实原则就是：默认第一个数为1，然后第二个、第三个、、、依次“读”出前面的数。“读”的意思就是，比如1，我们会读作，"一个一"，因此，第二个数字就是11；然后第三个数读第二个数，读作“两个一”,因此第三个数字就是21；然后第四个数读第三个数，读作“一个二，一个一”，因此，第四个数字就是1121。总结来说就是，读出前一个数的数字构成，作为下一个数。

1. 因为涉及到前一个数字，所以采用递归的方式。
2. 又因为我们需要输出一个字符串，而且我们在递归读数的过程中需要不断的更新这个字符串，所以用stringBuffer保存这个字符串，因为stringbuffer是变量，string是字符串常量，所以在更新的过程中stringBuffer的速度更快。

【java1.0】

class Solution {
    public String countAndSay(int n) {
        
        if(n == 1){
            return "1";
        }
        else{
            
            String post = countAndSay(n-1); //递归获取前一个数
            StringBuilder result = new StringBuilder(); //相比string，速度更快
            int len = post.length();
            int count = 1;
 
            for( int i = 0; i< len; i++){    
                if(i == len-1){                 //最后一个元素，直接将目前的计数和最后一个元素存入result
                    result.append(count);   
                    result.append(post.charAt(i));
                    break;
                }
                
                if(post.charAt(i+1) == post.charAt(i)){
                    count++;        //元素相同，累加计数
                }
                else{
                    result.append(count);         //前一个元素与后一个元素不同，将前一个元素个数和前一个元素存入result中，后面还需要将count重置为1
                    result.append(post.charAt(i));
                    count = 1;     
                }
            }
            return result.toString();
            
        }
        
    }
}

118 杨辉三角

求杨辉三角很简单，其实就是利用a[i][j] = a[i-1][j-1] + a[i-1][j]往下累加计算。

这里要求存储在二维列表里（我也不清楚是不是应该这么叫），但是我先将结果存储在二维数组中，然后再存入二维列表中。

对列表添加元素的操作是  list.add(元素值)，所以在转化二维列表的过程中，先新建一个一维列表，将每一行的结果存入，然后list.add(内层的一维列表)。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();  //存放结果
        
        int[][] a = new int[numRows][numRows];  //暂时存放结果
        
        for(int i = 0; i< numRows; i++){
            for(int j = 0 ; j< i+1; j++){
                if( i == 0){     
                    a[i][j] = 1;       //第一行
                }
                else if( j == 0 | j == i){  //每一行的第一个和最后一个元素
                    a[i][j] = 1; 
                }else{
                    a[i][j] = a[i-1][j-1]+a[i-1][j];   //计算中间元素
                }
            }
        }
        
        for(int i = 0; i< numRows; i++){
            List<Integer> jlist = new ArrayList<Integer>();
            for(int j = 0 ; j< i+1; j++){
                jlist.add(a[i][j]);   //将每一行的结果存入jlist
            }
            list.add(jlist); //将每一行的结果存入list
        }
        return list;
    }
}

171 Excel表列序号

要写这道题需要明确列序列号和列名称之间的对应关系。

列名称的命名规则为：A,B,C,D,,,,,,X,Y,Z,AA,AB,AC,,,,,,AX,AY,AZ,BA,BB,BC,,,,,,BX,BY,BZ,,,,,,,,YZ,ZA,ZB,ZC,,,ZX,ZY,ZZ,AAA,AAB,AAC,,,,,AAX,AAY,AAZ,ABA,ABB,ABC,ABD,,,,,,ABX,ABY,ABZ,,,,,,(注意加粗部分的转换)，其实相当于“多级索引”，用一个字母可以表示26列，然后从第27个数字开始，使用“二级索引”，即用两个字母表示列，而且第二级索引也就是从右往左的第二个字母(AA),是从A-Z顺序使用的，与“一级索引”相同。

对应关系：

A---$26^{0}$*1

B---$26^{0}$*2

C--$26^{0}$*3

...

Y---$26^{0}$*25

Z---$26^{0}$*26

AA---27= $26^{1}$*1+$26^{0}$*1

AB---28= $26^{1}$*1+$26^{0}$*2

...

AZ---52= $26^{1}$*1+$26^{0}$*26

BA--- 53= $26^{1}$*2+$26^{0}$*1

...

YZ---676= $26^{1}$*25+$26^{0}$*26

ZA---677= $26^{1}$*26+$26^{0}$*1

ZZ---702= $26^{1}$*26+$26^{0}$*26

AAA---703=$26^{2}$*1 + $26^{1}$*1+$26^{0}$*1

AAB---704=$26^{2}$*1 + $26^{1}$*1+$26^{0}$*2

(其中到达第几层就是26的几次方，对应哪个字母就是乘以几)

【java1.0】

（不知道为什么leetcode里求次方不能用Math.pow(26, 2),所以写了一个循环计算）

class Solution {
    public int titleToNumber(String s) {
        
        char[] alpha = new char[27];
        for(int i = 1; i <= 26; i++){    //将每个字母对应的数字设置为其索引
            alpha[i] = (char)('A'+i-1);
        }
        String a = new String(alpha);
        int len = s.length();    //计算输入的字符串的长度，为了下面的计算
        
        char[] input = s.toCharArray();
        int result = 0;
        int temp = 0;
        
        for(int i = 0; i < len; i++){
            int b = 1;
            //temp = a.indexOf(input[i])
            temp = len-i-1;         //计算处于第几层索引
            for(int j = 1; j<=temp; j++)   //计算次方
                b *= 26;
            result += b*a.indexOf(input[i]);  //将每一层的结果累加
            
        }
        return result;
    }
}

136 只出现一次的数字

1. 题目要求线性时间复杂度，不能使用额外的空间。

我竟然首先想到的是先排序，再判断，这样相同的两个数字就可以放在一起，不用对每个出现的数字计算出现的次数，但是java的排序函数Arrays.sort()函数的时间复杂度是o(n)，并不符合题目要求。

【java1.0】

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);   //排序
        for(int i = 0; i< nums.length; i+=2){   //判断每两个数是不是相同
            if(i == nums.length -1){   //判断到最后一个数字，说明前面的都是成对存在，只有最后一个数个数为1，比如1，1，2，2，3
                return nums[i];
            }
            if( nums[i] != nums[i+1])    //如果存在两个数不同，说明第一个数出现的次数为1，比如1，1，2，3，3
                return nums[i];
        }
        return 0;
    }
}

由于对于这种不能使用额外空间的问题不是很了解，所以查阅了网上的解题方法，决定采用亦或的方法。

举例：1，1，2，2，4 

1^1^2^2^4 = (1^1)^(2^2)^4=0^0^4=4

所以把所有的数字进行异或操作，两个相同的数字异或结果为0，剩下的一个是数字就是结果

6^5  = 3   

6^5^5 = 6

【java2.0】

class Solution {
    public int singleNumber(int[] nums) {
    
        int result = 0;
        for(int i = 0; i< nums.length; i++){
            result = result^nums[i];
        }
        return result;
    }
}

412. Fizz Buzz

今天这一题很简单，完全就是if-else的简单使用。

复习一下list操作：

新建一个list: List<String> aaa = new ArrayList<>();

添加元素：aaa.add()  aaa.add(索引，值)

删除元素：aaa.remove()

获取元素：aaa.get(索引或者值)

是否包含：aaa.contains(值)，返回值true或者false

修改元素：aaa.set(索引，值)

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> result = new ArrayList<>();//新建list
        
        for( int i = 1; i<=n; i++){
            if( (i % 3 == 0) && (i % 5 == 0)){  //同时被3和5整除
                result.add("FizzBuzz");
            }
            else if( i % 3 == 0){  //被3整除
                result.add("Fizz");
                
            }else if( i % 5 == 0){  //被5整除
                result.add("Buzz");
                
            }else{
                result.add(String.valueOf(i));  //不能整除
            }
        }
        return result;
    }
}