C#和.Net框架

topk

• 215. 数组中的第K个最大元素

class Solution {
public:
    int partition(vector<int>& nums,int i,int j)
    {
        int pviot = nums[i];
        while(i < j)
        {
            for(;i<j && nums[j] <= pviot ;--j);
                nums[i] = nums[j];
            for(;i<j && nums[i] >= pviot;++i);
                nums[j] = nums[i];
        }
        nums[i] = pviot;
        return i;
    }

    int quickSort(vector<int>& nums,int i,int j ,int k)
    {
        int pos = partition(nums,i,j);
        if(k > pos)
            return quickSort(nums,pos+1,j,k);
        else if( k < pos)
            return quickSort(nums,i,pos-1,k);
        else 
            return nums[pos];

    }


    int findKthLargest(vector<int>& nums, int k) {
        return quickSort(nums,0,nums.size()-1,k-1);
    }
};

手撕堆排

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    void HeapShiftDown(vector<int>& arr,int k,int n)
    {
        for(int m = k*2+1; m < n; m=m*2+1)
        {
            if(m+1 < n && arr[m+1] > arr[m])
                 m++;

            if(arr[m]> arr[k])
            {
               swap(arr[k],arr[m]);
                k = m;
            }
            else
                break;
        }
    }

    void HeapAdjust(vector<int>& arr)
    {
        int k = (arr.size()-1)/2;
        for(int i = k; i >=0;--i)
            HeapShiftDown(arr,i,arr.size());
    }

    vector<int> MySort(vector<int>& arr) {
        // write code here
        int n = arr.size();
        HeapAdjust(arr);
        for(int i = n-1;i>0;--i)
        {
            swap(arr[0],arr[i]);
            HeapShiftDown(arr,0,i);
        }
        return arr;
    }
};

手撕快速

• 复杂度证明

  class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    int Partition(vector<int>& nums,int i,int j)
    {
        int pivot = nums[i];
        while(i<j)
        {
              while(i<j && nums[j] >= pivot)
                  --j;
                nums[i] = nums[j];
            while(i<j && nums[i] <= pivot)
                  ++i;
                nums[j] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }
  
    void QuickSort(vector<int>& nums,int i,int j)
    {
        if(i < j)
        {
            int index = Partition(nums,i,j);
            QuickSort(nums, i, index-1);
            QuickSort(nums, index+1, j); 
        }
  
    }
  
    vector<int> MySort(vector<int>& arr) {
        // write code here
        QuickSort(arr, 0, arr.size()-1);
        return arr;
    }
  };
  

手撕归并

#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int>& nums,int i,int mid,int j)
{
    vector<int> v;
    int a=i,b=mid+1;
    while(a <= mid && b <=j)
    {
        if(nums[a] < nums[b])
        {
            v.push_back(nums[a]);
            ++a;
        }
        else
        {
            v.push_back(nums[b]);
            ++b;   
        }
    }

    while(a <= mid)
    {
        v.push_back(nums[a]);
        ++a;
    }

    while(b <= j)
    {
        v.push_back(nums[b]);
        ++b;   
    }

    for(int k= 0; k< v.size();++k)
        nums[i+k] = v[k];
}

void MergeSort(vector<int>& nums,int i,int j)
{
    if(i < j)
    {
        int mid = i + (j-i)/2;
        MergeSort(nums,i,mid);
        MergeSort(nums,mid+1,j);
        Merge(nums,i,mid,j);
    }
}

int main()
{
    int n;
    cin>>n;
    vector<int> v(n,0);
    for(int i = 0; i< n; ++i)
    {
        cin>>v[i];
    }
    MergeSort(v,0,n-1);
    for(int i =0; i < v.size();++i)
    {
        cout<<v[i];
        if(i != v.size()-1)
            cout<<" ";
    }
    return 0;
}

最长回文字串

• dp

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));

        for(int i = s.size()-1; i>=0 ;--i)
        {
            for(int j = i; j < s.size();++j)
            {
                if( (j-i > 1 && s[i] == s[j] && dp[i+1][j-1]) || (j-i <= 1 && s[i] == s[j] ))
                {
                    dp[i][j] = true;
                    if(j-i+1 > res.size())
                    res = s.substr(i,j-i+1);
                }
            }
        }
        return res;
    }
};

• 中心扩展

  class Solution {
  public:
    pair<int,int> expandAroundCenter(string s,int i,int j)
    {
        while(i>=0 && j < s.size() && s[i] == s[j])
        {
            --i;
            ++j;
        }
        return {i+1,j-1};
    }
  
    string longestPalindrome(string s) {
        int start=0,end = 0;
        for(int i = 0; i < s.size();++i)
        {
            auto [left1,right1] = expandAroundCenter(s,i,i);
            auto [left2,right2] = expandAroundCenter(s,i,i+1);
  
            if(right1 -left1 > end -start)
            {
                end = right1;
                start = left1;
            }
  
            if(right2 - left2 > end - start)
            {
                end = right2;
                start = left2;
            }
        }
  
        return s.substr(start,end-start+1);
    }
  };
  

最大连续子数组的和

• dp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int res = nums[0];
        vector<int> dp(n,nums.size());
        dp[0] = nums[0];
        for(int i = 1; i < nums.size();++i)
        {
            if(dp[i-1] + nums[i] < nums[i])
                dp[i] = nums[i];
            else
                dp[i] = dp[i-1] + nums[i];
            res = max(res,dp[i]);
        }
        return res;
    }
};

如果删除vector中间元素 怎么实现（不能用erease，无序）

• 将中间之后的元素往前移动一个位置并vector大小减一

strcpy

#include <QCoreApplication>
#include <assert.h>
#include <QDebug>

//普通版本的strcpy，实现没有检查dst和src内存重叠问题,会崩溃
char* myStrcpy(char* dst, const char* src)
{ //const约束,内容不可变
    assert(src != Q_NULLPTR && dst != Q_NULLPTR); //参数非0检验
    char* pstr = dst;
    while ((*dst++ = *src++) != '\0'){}
    return pstr;
}

//检查内存重叠
char* my1Strcpy(char* dst, const char* src)
{
    assert(src != Q_NULLPTR && dst != NULL);
    char * nsrc = const_cast<char*>(src);
    char * adest = dst;
    size_t size = strlen(src);
    if (src < dst && (src + size) > dst) {
        //内存重叠,从后向前复制
        char* bsrcp = nsrc + size - 1;
        char* bdestp = dst + size - 1;
        while ((*bdestp-- = *bsrcp--) && size-- != 0){}
    } else {
        while ((*dst++ = *nsrc++) != '\0'){}
    }
    return dst;
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    char dest[10] = "hello";
    qDebug() << my1Strcpy(&dest[3], dest) << endl;
    return a.exec();
}

输入1~n共n个数，打乱后随机删除一个，找出删除的那个数（不许排序）

对于删除一个数，大概有四种方法：

（1）用1+2+…+n减去当前输入数据的总和。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

（2）用12…n除以当前输入数据的总积。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

（3）用1^2^…^n的结果在逐个异或当前输入数据。时间复杂度：O(n) 空间复杂度：O(1)

（4）对输入数据进行Hash，然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n)

输入1~n共n个数，打乱后随机删除一个，再复制一个，找出这两个数

• 类似 剑指 Offer 56 - I. 数组中数字出现的次数

  • 第一轮整体遍历，求出a^b（因为相同的数字异或为0，0异或任何数字为数字自身）
  • 然后结合a^b以及原来数组求出这两个数字
  • 原理：用一个只有一位为1的数字来遍历异或整个数组，把这个数组分成两个子数组（异或结果相同的数字在同一个子数组），如果是两个相同的数字，它们一定在同一个子数组里（保证子数组异或时为0），现在只需要把两个只出现一次的数字分到不同的子数组，那么子数组分别遍历异或得到的两个数字就是这两个数字。
  • 怎么把两个只出现一次的数字分到不同地子数组？
    • 找到a^b第一个为1的位置，异或结果为1说明a和b在这一位上不同，那用只有这一位为1的数字m去分别异或a和b，得到的结果一定不同，也就把a和b分到了不同的子数组。结合上一点得出结果。

• 实在写不出来hash

非递归遍历

/**
 * 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<int> preorder(TreeNode* root)
    {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur;
        s.push(root);
        while(!s.empty())
        {
            cur = s.top();
            s.pop();
            res.push_back(cur->val);
            if(cur->right)
                s.push(cur->right);
            if(cur->left)
                s.push(cur->left);
        }
        return res;
    }

    vector<int> inorder(TreeNode* root)
    {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(!s.empty() || cur != nullptr)
        {
            if(cur != nullptr)
            {
                s.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }

    vector<int> postoreder(TreeNode* root)
    {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(!s.empty() || cur != nullptr)
        {
            if(cur!=nullptr) {
                s.push(cur);
                cur = cur->left;
            }
            else {
                cur = s.top();
                s.pop();
                if(cur->right==nullptr || pre==cur->right) { // 访问节点的条件
                    res.push_back(cur->val); // 访问
                    pre = cur; // 这一步是记录上一次访问的节点
                    cur = nullptr; // 此处为了跳过下一次循环的访问左子节点的过程，直接进入栈的弹出阶段，因为但凡在栈中的节点，它们的左子节点都肯定被经过且已放入栈中。
                }
                else 
                { // 不访问节点的条件
                    s.push(cur); // 将已弹出的根节点放回栈中
                    cur = cur->right; // 经过右子节点
                }
        }

    }
         return res;
}
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int> > res;
        res.push_back(preorder(root));
        res.push_back(inorder(root));
        res.push_back(postoreder(root));
        return res;
    }
};