活动打卡

#include <iostream>
#include <vector>
#include <memory>

using namespace std;

class Trie {
public:
  Trie() : root_(new TrieNode()) {}

  void insert(const string& word) {
    auto p = root_.get();
    for (const auto& c : word) {
      if (!p->children[c - 'a'])
        p->children[c - 'a'] = new TrieNode();
      p = p->children[c - 'a'];
    }
    ++p->count;
  }

  int search(const string& word) {
    int cnt = 0;
    auto p = root_.get();
    for (const auto& c : word) {
      if (!p->children[c - 'a']) break;
      p = p->children[c - 'a'];
      cnt += p->count;
    }
    return cnt;
  }

private:
  struct TrieNode {
    TrieNode() : count(0), children(26, nullptr) {} 
    ~TrieNode() {
      for (const auto& child : children) delete child;
    }

    int count; // 单词的个数 
    vector<TrieNode*> children;
  };

  unique_ptr<TrieNode> root_;
};

int n, m;
Trie trie;

int main(void) {
  cin >> n >> m;
  string word;
  while (n--) {
    cin >> word;
    trie.insert(word);
  }
  while (m--) {
    cin >> word;
    cout << trie.search(word) << endl;
  }
}

活动打卡

typedef struct TrieNode {
  struct TrieNode* children[26];
  bool is_word;
} TrieNode;

typedef struct {
  TrieNode* root;
} Trie;

/** Initialize your data structure here. */
Trie* trieCreate() {
  Trie* trie = malloc(sizeof(Trie));
  // dummy root
  trie->root = malloc(sizeof(TrieNode));
  memset(trie->root->children, 0x0000, sizeof trie->root->children);
  trie->root->is_word = false;

  return trie;
}

/** Inserts a word into the trie. */
void trieInsert(Trie* trie, char * word) {
  TrieNode* p = trie->root;
  for (char * c = word; *c; ++c) {
    if (!p->children[*c - 97]) {
      TrieNode* node = malloc(sizeof(TrieNode));
      memset(node->children, 0x0000, sizeof node->children);
      node->is_word = false;
      p->children[*c - 97] = node;
    }
    p = p->children[*c - 97];
  }
  p->is_word = true;
}

TrieNode* find(Trie* trie, char * prefix) {
  TrieNode* p = trie->root;
  for (char * c = prefix; *c; ++c) {
    if (!p->children[*c - 97]) return NULL;
    p = p->children[*c - 97];
  }
  return p;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie* trie, char * word) {
  TrieNode* p = find(trie, word);
  return p && p->is_word;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* trie, char * prefix) {
  return find(trie, prefix) != NULL; 
}

void trieFree(Trie* trie) {
  free(trie);
}

活动打卡

算法1: DFS

class Solution {
public:
  int treeDepth(TreeNode* root) {
    return root ? 1 + max(treeDepth(root->left), treeDepth(root->right)) : 0;
  }
};

算法2: BFS

class Solution {
public:
  int treeDepth(TreeNode* root) {
    // corrner case
    if (!root) return 0;

    queue<TreeNode*> q{{root}};

    int level = 0;
    while (not q.empty()) {
      int sz = q.size();
      while (sz--) {
        TreeNode* cur = q.front(); q.pop();
        if (cur->left)  q.emplace(cur->left);
        if (cur->right) q.emplace(cur->right);
      }
      ++level;
    }

    return level;
  }
};

活动打卡

class Solution {
public:
  int minDiffInBST(TreeNode* root) {
    vector<int> vals;
    inOrder(root, vals);
    int ans = vals.back();
    for (int i = 1; i < vals.size(); ++i)
      ans = min(ans, vals[i] - vals[i - 1]);

    return ans;
  }

private:
  void inOrder(TreeNode* root, vector<int>& vals) {
    if (!root) return;
    inOrder(root->left, vals);
    vals.emplace_back(root->val);
    inOrder(root->right, vals);
  }
};

活动打卡

class Solution {
public:
  int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
      int m = l + ((r - l) >> 1);
      if (nums[m] < nums[r]) r = m;
      else l = m + 1;
    }
    return nums[l];
  }
};

活动打卡

class Solution {
public:
    int findMin(vector<int>& nums) {
        // corner case
        if (nums.empty()) return -1;

        for (int i = 0; i < nums.size() - 1; ++i)
            if (nums[i] > nums[i + 1]) return nums[i + 1];

        return -1;
    }
};

活动打卡

bool search(int* nums, int numsSize, int target) {
  for (int i = 0; i < numsSize; ++i)
    if (*(nums + i) == target) return true;
  return false;

活动打卡

int removeDuplicates(int* nums, int numsSize) {
  // corner case
  if (numsSize < 3) return numsSize;

  // 维护住[0..k]左闭右闭区间内每个元素至多出现两次的循环不定式
  int k = 0, cnt = 1;
  for (int i = 1; i < numsSize; ++i) {
    if (*(nums + i) == *(nums + k)) {
      if (++cnt <= 2) *(nums + ++k) = *(nums + i);
    } else {
      *(nums + ++k) = *(nums + i);
      cnt = 1;
    }
  }

  return k + 1;
}

活动打卡

#include <iostream>
#include <unordered_set>

using namespace std;
int n, x;
unordered_set<int> s;

int main(int argc, char** argv) {
  cin >> n;
  while (n--) {
    cin >> x;
    s.emplace(x);
  }
  return printf("%d\n", s.size()), 0;
}

活动打卡

#include <iostream>
#include <unordered_map>

using namespace std;
int n, x;

unordered_map<int, int> freq;

int main(int argc, char** argv) {
  cin >> n;
  int max_freq = 0, ans;
  while (n--) {
    cin >> x;
    ++freq[x];
    if (freq[x] > max_freq) max_freq = freq[x], ans = x;
    else if (freq[x] == max_freq && x < ans) ans = x;
  }

  return printf("%d\n", ans), 0;
}