✅ 191. 位1的个数
描述
解答
- cpp
- py
✅ 107. 二叉树的层次遍历 II
描述
解答
- c todo 观赏 0222
- py
✅ 806. 写字符串需要的行数
描述
解答
- cpp
- js

✅ 191. 位1的个数

描述

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

 

示例 1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/number-of-1-bits

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

cpp

class Solution {

public:

    int hammingWeight(uint32_t n) {

        // 10 based to 2 based

        int ans = 0;

        while(n) {

            ans += n&1;

            n>>=1;

        }

        return ans;

    }

};

/*执行用时 :

4 ms

, 在所有 C++ 提交中击败了

76.64%

的用户

内存消耗 :

8.3 MB

, 在所有 C++ 提交中击败了

5.95%

的用户*/

or:

class Solution {

public:

    int hammingWeight(uint32_t n) {

        return bitset<32>(n).count();

    }

};

/*执行用时 :

8 ms

, 在所有 C++ 提交中击败了

30.26%

的用户

内存消耗 :

8.2 MB

, 在所有 C++ 提交中击败了

52.87%

的用户*/

py

class Solution:

    def hammingWeight(self, n: int) -> int:

        return str(bin(n)).count('1');

'''

执行用时 :

32 ms

, 在所有 Python3 提交中击败了

75.73%

的用户

内存消耗 :

13.4 MB

, 在所有 Python3 提交中击败了

22.90%

的用户

'''

✅ 107. 二叉树的层次遍历 II

描述



给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

给定二叉树 [3,9,20,null,null,15,7],

    3

   / \

  9  20

    /  \

   15   7

返回其自底向上的层次遍历为：

[

  [15,7],

  [9,20],

  [3]

]

解答

传统解法：使用层序遍历，中间加上 stack

问题是，我不知道如何让截止一个层。这个问题就描述不清楚。那你去看看py的实现

while(!q.empty()){

    node = q.poll();

    stack.push(node);

    if(node.left): q.enque(node.left);

    if(node.right): q.enque(node.right);

}

int ret[stack.size()];

while(!stack.empty()){

    ret.append(stack.pop());

}

c todo 观赏 0222

typedef struct queue

{

    struct TreeNode* data;

    int front;

    int rear;

}Myqueue;

void initqueue(Myqueue* queue, int maxsize)

{

    queue->data = (struct TreeNode*)malloc(sizeof(struct TreeNode) * maxsize);

    queue->front = 0;

    queue->rear = 0;

}

void enqueue(Myqueue* obj, struct TreeNode* root)

{

    obj->data[obj->rear++] = root[0];

}

struct TreeNode* dequeue(Myqueue* obj, struct TreeNode* root)

{

    return &obj->data[obj->front++];

}

int isqueueempty(Myqueue* obj)

{

    return obj->front == obj->rear ? 1 : 0;

}

int height(struct TreeNode* root) //求深度

{

    int HL, HR, MaxH;

    if(root)

    {

        HL = height(root->left);

        HR = height(root->right);

        MaxH = (HL > HR) ? HL : HR;

        return (MaxH + 1);

    }

    else return 0;

}

int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize)

{

    int **ret = (int**)malloc(sizeof(int*) * 1000);

    int count = 0, i = 0, depth;

    depth = height(root);

    *returnSize = depth;

    Myqueue* queue = (Myqueue*)malloc(sizeof(Myqueue));

    columnSizes[0] = (int*)malloc(sizeof(int) * 1000);

    initqueue(queue, 10000);

    if(!root) return NULL;

    enqueue(queue, root);

    while(!isqueueempty(queue))

    {

        depth--;

        count = queue->rear - queue->front;

        ret[depth] = (int*)malloc(sizeof(int) * count);

        columnSizes[0][depth] = count;

        while(i != count)

        {

            root = dequeue(queue, root);

            ret[depth][i++] = root->val;

            if(root->left) enqueue(queue, root->left);

            if(root->right) enqueue(queue, root->right);

        }

        i = 0;

    }

    return ret;

}

最早

最新

miaoxingren喵星人

1 年前

@福 膜拜大佬，，看了那么多其他语言写的，，我只佩服大佬写的c语言 程序

大佬你的c语言功底也太好了吧

fu-Z2aABL1fkT福

1 年前

@喵星人 惭愧，因为我只会C语言【捂脸】, 来日方长，加油！

get_money走过的路、沉淀了回忆

10 个月前

@福 大佬，有空做个注释咯！ 感激不尽

xiu-nya修~Nya

10 个月前

@福 果然这种题目，用C写起来，代码量和思维都，令人咂舌，佩服佩服，太惊人了

poison-9poison

6 个月前

@福 用C写是真的牛皮

lao-ju-wei-lai-ke-ji-gong-si老菊未来科技公司

6 个月前

@福 用C语言做最大的问题就是不知道这些函数参数都是干嘛的ORZ

py

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:

        if root == None: return [] # must add this line

        q = []

        res = []

        q.append(root)

        while len(q):

            tmp_q = []

            small_list = []

            for i in q:

                if i:

                    small_list.append(i.val)

                    if i.left: tmp_q.append(i.left)

                    if i.right: tmp_q.append(i.right)

            q = tmp_q

            res.insert(0, small_list)

        return res

'''

执行用时 :

64 ms

, 在所有 Python3 提交中击败了

6.18%

的用户

内存消耗 :

13.7 MB

, 在所有 Python3 提交中击败了

35.13%

的用户

'''

✅ 806. 写字符串需要的行数

描述



我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例 1:

输入:

widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]

S = "abcdefghijklmnopqrstuvwxyz"

输出: [3, 60]

解释:

所有的字符拥有相同的占用单位10。所以书写所有的26个字母，

我们需要2个整行和占用60个单位的一行。

示例 2:

输入:

widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]

S = "bbbcccdddaaa"

输出: [2, 4]

解释:

除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.

最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。

所以，这个答案是2行，第二行有4个单位宽度。

注:

字符串 S 的长度在 [1, 1000] 的范围。

S 只包含小写字母。

widths 是长度为 26的数组。

widths[i] 值的范围在 [2, 10]。

解答

cpp

js

/**

 * @param {number[]} widths

 * @param {string} S

 * @return {number[]}

 */

var numberOfLines = function(widths, S) {

//妙啊

//不用求余求商，那样扣边界烦死，逐项相加，累加一旦大于100，行数加1，那么要到下一行的一定是当前这个使得累加和大于100 的那个元素，累加和更新为当前元素的单位，开始新的一行，直到最后。。。 72ms， 34.7MB.

    let count = 1;

    let sum = 0;

    for (let i = 0; i < S.length; i++) {

        let code = S.charCodeAt(i);

        sum += widths[code - 97];

        if (sum > 100) {

            count += 1;

            sum = widths[code - 97];

        }

    }

    return [count, sum];

};

/*执行用时 :

64 ms

, 在所有 JavaScript 提交中击败了

81.54%

的用户

内存消耗 :

34.8 MB

, 在所有 JavaScript 提交中击败了

75.56%

的用户 */

巴特西

lc 0222

✅ 191. 位1的个数

描述

解答

cpp

py

✅ 107. 二叉树的层次遍历 II

描述

解答

c todo 观赏 0222

py

✅ 806. 写字符串需要的行数

描述

解答

cpp

js

最新文章

热门文章