头像

optimjie

山东科技大学


访客:10726

离线:7分钟前


活动打卡代码 LeetCode 2. 两数相加

算法:遍历一遍 $O(n)$

直接遍历两个链表计算即可。

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *tail = dummy;
        int t = 0;
        while (l1 && l2) {
            int sum = t + l1->val + l2->val;
            addTail(tail, sum % 10);
            t = sum / 10;
            l1 = l1->next, l2 = l2->next;
        }
        while (l1) {
            int sum = t + l1->val;
            addTail(tail, sum % 10);
            t = sum / 10;
            l1 = l1->next;
        }
        while (l2) {
            int sum = t + l2->val;
            addTail(tail, sum % 10);
            t = sum / 10;
            l2 = l2->next;
        }
        if (t) addTail(tail, t);
        return dummy->next;
    }
    void addTail(ListNode* &tail, int x) {
        ListNode *p = new ListNode(x);
        tail->next = p;
        tail = p;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int t = 0;
        ListNode p1 = l1, p2 = l2;
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while (p1 != null && p2 != null) {
            t += p1.val;
            t += p2.val;
            tail = add(tail, t % 10);
            t /= 10;
            p1 = p1.next;
            p2 = p2.next;
        }
        while (p1 != null) {
            t += p1.val;
            tail = add(tail, t % 10);
            t /= 10;
            p1 = p1.next;
        }
        while (p2 != null) {
            t += p2.val;
            tail = add(tail, t % 10);
            t /= 10;
            p2 = p2.next;
        }
        if (t > 0) {
            tail = add(tail, t);
        }
        return head.next;
    }
    public ListNode add(ListNode tail, int val) {
        ListNode tmp = new ListNode(val);
        tail.next = tmp;
        tail = tmp;
        return tail;
    }
}


活动打卡代码 LeetCode 1. 两数之和

算法一:暴力 $O(n^2)$

枚举所有的情况,判断和是否为target

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 1; i < n; i++) 
            for (int j = 0; j < i; j++)
                if (nums[i] + nums[j] == target) return vector<int>{j, i};
        return vector<int>();
    }
};

算法二:哈希 $O(n)$

暴力的时间瓶颈在于,对于每一个数i,我们在判断i与前面的数是否满足要求时需要遍历一遍,需要$O(n)$的时间复杂度,所以我们可以将前面出现过的数用哈希表存下来,这样可以将这一步操作降到$O(1)$,从而总的时间复杂度为$O(n)$。

C++:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++) {
            if (hash.find(target - nums[i]) != hash.end())
            return vector<int>{hash[target - nums[i]], i};
            hash.insert({nums[i], i});
        }
        return vector<int>();
    }
};

Java:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hash = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (hash.containsKey(target - nums[i])) 
                return new int[]{hash.get(target - nums[i]), i};
            hash.put(nums[i], i);
        }
        return new int[2];
    }
}


活动打卡代码 AcWing 5426. 重新规划路线

const int N = 5e4 + 10;

class Solution {
public:  

    int h[N] = {0}, e[2 * N] = {0}, ne[2 * N] = {0}, idx = 0;
    int ans = 0;
    unordered_set<string> hash;

    int minReorder(int n, vector<vector<int>>& connections) {
        memset(h, -1, sizeof h);
        for (auto v : connections) {
            add(v[0], v[1]);
            add(v[1], v[0]);
            hash.insert(to_string(v[0]) + "#" + to_string(v[1]));
        }
        dfs(0, -1);
        return ans;
    }

    void dfs(int u, int fa) {
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            if (hash.find(to_string(u) + "#" + to_string(j)) != hash.end()) ans++;
            dfs(j, u);
        }
    }

    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, (int)-1e5);
    }
    int dfs(TreeNode *p, int maxv) {
        if (p == nullptr) return 0;
        int res = 0;
        if (p->val >= maxv) res++;
        res += dfs(p->left, max(maxv, p->val));
        res += dfs(p->right, max(maxv, p->val));
        return res;
    }
};



optimjie
12天前

算法:DFS

做法:

  1. dfs找到所有的路径
  2. 对于每一个路径判断能否构成回文,我这里的做法是用一个set,如果之前有当前的数字,那么从set中删掉(相当于抵消),否则添加,最后看set的长度,若小于等于1则可以构成回文,等于0代表:所有的数字都抵消则将每一个数字分别放在两边可构成回文;等于1代表:还剩一个数字,将这个数放在中间,其余数字放在两边可构成回文。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    vector<int> path;
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root);
        return ans;
    }
    void dfs(TreeNode *root) {
        if (root == NULL) return;
        path.push_back(root->val);
        if (root->left == NULL && root->right == NULL) {
            set<int> s;
            for (auto v : path) {
                if (s.find(v) == s.end()) s.insert(v);
                else s.erase(v);
            }
            if (s.size() <= 1) ans++;
        }
        if (root->left) dfs(root->left);
        if (root->right) dfs(root->right);
        path.pop_back();
    }
};



optimjie
12天前

算法:滑动窗口

时间复杂度:$O(n)$

做法:

  • i指针在后,j指针在前,当j~i的长度大于k时将j向后移动,并判断是否为元音,来修改当前窗口元音的数量,若区间i~j的长度等于k则更新答案。
class Solution {
public:
    int maxVowels(string s, int k) {
        int n = s.size();
        if (n == 0) return 0;
        int ans = 0;
        for (int i = 0, j = 0, cnt = 0; i < n; i++) {
            if (i - j + 1 > k) {
                if (check(s[j++])) cnt--;
            }
            if (check(s[i])) cnt++;
            if (i - j + 1 == k) ans = max(ans, cnt);
        }
        return ans;
    }
    // a, e, i, o, u
    bool check(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
        return false;
    }
};



optimjie
12天前

暴力

找出所有的单词,看前缀。

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int n = sentence.size();
        if (n == 0) return -1;
        vector<string> word;
        for (int i = 0; i < n; ) {
            string s;
            while (i < n && sentence[i] != ' ') s += sentence[i++];
            word.push_back(s);
            i++;
        }
        for (int i = 0; i < word.size(); i++) {
            if (searchWord.size() > word[i].size()) continue;
            if (word[i].substr(0, searchWord.size()) == searchWord) return i + 1;
        }
        return -1;
    }
};


活动打卡代码 AcWing 696. 哈默队长

optimjie
13天前

这不是个物理题吗???😰

#include <bits/stdc++.h>

using namespace std;

const double g = 9.8;

int t;
int v, d;

int main() {
    cin >> t;
    for (int u = 1; u <= t; u++) {
        cin >> v >> d;
        double s = d * g / v / v;
        double l = 0, r = 45;
        while (r - l > 1e-8) {
            double mid = (l + r) / 2;
            if (sin(2 * mid * M_PI / 180) > s) r = mid;
            else l = mid;
        }
        printf("Case #%d: %.7lf\n", u, l);
    }
    return 0;
}


活动打卡代码 AcWing 697. 蒙斯特

optimjie
13天前
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int t, n;

int main() {
    cin >> t;
    for (int u = 1; u <= t; u++) {
        vector<string> str;
        int ans = 0;
        cin >> n;
        getchar();
        while (n--) {
            string s;
            getline(cin, s);
            if (str.size() == 0) str.push_back(s);
            else {
                if (s < str.back()) ans++;
                str.push_back(s);
                sort(str.begin(), str.end());
            }
        }
        printf("Case #%d: %d\n", u, ans);
    }
    return 0;
}



optimjie
17天前

看leetcode上的题解都是DP,分享一下分治的做法

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        return merge(nums, 0, n - 1);
    }
    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return nums[l];
        int mid = l + r >> 1;
        int res = max(merge(nums, l, mid), merge(nums, mid + 1, r)); 
        int leftPos, leftNeg, rightPos, rightNeg;
        leftPos = rightPos = 0;
        leftNeg = rightNeg = 0;
        for (int i = mid + 1, s = 1; i <= r; i++) {
            s *= nums[i];
            if (s > rightPos) rightPos = s;
            if (s < rightNeg) rightNeg = s;
        }
        for (int i = mid, s = 1; i >= l; i--) {
            s *= nums[i];
            if (s > leftPos) leftPos = s;
            if (s < leftNeg) leftNeg = s;
        }
        return max(res, max(leftNeg * rightNeg, leftPos * rightPos));
    }
};