LeetCode算法题库练习1

作者: 毛十三_ | 来源:发表于2019-04-13 14:03 被阅读0次

1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
我通过的代码(C++)：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result(2,0);
        for(int a=0;a<nums.size();a++)
        {
            for(int b=a+1;b<nums.size();b++)
            {
               if((nums[a]+nums[b])==target)
               {
                   result[0]=a;
                   result[1]=b;
                   break;
               }
            }
        }
        return result;   
    }
};

更好的解答(java)：
方法一：暴力法。
遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素。

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

方法二：一遍哈希表。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
思路：
1.相加的过程中可能存在进位的操作，所以需要采用一个变量carry来记录进位的情况，初始化carry = 0;
2.因为链表的数字是倒着放的，所以相加起来很方便，将两个链表从头到尾一起遍历，如果有值的话就将它们的值相加sum = val1+val2+carry。
3.如果是两个长度不一样的链表，则需要注意将不再继续向后，且让相应位的和为val1+0.
4.carry的更新，carry = sum/10, 而当前节点和 curr->val = sum%10.
5.循环直至l1,l2都为空。
6.遍历完之后如果carry == 1, 新建一个节点存在进位。
我通过的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p=l1;
        ListNode* q=l2;
        ListNode* result=new ListNode(0);
        ListNode* cur=result;
        int carry=0;
        while(p||q){
            int x=0,y=0,sum=0;
            if(p!=NULL){
                x=p->val;
                p=p->next;
            }
            if(q!=NULL){
                y=q->val;
                q=q->next;
            }
            sum=x+y+carry;
            carry=sum/10;
            cur->next=new ListNode(sum%10);
            cur=cur->next;
        }
        if(carry)
            cur->next=new ListNode(carry);
        return result->next;
    }
    
};

3.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提交的错误代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max=0,k=0;
        for(int i=0;i<s.size();i++){
            for(int index=k;index<i;index++)
            {
                if(s[index]==s[i]){
                    k=index+1;
                    break;
                }
                if(i-k+1>max)
                    max=i-k+1;
            }
            
        }
        return max;
    }
};

提交通过的代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size,max=0,k=0,index;
        size=s.size();
        for(int i=0;i<size;i++){
            for(index=k;index<i;index++)
                if(s[index]==s[i]){
                    k=index+1;
                    break;
                }
            if(i-k+1>max)
                max=i-k+1;
        }
        return max;
    }
};

4.整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31−1]。请根据这个假设，如果反转后整数溢出那么就返回0。

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

提交错误：

更改后通过：

class Solution {
public:
    int reverse(int x) {
        long int reverse=0;
        int y=0;
        while(x)
        {
            y=x%10;
            x=x/10;
            reverse=reverse*10+y;
            if(reverse<-2147483648||reverse>2147483647||reverse==2147483647||reverse==2147483647)
            return 0;
        }
        return reverse;
    }
};

5. Z字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G

class Solution {
public:
    string convert(string s, int numRows) {
        string ret;
        int cycle=2*numRows-2;
        int i,j;
        if(numRows==1)
            return s;
        for(i=0;i<numRows;i++)
        {
            for(j=0;i+j<s.size();j+=cycle)
            {
                ret +=s[i+j];
                if(i!=0&&j+cycle-i<s.size()&&i!=numRows-1)
                    ret +=s[j+cycle-i];
            }
        }
        return ret;
    }
};

11. 盛最多水的容器

给定 n 个非负整数 a₁，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
第一次提交的代码（暴力算法）：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i,j;
        long s=0,max=0;
        for(i=0;i<height.size();i++)
            for(j=height.size()-1;j>i;j--)
            {
                if(height[i]<height[j])
                    s=height[i]*(j-i);
                else s=height[j]*(j-i);
                if(s>max)
                    max=s;
            }
        return max;
    }
};

当遇到最后一次算例[15000,14999,14998,14997,14996,14995,14994,14993,....,6014,6013,6012,6011,6010,6009,6008,6007,6006,6005,6004,6003,6002,600... 28895 more chars]时报：超出时间限制。

更改通过：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0,j=height.size()-1;
        int s=0;
        while(i<j)
        {
            s = max(s,min(height[i], height[j]) * (j-i));
            if(height[i]<height[j])
                i++;
            else j--;
            
        }
        return s;
        
    }
};

12.整数转罗马数字

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

例如，罗马数字 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:
输入: 3
输出: "III"

示例 2:
输入: 4
输出: "IV"

示例 3:
输入: 9
输出: "IX"

示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

我的沙雕方法：

class Solution {
public:
    string intToRoman(int num) {
        if(num==0) return "0";
        string res;
        while(num)
        {
            if(num>=1000)
            {
               res+="M";
               num-=1000;
            }
            if(num<1000&&num>=900)
            {
                res+="CM";
                num-=900;
            }
            if(num<900&&num>=500)
            {
                res+="D";
                num-=500;
            }
            if(num<500&&num>=400)
            {
                res+="CD";
                num-=400;
            }
            if(num<400&&num>=100)
            {
                res+="C";
                num-=100;
            }
            if(num<100&&num>=90)
            {
                res+="XC";
                num-=90;
            }
            if(num<90&&num>=50)
            {
                res+="L";
                num-=50;
            }
            if(num<50&&num>=40)
            {
                res+="XL";
                num-=40;
            }
            if(num<40&&num>=10)
            {
                res+="X";
                num-=10;
            }
            if(num<10&&num>=9)
            {
                res+="IX";
                num-=9;
            }
            if(num<9&&num>=5)
            {
                res+="V";
                num-=5;
            }
            if(num<5&&num>=4)
            {
                res+="IV";
                num-=4;
            }
            if(num<4&&num>=1)
            {
                res+="I";
                num-=1;
            }     
        } 
        return res;
    }
};

更好的方法：

class Solution {
public:
    string intToRoman(int num) {
        int values[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        string reps[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        string res;
        for(int i=0; i<13; i++){
            while(num>=values[i]){
                num -= values[i];
                res += reps[i];
            }
        }
        return res;
    }
};

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。

class Solution {
public:
    int romanToInt(string s) {
        vector<string> roma {"CM","M","CD","D",
                            "XC","C","XL","L",
                            "IX","X","IV","V",
                            "I"};
        
        vector<int> nums {900,1000,400,500,
                          90,100,40,50,
                          9,10,4,5,
                          1};
        int res = 0;
        for(int i = 0;i<13;i++)
        {
            while(s.find(roma[i])!= string::npos)
            {
                s.erase(s.find(roma[i]),roma[i].size());
                res+=nums[i]; 
            }
        }
        return res;
    }
};

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
我的代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {     
        int i,aa=0;
        for(i=0;i<=nums.size();++i)
        {
            if(nums[i]!=nums[i+1])
            {
                aa=nums[i];
                break;
            }    
        }
        return nums[i+1]; 
    }
};

网上的答案：一个数字异或它自己结果为0，异或0结果为它自己即a ^ a=0，a ^ 0=a，且异或满足a ^ b ^ c=a ^ (b ^ c)。因此我们可以设置一个ret异或每个数组元素，最后相同的都抵消为0，那个唯一的数字异或0为它自己即为答案。

int singleNumber(vector<int>& nums) {
       int tmp = 0; 
        for(int i = 0;i < nums.size();i++){   
            tmp = tmp ^ nums[i];
        }
        return tmp;
    }

605. 种花问题

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

我的沙雕方法：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int i,length=0,j=0;
        /**
        数组中只有一个数（只有一个花坛）的情况：
        [1] 1:False
        [1] 0:True
        [0] 1:True
        [0] 0:True
        **/
        if(flowerbed.size()==1)
        {
            if(flowerbed[0]==0)
                return(n<=1);
            else
                return(n<1);
        }
        /**
        更改数组：遇到是1的元素就将前后元素都变为1
        **/
        for(i=0;i<flowerbed.size();)
        {
            if(flowerbed[i]==0)
            {
                i++;
                continue;
            }
            if(flowerbed[i]==1)
            {
                if(i!=0)
                    flowerbed[i-1]=1;
                if(i!=flowerbed.size()-1)
                    flowerbed[i+1]=1;
                if(i==flowerbed.size()-1)
                {
                    flowerbed[i-1]=1;
                    break;
                }
                i=i+2;         
            }
            
        }
        /**
        对更改完的数组进行累加计算：计算连续的0的个数以推得能种花数
        **/
        for(i=0;i<flowerbed.size();i++)
        {
            
            if(flowerbed[i]==0)
                length++;
            if(flowerbed[i]==1)
            {
                j+=(int)(length+1)/2;
                length=0;
            }
        }
        if(length!=0)
            j+=(int)(length+1)/2;
        if(j>=n) return true;
        else return false;
    }
};

LeetCode算法题库练习1

1.两数之和

2.两数相加

3.无重复字符的最长子串

4.整数反转

5. Z字形变换

11. 盛最多水的容器

12.整数转罗马数字

13.罗马数字转整数

136. 只出现一次的数字

605. 种花问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读