面试 | #算法#

更新面试可能遇到以及遇到的算法题

排序

快速排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      quick_sort(arr, 0, arr.size()-1); 
      return arr;
    }

  private:
    void quick_sort(std::vector<int> &arr, int low, int high) {
      if (low < high) {
        int key = partition(arr, low, high);
        quick_sort(arr, low, key-1);
        quick_sort(arr, key+1, high);
      }
    }
    int partition(std::vector<int> &arr, int low, int high) {
      int base = low;  // 第一个元素作为基准
      while (low < high) {
        while (arr[high] > arr[base] && low < high) --high;
        while (arr[low] <= arr[base] && low < high) ++low;
        std::swap(arr[low], arr[high]);
      }
      if (arr[base] >= arr[low]) {   //  这里使用等于判断,防止首元素进行交换时产生越界
        std::swap(arr[base], arr[low]);
        return low;
      } else {
        std::swap(arr[base], arr[low-1]);
        return low-1;
      }
    }
};

归并排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      merge_sort(arr, 0 , arr.size()-1);
      return arr;
    }

  private:  
    void merge_elem(std::vector<int> &arr, int low, int mid, int high) {
      std::vector<int> temp;
      int i = low, j = mid + 1;

      // 排序插入
      while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
          temp.push_back(arr[i++]);
        } else {
          temp.push_back(arr[j++]);
        }
      }

      // 遍历剩下部分
      while (i <= mid) {
        temp.push_back(arr[i++]);
      }
      while (j <= high) {
        temp.push_back(arr[j++]);
      }

      // 拷贝回原数组
      for (int i = low, j = 0; i <= high; i++) {
        arr[i] = temp[j++];
      }
    }

    void merge_sort(std::vector<int> &arr, int low, int high) {
      if (low < high) {    // 分割到两个元素
        int mid = (low+high) / 2;
        merge_sort(arr, low, mid);
        merge_sort(arr, mid+1, high);
        merge_elem(arr, low, mid, high);   // 递归到两个元素后合并回退
      }
    }
};

堆排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      heap_sort(arr, 0, arr.size()-1);
      return arr;
    }

  private:
    void sink(std::vector<int> &arr, int node, int size) {
      while (2*node + 1 <= size) {
        int max_node = 2*node + 1;
        if (max_node < size && arr[max_node] < arr[max_node+1]) {  // 找到最大孩子
          max_node++;
        }
        if (arr[node] >= arr[max_node]) {
          break;
        } else {
          std::swap(arr[node], arr[max_node]);
        }
        node = max_node;   // 持续下沉到叶子结点或满足条件
      }
    }
    // 从零开始,使用(n-1)/2
    void heap_sort(std::vector<int> &arr, int low, int high) {
      for (int i = (high-1) / 2; i >= 0; i--) {   // 构建最大堆 
        sink(arr, i, high);
      }
      while (high > 0) {    // 交换-下沉 完成排序
        std::swap(arr[high--], arr[0]);   // 最大元素挪到末尾,再调整堆
        sink(arr, 0, high);
      }
    }
};

冒泡排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      bubble_sort(arr, arr.size()-1);
      return arr;
    }

  private:
    void bubble_sort(std::vector<int> &arr, int size) {
      for (int i = 0; i < size; i++) {  // n个元素循环n-1次
        for (int j = 0; j < size - i; j++) {  // 每次取出最大元素到最尾
          if (arr[j] > arr[j+1]) {
            std::swap(arr[j], arr[j+1]);
          }
        }
      }
    }
};

插入排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      insertion_sort(arr, arr.size()-1);
      return arr;
    }

  private:
    void insertion_sort(std::vector<int> &arr, int size) {
      for (int i = 1; i <= size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
          arr[j+1] = arr[j];
          j--;
        }
        arr[j+1] = key;
      }
    }
};

选择排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      selection_sort(arr, arr.size()-1);
      return arr;
    }

  private:
    void selection_sort(std::vector<int> &arr, int size) {
      // 第一层循环选中n-1个元素
      // 从选中元素后面 挑选出最小的元素与当前元素交换
      // 选中元素最小则不交换
      for (int i = 0; i < size; i++) {
        int min = arr[i];
        int index = i;
        for (int j = i+1; j <= size; j++) {
          if (arr[j] < min) {
            min = arr[j];
            index = j;
          }
        }
        if (index != i) {
          std::swap(arr[i], arr[index]);
        }
      }
    }
};

计数排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      counting_sort(arr, arr.size()-1);
      return arr;
    }

  private:
    void counting_sort(std::vector<int> &arr, int size) {
      int max = arr[0];
      std::vector<int> copy_arr(arr);  // 辅助数组
      for (int i = 0; i <= size; i++) {
        if (arr[i] > max) {
          max = arr[i];
        }
      }  
      std::vector<int> temp(max+1, 0);  // 大小为数据区间
      for (int i = 0; i <= size; i++) {
        temp[arr[i]]++;  // 统计每个值出现的次数,存放在对应下标
      }
      // 计数累加
      for (int i = 1; i < temp.size(); i++) {
        temp[i] += temp[i-1];   // 记录当前值排的位数
      }
      // 反向填充数组
      for (int i = size; i >= 0 ; i--) {
        arr[--temp[copy_arr[i]]] = copy_arr[i];  // 索引比计数值小1,先自减
      }
    }
};

希尔排序

void shell_sort(std::vector<int> &a, int n) {
  int i,j,gap;

    // gap为步长,每次减为原来的一半。
  for (gap = n / 2; gap > 0; gap /= 2) {
        // 共gap个组,对每一组都执行直接插入排序
    for (i = 0 ;i < gap; i++) {
      for (j = i + gap; j < n; j += gap) {
                // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
        if (a[j] < a[j - gap]) {
          int tmp = a[j];
          int k = j - gap;
          while (k >= 0 && a[k] > tmp) {
            a[k + gap] = a[k];
            k -= gap;
          }
          a[k + gap] = tmp;
        }
      }
    }
  }
}     

二叉树的前中后序遍历(迭代)

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeOrders(TreeNode* root) {
      if (root == nullptr) {
        return std::vector<std::vector<int>>(3, std::vector<int>());
      }
      //
      std::vector<std::vector<int>> res;
      std::stack<TreeNode *> s;
      std::vector<int> tmp;
      //
      s.push(root);

      while (!s.empty()) {
        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        if (cur->right) {
          s.push(cur->right);
        }
        if (cur->left) {
          s.push(cur->left);
        }
      }

      res.push_back(tmp);
      tmp.clear();

      //
      TreeNode *node = root;

      while (node || !s.empty()) {
        while (node) {
          s.push(node);
          node = node->left;
        }

        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        node = cur->right;
      }

      res.push_back(tmp);
      tmp.clear();

      //
      s.push(root);

      while (!s.empty()) {
        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        if (cur->left) {
          s.push(cur->left);
        }
        if (cur->right) {
          s.push(cur->right);
        }
      }

      std::reverse(tmp.begin(), tmp.end());
      res.push_back(tmp);

      return res;
    }
};
#浦发银行##offer比较##中国农业银行#
全部评论
楼主最后签哪里了,农行省分科技岗的待遇可以告知一下吗,农行省分科技岗给我补录了
1 回复
分享
发布于 2021-04-25 01:17
听说农行早就签了呀
点赞 回复
分享
发布于 2020-01-14 10:03
小红书
校招火热招聘中
官网直投
浦发信息科技钱多,加班,而且有独立成子公司的可能。省分行不会独立,具有待遇不清楚,应该没有浦发多,加班情况应该也没有浦发多。所以就是钱和安逸之间选吧
点赞 回复
分享
发布于 2020-01-14 11:05
请问你是收到了浦发科技岗武汉的offer了么,我背调十多天了,好焦急😂望回复,感谢感谢😀
点赞 回复
分享
发布于 2020-01-14 12:05

相关推荐

点赞 评论 收藏
转发
点赞 1 评论
分享
牛客网
牛客企业服务