《逆袭进大厂》第十弹之数据结构与算法 | 开放PDF编辑权限

简介: 笔记

大家好,我是阿秀。

我想很多人等这期可能很久了,但说实话,算法这种东西没什么方法能快速提升,算法能力的提升需要日积月累、慢慢形成的。

在互联网招聘中,不管是笔试还是面试中的手撕算法,可以考察的算法题类型真的太多了,比如链表、树、数组、动态规划、回溯算法、贪心算法、甚至是拓扑都有可能考察到。

而一般说来笔试的难度是比面试稍微高一些的,面试中的手撕算法难度一般是力扣的 medium 水平,也有一些 easy 的,而笔试至少都是力扣 medium 难度以上的,hard 也是常有的事儿。

所以对于那些想抱着求一把算法通关秘钥的想法点开这篇文章同学来说,可能要让他们失望了,抱歉,我这里并没有能保证你百分百顺利通过算法考核的灵丹妙药。

我仅在这片文章中为大家盘点一下互联网大厂面试考察频率比较高的 7 道手撕算法题,有答案的那种。

另外 《逆袭进大厂》的第四版 PDF 已经整理出来了,下载方式在文末。


1、合并有序链表


将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的。

输入:1->2->4, 1->3->4

输出:1->1->2->3->4->4

力扣链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

#include <iostream>
using namespace std;
struct myList {
    int val;
    myList* next;
    myList(int _val) :val(_val), next(nullptr) {}
};
myList* merge(myList* l1, myList* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    myList head(0);
    myList* node = &head;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            node->next = l1;
            l1 = l1->next;
        }
        else {
            node->next = l2;
            l2 = l2->next;
        }
        node = node->next;
    }
    if (l1 == nullptr)
        node->next = l2;
    if (l2 == nullptr)
        node->next = l1;
    return head.next;
};
int main(void) {
    myList* node0 = new myList(0);
    myList* node1 = new myList(1);
    myList* node2 = new myList(2);
    myList* node3 = new myList(3);
    myList* node4 = new myList(1);
    myList* node5 = new myList(4);
    node0->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = nullptr;
    node4->next = node5;
    node5->next = nullptr;
    auto node = merge(node0, node4);
    while (node != nullptr) {
        cout << node->val << endl;
        node = node->next;
    }
    return 0;
}


2、反转链表


定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

力扣链接:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

第一种做法

#include<algorithm>
#include<unordered_map>
#include <iostream>
#include<vector>
using namespace std;
struct node {
 int  data;
 struct node* next;
 node(int _data) :data(_data), next(nullptr) {
 }
};
struct node* init() {
 node* head = new node(1);
 node* node1 = new node(2);
 node* node2 = new node(3);
 node* node3 = new node(4);
 node* node4 = new node(5);
 head->next = node1;
 node1->next = node2;
 node2->next = node3;
 node3->next = node4;
 node4->next = nullptr;
 return head;
}
struct node* reverse(node* head) {
 struct node* pre = new node(-1);
 struct node* temp = new node(-1);
 pre = head;
 temp = head->next;
 pre->next = nullptr; 
 struct node* cur = new node(-1);
 cur = temp;
 while (cur != nullptr) {
  temp = cur;
  cur = cur->next;
  temp->next = pre;
  pre = temp;
 }
 return pre;
}
int main(){
 auto head = init();
 head = reverse(head);
 while (head != nullptr) {
  cout << head->data << endl;
  head = head->next;
 }
 return 0;
}

第二种做法

//头插法来做,将元素开辟在栈上,这样会避免内存泄露
ListNode* ReverseList(ListNode* pHead) {
 // 头插法
 if (pHead == nullptr || pHead->next == nullptr) return pHead;
 ListNode dummyNode = ListNode(0);
 ListNode* pre = &(dummyNode);
 pre->next = pHead;
 ListNode* cur = pHead->next;
 pHead->next = nullptr;
 //pre = cur;
 ListNode* temp = nullptr;
 while (cur != nullptr) {
  temp = cur;
  cur = cur->next;
  temp->next = pre->next;
  pre->next = temp;
 }
 return dummyNode.next;
}

在面试中考察设计模式较少,一般考察的就是单例工厂、观察者或者策略这几种,如果你对这些设计模式不太了解的话可以看看下面这篇设计模式全讲解硬核文章!


3、单例模式


恶汉模式

class singlePattern {
private:
 singlePattern() {};
 static singlePattern* p;
public:
 static singlePattern* instacne();
 class CG {
 public:
  ~CG() {
   if (singlePattern::p != nullptr) {
    delete singlePattern::p;
    singlePattern::p = nullptr;
   }
  }
 };
};
singlePattern* singlePattern::p = new singlePattern();
singlePattern* singlePattern::instacne() {
 return p;
}

懒汉模式

class singlePattern {
private:
 static singlePattern* p;
 singlePattern(){}
public:
 static singlePattern* instance();
 class CG {
 public:
  ~CG() {
   if (singlePattern::p != nullptr) {
    delete singlePattern::p;
    singlePattern::p = nullptr;
   }
  }
 };
};
singlePattern* singlePattern::p = nullptr;
singlePattern* singlePattern::instance() {
 if (p == nullptr) {
  return new singlePattern();
 }
 return p;
}


4、简单工厂模式


typedef enum productType {
 TypeA,
 TypeB,
 TypeC
} productTypeTag;
class Product {
public:
 virtual void show() = 0;
 virtual ~Product() = 0;
};
class ProductA :public Product {
public:
 void show() {
  cout << "ProductA" << endl;
 }
 ~ProductA() {
  cout << "~ProductA" << endl;
 }
};
class ProductB :public Product {
public:
 void show() {
  cout << "ProductB" << endl;
 }
 ~ProductB() {
  cout << "~ProductB" << endl;
 }
};
class ProductC :public Product {
public:
 void show() {
  cout << "ProductC" << endl;
 }
 ~ProductC() {
  cout << "~ProductC" << endl;
 }
};
class Factory {
public:
 Product* createProduct(productType type) {
  switch (type) {
  case TypeA:
   return new ProductA();
  case TypeB:
   return new ProductB();
  case TypeC:
   return new ProductC();
  default:
   return nullptr;
  }
 }
};


5、快排排序


void quickSort(vector<int>& data, int low, int high) {
 //for_each(data.begin(), data.end(), [](const auto a) {cout << a << " "; });
 //cout << endl;
 if (low >= high) return;
 int key = data[low], begin = low, end = high;
 while (begin < end) {
  while (begin<end && data[end]>key) {
   end--;
  }
  if (begin < end) data[begin++] = data[end];
  while (begin<end && data[begin]<= key) {
   begin++;
  }
  if (begin < end) data[end--] = data[begin];
 }
 data[begin] = key;
 quickSort(data, low, begin - 1);
 quickSort(data, begin + 1,high);
}


6、归并排序


void mergeSort(vector<int>& data, vector<int>& copy, int begin, int end) {
 if (begin >= end) return;
 int mid = begin + (end - begin) / 2;
 int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end, index = begin;
 mergeSort(copy, data, low1, high1);
 mergeSort(copy, data, low2, high2);
 while (low1 <= high1 && low2 <= high2) {
  copy[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
 }
 while (low1 <= high1) {
  copy[index++] = data[low1++];
 }
 while (low2 <= high2) {
  copy[index++] = data[low2++];
 }
}
void mergeTest() {
 vector<int> nums = { -5,-10,6,5,12,96,1,2,3 };
 vector<int> copy(nums);
 mergeSort(nums, copy, 0, nums.size() - 1);
 nums.assign(copy.begin(), copy.end());
 for_each(nums.begin(), nums.end(), [](const auto& a) {cout << a << " "; });
}


7、设计LRU缓存


设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。

它应该支持以下操作:获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

力扣链接:https://leetcode-cn.com/problems/lru-cache-lcci

struct DoubleList {
 int key, val;
 DoubleList* pre, * next;
 DoubleList(int _key,int _val):key(_key),val(_val),pre(nullptr),next(nullptr){ }
};
class LRU {
private:
 int capacity;
 DoubleList* head, * tail;
 unordered_map<int, DoubleList*> memory;
public:
 LRU(int _capacity) {
  this->capacity = _capacity;
  head = new DoubleList(-1, -1);
  tail = new DoubleList(-1, -1);
  head->next = tail;
  tail->pre = head;
 }
 ~LRU(){
  if (head != nullptr) {
   delete head;
   head = nullptr;
  }
  if (tail != nullptr) {
   delete tail;
   tail = nullptr;
  }
  for (auto& a : memory) {
   if (a.second != nullptr) {
    delete a.second;
    a.second = nullptr;
   }
  }
 }
 void set(int _key, int _val) {
  if (memory.find(_key) != memory.end()) {
   DoubleList* node = memory[_key];
   removeNode(node);
            node->val = _val;
   pushNode(node);
   return ;
  }
  if (memory.size() == this->capacity) {// 这里很重要,也很爱错,千万记得更新memory
   int topKey = head->next->key;//取得key值,方便在后面删除
   removeNode(head->next);//移除头部的下一个
   memory.erase(topKey);//在memory中删除当前头部的值
  }
  DoubleList* node = new DoubleList(_key, _val);//新增node
  pushNode(node);//放在尾部
  memory[_key] = node;//记得在memory中添加进去
 }
 int get(int _key) {
  if (memory.find(_key) != memory.end()) {
   DoubleList* node = memory[_key];
   removeNode(node);
   pushNode(node);
   return node->val;
  }
  return - 1;
 }
 void removeNode(DoubleList* node) {
  node->pre->next = node->next;
  node->next->pre = node->pre;
 }
 void pushNode(DoubleList* node) {
  tail->pre->next = node;
  node->pre = tail->pre;
  node->next = tail;
  tail->pre = node;
 }
};



相关文章
|
2月前
|
Web App开发 JavaScript 前端开发
网页VUE纯前端在线预览编辑Office,支持doc/docx、xls/xlsx、ppt/pptx、pdf等格式
随着互联网技术的不断发展,越来越多的企业开始采用在线办公模式,微软Office Word 是最好用的文档编辑工具,然而doc、docx、xls、xlsx、ppt、pptx等格式的Office文档是无法直接在浏览器中直接打开的,如果可以实现Web在线预览编辑OffIce,肯定会还带来了更高效、便捷的办公体验,为我们的工作带来了更多可能性。
847 0
|
2月前
|
人工智能 编解码 算法
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
在本教程中,您将学习在阿里云交互式建模平台PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理,实现文本驱动的图像编辑功能单卡即可完成AIGC图片风格变化、背景变化和主体变化等功能。让我们一同开启这场旅程,为您的图像编辑添上无限可能性的翅膀吧。
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
|
10天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
180 1
|
26天前
|
机器学习/深度学习 人工智能 算法
【CVPR2024】面向StableDiffusion的编辑算法FreePromptEditing,提升图像编辑效果
近日,阿里云人工智能平台PAI与华南理工大学贾奎教授团队合作在深度学习顶级会议 CVPR2024 上发表 FPE(Free-Prompt-Editing) 算法,这是一种面向StableDiffusion的图像编辑算法。在这篇论文中,StableDiffusion可用于实现图像编辑的本质被挖掘,解释证明了基于StableDiffusion编辑的算法本质,并基于此设计了新的图像编辑算法,大幅度提升了图像编辑的效率。
|
27天前
|
机器学习/深度学习 人工智能 自然语言处理
【CVPR2024】阿里云人工智能平台PAI图像编辑算法论文入选CVPR2024
近期,阿里云人工智能平台PAI发表的图像编辑算法论文在CVPR-2024上正式亮相发表。论文成果是阿里云与华南理工大学贾奎教授领衔的团队共同研发。此次入选标志着阿里云人工智能平台PAI自主研发的图像编辑算法达到了先进水平,赢得了国际学术界的认可。在阿里云人工智能平台PAI算法团队和华南理工大学的老师学生们一同的坚持和热情下,将阿里云在图像生成与编辑领域的先进理念得以通过学术论文和会议的形式,向业界传递和展现。
|
26天前
|
算法 调度 Python
【调度算法】开放车间调度问题遗传算法
【调度算法】开放车间调度问题遗传算法
16 1
|
1月前
|
Java 数据安全/隐私保护
Java使用PDFBox开发包实现对PDF文档内容编辑与保存
Java使用PDFBox开发包实现对PDF文档内容编辑与保存
64 7
|
1月前
|
存储 算法 NoSQL
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
41 1
|
2月前
|
Python
小白入门必备!计科教授的Python精要参考PDF开放下载!
随着互联网产业的高速发展,在网络上早已积累了极其丰富的Python学习资料,任何人都可以基于这些资源,自学掌握 Python。 但实际上,网络上充斥的资源太多、太杂且不成体系,在没有足够的编程/工程经验之前,仅靠“看”线上资源自学,的确是一件非常困难的事。
|
1月前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
23 0

热门文章

最新文章