[TOC]
给定一个整数，将其转化为7进制，并以字符串形式输出。
示例 1:
输入: 100 输出: "202" 示例 2:
输入: -7 输出: "-10"
class Solution {
public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean flag = num < 0;
if (flag) {
num = -num;
}
while (num > 0) {
sb.append(num % 7);
num /= 7;
}
String ret = sb.reverse().toString();
return flag ? "-" + ret : ret;
}
}给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 给定的数确保在32位有符号整数范围内。 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。 示例 1：
输入: 26
输出: "1a" 示例 2：
输入: -1
输出: "ffffffff"
class Solution {
public String toHex(int num) {
if (num == 0) {
return "0";
}
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
StringBuilder sb = new StringBuilder();
while (num != 0) {
sb.append(map[num & 15]);
num >>>= 4;
}
return sb.reverse().toString();
}
}给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1 输出: "A" 示例 2:
输入: 28 输出: "AB" 示例 3:
输入: 701 输出: "ZY"
class Solution {
public String convertToTitle(int n) {
if (n == 0) {
return "";
}
n--;
return convertToTitle(n / 26) + (char) (n % 26 + 'A');
}
}给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。 示例 2:
输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零. 说明: 你算法的时间复杂度应为 O(log n) 。
尾部的 0 由 2 * 5 得来，2 的数量明显多于 5 的数量，因此只要统计有多少个 5 即可。
对于一个数 N，它所包含 5 的个数为：N/5 + N/52 + N/53 + ...，其中 N/5 表示不大于 N 的数中 5 的倍数贡献一个 5，N/52 表示不大于 N 的数中 52 的倍数再贡献一个 5 ...。
class Solution {
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
}统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
class Solution {
public int countPrimes(int n) {
boolean[] notPrimes = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; ++i) {
if (notPrimes[i]) {
continue;
}
count++;
for (long j = (long) i * i; j < n; j += i) {
notPrimes[(int) j] = true;
}
}
return count;
}
}int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1" 输出: "100" 示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 "0" ，就都不含前导零。
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, count = 0;
StringBuilder str = new StringBuilder();
while(count == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
count++;
}
if (j >= 0 && b.charAt(j--) == '1') {
count++;
}
str.append(count % 2);
count /= 2;
}
return str.reverse().toString();
}
}给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder stb = new StringBuilder();
int total = 0, i = num1.length() - 1, j = num2.length() - 1;
while (total == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
stb.append((x + y + total) % 10);
total = (x + y + total) / 10;
}
return stb.reverse().toString();
}
}给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如:
输入: [1,2,3]
输出: 2
说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
[1,2,3] => [2,2,3] => [2,2,2]
这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：
设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，也就是把这两个数移动到中位数的移动次数。
设数组长度为 N，则可以找到 N/2 对 a 和 b 的组合，使它们都移动到 m 的位置。
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int move = 0;
int left = 0, right = nums.length - 1;
while (left <= right) {
move += nums[right] - nums[left];
left++;
right--;
}
return move;
}
}先进行快速选择找到中位数，然后遍历数组减去中位数即可。
public int minMoves2(int[] nums) {
int move = 0;
int median = findKthSmallest(nums, nums.length / 2);
for (int num : nums) {
move += Math.abs(num - median);
}
return move;
}
private int findKthSmallest(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
}
if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] nums, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (nums[++i] < nums[l] && i < h) ;
while (nums[--j] > nums[l] && j > l) ;
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3] 输出: 3 示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}public int majorityElement(int[] nums) {
int cnt = 0, majority = nums[0];
for (int num : nums) {
majority = (cnt == 0) ? num : majority;
cnt = (majority == num) ? cnt + 1 : cnt - 1;
}
return majority;
}给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16 输出：True 示例 2：
输入：14 输出：False
平方序列：1,4,9,16,..
间隔：3,5,7,...
间隔为等差数列，使用这个特性可以得到从 1 开始的平方序列。
class Solution {
public boolean isPerfectSquare(int num) {
int sum1 = 1;
while(num > 0) {
num -= sum1;
sum1 += 2;
}
return num == 0;
}
}给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27 输出: true 示例 2:
输入: 0 输出: false 示例 3:
输入: 9 输出: true 示例 4:
输入: 45 输出: false
int范围类3的幂次数最大是1162261467。
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
}
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4] 输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] out = new int[n];
Arrays.fill(out, 1);
int left = 1;
for (int i = 1; i < n; ++i) {
left *= nums[i - 1];
out[i] *= left;
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
out[i] *= right;
}
return out;
}
}给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:
输入: [1,2,3] 输出: 6 示例 2:
输入: [1,2,3,4] 输出: 24 注意:
给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
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);
}
}给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123 输出：321 示例 2：
输入：x = -123 输出：-321 示例 3：
输入：x = 120 输出：21 示例 4：
输入：x = 0 输出：0
import java.util.*;
public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public int reverse (int x) {
// write code here
int ans = 0, f = 1;
if (x < 0) {
f = -1;
x = -x;
}
while (x != 0) {
if ((x > 0 && (Integer.MAX_VALUE - x % 10) / 10 < ans) || (x < 0 && (Integer.MIN_VALUE + x % 10) / 10 > -ans)) {
return 0;
}
ans = ans * 10 + x % 10;
x /= 10;
}
return ans * f;
}
}给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121 输出：true 示例 2：
输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3：
输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。 示例 4：
输入：x = -101 输出：false
提示：
-231 <= x <= 231 - 1
class Solution {
public boolean isPalindrome(int x) {
if (x == 0) {
return true;
}
int temp = x;
if (x < 0 || x % 10 == 0) {
return false;
}
int right = 0;
while (x != 0) {
right = right * 10 + x % 10;
x /= 10;
}
return temp == right;
}
}输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
用返回一个整数列表来代替打印
n 为正整数
此题应该主要考察大数越界的情况，详解见leetcode
class Solution {
int[] res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public int[] printNumbers(int n) {
this.n = n;
res = new int[(int)Math.pow(10, n) - 1];
num = new char[n];
start = n - 1;
dfs(0);
return res;
}
void dfs(int x) {
if (x == n) {
String s = String.valueOf(num).substring(start);
if (!s.equals("0")) {
res[count++] = Integer.parseInt(s);
}
if (n - start == nine) {
start--;
}
return;
}
for (char i : loop) {
if (i == '9') {
nine++;
}
num[x] = i;
dfs(x + 1);
}
nine--;
}
}请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。
class Solution {
public boolean isNumber(String s) {
if (s == null || s.length() == 0) {
return false;
}
// 标记是否遇到数位、小数点、‘e’或'E'
boolean numFlag = false, dotFlag = false, eFlag = false;
char[] str = s.trim().toCharArray();
for (int i = 0; i < str.length; i++) {
if (str[i] >= '0' && str[i] <= '9') {
numFlag = true;
} else if (str[i] == '.') {
// 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
if (eFlag || dotFlag) {
return false;
}
dotFlag = true;
} else if (str[i] == 'e' || str[i] == 'E') {
if (!numFlag || eFlag) {
return false;
}
eFlag = true;
// 重置numFlag，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
numFlag = false;
} else if (str[i] == '-' || str[i] == '+') {
// 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
if (i != 0 && str[i - 1] != 'e' && str[i - 1] != 'E') {
return false;
}
} else {
return false;
}
}
return numFlag;
}
}输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31
详解见leetcode
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;
}
}数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
class Solution {
public int findNthDigit(int n) {
int digit = 1;
long start = 1;
long count = 9;
while (n > count) { // 1.
n -= count;
digit += 1;
start *= 10;
count = digit * start * 9;
}
long num = start + (n - 1) / digit; // 2.
return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
}
}我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n4 = dp[c] * 5;
dp[i] = Math.min(n2, Math.min(n3, n4));
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n4) c++;
}
return dp[n - 1];
}
}