速手19春招実习笔记试験(Leetcode 136&&Leetcode 665)
速手19春招実习笔记试験(Leetcode 136&&Leetcode 665)
速い手の3.30晩の筆記試験のプログラミングの問題、比較的に簡単で、2つはすべてLeetcodeの原題です.
1.Leetcode 136 Single Number
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1: Input: [2,2,1] Output: 1
Example 2: Input: [4,1,2,1,2] Output: 4
問題:
タイトルリンク:https://leetcode.com/problems/single-number/題意:配列をあげます.配列の中の要素は2回現れます.1つの要素を除いて、この要素を見つけてください.
考え方:この問題の解法は比較的多い.の最も巧みな方法は、時間的複雑度がO(n)O(n)O(n)、空間的複雑度がO(1)O(1)O(1)O(1)O(1)である異或演算によって解くことである.1つの数と0がそれ自体であるか、および自身が0であるかの結果が得られる.a ⊕ 0 = a a ⊕ 0 = a a⊕0=a a ⊕ a = 0 a ⊕ a = 0 a⊕a=0 a ⊕ b ⊕ a = ( a ⊕ a ) ⊕ b = 0 ⊕ b = b a⊕b⊕a=(a⊕a)⊕b=0⊕b=b a⊕b⊕a=(a⊕a)⊕b=0⊕b=b はまた、 であった.はまた、配列の和を減算するために
コード:排他的論理和:
辞書による記録:
setによる重量除去:
2.Leetcode 665 Non-decreasing Array
Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).
Example 1:
Input: [4,2,3] Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: [4,2,1] Output: False Explanation: You can’t get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
問題:
タイトルリンク:https://leetcode.com/problems/non-decreasing-array/題意:1つの配列が非減少配列であるかどうかを判断するには、せいぜい配列の1つの要素しか修正できず、配列を非減少配列に変え、非減少配列の定義は:
考え方:
コード:
より多くのコードはgithubを表示できます.
速い手の3.30晩の筆記試験のプログラミングの問題、比較的に簡単で、2つはすべてLeetcodeの原題です.
1.Leetcode 136 Single Number
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1: Input: [2,2,1] Output: 1
Example 2: Input: [4,1,2,1,2] Output: 4
問題:
タイトルリンク:https://leetcode.com/problems/single-number/題意:配列をあげます.配列の中の要素は2回現れます.1つの要素を除いて、この要素を見つけてください.
考え方:この問題の解法は比較的多い.
Hashtableによって解くことができ、各要素の出現回数を記録することができる.時間的複雑度はO(n)O(n)O(n),空間的複雑度はO(n)O(n)O(n)setで重量除去することもできる.コード:排他的論理和:
class Solution{
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i=0; i<nums.size(); i++){
res ^= nums[i];
}
return res;
}
};
辞書による記録:
#
def singleNumber1(self, nums):
dict = {}
for num in nums:
dict[num] = dict.get(num, 0) + 1
for key, value in dict.items():
if value == 1:
return key
setによる重量除去:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#
return sum(set(nums))*2 - sum(nums)
2.Leetcode 665 Non-decreasing Array
Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).
Example 1:
Input: [4,2,3] Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: [4,2,1] Output: False Explanation: You can’t get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
問題:
タイトルリンク:https://leetcode.com/problems/non-decreasing-array/題意:1つの配列が非減少配列であるかどうかを判断するには、せいぜい配列の1つの要素しか修正できず、配列を非減少配列に変え、非減少配列の定義は:
array[i] <= array[i + 1]で、最初の要素と最後の要素を除いて、配列の各要素はその後の要素より小さい.考え方:
array[i]とarray[i+1]の大きさ関係を直接判断し、要素を修正する必要があるかどうかを判断する.要素は1回しか変更できないため、変更された要素はarray[i-1]とarray[i+1]のサイズ関係によって決定されます.array[i-1]がarray[i+1]より大きい場合、array[i+1]はarray[i]に変更される.array[i-1]がarray[i+1]より小さい場合、array[i]はarray[i+1]に変更される.1回以上の修正は、直接return falseです.コード:
class Solution{
public:
bool checkPossibility(vector<int>& nums){
int len = nums.size(), count = 0;
for(int i=0; i < len-1; i++){
if(nums[i] > nums[i+1]){
count++;
if(count > 1){
return false;
}
if(i > 0 && nums[i+1] < nums[i-1]){
nums[i+1] = nums[i];
}
else{
nums[i] = nums[i+1];
}
}
}
return true;
}
};
より多くのコードはgithubを表示できます.