Skip to content

Instantly share code, notes, and snippets.

@lyleaf
Last active August 24, 2016 18:20
Show Gist options
  • Save lyleaf/1e3ac392106ea1309f33ee7bc996a2dd to your computer and use it in GitHub Desktop.
Save lyleaf/1e3ac392106ea1309f33ee7bc996a2dd to your computer and use it in GitHub Desktop.
sorted array去重只需要O(n) time, O(1) space
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int cur = 0;
for (int i=1;i<nums.size();i++){
if (nums[i] != nums[cur]){
swap(nums[i],nums[++cur]);
}
}
return cur+1;
}
};
int removeDuplicates(vector<int>& nums) {
int i = !nums.empty();
for (int n : nums)
if (n > nums[i-1])
nums[i++] = n;
return i;
}
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int cur = -1;
for (auto n:nums){
if (n!=val){
nums[++cur] = n;
}
}
return cur+1;
}
};
//有一个更好的方法,还没有写出来,明天写出来。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
bool flag = false;
for (int i=0;i<haystack.size();i++){
if (haystack[i] == needle[0]){
flag = true;
for (int j=0;j<needle.size();j++){
if (i+needle.size()>haystack.size() || haystack[i+j] != needle[j]){
flag = false;
break;
}
}
if (flag) return i;
}
}
return -1;
}
};
//改进1: 判断条件可以变成i<m-n+1
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
bool flag = false;
for (int i=0;i<haystack.size()-needle.size()+1;i++){
if (haystack[i] == needle[0]){
flag = true;
for (int j=0;j<needle.size();j++){
if (haystack[i+j] != needle[j]){
flag = false;
break;
}
}
if (flag) return i;
}
}
return -1;
}
};
//改进2:不用flag,而是比较j是不是全部比较完了。
//不用比较第一个,直接开始For循环。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
bool flag = false;
for (int i=0;i<int(haystack.size())-int(needle.size())+1;i++){
int j=0;
for (;j<needle.size();j++){
if (haystack[i+j] != needle[j]){
flag = false;
break;
}
}
if (j == needle.size()) return i;
}
return -1;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment