fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
双指针技巧秒杀七道数组题目 :: labuladong的算法小抄
142.环形链表II https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/kuai-man-zhi-zhen-shu-xue-tui-dao-by-yuhhen/ 这个数学证明比较好。
反转数组c++一行代码{狗头}{狗头}
void reverseString(vector<char>& s) {
for(int i = 0, j = s.size()-1; i <= j; ++i, --j) swap(s[i], s[j]);
}
167题，还能使用 二分查找+双指针，更优
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int m = (i + j) >>> 1;
if (numbers[i] + numbers[m] > target) {
j = m - 1;
} else if (numbers[m] + numbers[j] < target) {
i = m + 1;
} else if (numbers[i] + numbers[j] > target) {
j--;
} else if (numbers[i] + numbers[j] < target) {
i++;
} else {
return new int[]{i + 1, j + 1};
}
}
return new int[]{0, 0};
}
}
27题，左右指针解法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
curr, tail = 0, len(nums) - 1
while curr <= tail:
if nums[curr] == val:
nums[curr], nums[tail] = nums[tail], nums[curr]
tail -= 1
else:
curr += 1
return curr
这里好像有点问题：”高效解决这道题就要用到快慢指针技巧：我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。“ 应该是先让slow前进一步，再赋值吧
第283题移动零的另一种解法，没必要再记住下标最后遍历赋值为0
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0){
int temp = nums[slow];
nums[slow++] = nums[fast];
nums[fast] = temp;
}
}
}
}
这个大概也算是双指针吧，另外一种移动零的解法，（前四题都可以用的）
public void moveZeroes(int[] nums) {
int i = 0;
int length = nums.length;
for(int num : nums){
if(num != 0){
nums[i++] = num;
}
}
while(i < length){
nums[i++] = 0;
}
}
使用C++解决第五题【最长回文子串】，貌似需要改写字符串子串结果返回代码：
class Solution {
public:
string longestPalindrome(string s) {
string res = "";
for(int i = 0; i < s.length(); i++){
string s1 = findPalindrome(s, i, i);
string s2 = findPalindrome(s, i, i+1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
string findPalindrome(string& s, int l, int r){
while(l >= 0 && r < s.length() && s[l] == s[r]){
l--;
r++;
}
return s.substr(l+1, r-l-1); // C++中的子串函数substr(pos, count)，第二参数count是子串长度
}
};
167两数之和C++ 注意+1
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left=0,right=numbers.size()-1;
while(left<right){
int sum=numbers[left]+numbers[right];
if(sum==target){
return vector<int> {left+1,right+1};
}
else if(sum<target){
left++;
}
else if(sum>target){
right--;
}
}
return vector<int>{-1,-1};
}
};
最後一題可以小優化一下，提前跳出for循環：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (s.length === 1) return s
let longest = ''
for (let i = 0; i < s.length-1; i++) {
let odd = palindrome(s, i, i)
let even = palindrome(s, i, i+1)
longest = longest.length < odd.length ? odd : longest
longest = longest.length < even.length ? even : longest
if (Math.ceil(longest.length / 2) >= s.length - i) break
}
function palindrome(s, l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l --
r ++
}
return s.slice(l+1, r)
}
return longest
};
求教大佬這個時間復雜度怎麼算呢？
@labuladong 26题我能不能直接赋值给slow为0 fast为1，当nums[slow] 和 nums[fast]不相等时 往前各前进一步 def removeDuplicates(self, nums: List[int]) -> int: fast = 1 slow = 0
while fast in range(len(nums)):
if nums[slow] != nums[fast]:
fast += 1
slow += 1
else:
nums.pop(fast)
return len(nums)
