头像

在下振予




离线:3天前


最近来访(16)
用户头像
玄澈_
用户头像
ζ肃ζ苑
用户头像
bella今天学算法
用户头像
如果在冬夜一个旅人
用户头像
用户头像
wps
用户头像
5120217729
用户头像
普通上班族
用户头像
kele21
用户头像
扳手工01
用户头像
Present.
用户头像
yxc
用户头像
冷眼大个子
用户头像
我是fw
用户头像
ζ卿枫醉あ
用户头像
wzyddy


What:

对数器是通过用大量测试数据来验证算法是否正确的一种方式。有时候,我们只能确定我们写出的算法在逻辑上大致正确的,不能一次性保证绝对的正确。特别是对于一些复杂的题目,例如贪心算法,往往无法在有限时间内用数学公式来推导证明我们程序的正确性。在线的OJ一般只会给出有数的几个简单的样例,可能我们的算法在这些简单的样例偶然通过了,但是在一些复杂的样例处却出现了问题。这时我们无法使用复杂的样例来分析调试我们的代码,人工设计样例来测试代码的效率又太低,而且不能确保考虑各种特殊情况。因此,能随机产生不同情况的数据的对数器就派上了用场。对数器,就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。既然我们知道了绝对正确的方法,直接用这个方法不就好了嘛?请注意,算法追求的不是解决问题,而是高效率的解决问题。对于一个数组的排序,如果笔试中要求的时间复杂度是O(NlogN),但是你却写了一个冒泡排序的算法交上去了,这时OJ就会提示:超时。而在对数器中,我们要求的绝对正确的算法是没有时间和空间复杂度的限制的,唯一的要求是确保绝对正确。因为只有绝对正确,我们才能通过样例的比对,发现我们的代码是在哪里出了错误。

How:

1、有一个你要测的方法a;
2、实现一个简单可能复杂度高但是绝对正确的方法b;
3、实现一个随机样本产生器;
4、实现对比算法a和b的方法,把方法a运行结果和方法b运行结果比对多次来验证方法a是否正确;
5、如果有一个样本使得比对出错,打印样本分析是哪个方法出错;
如果当样本数量很多时比对测试依然正确,可以确定方法a已经正确。

Attention:

随机产生的样本要进行多次(至少上千次甚至上万次)的对比。算法b要保持正确性。




题目:60题 礼物的最大价值
算法:动态规划dp
时间复杂度:O(m + n)
空间复杂度:O(1)
c++代码:
class Solution {
public:

    int getMaxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 1;i < n;i ++)    // 计算第一行的dp值
            grid[0][i] += grid[0][i - 1];
        for(int j = 1;j < m;j ++)    // 计算第一列的dp值
            grid[j][0] += grid[j - 1][0];

        /** 下面开始计算剩余的dp值 */
        for(int i = 1;i < m;i ++) {  
            for(int j = 1;j < n;j ++) {
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
};



题目:27题 树的子结构
算法:在树a中找某个结点,其值和b树的根节点的值相同,然后以此开始匹配,只要找到这么一个匹配的段就ok,思想类似在一个长串中去找是否存在一个短串。
c++代码:
class Solution {
public:
    bool pipei(TreeNode* a, TreeNode* b) {  // 只要有一个条件不满足就匹配失败,所以最后一个返回&&
        if(!b) return true;
        if(b && !a) return false;
        if(a->val != b->val) return false;
        return pipei(a->left, b->left) && pipei(a->right, b->right);
    }
    bool hasSubtree(TreeNode* a, TreeNode* b) {  // 只要有一个匹配成功,就ok,所以最后那里用|| 
        if(!a || !b) return false;
        if(pipei(a, b)) return true;  // 匹配成功了
        return hasSubtree(a->left, b) || hasSubtree(a->right, b);
    }
};



题目:23题 矩阵中的路径
算法:深度优先搜索,dfs。几个注意点:需要状态数组、初始化第一个位置已经被搜索过了、回溯恢复现场。
c++代码:
class Solution {
public:
    int used[31][31];
    int m, n, len;
    bool ans_dfs = false;
    void dfs(vector<vector<char>>& board, string word, int id, int x, int y) {
        if(id + 1 == len) {      // 完成了了整个单词的搜索
            ans_dfs = true;      // 找到的标志变为true
            return;              // 越界或者已经找到,则退出
        }
        int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
        for(int i = 0;i < 4;i ++) {
            if(ans_dfs) break; // 已经找到了满足单词的串
            int xx = dx[i] + x, yy = dy[i] + y;
            if(xx < 0 || xx == m || yy < 0 || yy == n) continue;        // 越界
            if(board[xx][yy] != word[id + 1] || used[xx][yy]) continue; // 不符合条件
            /** 下面是符合条件的,继续递归 */
            used[xx][yy] = 1;  // 标记该位置已经遍历
            id ++;
            dfs(board, word, id, xx, yy);
            used[xx][yy] = 0;  // 恢复现场
            id --;
        }
    }
    bool hasPath(vector<vector<char>>& board, string &word) {
        m = board.size();
        if(m == 0) return false;
        n = board[0].size();
        len = word.size();
        if(m * n < len) return false;  // 单词长度超过字母总数
        char head = word[0];           // 单词的第一个字母
        for(int i = 0;i < m;i ++) {
            for(int j = 0;j < n;j ++) {
                if(board[i][j] == head) {
                    memset(used, 0, sizeof(used));  // 先初始化状态数组全0
                    used[i][j] = 1;                 // 第i、j位置已经被搜索
                    ans_dfs = false;                // 初始化答案为false
                    dfs(board, word, 0, i ,j);      // 搜索
                    if(ans_dfs) return true;        // 搜索成功返回结果
                }
            }
        }
        return false;
    }
};



题目:73题 数组中只出现一次的两个数字
算法:可以用哈希表。也可以用位运算,下面阐述位运算的方法。首先,数组中除了两个单独出现数(假设为m、n),其余数都是成对的。对于一个数x,有x^x=0,那么对数组全部异或后得到m^n,然后找到m^n的最后一个1(假设为t),当然也可以第一个1,这个1可以把m、n分开,假设m=3,n=1,那么m^n=2,t=2,于是m&t=1 != n&t=0,所以就把m、n分开了,对于其他的数,两两异或就为0。详细见代码。
时间复杂度:O(n)
空间复杂度:O(1)
c++代码:
class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        vector<int>ans;
        int mn = 0;
        for(auto num:nums) {  // 得到这两个数(m、n)的异或值
            mn ^= num;   
        }

        int t = 1;
        while((mn & t) == 0)  // 找到mn的最右边的1
            t = t << 1;

        int m = 0, n = 0;
        for(auto num:nums) {  // 利用t把数组分成两组,m、n必定在不同组,其他数据,^之后就是0,最后相当于m = m ^ 0和n = n ^ 0
            if(t & num)
                m = m ^ num;
            else
                n = n ^ num;
        }
        ans.push_back(m);
        ans.push_back(n);
        return ans;
    }
};



题目 40题 顺时针打印矩阵
算法:按照第一行、最后一列、最后一行、第一列的顺序打印,每次打印后,把边界调整一下,然后再判断是否出界。
时间复杂度:O(mn)
空间复杂度:O(mn)
c++代码:
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int>ans;
        int m = matrix.size();
        if(m == 0) return ans;
        int n = matrix[0].size();

        int top = 0, bottom = m - 1, left = 0, right = n - 1;

        while(true) {
            for(int i = left;i <= right;i ++) { // 上行
                ans.push_back(matrix[top][i]);
            }
            top ++;
            if(top > bottom || left > right) break;

            for(int i = top;i <= bottom;i ++) { // 右列
                ans.push_back(matrix[i][right]);
            }
            right --;
            if(top > bottom || left > right) break;

            for(int i = right;i >= left;i --){
                ans.push_back(matrix[bottom][i]);
            }
            bottom --;
            if(top > bottom || left > right) break;

            for(int i = bottom;i >= top;i --) {
                ans.push_back(matrix[i][left]);
            }
            left ++;
            if(top > bottom || left > right) break;
        }
        return ans;
    }
};



题目:53 题:最小的k个数
算法:利用快排找到最小的前k个数,但不一定是有序的。然后再对前k个数排序
时间复杂度:O(logn)
空间复杂度:O(n)
class Solution {
public:
    void swap(int& a, int& b) {  // 交换a、b的值
        int temp = a;
        a = b;
        b = temp;
    }
    void quick_sort(vector<int>& nums, int l, int r, int k) {  // 标准快排代码
        if (l >= r) return ;
        int i = l - 1;
        int j = r + 1;
        int x = nums[l + (r - l) / 2];  // 选中间这个数作为基准
        while(i < j) {
            do i++;while(nums[i] < x);
            do j--;while(nums[j] > x);
            if(i < j) swap(nums[i], nums[j]);
        }
        if(k < i) quick_sort(nums, l, j, k);
        if(k > i) quick_sort(nums, j + 1, r, k);
        return;
    }
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        if (k < input.size()) {  // k小于数组的长度,需要找前k个数
            quick_sort(input, 0, input.size() - 1, k);
        }
        sort(input.begin(), input.begin() + k);  // 对前k个数排序
        vector<int>ans;
        for(int i = 0;i < k;i ++) {
            ans.push_back(input[i]);
        }
        return ans;
    }
};



题目: 78题 左旋转字符串
算法1:substr()拼接
算法2:翻转
算法2c++代码:
class Solution {
public:
    string leftRotateString(string str, int n) {
        reverse(str.begin(), str.begin() + n);  // 翻转前n个字符
        reverse(str.begin() + n, str.end());    // 翻转剩余的字符
        reverse(str.begin(), str.end());        // 翻转整个串
        return str;
    }
};



题目:52题 数组中出现次数超过一半的数字
算法1:排序后直接输出中位数
时间复杂度:O(nlogn)
空间复杂度:O(1)
算法2:摩尔投票。对于不相同的两个数的票数互相抵消,对于相同的两个数票数+1。
时间复杂度:O(n)
空间复杂度:O(1)
c++代码:
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int len = nums.size();
        if(len <= 2) return nums[0];  // 数组长度小于等于2直接返回

        int ans = nums[0];            // 初始化答案为nums[0]
        int sum = 1;                  // 初始化ans的投票数为1
        for(int i = 1;i < len;i ++) {
            if(sum == 0) {            // 如果投票数为0,说明前面的互相抵消,重新选择当前值为ans
                ans = nums[i];
                sum ++;
            } else {
                if(nums[i] == ans) sum ++;    // 当前值和ans相同,其投票数+1
                else sum --;                  // 否则-1
            }
        }
        return ans;
    }
};



题目:36题 合并两个排序的链表
算法:遍历链表,重新将两个链表链在一起,不用开辟新空间。需要两个额外的指针,一个head作为新链表的头结点,一个now,作为合并两个链表的工具,now始终指向当前新链表的尾巴处,l1、l2指针不断往后移动。将now的next域指向当前的l1、l2值最小的结点,如果值相等,默认指向l1。直到有一个指针指到NULL,退出while循环,并将另一个指针接到now的next域,最后返回head头节点。
时间复杂度:O(n)
空间复杂度:O(1)
一个例子:

kk.png

c++代码:
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* now = NULL;
        // 先让now指向最小的那个结点
        if (l1->val <= l2->val) {
            now = l1;
            l1 = l1->next;
        } else {
            now = l2;
            l2 = l2->next;
        }
        ListNode* head = now;
        while (l1 != NULL && l2 != NULL) { // l1和l2没到链表尾时,重复执行下面
            // 先比较l1、l2当前指向结点的值
            // 让now的next域指向l1、l2中值小的结点,同时把值小的结点的指针往后挪一个位置
            if (l1->val <= l2->val) {  
                now->next = l1;
                l1 = l1->next;
            } else {
                now->next = l2;
                l2 = l2->next;
            }
            now = now->next;  // 此时链表增加一个结点,now指针也往后挪一个位置
        }
        if (l1 == NULL) now->next = l2;
        else now->next = l1;
        return head;
    }
};