剑指Offer：翻转单词顺序列
题目牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？ 思路 + 代码先翻转每个单词，再重头到尾进行翻转。 1234567891011121314151617181920212223242526272829public class Solution { public String ReverseSentence(String str) { if(str==null || str.length()==0) return str; char[] chs = str.toCharArray(); int len = chs.length; int i=0, j=0; ...
剑指Offer：左旋字符串
题目汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！ 思路 + 代码先将 “abc” 和 “XYZdef” 分别翻转，得到 “cbafedZYX”，然后再把整个字符串翻转得到 “XYZdefabc”。 123456789101112131415161718192021222324public class Solution { public String LeftRotateString(String str,int n) { if(str==null || str.length()==0) return str; char[] chs = str.toCharArray(); int len = chs.length-1; inverse(...
Leetcode 2：两数相加
题目给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例：123输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807 代码123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode addTwoNumbers(ListNode...
剑指Offer：数组中只出现一次的数字
题目一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 思路 + 代码思路1利用Map统计每个数字出现的次数。 123456789101112131415161718192021//num1,num2分别为长度为1的数组。传出参数//将num1[0],num2[0]设置为返回结果import java.util.*;public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { ArrayList<Integer> list = new ArrayList<Integer>(); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int num: array){ if(!map.co...
剑指Offer：平衡二叉树
题目输入一棵二叉树，判断该二叉树是否是平衡二叉树。 思路 + 代码平衡二叉树的左右子树的高度差不大于 1。 12345678910111213141516public class Solution { private boolean isBalanced = true; public boolean IsBalanced_Solution(TreeNode root) { height(root); return isBalanced; } private int height(TreeNode root){ if(root==null || !isBalanced) return 0; int left = height(root.left); int right = height(root.right); if(1<Math.abs(left-right)) isBalanced ...
剑指Offer：数组在排序中出现的次数
题目统计一个数字在排序数组中出现的次数。 思路 + 代码不能遍历，否则时间超出。二分查找，寻找边界位置。 12345678910111213141516171819202122public class Solution { public int GetNumberOfK(int [] array , int k) { if(array==null||array.length==0) return 0; int l = binarySearch(array, k); int h = binarySearch(array, k+1); return (l>array.length-1 || array[l]!=k)?0:h-l; } private int binarySearch(int[] n, int k){ int l = 0, r = n.length; int m; while(l<r)&...
剑指Offer：两个链表的第一个公共结点
题目输入两个链表，找出它们的第一个公共结点。 思路 + 代码设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。 当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 1234567891011121314151617181920/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ...
剑指Offer：数组中的逆序对
题目在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 题目描述: 123456789题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5 示例112345输入1,2,3,4,5,6,7,0输出7 思路归并排序，先拆分成单个的数字，然后向上归并同时统计逆数数量。 12345678910111213141516171819202122232425262728293031323334353637383940public class Solution { private int count = 0; public int InversePairs(int [] array) { if(array==null || array.length==0) ...
剑指Offer：第一个只出现一次的字符
题目在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）. 思路 + 代码用一个LinkedHashMap统计每个字符出现的次数，同时保存顺序。然后String查找该字符第一次出现的位置。 12345678910111213141516171819202122import java.util.*;public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null || str.length()==0) return -1; char[] chs = str.toCharArray(); LinkedHashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>(); in...
剑指Offer：丑数
题目把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 思路 ＋ 代码丑数只能是丑数乘以 2、３、５。 按照顺序存储丑数，也就是比较每次丑数的大小。 1234567891011121314151617181920public class Solution { public int GetUglyNumber_Solution(int index) { if(index <= 0) return 0; int[] dp = new int[index]; dp[0] = 1; int i2 = 0, i3 = 0, i5 = 0; for(int i=1; i<index; i++){ dp[i] = Math.min(Math.min(dp[i2]*2, dp[i3]*3), dp[i5]...
