Welcome to Andy's Blog!
一念净心，花开遍世界-
剑指offer-数组中只出现一次的数字
题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解体思路
先考虑只有一个出现一次的数字： 利用异或的特性，x^y^x=y^x^x=y。对数组所有元素一次进行异或操作，最终得到的值就是那个只出现一次的数字。
现在考虑有两个只出现一次的数字： 假设两个只出现一次的数字分别为a、b，对数组元素进行两两异或后得到的值为c,可知c=a^b。因为a和b一定不同，所以c不等于0，那么c的二进制表示中一定有一位是1，即a,b在此位上分别为0,1或1,0。假设该位置是从低位起第x位，那么将数组分成两组，一组中的数字在第x位是0，另一组中的数字在第x位是1，则a和b分别属于两个子数组。分别求子数组中唯一只出现1次的数字，即可得到a和b
代码实现:
public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { if(array == null || array.length < 2) { num1[0] = 0; num2[0] = 0; return; } int sum = 0; for(int num : array) sum ^= num; sum &= -sum; for(int num : array) { if((num & sum) == 0) { num1[0] ^= num; } else { num2[0] ^= num; } } } }
-
剑指offer-两个链表的第一个公共结点
题目描述 输入两个链表，找出它们的第一个公共结点
解体思路
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
代码实现：
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode l1 = pHead1; ListNode l2 = pHead2; while(l1 != l2) { l1 = (l1 == null) ? pHead2 : l1.next; l2 = (l2 == null) ? pHead1 : l2.next; } return l1; } }
-
剑指offer-求1+2+3+...+n
题目描述 求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
解体思路
使用递归解法最重要的是指定返回条件，但是本题无法直接使用 if 语句来指定返回条件。
条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。
以下实现中，递归的返回条件为 n <= 0，取非后就是 n > 0，递归的主体部分为 sum += Sum_Solution(n - 1)，转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。
代码实现：
public class Solution { public int Sum_Solution(int n) { int sum = n; boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0); return sum; } }
-
剑指offer-把字符串转换成整数
题目描述 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
解体思路
先记录第一个符号位，然后通过continue跳过第一个符号字符。 通过检查是否在’0’到’9’之间动态判读，不是返回0 字符满足要求执行循环： ret = ret * 10 + (c - ‘0’);
代码实现：
public class Solution { public int StrToInt(String str) { if(str == null || str.length() == 0) return 0; boolean isNegative = str.charAt(0) == '-'; int ret = 0; for(int i=0; i<str.length(); i++) { char c = str.charAt(i); if(i == 0 && ( c == '-' || c == '+')) continue; if(c <'0' || c > '9') return 0; ret = ret * 10 + (c - '0'); } return isNegative ? -ret : ret; } }
-
剑指offer-第一个只出现一次的字符
题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1.
解体思路1
最直观的解法是使用 HashMap 对出现次数进行统计，但是考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap。
代码实现：
public class Solution { public int FirstNotRepeatingChar(String str) { int[] cnts = new int[256]; for(int i=0; i<str.length(); i++) cnts[str.charAt(i)]++; for(int i=0; i<str.length(); i++) if(cnts[str.charAt(i)] == 1) return i; return -1; } }解体思路2
以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么我们只需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。
代码实现:
import java.util.BitSet; public class Solution { public int FirstNotRepeatingChar(String str) { BitSet bs1 = new BitSet(256); BitSet bs2 = new BitSet(256); for(char c : str.toCharArray()) { if(!bs1.get(c) && !bs2.get(c)) bs1.set(c); else if(bs1.get(c) && !bs2.get(c)) bs2.set(c); } for(int i=0; i<str.length(); i++) { char c = str.charAt(i); if(bs1.get(c) && !bs2.get(c)) return i; } return -1; } }
-
剑指offer-从1到n整数中1出现的次数
题目描述 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解体思路
-
主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析 根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
1) 当i表示百位，且百位对应的数>=2,如n=31456,i=100， 则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1
2) 当i表示百位，且百位对应的数为1，如n=31156,i=100， 则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1
3) 当i表示百位，且百位对应的数为0,如n=31056,i=100， 则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
-
综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1 之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
代码实现：
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int cnt = 0; for(int m = 1; m<=n; m *= 10) { int a = n / m; int b = n % m; cnt += (a + 8)/10 * m + (a % 10 == 1 ? b + 1 : 0); } return cnt; } }
-