一般般帅
上一篇:25~30题
31~36题
1383 2018-11-20 2020-06-25
前言：牛客网剑指Offer编程题31~36题。
一、 整数中1出现的次数
1、问题描述
考点时间效率，输入一个整数n，求1～n这n个整数的十进制中1出现的次数。例如，输入12，1~12这些整数中包含1的数字有1,10,11和12，1一共出现了5次。
2、别人的代码
public int NumberOf1Between1AndN_Solution(int n) {
// 1的个数
int count = 0;
// 当前位
int i = 1;
int current = 0, after = 0, before = 0;
while ((n / i) != 0) {
// 高位数字
current = (n / i) % 10;
// 当前位数字
before = n / (i * 10);
// 低位数字
after = n - (n / i) * i;
// 如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
if (current == 0) {
count += before * i;
}
// 如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
else if (current == 1) {
count += before * i + after + 1;
}
// 如果大于1,出现1的次数由高位决定,//（高位数字+1）* 当前位数
else {
count += (before + 1) * i;
}
// 前移一位
i = i * 10;
}
return count;
}
这个题目不想深究，就暂时跳过吧。
二、把数组排成最小的数
1、题目描述
考点时间效率，输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
2、我的代码
static class ThirtyTwo {
public String PrintMinNumber(int[] numbers) {
StringBuilder sb = new StringBuilder();
ArrayList<String> list = new ArrayList<>();
for (int n : numbers) {
list.add(String.valueOf(n));
}
list.sort(new NumberComparator());
for (String s : list) {
sb.append(s);
}
return sb.toString();
}
static class NumberComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
if (a.length() >= b.length()) {
for (int i = 0; i < b.length(); i++) {
if (a.charAt(i) > b.charAt(i)) {
return 1;
} else if (a.charAt(i) < b.charAt(i)) {
return -1;
}
}
return a.length() == b.length() ? 0 : compare(a.substring(b.length() - 1), b);
}
return -compare(b, a);
}
}
}
本来觉得自己写得挺好的，直到看了别人的代码。
3、别人的代码
* 解题思路：
* 先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
* 排序规则如下：
* 若ab > ba 则 a > b，
* 若ab < ba 则 a < b，
* 若ab = ba 则 a = b；
* 解释说明：
* 比如 "3" < "31"但是 "331" > "313"，所以要将二者拼接起来进行比较
public String PrintMinNumber(int [] numbers) {
if(numbers == null || numbers.length == 0) return "";
int len = numbers.length;
String[] str = new String[len];
StringBuilder sb = new StringBuilder();
for(int i = 0; i < len; i++){
str[i] = String.valueOf(numbers[i]);
}
Arrays.sort(str,new Comparator<String>(){
@Override
public int compare(String s1, String s2) {
String c1 = s1 + s2;
String c2 = s2 + s1;
return c1.compareTo(c2);
}
});
for(int i = 0; i < len; i++){
sb.append(str[i]);
}
return sb.toString();
}
三、丑数
1、问题描述
考点时间空间效率的平衡，把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
2、我的代码
public int GetUglyNumber_Solution1(int index) {
int count = 1;
if (index <= 0) {
return 0;
}
int i = 1;
while (count != index) {
if (isUgly(++i)) {
count++;
}
}
return i;
}
private boolean isUgly(int n) {
while (n % 2 == 0) {
n /= 2;
}
while (n % 3 == 0) {
n /= 3;
}
while (n % 5 == 0) {
n /= 5;
}
return n == 1 || n == 2 || n == 3 || n == 5;
}
哈哈，牛客网提交通不过。
3、别人的代码
public int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int[] result = new int[index];
result[0] = 1;
int i = 1, t2 = 0, t3 = 0, t5 = 0;
while (i < index) {
int a = result[t2] * 2;
int b = result[t3] * 3;
int c = result[t5] * 5;
int min = min(a, b, c);
result[i++] = min;
if (min == a) {
t2++;
}
if (min == b) {
t3++;
}
if (min == c) {
t5++;
}
}
return result[i - 1];
}
为什么别人这么聪明？
四、第一个只出现一次的字符位置
1、问题描述
考点时间空间效率的平衡，在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。
2、我的代码
static class ThirtyFour {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0 || str.length() > 10000) {
return -1;
}
int[] hashTable = new int[52];
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) > 96) {
int index = str.charAt(i) - 97;
hashTable[index + 26]++;
} else {
int index = str.charAt(i) - 65;
hashTable[index]++;
}
}
for (int i = 0; i < str.length(); i++) {
int index;
if (str.charAt(i) > 96) {
index = str.charAt(i) - 97 + 26;
} else {
index = str.charAt(i) - 65;
}
int t = hashTable[index];
if (t == 1) {
return i;
}
}
return -1;
}
private static void test() {
// 97
System.out.println((int)'a');
// 122
System.out.println((int)'z');
// 65
System.out.println((int)'A');
// 90
System.out.println((int)'Z');
}
}
主要还是哈希思想的应用。
五、数组中的逆序对
1、问题描述
考点时间空间效率的平衡 ，在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
2、我的思路
这个题目的通过率是最低的，不是很想搞，还是用自己的傻思路吧。一个一个往后遍历，统计逆序对。
六、两个链表的第一个公共结点
1、题目描述
考点时间空间效率的平衡，输入两个链表，找出它们的第一个公共结点。
2、我的代码
static class ThirtySix {
static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1, p2 = pHead2;
while (p1 != null) {
while (p2 != null) {
if (p1 == p2) {
return p1;
}
p2 = p2.next;
}
p1 = p1.next;
p2 = pHead2;
}
return null;
}
}
3、别人的代码
一开始题目我就理解错了，图画错了，所以一时没想到好办法。下面是别人的代码
public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
int length1 = getLength(pHead1);
int length2 = getLength(pHead2);
if (length1 > length2) {
while (length1 - length2 != 0) {
pHead1 = pHead1.next;
length1--;
}
}
if (length1 < length2) {
while (length2 - length1 != 0) {
pHead2 = pHead2.next;
length2--;
}
}
while (pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}
private static int getLength(ListNode head) {
int i = 0;
while (head != null) {
i++;
head = head.next;
}
return i;
}
思想也不是很难，关键还是理解题目意思啊。
总访问次数: 340次, 一般般帅 创建于 2018-11-20, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！