LeetCode题 338比特位计数,20有效的括号,415字符串相加

简介: LeetCode题 338比特位计数,20有效的括号,415字符串相加



338比特位计数

题目要求:

连接:338. 比特位计数 - 力扣(LeetCode)

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入:n = 2

输出:[0,1,1]

解释:

0 --> 0

1 --> 1

2 --> 10


示例 2:

输入:n = 5

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

解释:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101


解题思路:

1、暴力穷举

遍历一遍 1 到 n,把里面的元素按位与上一个1,如果等于1,则说明当前i的末尾是1,用计数器记录下来,不是则不记录下来,然后再右移1位,如图:

代码:

public int[] countBits(int n) {
        int[] array = new int[n + 1];
        array[0] = 0;
        for(int i = 1; i <= n; i++) {
            int x = i;
            int count = 0;
            while(x > 0) {
                if((x & 1) == 1) {
                    count++;
                }
                x >>= 1;
            }
            array[i] = count;
        }
        return array;
    }

2、N&(N - 1)公式求解

如图:

解释:如果我们求21的二进制1的个数,那么就可以求20的二进制1的个数 + 1,求20的二进制1的个数就可以求16的二进制1的个数 + 1,求16的二进制1的个数就可以求0的二进制1的个数 + 1,所以,我们得到求某一数字N的二进制1的个数:(N &(N - 1))+ 1

代码:

public int[] countBits(int n) {
        int[] array = new int[n + 1];
        array[0] = 0;
        for(int i = 1; i < array.length; i++) {
            array[i] = array[i & (i-1)] + 1;
        }
        return array;
    }

3、奇偶数性质解法:

如图:

i = 5,7时,是奇数,观察上图可以发现,他们的二进制1的个数是 i 的前一个下标4,5的二进制1的个数 + 1。

所以当 i 是奇数时,我们就算它前一个下标的二进制个数+1就好了。

我们可以发现,i 为偶数时,他们的二进制1的个数和 i 右移一位(或者除 2)的二进制1的个数一样。

所以 i 为偶数时,我们算它右移一位的数二进制1个个数就好了。

代码:

public int[] countBits(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 0;
        for(int i = 1; i < arr.length; i++) {
            arr[i] = (i & 1) == 1 ? arr[i - 1] + 1 : arr[i >> 1];
        }
        return arr;
    }

20有效的括号

题目要求:

连接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"

输出:true


示例 2:

输入:s = "()[]{}"

输出:true


示例 3:

输入:s = "(]"

输出:false

解题思路

利用栈的这种数据结构,对比前一个括号左是否和当前的右括号匹配,利用栈的先进后出的特性,当遇到一个左括号,就放进栈里面一个右括号,取到的字符是右括号时,就判断这个这个右括号和栈里的栈顶元素是否相等,不相等就返回false,相等就弹出,继续下一次判断,。字符串没遍历完,如果栈为空了,则是右括号多了,返回false,如果字符串遍历完了,但是栈不为空,则是左括号多了,返回false。

代码:

public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char x : s.toCharArray()) {
            if(x == '(') {
                stack.push(')');
            } else if(x == '[') {
                stack.push(']');
            } else if(x == '{') {
                stack.push('}');
            } else if(stack.empty() || stack.pop() != x) {
                return false;
            }
        }
        return stack.empty();
    }

415字符串相加

题目要求

连接:415. 字符串相加 - 力扣(LeetCode)

给定两个字符串形式的非负整数 num1num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

示例 1:

输入:num1 = "11", num2 = "123"

输出:"134"


示例 2:

输入:num1 = "456", num2 = "77"

输出:"533"


示例 3:

输入:num1 = "0", num2 = "0"

输出:"0"


提示:

  • 1 <= num1.length, num2.length <= 104
  • num1num2 都只包含数字 0-9
  • num1num2 都不包含任何前导零

解题思路

要把两个字符串数字相加,再放进字符串中,返回字符串类型,那么就需要把这两个字符串分别取出来,然后求出两字符串的长度 - 1,定义为下标,从后往前进行遍历(arr.length()),同时遍历他们,每次都要取出当前下标的字符,然后当前下标字符再减去'0'下标字符,就是这个字符的的整型数字了,ASCLL表如图

再定义一个进位遍历carry,拿到当前下标的两字符数字(x + y + carry),定义一个StringBuilder类型,把(x + y + carry)放进这个类里面,再和carry相加 % 10,

carry = (x + y +carry)/ 10,每遍历一次下标,都要执行以上操作,当字符串遍历完时,逆转这个字符串,再返回这个字符串。

代码:

public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        //记录进位的变量
        int carry = 0;
        //记录字符串的下标
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        for(; n1 >= 0 || n2 >= 0 || carry != 0; n1--, n2--) {
            int c1 = (n1 < 0) ? 0 : (num1.charAt(n1) - '0');
            int c2 = (n2 < 0) ? 0 : (num2.charAt(n2) - '0');
            sb.append((c1 + c2 + carry) % 10);
            carry = (c1 + c2 + carry) / 10;
        }
        //翻转字符串
        return sb.reverse().toString();
    }
相关文章
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
32 6
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
21 0
|
1月前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
30天前
|
存储
leetcode2744. 最大字符串配对数目
leetcode2744. 最大字符串配对数目
16 0
|
30天前
|
机器学习/深度学习 NoSQL Shell
力扣刷题-翻转字符串
力扣刷题-翻转字符串
11 1
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
18 0
|
1月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
29 8
|
1月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
13 0
|
1月前
|
算法 安全 Java
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
21 0
|
2月前
|
机器学习/深度学习 人工智能 测试技术
【动态规划】【矩阵快速幂】LeetCode2851. 字符串转换
【动态规划】【矩阵快速幂】LeetCode2851. 字符串转换