美文网首页
腾讯优图常见算法题

腾讯优图常见算法题

作者: 加油11dd23 | 来源:发表于2021-05-11 00:47 被阅读0次

最常见的：

一、 两数之和

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

二、链表反转

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* p = head;
        while (p) {
            ListNode* next = p->next;
            p->next = prev;
            prev = p;
            p = p-next;
        }
        return prev;
    }
};

#include<bits/stdc++.h>
using namespace std ;
struct ListNode{
    int value;
    ListNode* next ;
};

int main()
{
    vector<int> nums ;
    char cha ;
    ListNode* head = nullptr ;
    ListNode* pre = head ;
    while(cin>>cha)
    {
        auto p = new ListNode(0);
      
        p->value = cha - '0' ;
        pre->next = p
        p->next = NULL ;
        pre = pre-next ;
    }
    
    ListNode* p = head->next;
    pre = head; 
    while(p != NULL)
    {
        p->next = pre ;
        pre = p ;
        p = p->next ;
    }
    p = head ;
    
    while(p != NULL)
    {
        cout <<p->value;
        p = p->next;   
    }
    return - ;
}

三、环状链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

#include<bits/stdc++.h>
using namespace std ;

struct ListNode
{
    int value ;
    ListNode* next ;
};

int main()
{
     ListNode* head = new ListNode ;
     ListNode *p = head ;
     char cha ;
     while(cin>>cha)
     {
         ListNode * temp = new ListNode;
         temp->value = cha - '0';
         p->next = temp ;
         p = p->next ;
     }
     
     unordered_set<ListNode> seen ;
     p = head ;
     while(p != nullptr)
     {
         if(seen.count(p))
         {
             ans = true;
             breal
         }
         seen.push(ans);
            p = p-next ;
     }
     if (p == nullptr) 
     {
         ans
     }    
}

四、快排

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

五、合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

六、最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

#include<bits/stdc++.h>
using namespace std ;
int main()
{
    string s1 , s2 ;
    cin>>s1>>s2 ;
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    
    for ( int i = 1 ; i < s1.length(); i++)
    {
        char c1 = s1[i];
        for(int j = 1 ; j < s2.length(); j++)
        {
            char c2 = s2[j];
            if (c1 == c2)
            {
                dp[i][j] = dp[i-1][j-1]+1 ;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])l 
            }
       
        }
    }
    cout<<dp[m-1][n-1]<<endl;
    return 0 ;
}
r

七、最长上升子序列

class solution{
public:
   int lengthOfLIS(vector<int>&nums){
       int n = (int)nums.size(); 
       if (n==0){
           return 0 ;
       }

       vector<int> dp(n,0);
       for ( int i = 0 ; i < n ; i ++)
       {
           dp[i] = 1 ;
           for ( int j = 0 ; j < i ; j ++)
           {
               if (nums[j]<nums[i])
               {
                   dp[i] = max(dp[i] , dp[j]  +1)
               }
           }
       }
       return * max_element(dp.begin() , dp.end()) ;
   }
}

八、最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};


#include<bits/stdc++.h>
using namespace std ;
int main()
{
    vector<int> nums ;
    char cha ;
    
    while(cin>>cha)
    {
        nums.push_back(cha='0');
    }
    sort(nums.begin(),nums.end()) ;
    vector<int> dp(nums.size(),0) ;
    int maxValue = 0 ;
    for ( int i = 0 ; i < nums.size() ; i++)
    {
        for ( int  = 0 j < i ; j ++)
        {
            dp[i] = max(dp[j], dp[j]+nums[i]);
            maxValue = max(dp[i], max);
        }
    }
    cout <<maxValue<<endl;
    return 0 ; 
}

九、数组的第k个最大元素

class solution：{
public:
   int findKthLargest(Vector<int>& nums, int k){
       return sort(nums.begin() , nums.end() , greater<int>()), nums[k-1] ;
   }
}

十、相交链表

int main()
{
    ListNode* head = new ListNode();
    
    
    ListNode *A = headA , *B = headB ;
    
    while( A != B)
    {
        A = A != nullptr ? A->next : headB ;
        B = B != nullptr ? B->next : headA ;
    }
    return (A == nullptr) ; 
    
    
    ListNode *A = headA , * B = headB ;
    while(A != B)
    {
        A = A != nullptr ? A->next : headB ;
        b = B != nullprt ? B->next : headA ;
    }
    
    return 0 ;  
}

import java.util.HashSet;
import java.util.Set;

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hashSet = new HashSet<>();

        ListNode curNode = headA;
        while (curNode != null) {
            hashSet.add(curNode);
            curNode = curNode.next;
        }

        curNode = headB;
        while (curNode != null) {
            if(hashSet.contains(curNode)){
                return curNode;
            }
            curNode = curNode.next;
        }
        return null;
    }
}

十一、判断回文串

 class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        int n = sgood.size();
        int left = 0, right = n - 1;
        while (left < right) {
           if (sgood[left] != sgood[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

十二、二分查找

image.png 
class Solution {
  public:
  int search(vector<int>& nums, int target) {
    int pivot, left = 0, right = nums.size() - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
};

十三、 打印二叉树从右边看能看到的节点/二叉树的右视图 

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> rightmostValueAtDepth;
        int max_depth = -1;

        stack<TreeNode*> nodeStack;
        stack<int> depthStack;
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode* node = nodeStack.top();nodeStack.pop();
            int depth = depthStack.top();depthStack.pop();

            if (node != NULL) {
                // 维护二叉树的最大深度
                max_depth = max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {
                    rightmostValueAtDepth[depth] =  node -> val;
                }

                nodeStack.push(node -> left);
                nodeStack.push(node -> right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        vector<int> rightView;
        for (int depth = 0; depth <= max_depth; ++depth) {
            rightView.push_back(rightmostValueAtDepth[depth]);
        }

        return rightView;
    }
};

十四、字符串相加

image.png 
![class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back('0' + result % 10);
            add = result / 10;
            i -= 1;
            j -= 1;
        }
        // 计算完以后的答案需要翻转过来
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

十五、LRU缓存机制

image.png
image.png 
struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

十六、#### 用 Rand7() 实现 Rand10()

image.png 
class Solution {
public:
    int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;
        } while (idx > 40);
        return 1 + (idx - 1) % 10;
    }
};

十七、字符串转整数

image.png 
class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

十八、无重复字符的最长子串

image.png 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录每个字符是否出现过
        unordered_set<char> occ;
        int n = s.size();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

十九、寻找旋转数组的最小值

image.png
image.png 
class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

相关文章

  • 腾讯优图常见算法题

    最常见的： 一、 两数之和 二、链表反转 三、环状链表 四、快排 五、合并两个有序链表 六、最大子序和 七、最长上...

  • 腾讯优图常见算法题(二)

    十九、手撕快排 二十、从前序和中序中构建二叉树 二十一、数组中重复的数据 二十二、买卖股票的最佳时机 二十三、爬楼...

  • 常见算法题

    1. reserve 让数组反转倒置 2. 排序算法 面试最常考:快速排序和希尔算法 （tips） 原理：如果是想...

  • 调用腾讯优图识别名片

    钉钉端实现扫名片，调用腾讯优图识别名片信息 调用后台接口获取腾讯优图的请求的url以及请求头请求体，appid，鉴...

  • 2021年腾讯校招季，各事业部算法题 TOP 10，你能手撕几道

    前言 腾讯校招开始了，不知道大家投了吗？这里为大家整理了腾讯6大事业群校招常问算法题TOP 10 算法题榜，希望能...

  • autojs人像变换

    牙叔教程 简单易懂 产品简介 腾讯云神图·人像变换（Face Transformation）基于腾讯优图领先的人脸...

  • 程序员进阶之算法练习（三十四）LeetCode专场

    前言 LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题：1、2、3题都是Medium的...

  • Python 常见算法题

    打印菱形 打印直角三角 打印等边三角形 打印100以内的斐波那契数列 求10万内的所有素数 猴子吃桃问题 猴子第一...

  • 面试常见算法题

    1.对象转换为数组 2.统计一个字符串出现最多的字母 3.找出下列正数组的最大差值 4.获取数组中最大或者最小值 ...

  • php常见算法题

网友评论

      本文标题：腾讯优图常见算法题

      本文链接：https://www.haomeiwen.com/subject/npqwdltx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|腾讯优图常见算法题|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！