力扣编程题_top == 0 || stk[top - 1] != ch

1. 两数之和
   给定一个整数数组 nums 和一个整数目标值 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]

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i,j;
int *result = (int *)malloc(sizeof(int)*2);

for(i=0;i<numsSize-1;i++)
{
    for(j=i+1;j<numsSize;j++)
    {
         if(nums[i]+nums[j]==target)
         {
             result[0] = i;
             result[1] = j;
             *returnSize = 2;
             return result;            
          }
    }
}
    *returnSize= 0;
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

20. 有效的括号
    给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

int reverse(int x){
int a[32];
int k=0;
while(x!=0)
    {
        a[k++] = x%10;
        x=x/10;
    }
    for(int i=0;i<k;i++)
    {
        x*=10;
        x+=a[i];
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

53. 最大子序和
    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

int maxSubArray(int* nums, int numsSize){
int max = INT_MIN;
for(int i=0;i<numsSize;i++)
{
    int sum = 0;
    
    for(int j=i;j<numsSize;j++)
    {
        sum=sum+nums[j];
        if(sum > max)
            max = sum;
    }
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

70. 爬楼梯
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶

int climbStairs(int n){
    int p=0,q=0,r=1;
    for(int i = 1;i<=n;i++)
    {
        p=q;
        q=r;
        r=p+q;
    }
    return r;

}
1
2
3
4
5
6
7
8
9
10
11

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
    if(l1->val < l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9. 回文数
   判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

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

bool isPalindrome(int x){
    long result = 0;
    if(x<0) return -1;
    if(x==0) return 1;
    int y=x;
    while(x!=0)
    {
        result = result*10 + x%10;
        x = x/10; 
    }
    return (int)result==y?1:-1;

}
1
2
3
4
5
6
7
8
9
10
11
12
13

206. 反转链表
     反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *p, *pre = NULL;
    while(head)
    {
        p = head->next;
        head->next = pre;
        pre = head;
        head = p;
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

344. 反转字符串
     编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：

输入：[“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

void reverseString(char* s, int sSize){
   /* char c;
    for(int i=0;i<sSize/2;i++)
    {
        c=s[i];
        s[i]=s[sSize-i-1];
        s[sSize-i-1] =c;
    }*/
    
    int i=0;
    int j=sSize-1;
    char c;
    while(i<j)
    {
        c = s[i];
        s[i] = s[j];
        i++;j--;
    }  

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

121. 买卖股票的最佳时机
     给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

int maxProfit(int* prices, int pricesSize){
    int maxprofit = 0;
    int profit;
    for(int i=0;i<pricesSize-1;i++)
    {
        for(int j=i+1;j<pricesSize;j++)
        {
            profit = prices[j]-prices[i];
            if(profit>maxprofit)
            maxprofit = profit;
        }
    }
    return maxprofit;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

26. 删除排序数组中的重复项
    给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

int removeDuplicates(int* nums, int numsSize){
   int i = 0;
   for(int j=1;j<numsSize;j++)
   {
       if(nums[j]!=nums[i])
        {   
            ++i;
            nums[i]=nums[j];
        } 
   }
   return i+1;
}
1
2
3
4
5
6
7
8
9
10
11
12

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
1

/
2 2
/ \ /
3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
1

/
2 2
\
3 3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool MyisSymmetric(struct TreeNode* Left,struct TreeNode* Right){
    //当左右为空时满足条件
    if(!Left&&!Right)
        return true;
    //当左右一个存在不满足条件
    if(!Left||!Right)
        return false;
    //当左边不满足右边不满足条件
    if(Left->val!=Right->val)
        return false;
    return MyisSymmetric(Left->left,Right->right)&&MyisSymmetric(Left->right,Right->left);
}

bool isSymmetric(struct TreeNode* root){
    //当前节点为空时，满足条件
    if(root ==NULL)
    return true;
    return MyisSymmetric(root->left,root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

557. 反转字符串中的单词 III
     给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入：“Let’s take LeetCode contest”
输出：“s’teL ekat edoCteeL tsetnoc”

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

char* reverseWords(char* s){
    int length = strlen(s);
    char* ret = (char*)malloc(sizeof(char)*(length + 1));
    ret[length] = 0;
    int i = 0;
    while(i < length){
        int start = i;
        while(i < length && s[i]!=' '){
            i++;
        }
        for(int p = start;p < i; p++){
            ret[p] = s[start+i-1-p];
        }
        while(i < length && s[i] == ' '){
            ret[i]=' ';
            i++;
        }
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

204. 计数质数
     统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：

输入：n = 0
输出：0
示例 3：

输入：n = 1
输出：0

int countPrimes(int n){
int count = 0;;
for(int i=2;i<n;i++)
{
    bool sign = true;
    for(int j=2;j<i;j++)
    {
        if(i%j==0)
        {
            sign = false;
            break;
        }
    }
    if(sign)
    count++;
}
return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：""
解释：输入不存在公共前缀。

提示：

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

//寻找两个字符串之间的公共长缀,找到后并在原来的基础上修改为当前最短前缀
void comparetwostring(char *minstr1,char *str2)
{
    int len = strlen(minstr1);
    for (int i = 0;i < len;i++)
    {
        if(minstr1[i] == str2[i])
        {
            if (minstr1[i] == '\0')
            {
                return;
            }

            if (minstr1[i+1] == '\0')
            {
                return;
            }
        }
        else 
        {
            minstr1[i] = '\0';
            return;
        }
    }

    return ;
}

char * longestCommonPrefix(char ** strs, int strsSize){
    
    if (strsSize == 0)
    {
        return "";
    }

    if (strsSize == 1)
    {
        return strs[0];
    }
        
    for (int i = 0;i < strsSize;i++)
    {
        if (i != 0)
        {
            comparetwostring(strs[0],strs[i]); 
        }
    }

    return strs[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

char* addStrings(char* num1, char* num2) {
    int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0;
    char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3));
    int len = 0;
    while (i >= 0 || j >= 0 || add != 0) {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        int result = x + y + add;
        ans[len++] = '0' + result % 10;
        add = result / 10;
        i--, j--;
    }
    // 计算完以后的答案需要翻转过来
    for (int i = 0; 2 * i < len; i++) {
        int t = ans[i];
        ans[i] = ans[len - i - 1], ans[len - i - 1] = t;
    }
    ans[len++] = 0;
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

69. x 的平方根
    实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

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

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

int mySqrt(int x){
    int num = exp(0.5*log(x));
    return (num+1)*(num+1)<=x?num+1:num;

}
1
2
3
4
5

88. 合并两个有序数组
    给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=m-1,j=n-1;
    int k=m+n-1;
    while(i>=0&&j>=0)
    {
      /*  if(nums2[j]>nums1[i])
        {
            nums1[k]=nums2[j];
            k--;j--;
        }
        else
        {
            nums1[k]=nums1[i];
            k--;i--;
        }*/
        nums1[k--]=(nums2[j]>nums1[i])?nums2[j--]:nums1[i--];
        while(j>=0){
            nums1[k]=nums2[j];
            k--;j--;
        }
    }
        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

387. 字符串中的第一个唯一字符
     给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = “leetcode”
返回 0

s = “loveleetcode”
返回 2

int firstUniqChar(char * s){
    int i=0;
for(int j=strlen(s)-1;j>=0;j--)
{
    if(s[i]==s[j])
    {
        i++;
    }
}
return i;
}
1
2
3
4
5
6
7
8
9
10
11

28. 实现 strStr()
    实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2
示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

int strStr(char * haystack, char * needle){
    int num =-1;
for(int i=0;i<strlen(haystack);i++)
{
    if(haystack[i]==needle[0])
          {
               num = i;break;
          }
}
return num;
}
1
2
3
4
5
6
7
8
9
10
11

题目描述
评论 (916)
题解 (1.7k)
提交记录
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
1

/
9 20
/
15 7
返回它的最大深度 3 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    if(root==NULL) return 0;
    return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

283. 移动零
     给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

void moveZeroes(int* nums, int numsSize){
int j=0;
for(int i =0;i<numsSize;i++)
{
    if(nums[i]!=0){
        nums[j++]=nums[i];
    }
}
for(int i=j;i<numsSize;i++)
{
    nums[i]=0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

202. 快乐数
     编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

bool isHappy(int n){
    int sum,count = 0;
    while(n!=1&&count< 500)
    {
        sum=0;
        while(n)
        {
            sum+=(n%10)*(n%10);
            n/=10;
        }
        n = sum;
        count++;
    }
    return n == 1;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

617. 合并二叉树
     给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL) {
        return t2;
    }
    if (t2 == NULL) {
        return t1;
    }
    struct TreeNode* merged = malloc(sizeof(struct TreeNode));
    merged->val = t1->val + t2->val;
    merged->left = mergeTrees(t1->left, t2->left);
    merged->right = mergeTrees(t1->right, t2->right);
    return merged;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

860. 柠檬水找零
     在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：

输入：[5,5,10]
输出：true
示例 3：

输入：[10,10]
输出：false
示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

bool lemonadeChange(int* bills, int billsSize){
        int five = 0,ten = 0;
        for(int i = 0;i < billsSize;i++){
            if(bills[i] == 5){
                five++;
            }else if(bills[i] == 10){
                if(five == 0){
                    return false;
                }
                five--;
                ten++;
            }else{
                if(five > 0 && ten > 0){
                    five--;
                    ten--;
                }else if(five >= 3){
                    five -=3;
                }else{
                    return false;
                }
            }
        }
        return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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.

int romanToInt(char * s){
	int count = 0;
	while (*s){
		if (*s == 'V')         count += 5;
		else if (*s == 'L')    count += 50;
		else if (*s == 'D')    count += 500;
		else if (*s == 'M')    count += 1000;
		else if (*s == 'I')
			count = (*(s + 1) == 'V' || *(s + 1) == 'X') ? count - 1 : count + 1;
		else if (*s == 'X')
			count = (*(s + 1) == 'L' || *(s + 1) == 'C') ? count - 10 : count + 10;
		else
			count = (*(s + 1) == 'D' || *(s + 1) == 'M') ? count - 100 : count + 100;
		s++;
	}
	return count;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19