美文网首页“菜鸟”程序员学习笔记
leetcode 中等题(部分一)

leetcode 中等题(部分一)

作者: 认真学计算机 | 来源:发表于2016-10-11 10:12 被阅读124次

    1、随机数
    #include<time.h>
    srand((int)time(0));
    rand()%x;

    2、数值题
    A:Single Number 类:
    题型1)给一个数组,里面有两个元素只出现了一次,而其他所有元素都出现了两次,找到这两个元素,这个主要用位的方法:

        vector<int> singleNumber(vector<int>& nums) {
            // 首先所有的元素进行异或,将会得到这两个数的异或值
            int num=nums[0];
            for(int i=1;i<nums.size();i++){
                num=num^nums[i];
            }
            // 找到异或得到的元素的最后一个1对应的值
            int rest = num&(~num+1);
            int left=0,right=0;
            for(int i=0;i<nums.size();i++){
                if((nums[i]&rest)==rest) left=left^nums[i];
                else if((nums[i]&rest)==0) right=right^nums[i];
            }
            return vector<int>{left,right};
        }
    

    B:Count Numbers with Unique Digits :
    Given a non-negative integer n, count all numbers with uniques digits, x, where 0 ≤ x < 10^n.
    这个题说的是给你一个n,指代n位的整数,求整数中,所有数字只出现一次的整数的数目。
    我在想,这个地方是不是应该反过来查:

    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {   
            if(n == 0) return 1;
            int count = 9, ret = 9;
            // In each iteration, try adding 0 - 9 to the end of number
            for(int i = 2; i <= n; ++i) {
                // Advoid repeating digits. f(k) = f(k - 1) * (10 - k - 1)
                count *= 11 - i;
                ret += count;
            }
            // Add 0
            return ret + 1;
        }
    };
    

    C:Integer Break
    (如果可以,还是有时间补补数学原理)
    这个题是说给一个整数n,然后将它分裂成至少N个正整数(N>2),然后将这N个正整数乘起来,返回正整数积最大的值。
    这里,数学原因我不知道,但是我只知道最多只能有2个2,也就是说5以下,尽可能考虑2,;5以上,尽可能考虑3,如果余数为1,变为2*2;

    class Solution {
    public:
        int integerBreak(int n) {
            // 这里,数学原因我不知道,但是我只知道最多只能有2个2,也就是说5以下,尽可能考虑2,;5以上,尽可能考虑3,如果余数为1,变为2*2;
            if(n==1||n==2) return 1;
            if(n<5) return 2*(n-2);
            else{
                if(n%3==1){
                    int res = 4;
                    res = res * pow(3,(n-4)/3);
                    return res;
                }else if(n%3==2){
                    return 2*pow(3,(n-2)/3);
                }else{
                    return pow(3,n/3);
                }
            }
        }
    };
    

    D:Divide Two Integers
    (在不用乘、除和取模操作的情况下,进行除法,如果溢出,返回INT_MAX)
    (可以用加减和左移右移运算符)
    首先考虑单例的情况,divisor 为 0 的时候,返回 INT_MAX,而 dividend 为 0 的时候,返回 0,而 divisor 为 1 的时候,返回 dividend。
    【abs() 主要用于对求整数的绝对值,在 "stdlib.h" 头文件里】
    【fabs() 主要是求精度要求更高的 double,float 型的绝对值,在 <cmath> 头文件里】
    【exp 主要就是计算 e 的多少次方】
    【默认 log() 是取自然对数为底 即 ln】
    【直接用换底公式 写个简单的表达式就完成了 例如: log2 x 写成 log(x)/log(2)】

     double x1 = log(fabs(dividend));
     double x2 = log(fabs(divisor));
     long long res = double(exp(x1-x2));
    
    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(dividend==0) return 0;
            else if (divisor==0&& dividend>0) return INT_MAX;
            else if (divisor==0&& dividend<0) return INT_MIN;
            else if (divisor==1) return dividend;
            
            double x1 = log(fabs(dividend));
            double x2 = log(fabs(divisor));
            double res = exp(x1-x2);
            
            bool ne = (dividend>0)^(divisor>0);
            if(ne==false){
                if(res<INT_MAX) return res;
                else return INT_MAX;
            }else if(ne==true){
                if(-res>INT_MIN) return -res;
                else return INT_MIN;
            } 
            return 0;
        }
    };
    

    E:Fraction to Recurring Decimal
    [ 给两个数,分别代表分子和分母,然后,以字符串的形式返回分数的小数形式 ]
    [ 如果分数部分是循环的,用括号的形式将重复的部分关起来 ]
    举例:

    Given numerator = 1, denominator = 2, return "0.5".
    Given numerator = 2, denominator = 1, return "2".
    Given numerator = 2, denominator = 3, return "0.(6)".
    (我原来的方法是把小数部分转换为字符串保存下来,然后再进行查找,重点在于这个查找方式)

    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
        // 分别判断分子分母是否为0,
            if(numerator==0) return "0";   // 分子为0,那么直接返回 0
            if(denominator==0) return "";     // 分母为0,那么直接返回 ""
            
            string res="";
            unordered_map<long,int> map;
            if((numerator>0)^(denominator>0)) res+='-';    // 根据正负进行符号判别
            long num1 = abs((long)numerator/(long)denominator);
            res= res+ to_string(num1);
            long num2 = abs((long)numerator%(long)denominator);
            if(num2==0) return res;  // 如果没有小数,那么就直接返回。
            res = res +".";         // 在有小数的情况下,加上点。
            // ---------------------------------------------------------------
            while(num2){        // 这里对应的是余数
                map[num2] = res.size();
                num2=num2*10;
                num1 = abs((long)num2 / (long)denominator);
                res= res+ to_string(num1);
                num2 = abs((long)num2 % (long)denominator);
                if(map.find(num2)!=map.end()){
                    res.insert(map[num2],"(");
                    res = res+")";
                    break;
                }
            }
            return res;
        }
    };
    

    F:Maximal Square

    // ------------------------用状态矩阵-------------------------
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            if(matrix.size()==0) return 0;
    
            int row_num = matrix.size();
            int col_num = matrix[0].size();
            
            int max_value=0;
     // 构建一个状态矩阵
            vector<int> record(col_num,0);
    
            // 初始化状态矩阵
            for(int i=0;i<col_num;i++) {
    record[i]=matrix[0][i]=='0'?0:1; 
    max_value=max(max_value,matrix[0][i]-'0');   // 找到最大值
     };
            
     //  调整状态矩阵
            for(int i=1;i<row_num;i++){
                int tmp =record[0];
                record[0]= matrix[i][0]-'0';
                for(int j=1;j<col_num;j++){
                    int mmm = record[j];
                    if(matrix[i][j]=='1'){
                        record[j]=min(min(record[j],record[j-1]),tmp)+1;   // 就是斜对角、左边、上边三个数的最小值。
                        max_value=max(max_value,record[j]);
                    }else record[j]=0;
                    tmp=mmm;
                }
            }
            return max_value*max_value;
        }
    };
    
    // 用真正的矩阵
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int row_num = matrix.size();
            if(row_num==0) return 0;
            int col_num = matrix[0].size();
            
            int sum=0;
            for(int i=0;i<col_num;i++){
                int num = matrix[0][i]-'0';
                sum = sum>num?sum:num;
            }
            
            for(int j=0;j<row_num;j++){
                int num = matrix[j][0]-'0';
                sum = sum>num?sum:num;
            } 
    
            for(int i=1;i<row_num;i++)
                for(int j=1;j<col_num;j++){
                    if(matrix[i][j]=='1'){
                        int num = min(min(matrix[i-1][j]-'0',matrix[i][j-1]-'0'),matrix[i-1][j-1]-'0')+1;
                        matrix[i][j] = num +'0';
                        sum = sum>num?sum:num;
                    } 
                }
            return sum*sum;
        }
    };
    

    3、链表类题
    A:Linked List Random Node(随机数题目)
    Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
    Follow up:
    What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

    B:Reverse Linked List ii(链表逆转)
    (Reverse a linked list from position m to n. Do it in-place and in one-pass)
    For example:
    Given 1->2->3->4->5->NULL, m=2 and n=4
    return 1->4->3->2->5->NULL.

        ListNode* reverseBetween(ListNode* head, int m, int n) {
            int count=0;
            ListNode* left = new ListNode(-1); //我还是需要养成一个好习惯,建立一个新的节点
            left->next = head;
            for(;count<m-1;count++) left=left->next;
            ListNode* cur = left->next, * back_up = left->next;
      // left 为逆转链表前的那个节点,back_up 为逆转链表的最后一个节点。
      // 这个是链表的逆转,逆转完了后,cur 为逆转完毕后的链表的下一个节点,before 为逆转之后的头节点。
            ListNode* next=nullptr,*before=nullptr;
            for(;count<n;count++){
                next = cur->next;
                cur->next = before;
                before=cur;
                cur=next;
            }
            left->next = before; back_up->next = cur;
            return m==1?before:head;
        }
    

    C:Remove Duplicates from Sorted List ii
    (给一个已排序的链表,删除所有有重复数字的节点,留下只出现过一次的数字的节点)

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            // 如果一旦需要删除掉一个链表的节点,必须重新设定节点。
            if(!head) return nullptr; // 节点不存在
            // 声明一个头节点,并设头节点的指针。
            ListNode begin(1);
            ListNode* start = &begin;
            // 进入循环体。
            while(1){
                if(head&&head->next&&head->val==head->next->val){
                    while(head&&head->next&&head->val==head->next->val) head = head->next;
                    if(!head->next) return begin.next;
                    else head=head->next;
                }else if(!head->next){   // 只有一个节点
                    start->next = head;
                    start=start->next;
                    start->next =nullptr;
                    return begin.next;  
                }else if(head->next){    // 有连续两个节点,但是两个节点的值不相等。
                    start->next = head;
                    start= start->next;
                    head = head->next;
                    start->next =nullptr;
                }
            }
            return begin.next;
        }
    };
    

    4、数组题
    A、Product of Array Except Self
    (这个轮子比较重要,因为,直接抽象为入口是一个数组,返回的数组中每一个元素是其他元素的乘积,但是不能用除法)
    For example, given [1,2,3,4], return [24,12,8,6].
    虽然要求是用常数的空间复杂度,其实这里也不会那么苛刻,可以用一个满足返回值需求的数组

    vector<int> productExceptSelf(vector<int>& nums){
            int size = nums.size();
            vector<int> vec(size,1);
            // 每个数左边的乘积都有了。
            for(int i=1;i<size;i++) vec[i]=nums[i-1]*vec[i-1];
            // 接着计算右边的乘积。
            int right = nums[size-1];
            for(int i=size-2;i>=0;i--){
                  vec[i] = vec[i]*right;
                  right=right*nums[i];
            }
            return vec;
    }
    

    Shuffle an Array
    [ 将数组进行漂移,返回数组任何一个可能的排列,这个叫做数组的漂移 ]
    ( 可见,现在的一个出题的趋势,就是走随机数,通过一定程度上的模拟随机)
    STL中的函数random_shuffle()用来对一个元素序列进行重新排序(随机的)

    ps:这个函数不仅可以用于 vector,还可以用于 数组:

    template<class RandomAccessIterator>  
       void random_shuffle(  
          RandomAccessIterator _First, //指向序列首元素的迭代器  
          RandomAccessIterator _Last  //指向序列最后一个元素的下一个位置的迭代器  
       );  
    

    C、对数组进行全排列【特别重要】
    (这个部分非常重要,因为全排列的方式有很多种,需要找到最有效率的方式)
    注意1:在进行交换之前,先进行全排列。这样方便过滤掉重复的数字。
    注意2:将结果集放在最外面,方便随时调用。
    注意3:设置数组的交换标志位。

    class Solution {
    private:
        vector<vector<int>> res; //  将结果集放在最外面,方便随时调用
    public:
        void help(vector<int>& nums,int left){  // 在形参中设置交换的标志位
            if(left==nums.size()){ 
                res.push_back(nums);
                return;
            }
            for(int i=left;i<nums.size();i++){ 
                if(i!=left&&nums[i]==nums[left]) continue;  // 跳过重复的值
                swap(nums[i],nums[left]);
                help(nums,left+1);
            }
            //  下面这个部分最为重要,因为需要逐步恢复标准的次序。
            int temp_last = nums[left];
            for (int i = left + 1; i < nums.size(); i++) {
                nums[i-1] = nums[i];
            }
            nums[nums.size()-1] = temp_last;
        }
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            if(nums.size()==0) return res;
            sort(nums.begin(),nums.end());  // 在进行交换之前,先进行全排列,这样方便过滤掉重复的数字
            help(nums,0);
            return res;
        }
    };
    

    D、Top K Frequent Elements(这个题目特别重要)
    (返回元素频率排到前K个的元素)
    这里的时间复杂度最快的是用到了O(n),因为不管是在unordered_map的统计过程中,还是在拟快排找top k 的过程中,时间复杂度都只是O(n)

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            if(k==nums.size()) return nums;
            
             // 算法复杂度小于O(nlogn) 也就意味着不能用排序,但其实排序也没什么用。
            unordered_map<int,int> record;
            for(int i=0;i<nums.size();i++) record[nums[i]]++;
            
            // 用 pair对将统计数据反向存起来
            vector<pair<int,int>> vec;
            for(auto p: record) vec.push_back(make_pair(p.second,p.first));
           
            if(k==vec.size()){
                vector<int> res;
                for(int i=0;i<k;i++){
                    res.push_back(vec[i].second);
                }
                return res;
            }
           // 确定最合适的位置
            int other = vec.size()-k; // left的下标一定得是在other这个位置
    
    // 用拟快排的思路去找 top k
            int left=0,right = vec.size()-1;
            while(1){
                int left_ori = left, right_ori = right;
                int mid = left+(right-left)/2;
                swap(vec[mid],vec[left]);
                pair<int,int> mid_value = vec[left];
                while(left<right){
                    while(left<right && vec[right].first>=mid_value.first) right--;
                    if(left<right) vec[left] = vec[right];
                    while(left<right && vec[left].first<=mid_value.first) left++;
                    if(left<right) vec[right] = vec[left];
                }
                vec[left] = mid_value;
                if(left==other){
                    vector<int> res;
                    for(int i=left;i<vec.size();i++){
                        res.push_back(vec[i].second);
                    }
                    return res;
                }
              
     // 这个地方最容易出问题。
                if(left<other){
                    left = left+1;
                    right = right_ori;  
                } 
                if(left>other){
                    left = left_ori;
                    right = right-1;
                } 
            }
        }
    };
    

    另附1:STL 方法:

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> freq;
            for (int num : nums) {
                ++freq[num];
            }
            vector<pair<int, int>> pa;
            for (auto p : freq) {
                pa.push_back(make_pair(-p.second, p.first));
            }
            nth_element(pa.begin(), pa.begin() + k, pa.end());  // 其实在nth_element中用的也是拟快排
            vector<int> res;
            for (int i = 0; i != k; ++i) {
                res.push_back(pa[i].second);
            }
            return res;
        }
    };
    

    Tip:STL中的nth_element()方法的使用 通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置(从0开始,其位置是下标为 n的元素),并且比这个元素小的元素都排在这个元素之前,比这个元素大的元素都排在这个元素之后,但不能保证他们是有序的

    另附2:STL 大顶堆的方法:
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) 
        {
            vector<int> v;
            unordered_map<int, int> count_map;
            for(auto n: nums) count_map[n]++;
            priority_queue<pair<int, int>> maxHeap;
            for(auto& pair: count_map)  maxHeap.emplace(pair.second, pair.first);
            while(k--)
            {
                v.push_back(maxHeap.top().second);
                maxHeap.pop();
            }
            return v;
        }
    };
    

    标准做法:

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) 
        {
            vector<int> v;
            unordered_map<int, int> count_map;
            for(auto n: nums) count_map[n]++;
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> minHeap;
            for(auto& pair: count_map) 
            {
                minHeap.emplace(pair.second, pair.first);
                if(minHeap.size() > k) minHeap.pop();
            }
            while(k--)
            {
                v.push_back(minHeap.top().second);
                minHeap.pop();
            }
            return v;
        }
    };
    

    链接:https://discuss.leetcode.com/topic/54560/five-efficient-solutions-in-c-well-explained

    E:Missing Number:
    (这个题之所以拿出来,是因为需要做原地归位交换)

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            // 这一轮走完,一定能把合适的数放在合适的位置,不合适的数,放在空缺的位置上。
            for(int i=0;i<nums.size();){
                if(nums[i]!=i&&nums[i]<nums.size()) swap(nums[nums[i]],nums[i]);
                else i++;
            }
            // 找到空缺位置上的数,也就是缺失的数
            for(int i=0;i<nums.size();i++){
                if(nums[i]>=nums.size()) return i;
            }
            // 如果都没有缺失,那么缺失的就是下一个数。
            return nums.size();
        }
    };
    

    F:Maximum Product of Word Lengths
    (这里面用到了字符压缩,通过对字符串进行预处理,来判别两个字符串中有没有共同的字母)。方法是按位进行处理):

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int max_length=0;
            vector<pair<string,int>> vec;
     // 大小是绝对够的,所以用按位或的方式。
            for(int i=0;i<words.size();i++){
                int tmp =0;
                for(auto c:words[i]){
                    int num = 2<<(c-'a');
                    tmp = (tmp|num);
                } 
                vec.push_back(make_pair(words[i],tmp));
            }
            for(int i=0;i<vec.size();i++){
                for(int j=i+1;j<vec.size();j++)
                    if(!(vec[i].second&vec[j].second)){
                        int length = vec[i].first.size()*vec[j].first.size();
                        max_length = max_length>length?max_length:length;
                    } 
            }
            return max_length;
        }
    };
    

    G:Kth Largest Element in an Array(在一个无序数组中,找到排序情况下第k大的元素)[这个轮子比较重要]

     int findKthLargest(vector<int>& nums, int k) {
            // 如果是第K大,那么肯定是在排好序的第K个下标位置,所以:k = nums.size()-k;
            // ==================================
            // 这个轮子就是如何用拟快排进行排序的,STL方法
            k=nums.size()-k;
            nth_element(nums.begin(),nums.begin()+k,nums.end());
            return nums[k];
            
            // ==================================
            priority_queue 堆排的效率要低很多
            priority_queue<int> p;
            for(int i=0;i<nums.size();i++) p.push(nums[i]);
            for(int i=0;i<k-1;i++) p.pop();
            return p.top();'
            
            // ==================================
            // 自己造轮子,实现一个nth_element();
            k=nums.size()-k;
            int left=0,right=nums.size()-1;
            int mid = left+(right-left)/2;
            int mid_value = nums[mid];
            swap(nums[mid],nums[left]); 
            while(1){
                int mid = left+(right-left)/2;
                int mid_value = nums[mid];
                swap(nums[mid],nums[left]); 
                int left_ori=left,right_ori=right;
                while(left<right){
                    while(left<right&&nums[right]>=mid_value) right--;
                    if(left<right) nums[left] = nums[right];
                    while(left<right&&nums[left]<=mid_value) left++;
                    if(left<right) nums[right] = nums[left];            
                }
                nums[left]=mid_value;
                if(left==k) return nums[left];
                else if(left<k){
                    left=left+1;
                    right =right_ori; 
                }else if(left>k){
                    right =right-1;
                    left = left_ori;
                }
            }
            return 0;
        }
    

    Tip:
    priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
    优先队列是队列的一种,不过它可以按照自定义的一种方式(数据的优先级)来对队列中的数据进行动态的排序,每次的 push 和 pop 操作,队列都会动态的调整,以达到我们预期的方式来存储。

    例如:我们常用的操作就是对数据排序,优先队列默认的是数据大的优先级高,所以我们无论按照什么顺序 push 一堆数,最终在队列里总是 top 出最大的元素。

    priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数: priority_queue<Type, Container, Functional>
    其中 Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。
    Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list.
    STL 里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,
    优先队列就是大顶堆,队头元素最大。

    用法:示例:将元素5,3,2,4,6依次push到优先队列中,print其输出。

    1. 标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。(大顶堆)
      priority_queue<int> pq;

    2. 数据越小,优先级越高(小顶堆)
      priority_queue<int, vector<int>, greater<int> >pq;
      http://www.cnblogs.com/flyoung2008/articles/2136485.html

    H:Rotate Image(nn;nm)**
    [ 给你一个 n*n 的矩阵,将它顺时针旋转90度;]
    感觉就是,只有n*n的矩阵,可以在原地进行旋转,但是n*m的矩阵,则必须用另一个矩阵进行置换。

    void rotate(vector<vector<int>>& matrix) {
                int num = matrix.size();
                //方法就是先沿着中心线进行对折再沿着反水平线进行对折
                for(int i=0;i<num;i++) for(int j=0;j<num/2;j++) swap(matrix[i][j],matrix[i][num-j-1]);
                for(int i=0;i<num;i++) for(int j=0;j<num-i;j++) swap(matrix[i][j],matrix[num-1-j][num-1-i]);
        }
    [ 给你一个 n*m 的矩阵,将它顺时针旋转90度;]
    ----------------------------------------------------
    m*n 的矩阵顺时针旋转90度
    
        int b[3][4];  
        int m=4,n=3;  // a 为4*3的原数据矩阵
        for(int i=0;i<n;i++){  
            for(int j=0;j<m;j++){  
               b[j][n-1-i]=a[i][j];  
            }  
        }  
    
    m*n 的矩阵逆时针旋转90度
        
        int b[3][4];  
        int m=4,n=3;  
        for(int i=0;i<n;i++){  
            for(int j=0;j<m;j++){  
               b[m-1-j][j]=a[i][j];  
            }  
        }  
    
    m*n 的矩阵旋转180度
        
        int b[4][3];  
        int m=3,n=4;  
        for(int i=0;i<n;i++){  
            for(int j=0;j<m;j++){  
               b[n-i-1][m-j-1]=a[i][j];  
            }  
        }  
    

    I 蛇形矩阵(考了若干次,还是需要再写一遍),这里有两种蛇形矩阵,一种是正方形,一种是长方形
    A):正方形蛇形:

    vector<vector<int>> generateMatrix(int n) {
            // 腾讯笔试的时候,是要求按蛇形矩阵的形式进行输出,但是你要输出,也一定要先构建出这样一个对应的矩阵
            vector<vector<int>> vec(n,vector<int>(n));
            // 定义蛇形矩阵的层数
            int level =1;
            // 按圈顺时针对矩阵进行赋值
            int count =1;
            while(level<=n/2){
                // 从level-1 到 n-1-level 水平
                for(int i=level-1;i<n-level;i++){
                        vec[level-1][i]=count;
                        count++;
                }         
                
       // 从level-1 到 n-1-level 竖直
                for(int i=level-1;i<n-level;i++){
                        vec[i][n-level]=count;
                        count++;
                }        
              
                // 从n-level 到 level 逆向水平
                for(int i=n-level;i>level-1;i--){
                        vec[n-level][i]=count;
                        count++;
                } 
             
                // 从n-level 到 level 逆向竖直
                for(int i=n-level;i>level-1;i--){
                        vec[i][level-1]=count;
                        count++;
                }
                level++;
            }
            
            // 如果是奇数,则填补中间的那个数
            if(n%2==1) vec[level-1][level-1]=count;
            
            return vec;
        }
    

    B):长方形蛇形(长方形受限于边短的那个长度,轮转完了后,需要对 第count 行(如果行数 m 大于列数)的 [count,m-count-1] 或者对第 count 列(如果列数 n 大于行数)的 [count,n-count-1] 进行填充。

    J Permutations

    (给一个数组,返回它的全排列:方法,深搜+回溯)
    class Solution {
    public:
        vector<vector<int>> res;
        int size=0;
        void help(vector<int>& nums, vector<int>& vec, int n,int k){
            if(k==nums.size()){
                res.push_back(vec);
                return;
            }
            for(int i=0;i<nums.size();i++){
                if(find(vec.begin(),vec.end(),nums[i])==vec.end()){
                    vec.push_back(nums[i]);
                    help(nums,vec,size,k+1);
                    vec.pop_back();
                }
            }
        }
        vector<vector<int>> permute(vector<int>& nums) {
            if(nums.size()==1){
                res.push_back(nums);
                return res;
            }
            // 两种方法吧,第一种是用深搜,第二种是用交换,但是交换和深搜本身差别不大,所以统一用深搜。
            vector<int> tmp;
            size = nums.size();
            for(int i=0;i<nums.size();i++){
                tmp.push_back(nums[i]);
                help(nums,tmp,size,1);
                tmp.pop_back();
            }
            return res;
        }
    };
    

    K:Remove Duplicates from Sorted Array II
    (从排序数组中,移除出现超过3次的数字,并返回符合要求的数组的长度)
    不管是出现几次,left 一定得是最直接的判断方式,不能和 left-2 对应的数字相同。

    class Solution {
    public:
        int removeDuplicates(vector<int>& nums) {
            //总而言之,只要不出现,nums[i]==nums[i-2]的情况就是符合要求的
            int lens = nums.size();
            if(lens<3) return lens;
            int left=2;
            for(int i=2;i<lens;i++){
                if(nums[i]!=nums[left-2]){
                    nums[left]=nums[i];
                    left++;
                }
            }
            return left;
        }
    };
    

    L:3Sum Closest[方法很重要]
    (给一个n个整数的数组,在里面找3个数,使得3个数的和最靠近所给的目标值。返回这三个数的和)
    // 需要先读懂题,也就是说,这里并没有说,需要连续的三个数
    // 三个数的动态变化时,先固定一个,然后另外两个进行左右夹逼

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
        // 实现排序
        sort(nums.begin(), nums.end()); 
        int res=nums[0]+nums[1]+nums[nums.size()-1]-target; // 这是一个参考值
        // 下面是实现夹逼的方法
        for (unsigned int i=0; i<nums.size(); i++) {
            int l = i+1, r = nums.size()-1;
            while (l<r) {
                int s = (nums[i]+nums[l]+nums[r])-target;
                if (s>0){  //  当s 大于0 时,得向0靠拢
                    if(abs(res)>s) res=s;
                    r--;
                } 
                else if (s<0){  //  当s 小于0 时,得向0靠拢
                    if(abs(res)>abs(s)) res=s;
                    l++;
                } 
                else {//0 和 -1 或者 1 都会到这里来
                    if(s==0) return target;
                }
            }
        }
        return target+res;
        }
    };
    

    M Combination Sum ii
    [给一个候选的数字集合C和一个目标值,找到C中所有的唯一组合,使得组合的数字和为T]
    [C中的每一个数字都只能被用一次]
    [其实这个题目更难一点,因为不知道有多少种可能]

    class Solution {
    private:
        vector<vector<int>> res;
    public:
        void help(vector<int>& candidates,vector<int>& vec, int target, int left,int sum){
            if(sum==target){
                res.push_back(vec);  
                return;
            } 
            for(int i=left;i<candidates.size();i++){
                if(sum+candidates[i]>target) return;
                int sign=0;
         // 顺序执行的时候,已经将同样字符的情况考虑到了, 就不需要再提前再考虑了。
                for(int j=left;j<i;j++){
                    if(candidates[j]==candidates[i]){
                        sign=1;
                        break;
                    } 
                }
         // 如果没问题就直接运行
                if(sign==0){
                    vec.push_back(candidates[i]);
                    help(candidates,vec,target, i+1, sum+candidates[i]);
                    vec.pop_back();
                }
            }
        }
    
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            if(candidates.size()==0) return res;
            vector<int> vec;
            sort(candidates.begin(),candidates.end());
            help(candidates,vec,target, 0, 0);
            return res;
        }
    };
    

    相关文章

      网友评论

        本文标题:leetcode 中等题(部分一)

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