剑指offer刷题笔记（八）
剑指 Offer 60. n个骰子的点数
- 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
动态规划
class Solution {
public double[] twoSum(int n) {
double[] res=new double[]{1/6d,1/6d,1/6d,1/6d,1/6d,1/6d};
//第几枚骰子
for(int i=2;i<=n;i++){
//初始化
double[] tmp=new double[5*i+1];
//当前点数总和遍历。
for(int j=0;j<res.length;j++){
//一到六点加到之前的点数总和上。
for(int k=0;k<6;k++){
tmp[j+k]+=res[j]/6;
}
}
res=tmp;
}
return res;
}
}
剑指 Offer 61. 扑克牌中的顺子
- 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
排序后，统计0的个数，顺子中不能出现两个一样的数，最大值减最小值之间的间隔在用0补上后不能大于4。可以选择手写排序
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int count=0;
for (int i = 0; i < nums.length; i++) {
if(nums[i]==0)
count++;
}
for(int i=count;i<4;i++){
if(nums[i]==nums[i+1])
return false;
}
return nums[4]-nums[count]<=4;
}
}
快排
private void sort(int[] nums,int start,int end) {
if(start>=end){
return;
}
int i=start;
int j=end;
int key=nums[start];
while(i<j){
while(i<j&&nums[i]<=key)
i++;
while(i<j&&nums[j]>=key)
j--;
if(i<j){
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
}
nums[start]=nums[i];
nums[i]=key;
sort(nums,start,i-1);
sort(nums,i+1,end);
}
剑指 Offer 62. 圆圈中最后剩下的数字
- 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
约瑟夫环，倒推。
class Solution {
public int lastRemaining(int n, int m) {
int res=0;
for(int i=2;i<n+1;i++){
res=(res+m)%i;
}
return res;
}
}
剑指 Offer 63. 股票的最大利润
- 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0||prices.length==1){
return 0;
}
int min=prices[0];
int max=prices[1]-min;
for(int i=2;i<prices.length;i++){
min=Math.min(prices[i-1],min);
int tmp=prices[i]-min;
max=Math.max(tmp,max);
}
return max>0?max:0;
}
}
优化
class Solution {
public int maxProfit(int[] prices) {
int min=Integer.MAX_VALUE;
int res=0;
for (int price:prices
) {
min=Math.min(min,price);
res=Math.max(res,price-min);
}
return res;
}
}
剑指 Offer 64. 求1+2+…+n
- 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
class Solution {
public int sumNums(int n) {
boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
return n;
}
}
剑指 Offer 65. 不用加减乘除做加法
- 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
class Solution {
public int add(int a, int b) {
int sum;
int tmp;
do{
//不带进位加法
sum=a^b;
//计算是否进位
tmp=(a&b)<<1;
a=sum;
b=tmp;
}while(b!=0);
return sum;
}
}
剑指 Offer 66. 构建乘积数组
- 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
class Solution {
public int[] constructArr(int[] a) {
if(a.length==0){
return new int[0];
}
int res[]=new int[a.length];
res[0]=1;
int tmp=1;
for(int i=1;i<a.length;i++){
res[i]=res[i-1]*a[i-1];
}
for(int i=a.length-2;i>=0;i--){
tmp*=a[i+1];
res[i]*=tmp;
}
return res;
}
}
剑指 Offer 67. 把字符串转换成整数
- 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
class Solution {
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if(c.length == 0) return 0;
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 1, sign = 1;
if(c[0] == '-') sign = -1;
else if(c[0] != '+') i = 0;
for(int j = i; j < c.length; j++) {
if(c[j] < '0' || c[j] > '9') break;
if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
}
作者：jyd
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solution/mian-shi-ti-67-ba-zi-fu-chuan-zhuan-huan-cheng-z-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
