lintcode--剑指offer---前20题（带详细解答）
再次接受大神同学小萌萌的建议-开始刷剑指offer，每天至少一道，希望这个学期结束的时候可以熟练掌握这75道题目。同时另一个目标，这个学期把SCI的论文写完。（PS:如果还能坚持健身的话就完美了）
①Fizz Buzz
Given number n. Print number from 1 to n. But:
- when number is divided by
3, print"fizz". - when number is divided by
5, print"buzz". - when number is divided by both
3and5, print"fizz buzz". -
class Solution {
public ArrayList<String> fizzBuzz(int n) {
ArrayList<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 != 0) {
result.add("fizz");
} else if (i % 5 == 0 && i % 3 != 0) {
result.add("buzz");
} else if (i % 3 == 0 && i % 5 == 0) {
result.add("fizz buzz");
} else {
//result.add("" + i);
//result.add(String.valueOf(i));
result.add(Integer.toString(i));
}
}
return result;
}
}②Fibonacci
-
Find the Nth number in Fibonacci sequence.
A Fibonacci sequence is defined as follow:
- The first two numbers are 0 and 1.
- The i th number is the sum of i-1 th number and i-2 th number.
The first ten numbers in Fibonacci sequence is:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...-
- Example
Given
1, return0Given
2, return1Given
10, return34//我最直观的做法就是递归，这也是本科c++书上的做法，自以为很快就做完了，然后却发现时间超出限制，细思恐极，
如果要求fibonacci(100)那就要求fibonacci(99)和fibonacci(98),要求99和98就需要97和96，以此类推.....
class Solution { public int fibonacci(int n) { if (n == 1) { return 0; } else if (n == 2) { return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } }//上述程序时间超限制主要是每次都得计算之前fibn，但是如果将之前记录的存起来就不要再计算了，代码如下（核心思想是：i作为加法运行的次数）：
class Solution { public int fibonacci(int n) { int fibone = 0; int fibtwo = 1; int fibn = 1;//很重要 if (n <= 1) { return 0; } else if (n == 2) { return 1; } else { for (int i = 3; i <= n; i++) { fibtwo = fibone; fibone = fibn; fibn = fibone + fibtwo; } } return fibn; } }
///////////////////////
class Solution {
public int fibonacci(int n) {
if (n <= 1) {
return 0;
}
int a = 0;
int b = 1;
for (int i = 2; i < n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
}③Singleton（单例模式）
为什么要用单例模式：
对于系统中的某些类来说，只有一个实例很重要，例如，一个系统中可以存在多个打印任务，但是只能有一个正在工作的任务；一个系统只能有一个窗口管理器或文件系统；一个系统只能有一个计时工具或ID(序号)生成器。如在Windows中就只能打开一个任务管理器。如果不使用机制对窗口对象进行唯一化，将弹出多个窗口，如果这些窗口显示的内容完全一致，则是重复对象，浪费内存资源；如果这些窗口显示的内容不一致，则意味着在某一瞬间系统有多个状态，与实际不符，也会给用户带来误解，不知道哪一个才是真实的状态。因此有时确保系统中某个对象的唯一性即一个类只能有一个实例非常重要。
顺便补充一下关于www.one88bet.com模式的基础知识：
ppt的全部内容已经上传到博客园的文件上面了。
Singleton is a most widely used design pattern. If a class has and only has one instance at every moment, we call this design as singleton. For example, for class Mouse (not a animal mouse), we should design it in singleton.
You job is to implement a
getInstancemethod for given class, return the same instance of this class every time you call this method.显然单例模式的要点有三个； 一是某个类只能有一个实例；二是它必须自行创建这个实例；三是它必须自行向整个系统提供这个实例。从具体实现角度来说，就是以下三点： 一是单例模式的类只提供私有的构造函数，二是类定义中含有一个该类的静态私有对象，三是该类提供了一个静态的公有的函数用于创建或获取它本身的静态私有对象。class Solution { private Solution(){ }//类只提供私有的构造函数 private static Solution instance = null;//定义该类的一个静态私有对象 public static Solution getInstance() {//提供一个静态的公有的用于创建或获取他本身私有对象的成员函数 if (instance == null) { instance = new Solution(); } return instance; } }
/////////////////////////////
class Solution {
//单例模式三个要素：①只有一个实例②必须自己创建这个实例③可以向外部提供这个实例
//对应的程序：①私有的构造函数保证只有一个实例②类定义中含有一个私有的静态类对象
//③公有的函数可以获取这个对象
//私有构造函数
private Solution() {
}
//自己创建这个实例
private static Solution instance = null;
//公有的获取实例函数
public static Solution getInstance() {
return instance;
}
}④Count 1 in Binary
Count how many
1in binary representation of a 32-bit integer.Example
Given
32, return1Given
5, return2Given
1023, return9我首先想到的是除法，但是除法的操作的效率会明显小于移位的操作。
下面程序的思路是：先将num与1做与操作，判断最后一位是不是1，然后将1左移编程10，判断右边第二位是不是1，然后一直判断最高位，这种算法循环次数是num的二进制位数。
public class Solution { public int countOnes(int num) { int count = 0; int flag = 1; while (flag != 0) { if ((num & flag) != 0) { count++; } flag = flag << 1; } return count; } }
最优质的解答：将一个数num做num&（num-1）操作相当于二进制最右边的1变为0（例如1100与1011做与操作之后变成1000将1100最右边的1变成0）所以一个数它的二进制有多少了个1就能进行多少次这样的操作。这种算法num的二进制有几个1就循环几次。
public class Solution { public int countOnes(int num) { int count = 0; while (num != 0) {//c++中可以写成while(num)因为while中的数字大于0都执行while的内容 num = num & (num - 1); count++; } return count; } }
⑤Reverse Linked List
Reverse a linked list.
Example
For linked list
1->2->3, the reversed linked list is3->2->1解题思路：定义三个指针，分别保存上一节点，当前节点，下一节点，将下一节点赋值给上一节点，然后所有节点右移。
public class Solution { public ListNode reverse(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pnode = head;//定义当前节点 ListNode pprev = null;//定义之前的节点 while (pnode != null) { ListNode pnext = pnode.next;//定义下一个节点 pnode.next = pprev;//核心操作 pprev = pnode;//所有节点后移 pnode = pnext;//所有节点后移 } ListNode newhead = pprev; return newhead; } }
Reverse Linked List II
1 public class Solution { //三个步骤，三个指针，保存三个节点 2 public ListNode reverseBetween(ListNode head, int m , int n) { 3 //边界判断 4 if (head == null || head.next == null || m >= n) { 5 return head; 6 } 7 //将链表的head保存，用于程序的返回 8 ListNode dummy = new ListNode(0); 9 dummy.next = head; 10 //第一步：从m节点到n节点进行反转 11 ListNode preNodem = dummy; 12 for (int i = 0; i < m - 1; i++) { //首先找到m节点的前一节点，并进行保存 13 preNodem = preNodem.next; 14 } 15 ListNode nodem = preNodem.next; //将m节点进行保存 16 //开始反转 17 ListNode pre = null; //定义三个个指针进行遍历反转（一个之前的pre和一个当前指针cur和一个之后指针after） 18 ListNode cur = nodem; 19 for (int i = 0; i < n - m + 1; i++) { 20 ListNode after = cur.next; //防止指针断掉，每次都要将cur.next进行保存 21 cur.next = pre; //进行反转 22 pre = cur; //指针后移 23 cur = after; //指针后移 24 } 25 ListNode noden = pre; //对n节点进行保存 26 //第二步：m-1节点的下一节点n节点 27 preNodem.next = noden; 28 //第三步：m节点的下一节点是n+1节点 29 nodem.next = cur; //写成noden.next或者pre.next内存超出限制 30 return dummy.next; //不管如何反转,dummy.next 永远指的是表头 31 } 32 }
Write a method to replace all spaces in a string with
%20. The string is given in a characters array, you can assume it has enough space for replacement and you are given the true length of the string.You code should also return the new length of the string after replacement.
解题思路：用原来的长度加空格的两倍计算得出现在的长度，然后从字符串的尾部开始复制，遇到空格用%20替换。（注意length是实际的长度可以直接用，而string.length不能用，因为后面有足够的空间用于复制）
public class Solution { public int replaceBlank(char[] string, int length) { if (string == null || length <= 0) { return 0; } int count = 0; for (int i = 0; i < string.length; i++) { if (Character.isWhitespace(string[i])) { count++; } } int newlen = string.length + 2 * count; char[] newstr = new char[newlen]; int i = string.length - 1; int j = newlen - 1; while (i >= 0 && j >= 0) { if (Character.isWhitespace(string[i])) { newstr[j] = '0'; j--; newstr[j] = '2'; j--; newstr[j] = '%'; j--; i--; } else { newstr[j] = string[i]; j--; i--; } } return newlen; } }
/////////////////////////////
public class Solution {
public int replaceBlank(char[] str, int length) {
int newLen = 0;
if (str == null || length <= 0) {
return newLen;
}
int numOfBlank = 0;
for (int i = 0; i < length; i++) {
if (str[i] == ' ') {
numOfBlank++;
}
}
newLen = length + 2 * numOfBlank;
//从字符数组末尾开始复制
int j = newLen - 1;
for (int i = length - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
} else {
str[j--] = str[i];
}
}
return newLen;
}
}可能是对lintcode不太了解，之前用了一个新的字符数组newstr用于复制，虽然newstr已经正确了，但是一直通过不了，最后才知道lintcode不但会测试返回值newlen，还会测试string，所以对字符串的修改一定要在string本身进行。
public class Solution { public int replaceBlank(char[] string, int length) {//length是字符串的真实长度 if (string == null || length <= 0) { return 0; } int count = 0; for (int i = 0; i < length; i++) { if (Character.isWhitespace(string[i])) { count++; } } int newlen = length + 2 * count; int i = length - 1; int j = newlen - 1; while (i >= 0 && j >= 0) { if (Character.isWhitespace(string[i])) { string[j] = '0';//对字符串的修改一定要对string本身进行 j--; string[j] = '2'; j--; string[j] = '%'; j--; i--; } else { string[j] = string[i]; j--; i--; } } return newlen; } }
（7）Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,
0 1 2 4 5 6 7might become4 5 6 7 0 1 2).Find the minimum element.、
解题思路：用nums[mid]与nums[right]比较，如果小的话说明在最小数在左边（6 0 1 2 3 4 5），如果大的话说明最小数在右边（5 6 7 8 9 0 1）说明最小数在右边。
public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int left = 0; int right = nums.length - 1; int mid = 0; while (left < right) { mid = left + (right - left) / 2; //防止int溢出所以不用（left + right）/ 2 if (nums[mid] < nums[right]) { right = mid; } else { left = mid + 1; } } return nums[left]; } }
Find Minimum in Rotated Sorted Array II（补充）--数组中可以由重复的数字
1 public class Solution { 2 public int findMin(int[] nums) { 3 if (nums == null || nums.length == 0) { 4 return -1; 5 } 6 int left = 0; 7 int right = nums.length - 1; 8 while (left < right) { 9 int mid = left + (right - left) / 2; 10 if (nums[mid] > nums[right]) { 11 left = mid + 1; 12 } else if (nums[mid] < nums[right]) { 13 right = mid; 14 } else { 15 right--;//对于两端重复的处理 16 } 17 } 18 return nums[left]; 19 } 20 }
（8）Construct Binary Tree from Preorder and Inorder Traversal
public class Solution { //寻找根节点的子函数 private int findPosition(int[] arr, int length, int key) { for (int i = 0; i < length; i++) { if (arr[i] == key) { return i; } } return -1; //如果没有找到返回-1,考虑全面，代码高质量 } //树的建立思想:首选找到根节点，然后先建立左树，然后建立右树 //解题思路：前序遍历是--根节点--左节点--右节点，中序遍历是--左节点--根节点--右节点，然后进行递归就行 private TreeNode mybuildTree(int[] inorder, int instart, int inend, int[] preorder, int prestart, int preend) { //考虑全面 if (instart > inend) { return null; } TreeNode root = new TreeNode(preorder[prestart]); int position = findPosition(inorder, inorder.length, preorder[prestart]); root.left = mybuildTree(inorder, instart, position - 1, preorder, prestart + 1, prestart + position - instart); root.right = mybuildTree(inorder, position + 1, inend, preorder, position - inend + preend + 1, preend);
//程序中最关键的地方：position - inend + preend + 1 return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { //考虑全面 if (preorder.length != inorder.length) { return null; } return mybuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1); } }
////////////////////////////////////////////
public class Solution {
public TreeNode buildTree(int[] preOrder, int[] inOrder) {
if (preOrder.length != inOrder.length) {
return null;
}
return buildTreeHelper(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
}
//build root, build the left tree, build the right tree, notice the importance of parameters
public TreeNode buildTreeHelper(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preOrder[preStart]);
int rootIndex = findRoot(inOrder, root.val);
root.left = buildTreeHelper(preOrder, preStart + 1, preStart + (rootIndex - inStart), inOrder, inStart, rootIndex - 1);
root.right = buildTreeHelper(preOrder, preStart + (rootIndex - inStart) + 1, preEnd, inOrder, rootIndex + 1, inEnd);
return root;
}
//find the position of root in Inorder traversal
public int findRoot(int[] inOrder, int root) {
int rootIndex = 0;
for (int i = 0; i < inOrder.length; i++) {
if (root == inOrder[i]) {
rootIndex = i;
return rootIndex;
}
}
return -1;
}
}Construct Binary Tree from Inorder and Postorder Traversal （补充）--用中序遍历和后序遍历恢复二叉树
1 public class Solution { 2 private int findPosition(int[] arr, int length, int key) { 3 for (int i = 0; i < length; i++) { 4 if (arr[i] == key) { 5 return i; 6 } 7 } 8 return -1; 9 } 10 private TreeNode mybuildTree(int[] inorder, int instart, int inend, 11 int[] postorder, int poststart, int postend) { 12 if (instart > inend) { 13 return null; 14 } 15 TreeNode root = new TreeNode(postorder[postend]); 16 int position = findPosition(inorder, inorder.length, postorder[postend]); 17 root.left = mybuildTree(inorder, instart, position - 1, 18 postorder, poststart, poststart + position - instart - 1);//最需要注意的地方 19 root.right = mybuildTree(inorder, position + 1, inend, 20 postorder, poststart + position - instart, postend - 1);//最需要注意的地方 21 return root; 22 } 23 public TreeNode buildTree(int[] inorder, int[] postorder) { 24 if (inorder.length != postorder.length) { 25 return null; 26 } 27 return mybuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); 28 } 29 }
（9）Implement Queue by Two Stacks
public class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<Integer>(); stack2 = new Stack<Integer>(); } //私有函数：如果栈1非空，将栈1中的元素全部压入栈2 private void stack1Tostack2() { while (!stack1.empty()) { stack2.push(stack1.pop()); } } //新到queue中的元素压入栈1中 public void push(int element) { stack1.push(element); } //栈2中的pop就是queue先进去queue的元素 public int pop() { if (stack2.empty()) { this.stack1Tostack2(); } return stack2.pop(); } //栈2中的peek也是queue的peek public int top() { if (stack2.empty()) { this.stack1Tostack2(); } return stack2.peek(); } }
/////////////////////////////////
public class MyQueue {
//核心思想：插入的时候插入到栈1中，弹出的时候从栈2弹出（如果栈2为空，则将栈1的全部元素弹入到栈2中）
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
//切勿忘记初始化，即构造函数
stack1 = new Stack<>();
stack2 = new Stack<>();
}
private void stack1Tostack2() {
//私有函数
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
}
public int pop() {
stack1Tostack2();
return stack2.pop();
}
public int top() {
stack1Tostack2();
return stack2.peek();
}
public void push(int element) {
stack1.push(element);
}
}1 public class Solution { 2 public int searchMatrix(int[][] matrix, int target) { 3 //二维数组的边界值判断 4 if (matrix == null || matrix.length == 0) { 5 return 0; 6 } 7 if (matrix[0] == null || matrix[0].length == 0) { 8 return 0; 9 } 10 int targetcount = 0; 11 int row = matrix.length; 12 int column = matrix[0].length; 13 int x = 0; 14 int y = column - 1; 15 //解题思路：取得矩阵右上角的值，如果小于target那么取消行，如果大于target则取消列 16 while (x < row && y >= 0) { 17 if (matrix[x][y] > target) { 18 y--; 19 //取消列 20 } else if (matrix[x][y] < target) { 21 x++; 22 //取消行 23 } else { 24 targetcount++; 25 y--; 26 x++; 27 } 28 } 29 return targetcount; 30 } 31 }
Search a 2D Matrix（补充）--查找是否存在这个数字
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 //首先进行边界判断 4 if (matrix == null || matrix.length == 0) { 5 return false; 6 } 7 if (matrix[0] == null || matrix[0].length == 0) { 8 return false; 9 } 10 int row = matrix.length; 11 int column = matrix[0].length; 12 int x = 0; 13 int y = column - 1; 14 while (x < row && y >= 0) { 15 if (matrix[x][y] > target) { 16 y--; 17 } else if (matrix[x][y] < target) { 18 x++; 19 } else { 20 return true; 21 } 22 } 23 return false; 24 } 25 }
1 public class Solution { 2 public int climbStairs(int n) { 3 //解题思路(本质应该是一个动态规划问题)：其实是个找规律问题，首先我们找出所有的n的规律，1(1)2(2)3(3)4(5)5(8)6(13), 发现规律是前两个数相加（前两个数字是1和2） 4 if (n <= 1) { 5 return 1; 6 } 7 int one = 1; 8 int two = 2; 9 int result = 2;//初始化必须为2，这样n为2的时候才能返回一个正确值 10 for (int i = 2; i < n; i++) { 11 result = one + two; 12 one = two; 13 two = result; 14 } 15 return result; 16 } 17 }
（11）Partition Array by Odd and Even
1 //解题思路：明显是个双指针问题，定义两个指针（一左一右），左边指向偶数，右边指向奇数，然后交换。 2 public class Solution { 3 public void partitionArray(int[] nums) { 4 int left = 0; 5 int right = nums.length - 1; 6 while (left < right) { 7 while (nums[left] % 2 != 0) { 8 left++; 9 } 10 while (nums[right] % 2 == 0) { 11 right--; 12 } 13 if (left < right) { 14 int temp = nums[left]; 15 nums[left] = nums[right]; 16 nums[right] = temp; 17 left++; 18 right--; 19 } 20 } 21 } 22 }补充：面试官会对可扩展程序更感兴趣。
1 //考虑可扩展性：如果题目改成负数和正数或者能被3整除和不能被3整除呢(写成一个子函数就只需要改子函数) 2 public class Solution { 3 public void partitionArray(int[] nums) { 4 int left = 0; 5 int right = nums.length - 1; 6 while (left < right) { 7 while (!isEven(nums[left])) { 8 left++; 9 } 10 while (isEven(nums[right])) { 11 right--; 12 } 13 if (left < right) { 14 int temp = nums[left]; 15 nums[left] = nums[right]; 16 nums[right] = temp; 17 left++; 18 right--; 19 } 20 } 21 } 22 public boolean isEven(int n) { 23 if (n % 2 == 0) { 24 return true; 25 } 26 return false; 27 } 28 }（12）Delete Node in the Middle of Singly Linked List
1 /** 2 * Definition for ListNode. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int val) { 7 * this.val = val; 8 * this.next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 //解题思路：所谓删除指针，我们只需要将需要删除的节点的值以及引用换成它的下一节点的值以及引用 14 public void deleteNode(ListNode node) { 15 //判断链表是否为空，分别判断值和引用是否为空 16 if (node == null || node.next == null) { 17 return; 18 } 19 //关键程序 20 node.val = node.next.val; 21 node.next = node.next.next; 22 } 23 }（13）Remove Nth Node From End of List
1 /** 2 * Definition for ListNode. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int val) { 7 * this.val = val; 8 * this.next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param head: The first node of linked list. 15 * @param n: An integer. 16 * @return: The head of linked list. 17 */ 18 ListNode removeNthFromEnd(ListNode head, int n) { 19 if (head == null || n <= 0) { 20 return null; 21 } 22 ListNode dummy = new ListNode(0); 23 dummy.next = head; 24 ListNode delete = dummy; 25 for (int i = 0; i < n; i++) { 26 head = head.next; 27 } 28 while (head != null) { 29 head = head.next; 30 delete = delete.next; 31 } 32 delete.next = delete.next.next; 33 return dummy.next; 34 } 35 }（14）Subtree
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param T1, T2: The roots of binary tree. 15 * @return: True if T2 is a subtree of T1, or false. 16 */ 17 public boolean isSubtree(TreeNode t1, TreeNode t2) { 18 //前两个边界判断不能调换 19 if (t2 == null) { 20 return true; 21 } 22 if (t1 == null) { 23 return false; 24 } 25 //判断两个树是否相同 26 if (isEqual(t1, t2)) { //相当于判断根节点是否相同 27 return true; 28 } 29 if (isSubtree(t1.left, t2) || isSubtree(t1.right, t2)) { 30 return true; 31 } 32 return false; 33 } 34 public boolean isEqual(TreeNode t1, TreeNode t2) { 35 if (t1 == null || t2 == null) { 36 return t1 == t2; //技巧 37 } 38 if (t1.val != t2.val) { 39 return false; 40 } 41 return isEqual(t1.left, t2.left) && isEqual(t1.right, t2.right); 42 } 43 }（15）Merge Two Sorted Lists
1 /** 2 * Definition for ListNode. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int val) { 7 * this.val = val; 8 * this.next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param ListNode l1 is the head of the linked list 15 * @param ListNode l2 is the head of the linked list 16 * @return: ListNode head of linked list 17 */ 18 public ListNode mergeTwoLists(ListNode head1, ListNode head2) { 19 //已经包含了两个都为空的情况 20 if (head1 == null) { 21 return head2; 22 } else if (head2 == null) { 23 return head1; 24 } 25 //采用递归调用的思想 26 ListNode mergeHead = null; 27 if (head1.val < head2.val) { 28 mergeHead = head1; 29 mergeHead.next = mergeTwoLists(head1.next, head2); 30 } else { 31 mergeHead = head2; 32 mergeHead.next = mergeTwoLists(head1, head2.next); 33 } 34 return mergeHead; 35 } 36 }（16）Print Numbers by Recursion
1 public class Solution { 2 /** 3 * @param n: An integer. 4 * return : An array storing 1 to the largest number with n digits. 5 */ 6 public List<Integer> numbersByRecursion(int n) { 7 if (n <= 0) { 8 return new ArrayList<Integer>(); 9 } 10 ArrayList arrList = new ArrayList<>(); 11 recursion(n, 0, arrList); 12 return arrList; 13 } 14 public static void recursion(int n, int ans, ArrayList<Integer> arrList) { 15 if (n == 0) { 16 if (ans > 0) { 17 arrList.add(ans); 18 } 19 return; 20 } 21 for (int i = 0; i <= 9; i++) { 22 recursion(n - 1, ans * 10 + i, arrList); 23 } 24 } 25 }1 class Solution { 2 /* 3 * @param a, b, n: 32bit integers 4 * @return: An integer 5 */ 6 // public int fastPower(int a, int b, int n) { 7 // return (int) pow(a, n) % b; 8 // } 9 // a的n次方必然会超出long表示的范围，那么先求出a的n次方再求余必然不正确 10 // public long pow(int a, int n) { 11 // if (n == 0) { 12 // return 1; 13 // } 14 // if (n == 1) { 15 // return a; 16 // } 17 // long result = pow(a, n >> 1); 18 // result *= result; 19 // if (n % 2 == 1) { 20 // result *= a; 21 // } 22 // return result; 23 // } 24 //一个要注意的地方：M^n mod q = (M mod q) ^ n mod q;(M * N) mod q = ((M mod q)*(N mod q)) mod q;加法换成乘法也行 25 //乘方的取模公式可以推广为：一个乘数取模之后，乘以后面的数再取模，一直递归下去 26 public int fastPower(int a, int b, int n) { 27 //3.递归出口 28 if (n == 0) { 29 return 1 % b; 30 } 31 if (n == 1) { 32 return a % b; 33 } 34 //1.递归定义 35 long result = fastPower(a, b, n >>1); 36 //2.递归拆解 37 result = result * result % b; 38 if (n % 2 == 1) { 39 result = result * a % b; 40 } 41 return (int)result; 42 } 43 }1 public class Solution { 2 /** 3 * @param A a string 4 * @param B a string 5 * @return a boolean 6 */ 7 public boolean stringPermutation(String a, String b) { 8 if (a.length() != b.length()) { 9 return false; 10 } 11 int[] temp = new int[1000]; //数组大小必须大于所有字符可能的对应的整型 12 for (int i = 0; i < a.length(); i++) { 13 temp[(int) a.charAt(i)] += 1; 14 } 15 for (int i = 0; i < b.length(); i++) { 16 temp[(int) b.charAt(i)] -= 1; 17 } 18 for (int i = 0; i < a.length(); i++) { 19 if (temp[(int) a.charAt(i)] != 0) { 20 return false; 21 } 22 } 23 return true; 24 } 25 }（19）Binary Tree Level Order Traversal
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param root: The root of binary tree. 15 * @return: Level order a list of lists of integer 16 */ 17 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { 18 ArrayList<ArrayList<Integer>> arrList = new ArrayList<>(); 19 if (root == null) { 20 return arrList; 21 } 22 //Queue是个接口，能通过LinkedList实现不能通过ArrayList实现 23 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 24 queue.offer(root); 25 // 26 while (!queue.isEmpty()) { 27 ArrayList<Integer> level = new ArrayList<>(); 28 int qSize = queue.size(); //注意，不能直接写入for循环 i < queue.size()，否则会因为后期的offer操作改变 29 for (int i = 0; i < qSize; i++) { 30 TreeNode head = queue.poll(); //poll()获取头部，并从队列中移除头部 31 level.add(head.val); 32 if (head.left != null) { 33 queue.offer(head.left); 34 } 35 if (head.right != null) { 36 queue.offer(head.right); 37 } 38 } 39 arrList.add(level); 40 } 41 return arrList; 42 } 43 }Binary Tree Level Order Traversal II （补充）
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 13 14 public class Solution { 15 /** 16 * @param root: The root of binary tree. 17 * @return: buttom-up level order a list of lists of integer 18 */ 19 public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) { 20 //1.边界判断 21 ArrayList<ArrayList<Integer>> arrList = new ArrayList<>(); 22 if (root == null) { 23 return arrList; 24 } 25 //定义一个queue 26 Queue<TreeNode> queue = new LinkedList<>(); 27 queue.offer(root); 28 //循环体 29 while (!queue.isEmpty()) { 30 ArrayList<Integer> level = new ArrayList<>(); 31 int qSize = queue.size(); 32 for (int i = 0; i < qSize; i++) { 33 TreeNode cur = queue.poll(); 34 level.add(cur.val); 35 if (cur.left != null) { 36 queue.offer(cur.left); 37 } 38 if (cur.right != null) { 39 queue.offer(cur.right); 40 } 41 } 42 arrList.add(level); 43 } 44 Collections.reverse(arrList); //关键代码 45 return arrList; 46 } 47 }
- Example
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。