【每日一题】1945. 字符串转化后的各位数字之和

题目描述

给你一个由小写字母组成的字符串 s ，以及一个整数 k 。
首先，用字母在字母表中的位置替换该字母，将 s 转化为一个整数（也就是，‘a’ 用 1 替换，‘b’ 用 2 替换，… ‘z’ 用 26 替换）。接着，将整数转换为其各位数字之和 。共重复 转换 操作 k 次 。

例如，如果 s = “zbax” 且 k = 2 ，那么执行下述步骤后得到的结果是整数 8 ：

转化：“zbax” ➝ “(26)(2)(1)(24)” ➝ “262124” ➝ 262124
转换 #1：262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
转换 #2：17 ➝ 1 + 7 ➝ 8
返回执行上述操作后得到的结果整数。

题目解析

该题按题目要求，可以分为两个步骤：
【转换为整数】：该步可以使用ascii码判断。
【转为数字之和】：循环使用除法、取余操作

class Solution {public int getLucky(String s, int k) {StringBuffer a = new StringBuffer();for(char c : s.toCharArray()){a.append(c - 'a' + 1);}//第一次转换：字符串 -> 数字int b = 0;for(char c : a.toString().toCharArray()){b += (c - 48);}k--;// 数字 -> 数字while(k-- > 0){int temp = 0;while(b != 0){temp += b % 10;b /= 10;}b = temp;}return b;        }
}

【leetcode hot 100】34. 在排序数组中查找元素的第一个和最后一个位置

题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

题目解析

【二分法】：该题【非递减】、【查找】可以分析出使用二分法找到target。并在target的左右两侧找到开始位置和结束位置的边界。

class Solution {public int[] searchRange(int[] nums, int target) {if(nums.length == 0) return new int[]{-1, -1};int index = binary(nums, target);if(index == -1) return new int[]{-1, -1};int begin = index;for(; begin >= 0; begin--){if(nums[begin] != target) break;}begin++;int end = index;for(; end < nums.length; end++){if(nums[end] != target) break;}end--;return new int[]{begin, end};}public int binary(int[] nums, int target){int left = 0, right = nums.length;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] == target){return mid;}if(nums[mid] < target) left = mid + 1;else right = mid;}return -1;}
}

【代码随想录】30. 二叉搜索树的最小绝对差

题目描述

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

题目解析

【二叉搜索树】：重要性质是中序遍历的结果是递增的序列。
所以首先进行中序遍历，计算相邻点的差值。

class Solution {int min = Integer.MAX_VALUE;int pre = -1;public int getMinimumDifference(TreeNode root) {inorder(root);return min;}public void inorder(TreeNode root){if(root.left != null) inorder(root.left);if(pre != -1){min = Math.min(min,root.val - pre);}pre = root.val;if(root.right != null) inorder(root.right);}
}