和数字相关算法题
移动零
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。>输入: [0,1,0,3,12] >输出: [1,3,12,0,0]
class Solution {
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0) nums[idx++] = num;
}
while (idx < nums.length) {
nums[idx++] =0;
}
}
}3. 接雨水(字节爱出)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
>输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] >输出：6 >解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。>输入：height = [4,2,0,3,2,5] >输出：9
class Solution {
public int trap(int[] height) {
int min = 0, max = 0;
int l = 0, r = height.length - 1;
int res = 0;
while(l < r) {
min = height[height[l] < height[r] ? l++ : r--];
max = Math.max(max, min);
res += max - min;
}
return res;
}
}4. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
>输入：nums = [1,2,3] >输出：[1,3,2]>输入：nums = [3,2,1] >输出：[1,2,3]>输入：nums = [1,1,5] >输出：[1,5,1]>输入：nums = [1] >输出：[1]
//源于离散数学及其应用的算法：（以3 4 5 2 1 为例）
//从后往前寻找第一次出现的正序对：（找到 4,5）
//之后因为从5 开始都是逆序，所以把他们反转就是正序：3 4 1 2 5
//之后4 的位置应该是：在它之后的，比他大的最小值（5）
//交换这两个值：得到 3 5 1 2 4
// 对于初始即为逆序的序列，将在反转步骤直接完成
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
if (len < 2) return;
int i = len - 1;
while (i > 0 && nums[i - 1] >= nums[i])
i--; // 从后向前找第一个正序，这里最后i指向的是逆序起始位置
reverse(nums, i, len - 1); // 翻转后面的逆序区域，使其变为正序
if (i == 0) return;
int j = i - 1;
while(i < len && nums[j] >= nums[i])
i++; // 找到第一个比nums[j]大的元素，交换即可
// 交换
swap(nums, i, j);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}5. 孩子们的游戏
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
>输入 >5,3 >返回值 >3
约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。
public int LastRemaining_Solution(int n, int m) {
if (n == 0) /* 特殊输入的处理 */
return -1;
if (n == 1) /* 递归返回条件 */
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}165. 比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。>输入：version1 = "1.01", version2 = "1.001" >输出：0 >解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1">输入：version1 = "1.0", version2 = "1.0.0" >输出：0 >解释：version1 没有指定下标为 2 的修订号，即视为 "0">输入：version1 = "0.1", version2 = "1.1" >输出：-1 >解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2>输入：version1 = "1.0.1", version2 = "1" >输出：1>输入：version1 = "7.5.2.4", version2 = "7.5.3" >输出：-1
class Solution {
public int compareVersion(String version1, String version2) {
String[] a1 = version1.split("\\.");
String[] a2 = version2.split("\\.");
for (int n = 0; n < Math.max(a1.length, a2.length); n++) {
int i = n < a1.length ? Integer.valueOf(a1[n]) : 0 ;
int j = n < a2.length ? Integer.valueOf(a2[n]) : 0 ;
if (i < j)
return -1;
else if (i > j)
return 1;
return 0;
}
}
}209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
>输入：target = 7, nums = [2,3,1,2,4,3] >输出：2 >解释：子数组 [4,3] 是该条件下的长度最小的子数组。>输入：target = 4, nums = [1,4,4] >输出：1>输入：target = 11, nums = [1,1,1,1,1,1,1,1] >输出：0
class Solution {
public int minSubArrayLen(int s, int[] nums) {
// 滑动窗口
int i = 0;
int sum = 0;
int len = 0;
for (int j = 0; j < nums.length; j++){
sum += nums[j];
// 注意这个骚条件
while (sum >= s){
len = len == 0 ? j - i + 1 : Math.min(len, j - i + 1);
// 滑动
sum -= nums[i++];
}
}
return len;
}
}628. 三个数的最大乘积
给你一个整型数组
nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积。>输入：nums = [1,2,3] >输出：6>输入：nums = [1,2,3,4] >输出：24>输入：nums = [-1,-2,-3] >输出：-6
class Solution {
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE,min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}
}179. 最大数
给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
>输入：nums = [10,2] >输出："210">输入：nums = [3,30,34,5,9] >输出："9534330">输入：nums = [1] >输出："1">输入：nums = [10] >输出："10"
class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0)
return "";
int n = nums.length;
String[] ss = new String[n];
for (int i = 0; i < n; i++)
ss[i] = nums[i] + "";
Arrays.sort(ss, (a, b) -> (b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for (String s : ss)
sb.append(s);
String res = sb.charAt(0) == '0' ? "0" : sb.toString();
return res;
}
}306. 累加数
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
>输入: "112358" >输出: true >解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8>输入: "199100199" >输出: true >解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
class Solution {
public boolean isAdditiveNumber(String num) {
return dfs(num, 0, 0, num.length(), 0, 0);
}
// num:原始字符串 idx：当前处理的下标 sum：上一层的两数和
// len：字符串长度 pre：前一个数 k：当前已经处理数的个数
private boolean dfs(String num, int idx, long sum, int len, long pre, int k) {
// 达到末尾，判断是否存在至少3个数
if (idx == len)
return k > 2;
// [idx, i] 代表当前尝试的数
// 为了避免溢出long 使用结论：不存在符合条件的数，其长度超过原始字符串一半
for (int i = idx + 1; i <= len && i - idx <= len / 2; i++) {
// 剪枝：以0开头且不是单纯的0的数不符合题意
if (i != idx + 1 && num.charAt(idx) == '0')
return false;
long cur = Long.parseLong(num.substring(idx, i));
// 剪枝：校验两数和 不等于当前数
if (k >= 2 && cur != sum)
continue;
// 继续dfs
if (dfs(num, i, pre + cur, len, cur, k + 1))
return true;
}
return false;
}
}402. 移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。>输入: num = "1432219", k = 3 >输出: "1219" >解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。>输入: num = "10200", k = 1 >输出: "200" >解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。>输入: num = "10", k = 2 >输出: "0" >解释: 从原数字移除所有的数字，剩余为空就是0。
class Solution {
public String removeKdigits(String num, int k) {
if (num.length() == k)
return "0";
StringBuilder s = new StringBuilder(num);
for (int i = 0; i < k; i++) {
int idx = 0;
for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++)
idx = j;
s.delete(idx, idx + 1);
while (s.length() > 1 && s.charAt(0) == '0')
s.delete(0, 1);
}
return s.toString();
}
}求一个数的平方根，精度0.01
public static void main(String[] args) {
int a = 5;
double l = 0, r = a;
while (l <= r) {
double m = l + (r - l) / 2;
double val = m * m - a;
if (Math.abs(val) <= 0.01) {
System.out.println(m);
return;
}
else if (val > 0.01)
r = m;
else
l = m;
}
}本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论