一些算法题及答案
程序员文章站
2022-03-18 15:45:21
1. 两数之和 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例:给定 nums = [2, 7, 11, 15], target = 9... ......
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
/**
* 暴力枚举法
* @param nums
* @param target
* @return
*/
public static int[] twosum(int[] nums, int target) {
int lgn = nums.length;
for(int i = 0; i < lgn; i++){
for(int j = i + 1; j < lgn; j++){
if(nums[i] + nums[j] == target){
return new int[]{i, j};
}
}
}
return new int[0];
}
/**
* map 处理
* @param nums
* @param target
* @return
*/
public static int[] twosum1(int[] nums, int target) {
map<integer, integer> map = new hashmap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containskey(complement)) {
return new int[] { complement, nums[i] };
}
map.put(nums[i], i);
}
return new int[0];
}
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
/**
* 链表相应位置依次相加，最后处理进位
* @param l1
* @param l2
* @return
*/
public listnode addtwonumbers(listnode l1, listnode l2) {
listnode head = null;
listnode curr = null;
while (l1 != null || l2 != null){
if(l1 != null && l2 != null){
listnode node = new listnode(l1.val + l2.val);
if(curr == null && head == null) head = node;
curr = initnode(curr, node);
}else{
curr = initnode(curr, new listnode(l1 != null?l1.val:l2.val));
}
l1 = l1 != null?l1.next:null;
l2 = l2 != null?l2.next:null;
}
curr = head;
while (curr != null){
if(curr.val >= 10){
curr.val -= 10;
if(curr.next == null){
curr.next = new listnode(1);
}else {
curr.next.val += 1;
}
}
curr = curr.next;
}
curr = null;
return head;
}
public listnode initnode(listnode curr, listnode newnode){
if(curr != null){
curr.next = newnode;
}
curr = newnode;
return curr;
}
3. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 o(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
/**
* 使用两个排序数据组的归并过程
* 分别定义两个数组的遍历索引，每次对比提取相应数组的元素
* 不实际存储归并后的数据，
* 处理前半数元素即可
* @param nums1
* @param nums2
* @return
*/
public static double findmediansortedarrays(int[] nums1, int[] nums2) {
int lgn1 = nums1.length;
int lgn2 = nums2.length;
int alllgn = lgn1 + lgn2;
int middleindex = alllgn/2;
int middleleft = 0,middleright = 0;
int index1 = 0;
int index2 = 0;
int curr = 0;
for (int i = 0; i < middleindex + 1; i++) {
if(index1 < lgn1 && index2 < lgn2) {
if (nums1[index1] > nums2[index2]) {
curr = nums2[index2];
index2++;
} else {
curr = nums1[index1];
index1++;
}
}else if(index1 < lgn1){
curr = nums1[index1];
index1++;
}else if(index2 < lgn2){
curr = nums2[index2];
index2++;
}
if(i == middleindex - 1){
middleleft = curr;
}
if(i == middleindex){
middleright = curr;
}
}
if(alllgn%2 == 0){
return (middleleft + middleright)/2.0;
}else {
return middleright;
}
}
4. z 字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 z 字形排列。
比如输入字符串为 "leetcodeishiring" 行数为 3 时，排列如下：
l c i r e t o e s i i g e d h n
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："lciretoesiigedhn"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numrows);
示例 1:
输入: s = "leetcodeishiring", numrows = 3 输出: "lciretoesiigedhn"
示例 2:
输入: s = "leetcodeishiring", numrows = 4 输出: "ldreoeiiecihntsg" 解释: l d r e o e i i e c i h n t s g
/**
* 定义目标行数个链表，如示例，每次中间间隔的 numrows - 2 个列表逐个填充一个值
* 便利给定的字符串，依次处理，直到末尾
* @param s
* @param numrows
* @return
*/
public static string convert(string s, int numrows) {
if(numrows == 1){
return s;
}
string result = "";
if(numrows == 2){
result = "";
for (int i = 0; i < s.length(); i = i + 2) {
result += s.charat(i);
}
for (int i = 1; i < s.length(); i = i + 2) {
result += s.charat(i);
}
return result;
}
int middlecount = numrows - 2;
list[] all = new linkedlist[numrows];
for (int i = 0; i < numrows; i++) {
all[i] = new linkedlist<>();
}
int sindex = 0;
int step = 0;
while (sindex < s.length()){
for (int i = 0; i < numrows; i++) {
if(sindex == s.length()) break;
all[i].add(s.charat(sindex));
sindex++;
}
for (int j = numrows - 2; j > 0 ; j--) {
if(sindex == s.length()) break;
all[j].add(s.charat(sindex));
sindex++;
}
step = step + middlecount;
}
for (int i = 0; i < numrows; i++) {
for (int j = 0; j < all[i].size(); j++) {
result += all[i].get(j);
}
}
return result;
}
5. 整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123 输出: 321
示例 2:
输入: -123 输出: -321
示例 3:
输入: 120 输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
/**
* 数据范围判断
* @param x
* @return
*/
public static int reverse(int x) {
double result = 0;
while (x != 0){
result = result * 10 + x%10;
if (result > integer.max_value) return 0;
if (result < integer.min_value) return 0;
x = x/10;
}
return (int) result;
}
6. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
/**
* 转化为字符串，一次便利，首末对称位置对比
* @param x
* @return
*/
public static boolean ispalindrome(int x) {
string s = string.valueof(x);
int lgn = s.length();
for (int i = 0,j = lgn -1; i <= j; i++,j--){
if(s.charat(i) == s.charat(j)){
continue;
}else {
return false;
}
}
return true;
}
7. 盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
/**
* 枚举
* @param height
* @return
*/
public static int maxarea(int[] height) {
int area = 0, lgn = height.length;
if(lgn < 2) return 0;
for (int i = 0; i < lgn; i++) {
for (int i1 = i + 1; i1 < lgn; i1++) {
int tmparea = (height[i]>height[i1]?height[i1]:height[i]) * (i1 - i);
if(tmparea > area){
area = tmparea;
}
}
}
return area;
}
/**
* 双指针
* @param height
* @return
*/
public static int maxarea2(int[] height) {
int area = 0, lgn = height.length;
if(lgn < 2) return 0;
for (int i = 0, j = lgn - 1; i < j; ) {
int tmparea = (height[i]>height[j]?height[j]:height[i]) * math.abs(j - i);
if(tmparea > area){
area = tmparea;
i++;//正方向前进一步，避免反方向遍历时，重复比较
}else {
j--;//反方向前进一步，避免正方向遍历时，重复比较
}
}
return area;
}
8. 整数转罗马数字
罗马数字包含以下七种字符： i， v， x， l，c，d 和 m。
字符 数值 i 1 v 5 x 10 l 50 c 100 d 500 m 1000
例如， 罗马数字 2 写做 ii ，即为两个并列的 1。12 写做 xii ，即为 x + ii 。 27 写做 xxvii, 即为 xx + v + ii 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 iiii，而是 iv。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 ix。这个特殊的规则只适用于以下六种情况：
-
i可以放在v(5) 和x(10) 的左边，来表示 4 和 9。 -
x可以放在l(50) 和c(100) 的左边，来表示 40 和 90。 -
c可以放在d(500) 和m(1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
public static string inttoroman(int num) {
if(num > 3999) return "";
if(num/1000 > 0){
return dealqianwei(num);
}else if(num/100 > 0){
return dealbaiwei(num);
}else if(num/10 > 0){
return dealshiwei(num);
}else {
return dealgewei(num);
}
}
/**
* 千位
* @param num
* @return
*/
public static string dealqianwei(int num){
return countstr(num/1000, "m") + dealbaiwei(num%1000);
}
/**
* 百位
* @param num
* @return
*/
public static string dealbaiwei(int num){
int bc = num/100;
if(bc == 9) return "cm" + dealshiwei(num % 100);
if(bc == 4) return "cd" + dealshiwei(num % 100);
int fbc = num/500;
num = num%500;
return countstr(fbc, "d") + countstr(num/100, "c") + dealshiwei(num%100);
}
/**
* 十位
* @param num
* @return
*/
public static string dealshiwei(int num){
int tens = num/10;
if(tens == 9) return "xc" + dealgewei(num % 10);
if(tens == 4) return "xl" + dealgewei(num % 10);
int ftens = num/50;
num = num%50;
return countstr(ftens, "l") + countstr(num/10, "x") + dealgewei(num%10);
}
/**
* 个位
* @param num
* @return
*/
public static string dealgewei(int num){
if(num == 9) return "ix";
if(num == 4) return "iv";
if(num >= 5) return "v" + dealgewei(num % 5);
return countstr(num, "i");
}
public static string countstr(int count, string num){
if(count == 0) return "";
string result = "";
for (int i = 0; i < count; i++) {
result += num;
}
return result;
}
9. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
注意：利用上面的两数值和
public static list<list<integer>> threesum(int[] nums) {
if(nums == null || nums.length < 3) return new arraylist();
set<list<integer>> result = new hashset<>();
list<integer> numlist = new arraylist();
for (int num : nums) {
numlist.add(num);
}
for (integer num : numlist) {
list<integer> copy = new arraylist();
copy.addall(numlist);
copy.remove(num);
list<int[]> tmp = twosum(copy, -num);
if(tmp.size()>0){
for (int[] ints : tmp) {
list<integer> list = new arraylist(){{add(num);add(ints[0]);add(ints[1]);}};
collections.sort(list);
result.add(list);
}
}
}
return new arraylist(result);
}
public static list<int[]> twosum(list<integer> nums, int target) {
list<int[]> result = new arraylist();
map<integer, integer> map = new hashmap<>();
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums.get(i);
if (map.containskey(complement)) {
result.add(new int[] { complement, nums.get(i) });
}
map.put(nums.get(i), i);
}
return result;
}
10. 最接近的三数之和
给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
public static int threesumclosest(int[] nums, int target) {
int min = integer.max_value;
int ele1 = 0, ele2 = 0, ele3 = 0;
for (int i = 0; i < nums.length; i++) {
for (int i1 = 0; i1 < nums.length; i1++) {
if (i1 == i) continue;
for (int i2 = 0; i2 < nums.length; i2++) {
if (i2 == i1 || i2 == i) continue;
int sum = math.abs(nums[i] + nums[i1] + nums[i2] - target);
if (sum < min) {
min = sum;
ele1 = nums[i];
ele2 = nums[i1];
ele3 = nums[i2];
}
}
}
}
return ele1 + ele2 + ele3;
}
11. 缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
/**
* 数组操作
* @param nums
* @return
*/
public static int firstmissingpositive(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] < 0) continue;
if(nums[i] > max){
max = nums[i];
}
}
max = max == integer.max_value?max:max + 2;
for (int i = 1; i < max; i++) {
if(contains(nums, i)) continue;
return i;
}
return max + 1;
}
public static boolean contains(int[] nums, int ele){
for (int i = 0; i < nums.length; i++) {
if(nums[i] == ele) return true;
}
return false;
}
/**
* map操作
* @param nums
* @return
*/
public static int firstmissingpositive1(int[] nums) {
map<integer, integer> vs = new hashmap<>();
int max = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] < 0) continue;
if(nums[i] > max){
max = nums[i];
}
vs.put(nums[i], i);
}
max = max == integer.max_value?max:max + 2;
for (int i = 1; i < max; i++) {
if(vs.get(i) != null) continue;
return i;
}
return max + 1;
}
12. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
/**
* 分割
* @param height
* @return
*/
public static int trap(int[] height) {
//最大索引位置
int maxindex = findmax(height);
int lsubmaxindex = maxindex, rsubmaxindex = maxindex;
int area = 0;
//左边处理
while (lsubmaxindex > 0){
int tmpmax = lsubmaxindex;
lsubmaxindex = findmax(arrays.copyofrange(height, 0, tmpmax));
area += height[lsubmaxindex] * (tmpmax - lsubmaxindex - 1);
for (int i = lsubmaxindex + 1; i < tmpmax; i++) {
area -= height[i] * 1;
}
}
//右边处理
while (rsubmaxindex < height.length - 1){
int tmpmax = rsubmaxindex;
rsubmaxindex = tmpmax + findmax(arrays.copyofrange(height, tmpmax + 1, height.length)) + 1;
area += height[rsubmaxindex] * (rsubmaxindex - tmpmax - 1);
for (int i = tmpmax + 1; i < rsubmaxindex; i++) {
area -= height[i] * 1;
}
}
return area;
}
public static int findmax(int[] nums){
int max = 0, maxindex = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] > max){
max = nums[i];
maxindex = i;
}
}
return maxindex;
}
13. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
说明：
-
num1和num2的长度小于110。 -
num1和num2只包含数字0-9。 -
num1和num2均不以零开头，除非是数字 0 本身。 - 不能使用任何标准库的大数类型（比如 biginteger）或直接将输入转换为整数来处理。
public static string multiply(string num1, string num2) {
if(num1 == null || num2 == null || "".equals(num1) || "".equals(num2) || "0".equals(num1) || "0".equals(num2)) return string.valueof(0);
int lgn1 = num1.length(), lgn2 = num2.length();
int[] result = new int[lgn1 + lgn2];
int resultindex = result.length - 1;
for (int i = lgn1 - 1; i > -1 ; i--) {
int first = integer.parseint(string.valueof(num1.charat(i)));
int innerindex = 0;
for (int j = lgn2 - 1; j > -1 ; j--) {
int second = integer.parseint(string.valueof(num2.charat(j)));
int plus = first * second;
result[resultindex - innerindex] += plus%10;
if(plus >= 10) {
result[resultindex - innerindex - 1] += plus / 10;
}
innerindex++;
}
resultindex--;
}
//处理进位
stringbuilder sb = new stringbuilder();
for (int i = result.length - 1; i >= 0; i--) {
if(result[i]>=10) {
result[i - 1] += result[i]/10;
result[i] %= 10;
}
}
//提取有效位
boolean start = false;
for (int i = 0; i < lgn1 + lgn2 ; i++) {
if(!start && result[i] != 0){
start = true;
}
if(start){
sb.append(result[i]);
}
}
return sb.tostring();
}
14. 跳跃游戏 ii
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
/**
* 枚举遍历
* @param nums
* @return
*/
public static int jump(int[] nums) {
if(nums == null || nums.length == 1) return 0;
if(nums.length == 2) return 1;
int steps = integer.max_value/2;
int initstep = 1;
if(nums[0] >= nums.length - 1) return 1;
if(nums[0] == 0) return steps;
while (initstep <= nums[0]){
int subneedstep = jump(arrays.copyofrange(nums, initstep, nums.length));
if(subneedstep + 1 < steps){
steps = subneedstep + 1;
}
initstep++;
}
return steps;
}
/**
* 每次选择 和下一跳（最大跳值）之和最远的=》递归处理
* @param nums
* @return
*/
public static int jump2(int[] nums) {
if(nums == null || nums.length == 1) return 0;
if(nums.length == 2) return 1;
int steps = integer.max_value/2;
int initstep = nums[0];
if(nums[0] >= nums.length - 1) return 1;
if(nums[0] == 0) return steps;
int maxsum = 0;
int fromstep = 1;
while (initstep > 0){
if(initstep + nums[initstep] > maxsum){
fromstep = initstep;
maxsum = initstep + nums[initstep];
}
initstep--;
}
steps = 1 + jump2(arrays.copyofrange(nums, fromstep, nums.length));
return steps;
}
15. 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
/**
* 递归处理
* @param nums
* @return
*/
public static list<list<integer>> permute(int[] nums) {
list<list<integer>> result = new arraylist();
if(nums.length == 1) {
result.add(new arraylist(){{add(nums[0]);}});
return result;
}
for (int num : nums) {
int[] tmp = new int[nums.length - 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
if(num == nums[i]) continue;
tmp[index] = nums[i];
index++;
}
list<list<integer>> sub = permute(tmp);
sub.stream().foreach(item->item.add(num));
result.addall(sub);
}
return result;
}
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
/**
* 递归处理
* set 处理重复
* @param nums
* @return
*/
public static list<list<integer>> permuteunique(int[] nums) {
list<list<integer>> result = new arraylist();
if(nums.length == 1) {
result.add(new arraylist(){{add(nums[0]);}});
return result;
}
for (int num : nums) {
int[] tmp = new int[nums.length - 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
if(num == nums[i] && index == i) continue;
tmp[index] = nums[i];
index++;
}
list<list<integer>> sub = permuteunique(tmp);
sub.stream().foreach(item->item.add(num));
result.addall(sub);
}
set<list<integer>> sets = new hashset();
result.stream().foreach(item->sets.add(item));
return new arraylist(sets);
}
16. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
public static void rotate(int[][] matrix) {
int step = matrix.length;
int[][] tmp = new int[step][step];
for (int i = 0; i < step; i++) {
for (int j = 0; j < step; j++) {
tmp[i][j] = matrix[step - j - 1][i];
}
}
for (int i = 0; i < step; i++) {
for (int j = 0; j < step; j++) {
matrix[i][j] = tmp[i][j];
}
}
}
17. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
public static list<list<string>> groupanagrams(string[] strs) {
list<list<string>> result = new arraylist();
if(strs == null ||strs.length == 0) return result;
if(strs.length == 1){
result.add(arrays.aslist(strs[0]));
return result;
}
map<string, list<string>> maps = new hashmap();
for (string str : strs) {
char[] arr = str.tochararray();
arrays.sort(arr);
string sorted = arrays.tostring(arr);
if(maps.get(sorted) != null){
maps.get(sorted).add(str);
}else {
maps.put(sorted, new arraylist(){{add(str);}});
}
}
maps.remove(null);
return maps.values().stream().collect(collectors.tolist());
}
18. pow(x, n)
实现 ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10 输出: 1024.00000
示例 2:
输入: 2.10000, 3 输出: 9.26100
示例 3:
输入: 2.00000, -2 输出: 0.25000 解释: 2
-2
= 1/2
2
= 1/4 = 0.25
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
/**
* 快速降幂 避免递归过深造成栈溢出
* @param x
* @param n
* @return
*/
public static double power(double x, int n) {
if(!(x > -100 && x < 100)) return 0;
if(!(n <= integer.max_value && n >= integer.min_value)) return 0;
if(x == 0) return 0;
if(x == 1) return 1;
if(n == 0) return 1;
if(n == 1) return x;
if(n == -1) return 1/x;
if(n > 1 || n < -1){
double nextvalue = power(x, n / 2);
return (n % 2 == 0 ? 1 : (n > 0 ? x : 1/x)) * nextvalue * nextvalue;
}
return x;
}
19. 进制转换
进制转换 十进制 =》 62进制
这里所谓62进制是指采用0~9a~za~z等62个字符进行编码（按ascii顺序由小到大）。
public static string base = "0123456789abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
public static string transfer(int num) {
int scale = 62;
stringbuilder sb = new stringbuilder();
while (num > 0) {
//余数对照进制基本位 base 放到相应位置
sb.append(base.charat(num % scale));
//除处理下一进位
num = num / scale;
}
sb.reverse();
return sb.tostring();
}
20. 报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1 2. 11 3. 21 4. 1211 5. 111221
1 被读作 "one 1" ("一个一") , 即 11。11 被读作 "two 1s" ("两个一"）, 即 21。21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
public static string countandsay(int n) {if(n < 1 || n > 30) return "";int start = 1;string report = "1";string result = "";while (start < n ){result = "";for (int i = 0; i < report.length();) {int c = i;int count = 1;while (c + 1 < report.length()){if(report.charat(c) != report.charat(c + 1)){break;}count++;c++;}result += string.valueof(count) + string.valueof(report.charat(i));i = i + count;}report = result;start++;}return report;}
待续 。。。 。。。