LeetCode 1,11,26


陣地を変えて、uvaをしないで直接LeetCodeに来て、1日に2つのeasyは1つのmediumで、1週間にhardで、堅持することができることを望みます.
0 1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
1つの配列と1つの目標数字に、2つの数を足した和がちょうど目標数字であることを探して、2つの数字の位置を返します(前後順にします).C++:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.size() < 2){
            return res;
        }
        map<int, int> m;
        for(int i = 0; i < nums.size(); i++){
            m[nums[i]] = i;
        }
        map<int, int>::iterator it;
        for(int i = 0; i < nums.size(); i++){
            it = m.find(target - nums[i]);
            if(it != m.end()){
                if (i == it->second) continue;
                res.push_back(i);
                res.push_back(it->second);
                return res;
            }
        }
        return res;
    }
};

java:
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map map = new HashMap();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i;
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        map.put(numbers[i], i);
    }
    return result;
}
}

1 1. Container With Most Water
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2. 座標軸には多くの線があり、2本の線がx軸に囲まれた面積を最大にすることができる(最大面積を返す).この問題については,考えが通じさえすれば何度も書き上げた.両端から真ん中に移動して、左の1本の線l、右の1本の線r、lrの高低を比較して、どの線が短いかはどの線を捨てて、lが短いとl++になります.しかし、毎回の最大面積値を記録するには、新しい面積が大きくなると、前の最大面積を置き換えます.この考え方は、面積の大きさは2本の線の距離と短い線の高さで決まるので、lがrより短い場合、lを動かさずにrを動かすと、その後得られる面積は今より大きくならないに違いありません.lはずっとそんなに長いからです.逆にlを移動すると、真ん中にlより長い線があり、min(l,r)が今より大きくなる可能性があります.
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size()-1;
        int maxv = 0;
        while(l < r){
            maxv = max(maxv, (r - l) * min(height[l], height[r]));
            if(height[l] < height[r]) l++;
            else r--;
        }
        return maxv;
    }
};

2 6. Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length. 注目すべきは、テーマが与えられているのはすでに順番に並んでいる配列で、よくできています.
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int temp = 0;//             
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[i-1]) temp++;
            else nums[i-temp] = nums[i];
        }
        return nums.size()-temp;
    }
};