程序员最近都爱上了这个网站  程序员们快来瞅瞅吧！  it98k网:it98k.com

小白一个，每天打卡，遇到不会的记录一下！

目录

1.比特位计数

2.俄罗斯套娃信封问题

3.用栈实现队列

1.比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]

思路

对于所有的数字，只有两类：

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
          举例： 
         0 = 0       1 = 1
         2 = 10      3 = 11
偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
           举例：
          2 = 10       4 = 100       8 = 1000
          3 = 11       6 = 110       12 = 1100
另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。

作者：duadua
链接：https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/
来源：力扣（LeetCode）

class Solution {
    public int[] countBits(int num) {
        int []result = new int[num+1];
        result[0]=0;
        for(int i=0;i<=num;i++){
            if(i%2==0){
                result[i]=result[i/2];
            }else{
                result[i]=result[i-1]+1;
            }
 
        }
        return result;
 
    }
}

2.俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

参考结题思路：

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/

https://leetcode-cn.com/problems/russian-doll-envelopes/solution/zui-chang-di-zeng-zi-xu-lie-kuo-zhan-dao-er-wei-er/

代码

class Solution {
 
    public int maxEnvelopes(int[][] envelopes) {
 
        int n = envelopes.length;
        //默认是升序，但我们对w按升序，当w相等按降序
        //将小的放在前面，大的放在后面。
        // 例如当返回负数的时候，表明第一个数应该排在第二个数的上面，也就是位置不变。
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int []a,int []b){
                if(a[0]==b[0]){
                    return b[1]-a[1];
                }else{
                   return a[0]-b[0];
                }
            }
        });
        //将h单独提取出来，作为一个数字，找到最长上升子序列
        int []h =new int[n];
        for(int i=0;i<n;i++){
            h[i]=envelopes[i][1];
        }
 
        return maxlen(h);
 
    }
 
 
    public int maxlen(int []h){
        int n=h.length;
        int []m = new int [n];
        // for(int i=0;i<n;i++){
        //     max[i]=1;
        // }
        // base case：dp 数组全都初始化为 1     
        Arrays.fill(m, 1);
        //动态规划
        for(int j=0;j<n;j++){
            for(int k =0;k<j;k++){
                if(h[j]>h[k]){
                    m[j]=Math.max(m[j],m[k]+1);
                }
                
            }
        }
 
        int res=0;
        for(int i=0;i<n;i++){
            res=Math.max(res,m[i]);
        }
 
        return res;
 
    }
}

3.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks

思路

https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/shi-yong-liang-ge-dui-lie-yong-shi-0ms-b-34bm/

https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/yong-zhan-shi-xian-dui-lie-by-leetcode/

代码

class MyQueue {
 
    /** Initialize your data structure here. */
    public Stack<Integer> s1;
    public Stack<Integer> s2;
    public int front;
    public MyQueue() {
           s1=new Stack();
           s2=new Stack();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if(s1.empty()){
            front =x;
        }
        s1.push(x);
 
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
 
        }
        int s = s2.pop();
        return s;
 
    }
    
    /** Get the front element. */
    public int peek() {
        if(s2.empty()){
            return front;
        }else{
            return s2.peek();
        }
 
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        // if(s1.empty()&&s2.empty()){
        //     return true;
        // }else{
        //     return false;
        // }
           return s1.empty()&&s2.empty();
    }
}
 
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

原文链接:https://blog.csdn.net/chenfang0529/article/details/114299374