Algorithm training(一)

1. two sum

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

求目标值刚好是数组里面两个数字之和返回数组位置

解法：

/**
     * two sum
     */
    public static int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {//检查key值
                result[1] = i + 1;
                result[0] = map.get(target - numbers[i]);
                return result;
            }
            map.put(numbers[i], i + 1);//存储数组的值作为key
        }
        return result;
    }

2. Reverse Integer (数字 反转输出)

比如：
Input: 123
Output:  321

Input: -123
Output: -321

Input: 120
Output: 21

    /**
     * 反转数字 比如123 输出321
     */
    public static int reverse(int x) {
        int result = 0;
        int sign = x >> 31;
        try {

            while (x != 0) {
                result = result * 10 + x % 10;
                x = x / 10;
            }
            if (sign != (result >> 31)) {
                System.out.println("overflow..");
                System.exit(1);
            }
            System.out.println("反转数字输出结果：" + result);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return result;
    }

避免不了溢出。。。

3.Remove Duplicates from Sorted Array （去掉分类数组里面相同值 返回array的长度）

Given nums = [1,1,2],里面相同1，返回长度2；

    /**
     * 去除相同 数字 返回数组长度
     * 
     * @param nums{1,1,3,3,5,6,7}
     * @return 数子值
     */
    public static 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;
    }

4.Remove Element

    public int removeElement(int[] nums, int val) {
       if(nums.length == 0) {
            return 0;
        }
        int i = nums.length;
        for (int j = 0; j < nums.length; j++) {
            if (val == nums[j]) {
                i--;
            }
        }
        System.out.println("返回相同数字个数：" + i);
        return i;
    }

5.Implement strStr()

如果needle是haystack的一部分，返回索引值，如果不是，返回-1；

Input: haystack = "hello", needle = "ll"
Output: 2 

Input: haystack = "aaaaa", needle = "bba"
Output: -1

实现：

 public int strStr(String haystack, String needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; ++i) {
            if (haystack.substring(i, i + l2).equals(needle)) {
                System.out.println("输出字符串位置：" + i);
                return i;
            }
        }
        
        return -1;
    }