头像

Ncik


访客:5514

在线 



Ncik
31分钟前

算法

(DP) $O(n)$

采用动态规划的方法,用一个有序数组dp记录前$n$个丑数。三个指针l2l3l5指向dp中的元素,最小的丑数只可能出现在dp[l2]2倍、dp[l3]3倍和dp[l5]5倍三者中间。通过移动三个指针,就能保证生成的丑数是有序的。

  • 初始化数组dp和三个指针l2l3l5dp[0] = 1,表示最小的丑数为1。三个指针都指向dp[0]
  • 重复以下步骤$n$次,dp[i]表示第i + 1小的丑数:
    – 比较2 * dp[l2], 3 * dp[l3], 5 * dp[l5]三者大小,令dp[i]为其中的最小值。
    – 如果dp[i] == 2 * dp[l2]l2指针后移一位。
    – 如果dp[i] == 3 * dp[l3]l3指针后移一位。
    – 如果dp[i] == 5 * dp[l5]l5指针后移一位。
  • dp[n - 1]即为第$n$小的丑数,返回。

C++ 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0] = 1;
        int l2 = 0, l3 = 0, l5 = 0;
        for(int i = 1; i < n; ++i) {
            // 生成第i+1小的丑数
            dp[i] = min(min(dp[l2] * 2, dp[l3] * 3), dp[l5] * 5);
            if (dp[i] == dp[l2] * 2) {
                ++l2;
            }
            if (dp[i] == dp[l3] * 3) {
                ++l3;
            } 
            if (dp[i] == dp[l5] * 5) {
                ++l5;
            }
        }
        return dp[n - 1];
    }
};


新鲜事 原文

Ncik
17小时前
发一下考点,复习的时候可以用~
图片



Ncik
1天前

算法

(DP) $O(n)$

一般对于最长XX问题容易想到利用$DP$求解,在这题中利用逆向$DP$,设状态$dp[i]$为从$i$到$len -1$中,以i开头的最长合法子串长度:

  • 初始化:$dp[len - 1] = 0$
  • 如果$s[i] = ‘)’$,则跳过,因为不可能有由$’(‘$开头的串
  • 如果$s[i] = ‘(‘$,则需要找到右括号和它匹配,可以跳过以$i + 1$开头的合法子串,则需要看$j = i + dp[i + 1] + 1$是否为右括号。如果没越界且为右括号,那么有$dp[i] = dp[i + 1] + 2$,此外在这个基础上还要将$j + 1$开头的子串加进来(只要不越界)

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.size() <= 1)   return 0;
        int res = 0;
        vector<int> dp(s.size(), 0);    //初始化
        for(int i = s.size() - 2; i >= 0; i--)
        {
            if(s[i] == '(') //如果s[i] = '(',则需要找到右括号和它匹配,可以跳过以i + 1开头的合法子串,则需要看j = i + dp[i + 1] + 1是否为右括号
            {
                int j = i + dp[i + 1] + 1;
                if(s[j] == ')' && j < s.size()) //如果没越界且为右括号
                {
                    dp[i] = dp[i + 1] + 2;
                    if(j + 1 < s.size())  //还要将j + 1开头的子串加进来
                        dp[i] += dp[j + 1];
                }    
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};


新鲜事 原文

Ncik
1天前
不适合用DP的场景: 1. 暴力算法是多项式级别 2. 输入数据无方向性 3. 求所有方案


新鲜事 原文

Ncik
1天前
DP问题的种类: 1. 求最值 2. 求可行性 3. 求方案总数



Ncik
1天前

算法

(二叉树的层次遍历) $O(n)$

层次遍历,可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历,开辟一个新队列,让头结点入队并计算此时的长度,每次都将一层的所有节点压入队列后,得到队列的大小,然后将这这一层的所有点都进行遍历,将从左到右每一个点的子节点都压入队列,将本层节点遍历完后,继续下一层的遍历,然后开始循环,一直遍历到底层,判断的终止条件就是队列为空。

  • 循环里面,队列头出队,判断其是否有左右子结点,如果有,则入队,但此时还不需要更新队列的长度,当前队列的长度 是每层的长度。当这层的长度减为0时,就说明这层的遍历结束,开始更新长度为下一层的长度
  • 出队的元素的值按照一层层压入结果数组
  • 因为题目要求自底向上,那么我们不移动每一层的内容,对层进行倒序

Java 代码

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
         List<List<Integer>> ans = new ArrayList<>();
      LinkedList<TreeNode> queue = new LinkedList<>();
      if (root != null) {
         queue.offer(root);
      }
      //层次遍历
      while (!queue.isEmpty()) {
         int len = queue.size();
         List<Integer> tmpList = new ArrayList<>();
         while (len > 0) {
            TreeNode treeNode = queue.poll();
            tmpList.add(treeNode.val);
            if (treeNode.left != null) { //左子树不为空的话压入队列
               queue.offer(treeNode.left);
            }
            if (treeNode.right != null) {//右子树不为空的话压入队列
               queue.offer(treeNode.right);
            }
            len--;
         }
         ans.add(tmpList);//储存当前层的节点
      }
      //倒序
      Collections.reverse(ans);
      return ans;
    }
}



Ncik
1天前

算法

(递归)

通过观察我们可以发现,生成的任何括号组合中都有两个规律:

  1. 括号组合中左括号的数量等于右括号的数量
  2. 括号组合中任何位置左括号的数量都大于等于右括号的数量

第一条很容易理解,我们来看第二条,比如有效括号”(())()”,在任何一个位置右括号的数量都不大于左括号的数量,所以是等效的。如果像这样”())()”第3个位置的是右括号,那么他前面只有一个左括号,而他和他前面的右括号有2个,那么无论如何都不能组合成有效的括号。搞懂了上面的原理,我们就以$n$等于$2$为例来画个图看一下

7.3.jpg

Java 代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(res, n, n, "");
        return res;
    }

    private void dfs(List<String> res, int left, int right, String curStr) {
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 左括号只有剩余的时候才可以选,如果左括号的数量已经选完了,是不能再选左括号了 
        // 如果选完了左括号我们还可以选择右括号
        if (left < 0) return;

        // 如果右括号剩余数量小于左括号剩余数量,说明之前选择的无效
        if (right < left) return;

        // 选择左括号
        dfs(res, left - 1, right, curStr + "(");

        // 选择右括号
        dfs(res, left, right - 1, curStr + ")");
    }
}


新鲜事 原文

Ncik
1天前
总结如何做题 1. 做题说白了就是建模和解决模型的过程。做不出来可能有两个原因,一个是模型建错了,一个数对模型不够了解。前者说明分析没有到位,后者说明知识不够扎实。 2. 对各种模型有清楚的了解,这样才能轻松的做题,真正的高手不一定智商很高,但是建模能力一定很强。 我的一些经验: 1. 从简单的情况开始分析:经典方法,对原题没有思路,那么分析问题的简化版。 经典例子:找出字典序最小的解,那么我们先分析怎么找出一个解。 2. 人的思维很大程度上跟关键字有关系,比如一个题目怎么想都不会,有人跟你说"容斥”,你可能瞬间就会做了。不妨列出对于这类问题已知的一些解决方法关键字,思考思考能否做。



Ncik
1天前

算法

(数学) $O(n)$

我们思考这样一个问题,如果$a+b$能被$k$整除,那么$a$和$b$分别对$k$取余的结果相加也一定能被$k$整除,即$(a%k+b%k)%k=0$。所以我们对$arr$中的圆度分别对$k$取余。即num = num % k,因为数组中可能会有负数,所以求余的结果也可能为负数,这里为了计算方便,我们把求余的结果全部转化为非负数,大小在$[0, k - 1]$中,包含$0$和$k-1$。所以计算公式是num = (num % k + k) % k
这样我们只需要计算余数相对应位置上的个数是否相等就可以了。还有一点就是$0$的个数必须是偶数。

Java 代码

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] mod = new int[k];

        // 统计求余之后各余数的个数
        for (int num : arr)
            mod[(num % k + k) % k]++;

        for (int i = 1; i < k / 2; ++i) {
            // 如果对应的个数不匹配,直接返回false
            if (mod[i] != mod[k - i])
               return false;
        }

        // 余数中0的个数必须是偶数
        return mod[0] % 2 == 0;
    }
}



Ncik
2天前

算法

(树、DFS)

每次选择一个区间的中点作为当前区间的根,然后对左右子树依次构造。

C++ 代码

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode *helper(vector<int> &nums, int left, int right) {
        if (left > right) { return NULL; }
        int aMid = (left + right) / 2;
        TreeNode *aRoot = new TreeNode(nums[aMid]);
        aRoot->left = helper(nums, left, aMid - 1);
        aRoot->right = helper(nums, aMid + 1, right);
        return aRoot;
    }
};