剑指offer(九):数学
题目一：剪绳子
数学推导得到：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 33
public int cuttingRope(int n) {
if(n<=3)return n-1;
int a = n/3,b=n%3;
if (b==0)return (int) Math.pow(3,a);
if (b==1)return (int) Math.pow(3,a-1)*4;
return (int)Math.pow(3,a)*2;
}
题目二：剪绳子（考虑大数越界问题）
class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int b = n % 3, p = 1000000007;
long rem = 1, x = 3;
for(int a = n / 3 - 1; a > 0; a /= 2) {
if(a % 2 == 1) rem = (rem * x) % p;
x = (x * x) % p;
}
if(b == 0) return (int)(rem * 3 % p);
if(b == 1) return (int)(rem * 4 % p);
return (int)(rem * 6 % p);
}
}
题目三：数组中出现次数超过一半的数字
数组先进行排序，排序之后统计每一个数出现的次数，大于数组长度一半则其即为所求数字
public static int majorityElement(int[] nums) {
int flag = nums.length / 2;
Arrays.sort(nums);
int cur = nums[0];
int k = 0;
for (int num : nums) {
if (num == cur) {
k++;
if (k > flag)return cur;
} else {
cur = num;
k = 1;
}
}
return cur;
}
}
本题最优解，摩尔投票法
推论一： 若记 众数 的票数为 +1 ，非众数的票数为 -1 ，则一定有所有数字的票数和 >0 。
推论二： 若数组的前 a个数字的票数和 = 0，则数组剩余 (n?a)个数字的票数和一定仍>0，即后 (n?a) 个数字的 众数仍为 xx 。
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
题目四：1～n 整数中 1 出现的次数
class Solution {
public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while(high != 0 || cur != 0) {
if(cur == 0) res += high * digit;
else if(cur == 1) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
题目五：数字序列中某一位的数字
class Solution {
//1、第一步：得到n对应的位数
public int findNthDigit(int n) {
int digit = 1;
//因为数值比较大，所以要在其中使用long
long start = 1;
long count = 9;
while (n > count) { // 1.
n -= count;
start *= 10;
digit += 1;
count = digit * start * 9;
}
//2、第二步：得到n对应的数字
long num = start + (n - 1) / digit;
//3、返回第n位对应的数字
return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
}
}
题目六：和为 s 的连续正数序列
方法一：自己的笨方法、执行效率低和内存占用很高；
class Solution {
public int[][] findContinuousSequence(int target) {
int k = target/2;
//创建一个数组长度可变化，里边嵌套一个数组，来存数字变量
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
for (int i = 1; i <= k; i++) {
ArrayList<Integer> cur = new ArrayList<>();
int flag = target;
int j = i;
while (flag>0&&j<=k+1){
cur.add(j);
flag-=j;
j++;
}
if (flag==0)res.add(cur);
}
// 将ArrayList<ArrayList<Integer>>转化为List<int[]>
int m = res.size();
List<int[]> intsres = new ArrayList<>();
for (int i = 0; i < m; i++) {
int[] tem = new int[res.get(i).size()];
for (int j = 0; j < res.get(i).size(); j++) {
tem[j] = res.get(i).get(j);
}
intsres.add(tem);
}
//二维 List<int[]> 转化成一个二维数组 int[][]
return intsres.toArray(new int[0][]);
}
}
问题：怎么把二维 List<int[]> 转化成一个二维数组 int[][]；
return intsres.toArray(new int[0][]);
方法二：求和公式
class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1;
double j = 2.0;
List<int[]> res = new ArrayList<>();
while(i < j) {
j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
if(j == (int)j) {
int[] ans = new int[(int)j - i + 1];
for(int k = i; k <= (int)j; k++)
ans[k - i] = k;
res.add(ans);
}
i++;
}
return res.toArray(new int[0][]);
}
}
方法三：滑动窗口（双指针）–类似于方法一，不过效率很高
class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1, j = 2, s = 3;
List<int[]> res = new ArrayList<>();
while(i < j) {
if(s == target) {
int[] ans = new int[j - i + 1];
for(int k = i; k <= j; k++)
ans[k - i] = k;
res.add(ans);
}
if(s >= target) {
s -= i;
i++;
} else {
j++;
s += j;
}
}
return res.toArray(new int[0][]);
}
}
题目七：圆圈中最后剩下的数字
class Solution {
public int lastRemaining(int n, int m) {
int x = 0;
for (int i = 2; i <= n; i++) {
x = (x + m) % i;
}
return x;
}
}
题目八：构建乘积数组
分别计算上三角和下三角两个部分
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if(len == 0) return new int[0];
int[] b = new int[len];
b[0] = 1;
int tmp = 1;
for(int i = 1; i < len; i++) {
b[i] = b[i - 1] * a[i - 1];
}
for(int i = len - 2; i >= 0; i--) {
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
模拟
题目九：顺时针打印矩阵
思想如下，自己做的时候思想差不多，但是问题在于不知道自己超过边界怎么处理，怎么结束循环？
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
int[] res = new int[(r + 1) * (b + 1)];
while(true) {
for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right
if(++t > b) break;
for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom
if(l > --r) break;
for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left
if(t > --b) break;
for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top
if(++l > r) break;
}
return res;
}
}
i++：是先把i拿出来使用，然后再+1
++i ：是先把i+1，然后再拿出来使用
题目十：栈的压入、弹出序列
模拟入栈出栈，当栈顶元素不等于出栈序列的第一个元素时，继续入栈
当栈顶元素等于出栈序列的第一个元素，则出栈，最后进行判断
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int k = 0;
for (int i : pushed) {
stack.push(i);
while (!stack.empty()&&stack.peek()==popped[k]){
stack.pop();
k++;
}
}
return stack.empty();
}
}