leetCode

2018-10-28 本文已影响0人 e26f55e7ec23

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

public class leetcode {

     static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int i,j;
        for (i=0;i<nums.length-1;i++){
            for (j=i+1;j<nums.length;j++)
                if (nums[i]+nums[j]==target){
                    result[0] = i;result[1] = j;
                    break;
                }
        }
        return result;
    }


    public static void main(String[] args) {


        int[] nums = {2, 5,7, 11, 15};
        int target = 9;
        int[] res = twoSum(nums,target);
        for (int n:res
             ) {
            System.out.println(n);
        }

    }
}

2.给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

public class reverse_integer {
    public static int reverse(int x) {
        String len = String.valueOf(x);
        long result = 0,num;
        if (x>0) {
            for (int i = 0; i < len.length(); i++) {
                num = x % 10;
                x = x / 10;
                System.out.println("num:" + num);

                result = result * 10 + num;

                System.out.println("result:" + result);
            }
        }
        else {
            for (int i = 0; i < len.length()-1; i++) {
                num = x % 10;
                x = x / 10;
//                System.out.println("num:" + num);
                result = result * 10 + num;
//                System.out.println("result:" + result);
            }
        }

        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE)
            result = 0;

        return (int) result;
    }


    public static void main( String args[] ){
        int outcome = reverse(1534236469);
        System.out.println(outcome);
    }
}

注意溢出

 if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE)
            result = 0;

方法2：

public int reverse(int x) { 
    long result = 0; 
    while (x != 0) { 
        result = result * 10 + x % 10; x /= 10; 
    } 
    if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) 
        result = 0; 
    return (int)result; 
}

3.罗马数字包含以下七种字符: 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 的范围内。

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

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

示例 1:

<pre>给定数组 nums = [1,1,2],

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

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

示例 2:

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
代码1：

public static int removeDuplicates(int[] nums) {

        int i,j = 0;
        for (i=1;i<nums.length;){
            if(nums[i]==nums[i-1]){

                for (j = i;j<nums.length-1;j++){
//前移一位
                    nums[j] = nums[j+1];
                }
                nums = Arrays.copyOf(nums, nums.length-1);
            }
            else {
                i++;
//                j = i;
            }

            for (int g:nums
                    ) {
                System.out.print(g);
            }
            System.out.println('\n');
        }

        for (int g:nums
                ) {
            System.out.print(g);
        }

        return nums.length;
    }

输入：

0011122334

输出：

代码一没有否和要求，但是结果是正确的，应为忽视了在原数组中操作的条件

答案：

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

输入：

0011122334

输出：

5.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

image

示例:

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        dict = {}
        dict[2] = ['a', 'b', 'c']
        dict[3] = ['d', 'e', 'f']
        dict[4] = ['g', 'h', 'i']
        dict[5] = ['j', 'k', 'l']
        dict[6] = ['m', 'n', 'o']
        dict[7] = ['p', 'q', 'r', 's']
        dict[8] = ['t', 'u', 'v']
        dict[9] = ['w', 'x', 'y', 'z']
        res = []
        list = ''
        self.helper(res, list, dict, digits, 0)
        return res
        
    def helper(self, res, list, dict, digits, pos):
        if pos == len(digits):
            res.append(list)
            return
        num = int(digits[pos])
        for c in dict[num]:
            list += c
            self.helper(res, list, dict, digits, pos + 1)
            list = list[:-1]