2019-07-08 • algor, array, leetcode

LC-array1-easy-1,26,27

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.1 python solution1：运用python字典结构

遍历数组（第一个数），算余值（求第二个数）；
将遍历过数和下标构建字典；
查询第二个数是否在字典中；
最多遍历一遍，便能找到余值，并返回两个数的下标。

class solution():
   def twoSum(self, nums, target):
       """
       :type nums: List[int]
       :type target: int
       :rtype: List[int]
       """
       hash = {}
       for i in range(len(nums)):
           if target - nums[i] in hash:
               return [i, hash[target - nums[i]]]
           else:
               hash[nums[i]] = i

       #无解时
       return [-1, -1]

注意返回值的格式；
注意括号的完整性；
注意python字典取值格式；
注意python字典的： key:word对； ***

1.1.2 python solution2：运用Python数组的index方法

遍历数组，计算另一数；
用 in 方法查询第二个数是否在数组中；
用.index方法查询该数在数组中的下标；

class Solution(object):
   def twoSum(self, nums, target):
       """
       :type nums: List[int]
       :type target: int
       :rtype: List[int]
       """
       for i in range(0,len(nums)):
           if (target - nums[i]) in nums[i+1:]:
               return [i, nums.index(target - nums[i], i+1, len(nums))]

in方法
python数组的.index方法

1.2.1 C++ solution1: 运用hash函数

vector<int> twoSum(vector<int> &numbers, int target)
{
   //Key is the number and value is its index in the vector.
       unordered_map<int, int> hash;
       vector<int> result;
       for (int i = 0; i < numbers.size(); i++) {
               int numberToFind = target - numbers[i];

           //if numberToFind is found in map, return them
               if (hash.find(numberToFind) != hash.end()) {
                   //+1 because indices are NOT zero based
                       result.push_back(hash[numberToFind]);
                       result.push_back(i);                  
                       return result;
               }

           //number was not found. Put it in the map.
               hash[numbers[i]] = i;
       }
       return result;
}

vector<int> result：结果用vector表示；
map<int, int> hash：构建空的哈希map；
for(int i = 0; i < 10; i++){ }：遍历数组下标；
number.size()：取得vector的大小；
if hash.find（numberToFind) != hash.end(){ }:如果hash表中能找到第二个数；
result.push_back()：向vector 中推入某数；

26. Remove Duplicates from Sorted Array

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example 1:

Given 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 returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
   print(nums[i]);
}

对一个已排序了的数组，进行去重操作，返回最后的长度：

空间复杂度要求：O(1)

26.1.1 python solution1:遍历法 + 双指针法

定义一个start指针 和 一个工作指针；
不一样，存储工作指针下的元素到start指针下，并接力挪位start指针；
一样，则后移工作指针；
返回最后数组的长度（即start指针的值 + 1）

def removeDuplicates(self, nums):
   """
   :type nums: List[int]
   :rtype: int
   """
   if not nums:    #因为nums可能为[]
       return 0
   start = 0

   for i in range(1, len(nums)):        #i即工作指针，工作指针遍历原数组，遍历完一个后即可扔掉
       if nums[start] == nums[i]:       #start为存储指针，存储指针恰好处于被扔掉的区域
      #     i += 1
       else:
           start += 1                   #找到新的尾巴
           nums[start] = nums[i]        #则存储
   return start+1

if not nums: :判断list是否为空（注意算法完备性）

26.2.1 C++ Solution:互斥思想

遍历数组，计算数组中，重复元素的个数count，最后用总个数减掉count;
后面一个数，等于前面的数，则count + 1;

int count = 0;
for(int i = 1; i < n; i++){
   if(A[i] == A[i-1]) count++;
   else A[i-count] = A[i];
}
return n-count;

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.