【LeetCode题解】2859. 计算 K 置位下标对应元素的和+938. 二叉搜索树的范围和+1028. 从先序遍历还原二叉树(三种方法:栈+递归+集合)

本文主要是介绍【LeetCode题解】2859. 计算 K 置位下标对应元素的和+938. 二叉搜索树的范围和+1028. 从先序遍历还原二叉树(三种方法:栈+递归+集合),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

      • [2859. 计算 K 置位下标对应元素的和](https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/)
          • 思路:
      • [938. 二叉搜索树的范围和](https://leetcode.cn/problems/range-sum-of-bst/)
          • 思路:
            • 写法一:在中间累加
            • 写法二:在最后累加
      • 1028. 从先序遍历还原二叉树(三种方法:栈+递归+集合)
    • 一、栈+ while迭代
      • 1.思路
      • 2.代码
    • 二、递归法
      • 1.思路
      • 2.代码
    • 三、集合存储
      • 1.思路
      • 2.代码

2859. 计算 K 置位下标对应元素的和

在这里插入图片描述

思路:

遍历输入列表,对于满足特定条件的元素做一些操作并将结果累加起来。其中,bitCount 辅助方法用于计算一个整数的二进制表示中有多少个 1。

  1. 遍历给定列表 nums 中的所有元素,用索引 i 表示当前元素所在位置。
  2. 对于每个索引 i,调用辅助方法 bitCount(i),返回它的二进制表示中 1 的个数。
  3. 检查步骤 2 中得到的 1 的个数是否等于给定值 k
  4. 如果匹配,则将当前索引 i 所在位置上的值加入到答案 ans 中。
  5. 循环结束后,返回 ans 作为最终结果。
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {int ans = 0;for (int i = 0; i < nums.size(); ++i) {if (bitCount(i) == k) {ans += nums.get(i);}}return ans;
}/*** 计算一个整数的二进制表示中有多少个1* @param x 要计算的整数* @return 二进制中1的个数*/
public int bitCount(int x) {int cnt = 0;while (x != 0) {cnt += (x % 2);x /= 2;}return cnt;
}

938. 二叉搜索树的范围和

在这里插入图片描述

思路:

1.在二叉搜索树中:左子树的结点都小于根节点,右子树的结点都大于根节点,每个结点法左右子树均要符合二叉搜索树

2.如果根节点的值大于hight,就排除右树,只在左树中查找

3.如果根节点的值小于low,就排除左树,只在右树中查找

4.如果正好在两者之间,则左树右树都要考虑,将根节点的值和递归的结果累加

写法一:在中间累加
    //[938. 二叉搜索树的范围和]-写法二
//public int rangeSumBST2(TreeNode root, int low, int high) {if (root==null){return 0;}int x = root.val;int sum = low<=x && x<=high?x:0;//根节点的值如果在范围内,返回根节点的值,否则就返回0,相当于排除了不在范围内的值if(x>low){sum+=rangeSumBST2(root.left,low,high);}if (x<high){sum+=rangeSumBST2(root.right,low,high);}return sum;}
写法二:在最后累加
    //[938. 二叉搜索树的范围和]public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}int x = root.val;if (x > high) {return rangeSumBST(root.left, low, high);//右树不在范围内,只需要递归左树}if (x < low) {return rangeSumBST(root.right, low, high);//左树不在范围内,只需要递归左树}return x + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);//左右子树都可能}

1028. 从先序遍历还原二叉树(三种方法:栈+递归+集合)


在这里插入图片描述
在这里插入图片描述

一、栈+ while迭代

1.思路

1.遍历整个字符串,从0开始,根节点在第0层
2.用level记录层数,每遇到一个-字符,当前层数+1
3.用val记录要插入的结点的值,遍历取到的数字,通过字符运算得到值。
4.找到当前要插入结点的父结点,栈的大小要小于当前层数
5.如果节点只有一个子节点,那么保证该子节点为左子节点。
6.将创建的新结点入栈
7.除了根节点,其他子节点全部出栈,返回根节点

2.代码

    public TreeNode recoverFromPreorder(String traversal) {Stack<TreeNode> stack = new Stack<>();//用栈来存储结点for (int i = 0; i < traversal.length(); ) {//遍历整个字符串,从0开始,根节点在第0层int level = 0;//记录当前层数while (traversal.charAt(i) == '-') {//每遍历到一个-,层数累加level++;i++;}int val = 0;//查看当前要插入结点的数字while (i < traversal.length() && traversal.charAt(i) != '-') {//当前的字符是数字,并且未超过字符串val = val * 10 + (traversal.charAt(i) - '0');//根据字符的相加,遍历字符串找数字时 只能一个数字一个数字的转,// 但是字符串中连续的数字是一个多位数,需要前面的数字*10变高位,再加上后面的数,// 成为一个数,作为新结点的值i++;}while (stack.size() > level) {stack.pop();//找到当前要插入结点的父结点}TreeNode node = new TreeNode(val);//创建新结点if (!stack.isEmpty()) {//如果节点只有一个子节点,那么保证该子节点为左子节点。if (stack.peek().left == null) {stack.peek().left = node;} else {stack.peek().right = node;}}stack.add(node);//入栈}while (stack.size() > 1) {stack.pop();//要返回根节点,出到栈只有一个结点}return stack.pop();}

二、递归法

1.思路

1.利用helper函数,根据字符和对应深度创建结点,还原二叉树
2.每遇到-字符,层数加一
3.如果遍历的深度和获取到的深度不一致,返回空
4.当深度等于层数时,下一个结点的位置从index + level开始
5.通过字符运算获取数字,同时创建结点
6.根节点的左树调用helper函数递归,如果左子节点是空,那么右子节点肯定也是空的
7.如果根节点的左树不为空,要想添加结点,递归右树。
8.最终返回根节点

2.代码

    //102. 二叉树的层序遍历---递归写法int index = 0;//index记录遍历到字符串的哪个位置public TreeNode recoverFromPreorder3(String traversal) {return helper(traversal,0);}public TreeNode helper(String s, int depth) {//helper函数用来创建二叉树int level = 0;//记录层数while (index + level < s.length() && s.charAt(index + level) == '-') {level++;}//如果遍历的深度和获取到的深度不一致,返回空if (level != depth){return null;}int next = index + level;//获取数字while (next < s.length() && s.charAt(next) != '-')next++;int val = Integer.parseInt(s.substring(index + level, next));index = next;//创建结点TreeNode root = new TreeNode(val);root.left = helper(s, depth + 1);if (root.left == null) {//如果左子节点是空,那么右子节点肯定也是空的root.right = null;} else {root.right = helper(s, depth + 1);}return root;}

三、集合存储

1.思路

1.使用正则匹配把字符串S拆成不同的数字存进数组中,用集合list来存储结点
2.将根节点添加到list中,层数从1开始,不包括根节点
3.数组存储的位置不为空时,根据转换的值创建结点
4.将结点加入到集合中
5.获取父结点,插入结点,并从新设置层数,果满了,层数加一
6.最终返回根节点

2.代码

    //102. 二叉树的层序遍历--正则匹配public TreeNode recoverFromPreorder2(String traversal) {String[] valus = traversal.split("-");//使用正则匹配把字符串S拆成不同的数字,用集合list来存储结点List<TreeNode> list = new ArrayList<>();list.add(new TreeNode(Integer.valueOf(valus[0])));//根节点//根节点添加到list中int level = 1;//层数层1开始,不包括根节点for (int i = 1; i < valus.length; i++) {if (!valus[i].isEmpty()) {//数组存储的位置不为空TreeNode node = new TreeNode(Integer.valueOf(valus[i]));//根据转化的值,创建结点//因为是前序遍历,每层我们只需要存储一个结点即可,这个节点值有可能//会被覆盖,如果被覆盖了说明这个节点以及他的子节点都以及遍历过了,//所以不用考虑被覆盖问题list.add(level, node);//将结点加入到集合中TreeNode parent = list.get(level - 1);//获取父结点,插入结点,并从新设置层数if (parent.left == null) {parent.left = node;} else {parent.right = node;}level = 1;} else {level++;//如果满了,层数加一}}return list.get(0);}

点击移步博客主页,欢迎光临~

偷cyk的图

这篇关于【LeetCode题解】2859. 计算 K 置位下标对应元素的和+938. 二叉搜索树的范围和+1028. 从先序遍历还原二叉树(三种方法:栈+递归+集合)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/771627

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;