面经准备-旷视

ゞ浴缸里的玫瑰 2021-12-15 14:51 212阅读 0赞

一. 字符的全排列

对一个数组进行全排列，无重复元素，定义递归函数为前i-1个元素全排列已经排好， 将第i个元素以及后面的元素进行全排列。过程为从第i个元素到最后一个元素轮流放在第i个位置上， 然后对第i+1个元素以及后续元素进行全排列。

class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>> res;
            permutehelper(nums, 0, res);
            return res;
        }
    
    private:
        void permutehelper(vector<int>&nums, int l, vector<vector<int>> &res){
            if (l == nums.size()) {
                res.push_back(nums);}       
           for (int i = l; i < nums.size(); i++) {
                    swap(nums[l], nums[i]);
                    permutehelper(nums, l+1, res);
                    swap(nums[i], nums[l]);
                }
       
        }  
    
    };

二. 大整数的乘法 leetcode43 MultiStrings

大整数的乘法分为两步， 第一步将第一个大整数乘以第二个大bit的每个位。 注意后面要补0， 第二个步将第一步的中间结果实现一个大数加法。

第一个trick。实现的时候用一个vector<int> 最后再统一处理进位和转成字符串。

class Solution {
    public:
        string multiply(string num1, string num2) {
            if (num1 == "0" || num2 == "0") return "0";
            int len_1 = num1.size();
            int len_2 = num2.size();
            vector<string> holdMul;
            for (int i=0; i<len_2; i++){
                string tmp= "";
                tmp = num2[len_2 - 1 -i];
                string fillZero(i, '0');
                holdMul.push_back(mulOnebit(num1, tmp) + fillZero);
            } 
            string sum=holdMul[0];
            for  (int j=1; j< holdMul.size(); j++) {
                sum = addStr(sum, holdMul[j]);
                
            }
            return sum;      
        }
        
    private:  
        string addStr(string a, string b) {
            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            int i = 0;
            int j = 0;
            vector<int> result;
            while(i< a.size() && j < b.size()) {
               result.push_back((a[i++] - '0')  +  (b[j++] - '0'));         
            }
            while(i < a.size()) result.push_back(a[i++] - '0');
            while(j < b.size()) result.push_back(b[j++] - '0');
            string re =  convertNumber(result);
            return re;
            
        }
        string mulOnebit(string a, string b) {
            vector<int> result;
            for(int i=a.size() -1; i >= 0; i--){
                result.push_back((a[i] - '0') * (b[0] - '0'));
                cout << result.back()<< " ";
            }
            string re = convertNumber(result);
            return re;
            
        }
        string convertNumber(vector<int> input) {
    
            int len = input.size();
            for(int i = 0; i < len; i++) {           
                if (input[i] >= 10) {
                    if (i < len - 1){
                    input[i + 1] += (input[i] / 10); 
                    }
                    else {
                       input.push_back(input[i] / 10);
                    }
                    input[i] %= 10;
                }           
            }
    
            reverse(input.begin(), input.end());
            string result(input.size(), '0');
            for (int i=0; i< result.size(); i++) {
                result[i] += input[i];
            }
                
            return result;
            
        }
        
    };

三. 完全二叉树如何高效插入

[https://blog.csdn.net/fangjian1204/article/details/39179343][https_blog.csdn.net_fangjian1204_article_details_39179343]

[https://www.cnblogs.com/qieerbushejinshikelou/p/3917019.html][https_www.cnblogs.com_qieerbushejinshikelou_p_3917019.html]

（1） O(n)的解法，采用一个queue层次遍历二叉树，取出来最右边的node插入

(2)  O(logn \* logn)的解法，递归。判断左右子树的高度，若左子树h大于右子树的h,则在左子树里面找，否则在右子树里面找

TreeNode* getLastNode(TreeNode* root) {
               If (root == NULL || root ->left == NULL)  return root;
                int lh = 0;
                TreeNode* p = root;
                while(p) {
                   lh++;
                   p = p-> left;
              }
                Int rh = 0
                 p = root;
                 while(p) {
                   rh++;
                   p = p->right;
               }
    
               If (lh > rh) return getLastNode(root->left);
               else return getLastNode(root->right);
    }

(3) O(logn)的方法

先统计树的深度，从右子树开始搜，一直向左搜到叶子结点，

如果右子树的深度 < 全树深，则回到左子树上搜索

否则如果搜到叶子结点对应的根结点没有右孩子， 则返回该叶子结点。

如果搜到的叶子结点对应的根结点有有孩子，则在右子树搜索。

TreeNode* getLastNode(TreeNode* root) {
    
              If (root ==NULL || root->left == NULL) return root;
              int height =0;
              TreeNode*p = root;
              while(p) {
                  height++;
                  p = p->next; 
             }
             int level = 0;
             while(root) {
                     level++;
                     If (level == height) break;  // 右子树为空的情况。
                    If (root->right) {
                    Int tmp_len = level;
                     p = root;
                    TreeNode *leaf = root->right;
                          while(leaf) {
                                 tmp_len++;
                                 p = leaf;
                                leaf = leaf ->left;
                          }
                         If (tmp_len < height)  root = root->left;
                         else if (p->right == NULL || p->right == leaf) return leaf;
                         else root = root->right;
    
                  }
                  else root = root->left；
                 
             }
             return root;
    }

四. 设计LRU

五. 在几亿个大小的数组中选出最大的k个数字

六. 单链表排序 leetcode 146

class Solution {
    public:// 归并排序 找中点
        ListNode* sortList(ListNode* head) {
            if(head == NULL || head->next == NULL) return head;
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast->next && fast->next->next) {
                fast = fast->next->next;
                slow = slow->next;
            }
            
            fast = slow->next;
            if(slow->next)
            slow->next = NULL;
            ListNode* l1 = sortList(head);
            ListNode* l2 = sortList(fast);
            return merge(l1, l2);
        }
    private: 
        ListNode* merge(ListNode* p1, ListNode* p2) {
            ListNode* p0 = new ListNode(0);
            if(p1 == NULL) return p2;
            if(p2 == NULL) return p1;
            ListNode* p = p0;
            while(p1 || p2) {
                int temp1 = (p1 == NULL ? INT_MAX : p1->val);
                int temp2 = (p2 == NULL ? INT_MAX : p2->val);
                if(temp1 <= temp2) {
                    p->next = p1;
                    p1 = p1->next;
                    p = p->next;
                } else {
                    p->next = p2;
                    p2 = p2->next;
                    p = p->next;
                }
            }
            /*if(p1){
                p->next = p1;
            }
            if(p2){
                p->next = p2;
            }*/
            return p0->next;
        }
    };

七. 合并两个有序链表

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (l1 == NULL) return l2;
            if (l2 == NULL) return l1;
            ListNode * head = new ListNode(0);
            ListNode * p = head;
            while (l1 != NULL && l2 != NULL) {
                if (l1->val <= l2->val) {
                    p->next = l1;
                    l1 = l1->next;
                }
                else {
                    p->next = l2;
                    l2 = l2->next;
                }
                p = p->next;
            }
            if (l1) {
                p->next = l1;
            }
            if (l2) {
                p->next = l2;
            }
            ListNode * tmp = head->next;
            delete head;
            return tmp;
        }
    };

八. 青蛙跳

问跳到第n个台阶有几种跳法

每次跳一步或者两步

lass Solution {
    public:
        int jumpFloor(int number) {
            if (number == 0) return 0;
            if (number == 1) return 1;
            if (number == 2) return 2;
            int pre_1 = 1;
            int pre_2 = 2;
            int re;
            for (int i=3; i<=number; i++){
                re = pre_1 + pre_2;
                pre_1 = pre_2;
                pre_2 = re;
            }
            return re;
        }
    };

每次可以跳n步

class Solution {
    public:
        int jumpFloorII(int number) {
    
             vector<int> record(number+1, 0);
             record[0] =1;
             for (int i = 1; i<= number; i++){
                 for(int j=0; j< i; j++)
                     record[i] += record[j];
             }
                
            return record[number];    
        }
    };

九. 输出矩阵的外围元素，类似剑指offer的顺时针打印矩阵

class Solution {
    public:
        vector<int> printMatrix(vector<vector<int> > matrix) {
            vector<int> result;
            int m = matrix.size();
            if (m==0) return result;
            int n = matrix[0].size();
            if (n==0) return result;
            int start=0;
            while(start < m/2.0 && start < n/2.0) {
               printCircle(matrix, start, m, n, result);
               start++;
            }
            return result;
        }
    // 先判断问题，拆成print Circle, 
    // 确定起点和终点的变化（看坐标，起点和终点的坐标和相同）
    // 四个顺序，除了第一个，剩下的都是有条件的，并且要执行后一个必须要满足前面所有的条件。
    private:
        void printCircle(vector<vector<int>> matrix, int start, int m, int n, vector<int> & result){
             int end_x = n - 1 - start;
             int end_y = m - 1 - start;
             // 从左到右
             for (int i = start; i <= end_x; i++)
             result.push_back(matrix[start][i]);
             // 从上到下
             if (end_y > start) {
                 for (int i = start+1; i <= end_y; i++)
                     result.push_back(matrix[i][end_x]);
             }
             // 从右到左
             if (end_x - 1 >= start && end_y > start) {
                 for (int i= end_x-1; i>=start; i--)
                     result.push_back(matrix[end_y][i]);
             }
             // 从下到上
            if (end_y - 1 > start && end_x -1 >= start) {
                for (int i= end_y - 1; i>= start+1; i--)
                    result.push_back(matrix[i][start]);
            }
        }
    };

大数组里某个数第一次出现的位置

八. 二叉树的前序，中序和后序序列的转换算法，有实现限制

九. 最短路径

十. 两行扫雷，给出第二行，判断第一行是不是有雷

十一. 公共子树的最进 O(h)

十二. 一维的max\_pooling

十三. 生成矩阵

转载于:https://www.cnblogs.com/cookcoder-mr/p/11129707.html

[https_blog.csdn.net_fangjian1204_article_details_39179343]: https://blog.csdn.net/fangjian1204/article/details/39179343
[https_www.cnblogs.com_qieerbushejinshikelou_p_3917019.html]: https://www.cnblogs.com/qieerbushejinshikelou/p/3917019.html