表示数值的字符串
请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。
- 正则表达式处理.(也可以用逻辑处理，但太复杂了)
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1 次
+ ： 重复 1 ~ n 次
* ： 重复 0 ~ n 次
. ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
\\s ：空白
public boolean isNumeric (String str) {
if (str == null || str.length() == 0)
return false;
return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}
public boolean isNumeric (String str) {
//正则表达式匹配
String pattern = "(\\s)*[+-]?((\\d+(\\.(\\d+)?)?)|(\\.\\d+))([Ee][+-]?\\d+)?(\\s)*";
//根据匹配值返回
return Pattern.matches(pattern, str);
}
数字序列中的某一位数字
数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
- 感觉像数学题
- 先将问题分解
a. 字符串的第index位上的数。先确定这个位上数是在哪个数里面。有点抽象，比如找的那个数是2，这个2是123里面的2，还是12里面的2。问题转变为，这个index位所在的数在哪。
b. 可以根据位数来判断。位为1的数有10个，位为2的数有90个......这样就可以判断出这个数的大致位置了。问题转变为，在确定几位数的一连串数据中，第index位所在的那个具体的数是谁。
c. 确定已经是几位数了，可以确定在index位之前，有多少个这样的数。那当前这个具体的数就能确定了。剩下的就是判断index位是在这个数中的第几个，取余即可。
public int getDigitAtIndex(int index) {
if (index < 0)
return -1;
int place = 1; // 1 表示个位，2 表示 十位...
while (true) {
int amount = getAmountOfPlace(place);
int totalAmount = amount * place;
if (index < totalAmount)
return getDigitAtIndex(index, place);
index -= totalAmount;
place++;
}
}
/**
* place 位数的数字组成的字符串长度
* 10, 90, 900, ...
*/
private int getAmountOfPlace(int place) {
if (place == 1)
return 10;
return (int) Math.pow(10, place - 1) * 9;
}
/**
* place 位数的起始数字
* 0, 10, 100, ...
*/
private int getBeginNumberOfPlace(int place) {
if (place == 1)
return 0;
return (int) Math.pow(10, place - 1);
}
/**
* 在 place 位数组成的字符串中，第 index 个数
*/
private int getDigitAtIndex(int index, int place) {
int beginNumber = getBeginNumberOfPlace(place);
int shiftNumber = index / place;
String number = (beginNumber + shiftNumber) + "";
int count = index % place;
return number.charAt(count) - '0';
}
把数字翻译成字符串
给定一个数字，按照如下规则翻译成字符串：1 翻译成“a”，2 翻译成“b”... 26 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 abbeh，lbeh，aveh，abyh，lyh。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
- 典型动态规划。
- 每判断一个数，到这个数为止，可能的情况进行计数。有2种可能性。
a. 当前这个数单个看待，前一个数有几种情况，那这个数就有几种情况。因为就是在前一个排列后，加一个新的数。
b. 当前这个数联合看待。那需要和前一个数联动，先判断是否可以联合看待，即是否符合26这个条件。如果可以，那把除去前一个数的可能性加上即可。可以理解为，出去前一个数后，后面再加一个数。
c. 特别考虑0的情况，因为如果当前数是3，然后前一个数是0，此时03和3组合是一样的。
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0)
dp[i] += dp[i - 1];
if (s.charAt(i - 2) == '0')
continue;
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26)
dp[i] += dp[i - 2];
}
return dp[n];
}
扑克牌顺子
五张牌，其中大小鬼为癞子，牌面为 0。判断这五张牌是否能组成顺子。
- 数学题
- 先确定一个基准，这个基准的用处是，判断答案。
- 在提供的题解里面，这个基准是癞子的数量。如果癞子的数量大于等于0，即代表可以有顺子。
- 根据这个基准，在判断数与下一个数之间的关系的时，如果连续，不管。如果不连续，癞子数减少，表示将其补全。如果相等，直接范围false。
public boolean isContinuous(int[] nums) {
if (nums.length < 5)
return false;
Arrays.sort(nums);
// 统计癞子数量
int cnt = 0;
for (int num : nums)
if (num == 0)
cnt++;
// 使用癞子去补全不连续的顺子
for (int i = cnt; i < nums.length - 1; i++) {
if (nums[i + 1] == nums[i])
return false;
cnt -= nums[i + 1] - nums[i] - 1;
}
return cnt >= 0;
}
求 1+2+3+...+n
要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A ? B : C。
- 递归
- 不能用乘除， 没说不能用加减，纯加减计算，不能用循环、判断，一眼递归。问题转变为，递归条件怎么写。
- &&存在短路计算，用这个实现递归条件。
public int Sum_Solution(int n) {
int sum = n;
boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0);
return sum;
}
https://github.com/CyC2018/CS-Notes/blob/master/notes/64.%20%E6%B1%82%201+2+3+...+n.md
不用加减乘除做加法
写一个函数，求两个整数之和，要求不得使用 +、-、、/ 四则运算符号。*
- 加减乘除都不让用，然后计算加法。肯定是位运算了，问题就是怎么位运算。
a ^ b ： 没有考虑进位的情况下两数的和
(a & b) << 1 ： 进位。
n&(n−1) ： 将n的二进制中最低位由1变成0
x^x^y^y^z^k = z^k
-
当没有进位，只有总和计算的时候，结束递归。
牛客题解动图截图1.png
牛客题解动图截图2.png
public int Add(int a, int b) {
return b == 0 ? a : Add(a ^ b, (a & b) << 1);
}
把字符串转换成整数
将一个字符串转换成一个整数，字符串不是一个合法的数值则返回 0，要求不能使用字符串转换整数的库函数。
- 字符串比较。
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (i == 0 && (c == '+' || c == '-')) /* 符号判定 */
continue;
if (c < '0' || c > '9') /* 非法输入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
