发表更新LeetCode / 算法9 分钟读完 (大约1373个字)

LeetCode-6

3. 无重复字符的最长子串

思路

双指针

  1. 如果字符串长度为1的话，直接返回1
  2. 建立哈希表，储存字符所在的位置（从1开始数）
  3. i，j两个指针，i用来遍历字符串（位置靠前），j用来记录当前不重复的字符的位置
  4. 每次循环，先查询map中s[i]的位置，如果在j的字符之前，说明从i到j没有重复字符
  5. 如果位置在j或j之后，说明出现重复字符，那么先不移动j，i-j的值就是一个非重复子串的长度
  6. 然后让j指向s[i]的下一个位置，这样就又变成了一个不重复的子串
  7. 循环结束，但是最后一次的统计没有记录，再记录一次。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 1) return 1;
        unordered_map<char, int> m;
        int len = s.length();
        int count = 0;
        int max = 0;
        int i = 0, j = 0;
        for ( ; i < len; i++) {
            if (m[s[i]] < j + 1) {
                m[s[i]] = i + 1;
            } else {
                count = i - j;
                j = m[s[i]];
                max = max > count ? max : count;
                m[s[i]] = i + 1;
            }
        }
        count = i - j;
        max = max > count ? max : count;
        return max;
    }
};
阅读更多
发表更新LeetCode / 算法14 分钟读完 (大约2088个字)

LeetCode-7

532. 数组中的K-diff数对

思路

  1. map，保存每个数出现的次数
  2. 遍历map，如果要找差为0的数对，那么如果出现次数大于1，说明有一对儿
  3. 如果差不是0，算出另一个数，在map里面查询，查询到了就是一对儿

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        map<int, int> m;
        for (int x : nums) {
            m[x]++;
        }
        int ans = 0;
        auto ite = m.begin();
        while (ite != m.end()) {
            if (k) {
                int sum = ite->first + k;
                if (m.count(sum)) ans++;//这里要用count函数查询是否存在元素，直接访问会超时
            } else {
                if (ite->second > 1) ans++;
            }
            ite++;
        }
        return ans;
    }
};

70. 爬楼梯

阅读更多
发表更新LeetCode / 算法18 分钟读完 (大约2630个字)

LeetCode-8

581. 最短无序连续子数组

思路

  1. 拷贝把备份排序，然后两个指针，依次从头到尾（i），从尾到头（j）比较排序前后两个数组相同下标的值，把第一次不同的下标值记录，最后返回j - i + 1，如果为负数返回0。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> cpy(nums.begin(), nums.end());
        sort(cpy.begin(), cpy.end());
        int len = nums.size();
        int j = len - 1, i = 0;
        for ( ; j >= 0; j--) {
            if (nums[j] != cpy[j]) {
                break;
            }
        }
        for (; i < len; i++) {
            if (nums[i] != cpy[i]) {
                break;
            }
        }
        int ans = j - i + 1;
        return ans > 0 ? ans : 0;
    }
};

思路

阅读更多
发表更新LeetCode / 算法27 分钟读完 (大约4010个字)

LeetCode-5

350. 两个数组的交集 II

思路

  1. 两个map分别统计在两个数组中一个元素的出现次数
  2. 把其中一个数组排序去重，然后查询两个map
  3. 取这个元素在两个数组里出现次数的最小值n，往ans里面push该元素n次

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> v,n;
        vector<int> ans;
        for (int x : nums1) {
            v[x]++;
        }
        for (int x : nums2) {
            n[x]++;
        }
        sort(nums1.begin(), nums1.end());
        nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
        for (int x : nums1) {
            if (v[x] && n[x]) {
                int l = v[x] > n[x] ? n[x] : v[x];
                for (int i = 0; i < l; i++)
                ans.push_back(x);
            }
        }
        return ans;
    }
};

大佬思路

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1712个字)

LeetCode-9

92. 反转链表 II

思路

  1. 两个指针a、b，分别找到被反转的第一个结点的前一个结点，被反转的结点的最后一个结点，（在开头设置一个哑结点，防止被反转的第一个结点是头结点）
  2. 再来一个指针c，保存被反转的最后一个结点的next，然后把最后一个结点的next设为null
  3. 反转链表，然后把新链表的head接回去，把c接回到末尾
  4. 返回哑结点的next，不能返回head，因为反转以后，head有可能不是head了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0), *a, *b, *c;
        dummy->next = head;
        a = b = c = dummy;
        for (int i = 0; i < m - 1; i++) {
            a = a->next;
            b = b->next;
        }
        for (int i = 0; i < n - m + 1; i++) {
            b = b->next;
        }
        c = b->next;
        b->next = NULL;
        a->next = reverseList(a->next);
        while (a->next != NULL) {
            a = a->next;
        }
        a->next = c;
        return dummy->next;
    }
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

15. 三数之和

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×