共67道，未完成47道
第1题：在二维数组中查找
这道题就属于巧妙的利用了数组的特点，从一个特定点开始找起。
public class Solution {
public boolean Find(int target, int [][] array) {
int row = array.length;
int column = array[0].length;
int m = row - 1, n = 0;
while (m >= 0 && n < column) {
if (array[m][n] == target) {
return true;
} else if (array[m][n] > target) {
m--;
} else {
n++;
}
}
return false;
}
}
第2题：替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
- 最简单的调用string的api
public String replaceSpace(StringBuffer str) {
return str.toString().replace(" ", "%20");
}
- 全部遍历，遇到" "就追加"%20"
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
stringBuilder.append("%20");
} else {
stringBuilder.append(str.charAt(i));
}
}
return stringBuilder.toString();
}
}
第3题：从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack();
ArrayList arraylist = new ArrayList();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.empty()) {
arraylist.add(stack.pop());
}
return arraylist;
}
}
这道题就非常的简单了，需要注意的就是从尾到头打印内容，所以需要考虑到其对应的数据结构，就是栈。
栈常用的api有4 + 1个 因为search我几乎是不用的
- 入栈：push()
- 出栈：pop()
- 返回栈顶元素：peek()
- 判断栈是否为空：empty()
- 查找栈的元素：search()，在就返回1，不在返回-1
第4题 重建二叉树
第5题 用两个栈来实现一个队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思考：毫无思路的就就是模拟进行考虑
总结：
- push的话就直接放到stack1中
- pop的话，先看stack2有没有元素，有的话就弹出。没有的话，把所有的stack1中的元素放到stack2中，然后stack2再出栈。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
//这个写的就不是很好，return上都重复了，就进行一波重构。
public int pop() {
if (!stack2.empty()) {
return stack2.pop();
} else {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
//上边的方法写的就不是很好，有重复的语句
public int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
第6题 旋转数组中最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
思考：
有三种情况
- 情况1，arr[mid] > target：4 5 6 1 2 3
- arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first = mid + 1
- 情况2，arr[mid] < target:5 6 1 2 3 4
- arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid;
- 情况3，arr[mid] == target:
如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int i = 0, j = array.length - 1;
while (i < j) {
if (array[i] < array[j]) {
return array[i];
}
int mid = (i + j) >> 1;
if (array[mid] > array[i]) {
i = mid + 1;
} else if (array[mid] < array[i]) {
j = mid;
} else i++;
}
return array[i];
}
}
第7题 斐波那契数列
递归
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
动态规划
public class Solution {
public int Fibonacci(int n) {
int[] dp = new int[n + 2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
第8题 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
**思考：*这个题和上边的那个题是一样的，都是需要来写一个公式，然后进行反推的。
public class Solution {
public int JumpFloor(int target) {
if (target == 1 || target == 2 || target == 0) return target;
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
}
第9题 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思考：这道题属于有一些公式上的推导了，本身上也不是特别的有意思的呢，不过这里边有一个强转，我有段时间没有写，确实是忘记了的
public class Solution {
public int JumpFloorII(int target) {
if (target == 0 || target == 1) return 1;
return (int) Math.pow(2, target - 1);
}
}
第10题 矩阵覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思考：这个和上边的情况基本上还是一样的，不过这次使用一种特别的方法来写一下
public class Solution {
public int RectCover(int target) {
if (target == 0 || target == 1 || target == 2) return target;
int a = 1, b = 2, c = 0;
for (int i = 3; i <= target; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
第11题 二进制中1的个数
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
思考：以后扯到了二进制，就考虑使用位运算
- 与（AND，&）：全1为1，有0则0。
特殊情况&0，得到的就是0 - 或（OR，|）：有1则1，全0为0。
- 异或（XOR，^）：不同为1，相同为0。
- 非（NOT，~）：取反。
在这道题里就是使用的有一个技巧
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
第13题 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思考：这里边用的是插入思想的方法
- 如果遇到偶数，j++
- 如果遇到奇数,假设位置为j，就将此奇数插入到i所指的位置，然后i往后移动一个位置，在插入之前，显然会涉及到数据的移动，也就是将[i,j-1]整体往后移动。
- 直到整个数组遍历完毕，结束
public class Solution {
public void reOrderArray(int [] array) {
int i = 0;
for (int j = 0; j < array.length; j++) {
if (array[j] % 2 == 1) {
int tmp = array[j];
for (int k = j - 1; k >= i; k--) {
array[k + 1] = array[k];
}
array[i] = tmp;
i++;
}
}
}
}
第14题 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
思考：链表是不知道长度的，所以要么是先一次遍历以后再二次遍历，或者是使用快慢指针的方法，我就让快指针比慢指针快k-1个身位，就可以解决这个问题了。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < k; i++) {
if (fast == null) return null;
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
第15题 反转列表
输入一个链表，反转链表后，输出新链表的表头。
思考：这里也是需要用两个指针，一个是新的链表，一个要遍历的链表。然后挨个节点，指向输出链表，即可得到需要的内容了。
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
第20题 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思考：因为是要用O(1)来实现，所以使用一个辅助栈，来解决。但一定要让两个栈的数量是相等的，才能实现这个同进同出的效果。
import java.util.Stack;
public class Solution {
Stack<Integer> stackTotal = new Stack<Integer>();
Stack<Integer> stackMin = new Stack<Integer>();
public void push(int node) {
stackTotal.push(node);
if (stackMin.empty()) stackMin.push(node);
else {
if (node < stackMin.peek()) stackMin.push(node);
else stackMin.push(stackMin.peek());
}
}
public void pop() {
stackTotal.pop();
stackMin.pop();
}
public int top() {
return stackTotal.peek();
}
public int min() {
return stackMin.peek();
}
}
第21题 栈的压入和退出
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思考：模拟法，新建一个栈，将数组A压入栈中，当栈顶元素等于数组B时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回true.
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.empty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.empty();
}
}
第32题 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思考：这里边用的是贪心算法，贪心算法就是在求局部最优解，从而逼近全局最优解。这里的做法，就是先得到第一个和别人拼接后最小的值，以此类推，进行循环遍历。在这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。
public class Solution {
public String PrintMinNumber(int [] numbers) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int sum1 = Integer.valueOf(numbers[i] + "" + numbers[j]);
int sum2 = Integer.valueOf(numbers[j] + "" + numbers[i]);
if (sum1 > sum2) {
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
String answer = "";
for (int i = 0; i < numbers.length; i++) {
answer += numbers[i];
}
return answer;
}
}
第34题 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思考：这个其实也没啥的，就是先用数组存一次，然后再遍历一次，看看谁等于1
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
int[] tmp = new int[256];
for (int i = 0; i < str.length(); i++) {
tmp[str.charAt(i)]++;
}
for (int i = 0 ; i < str.length(); i++) {
if (tmp[str.charAt(i)] == 1) {
return i;
}
}
return -1;
}
}
第36题 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思考：设置a和b两个指针，a走head1，b走head2，走到尽头了以后就再走另一个链表，这样第一次重合的地方就是两者第一个公共节点。
//这个方法很简单，但是问题是如果两个链表没有交点就会死循环。
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1 != null ? p1.next : pHead2;
p2 = p2 != null ? p2.next : pHead1;
}
return p1;
}
}
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
//这个方法的问题是不加if判断这一句就会死循环，我没有搞懂
if (p1 != p2) {
if (p1 == null) p1 = pHead2;
if (p2 == null) p2 = pHead1;
}
}
return p1;
}
}
第37题 数字在升序数组中重现的次数
统计一个数字在升序数组中出现的次数。
思考：看到有序数组就考虑使用二分查找
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int lbound = 0, rbound = 0;
int left = 0, right = array.length;
int mid = 0;
while (left < right) {
mid = (left + right) >> 1;
if (array[mid] < k) left = mid + 1;
else right = mid;
}
lbound = left;
left = 0;
right = array.length;
while (left < right) {
mid = (left + right) >> 1;
if (array[mid] <= k) left = mid + 1;
else right = mid;
}
rbound = left;
return rbound - lbound;
}
}
总结：二分查找
- 寻找左侧边界的二分搜索
public int left_bound(int[] nums, int target) {
int left = 0; int right = nums.length; //因为就算是左边界，可能所有的数都比他小
int mid = 0;
while (left < right) { //这里是<
mid = left + (right - left) / 2;
if (nums[mid] < target) mid = left + 1;
//上边没有判断等号情况，而是在这里进行判断的，因为这个“=”不一定就是最左侧的，还需要继续逼近
else mid = right;
}
return nums[left] == target ? left : -1;
}
- 寻找右侧边界的二分搜索
public int right_bound(int[] nums, int target) {
int left = 0; int right = nums.length; //因为就算是左边界，可能所有的数都比他小
int mid = 0;
while (left < right) { //这里是<
mid = left + (right - left) / 2;
//left的指向的位置本身就是要最右侧的右一个，所以相等了，可以继续逼近的
if (nums[mid] <= target) mid = left + 1;
else mid = right;
}
//这里返回的是最右侧的值
return nums[left] == target ? left - 1 : -1;
}
第42题 和为s的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思考：最外围的情况时才是两个数的乘积是最小的。所以设置两个指针左右逼夹就好了。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
int left = 0;
int right = array.length - 1;
int tmp = 0;
while (left < right) {
tmp = array[left] + array[right];
if (tmp == sum) {
list.add(array[left]);
list.add(array[right]);
return list;
} else if (tmp > sum) right--;
else left++;
}
return list;
}
}
第43题 左旋字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它
思考：这个题就很简单的了，拼接字符串就可以了
public class Solution {
public String LeftRotateString(String str,int n) {
// 这里图省事了，n要是大于字符串的长度，应该是做一个除模处理的
if (str == null || n > str.length()) {
return str;
}
//substring(pos):表示开始位置，一直截取完
//substring(begin, end):从begin截取到end，左闭右开的格式
return str.substring(n) + str.substring(0, n);
}
}
别人的方法
public:
string LeftRotateString(string str, int n) {
int len = str.length();
if(len == 0) return "";
n = n % len;
str += str;
return str.substr(n, len + n);
}
};
第44题 翻转单词顺序
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思考：就也没啥的，分割以后装进去呗。
public String ReverseSentence(String str) {
if (str.trim().equals("")) return str;
String[] tmp = str.split(" ");
StringBuffer answer = new StringBuffer();
for (int i = tmp.length - 1; i >= 0; i--) {
answer.append(tmp[i]);
if (i != 0) answer.append(" ");
}
return answer.toString();
}
第46题 孩子们的游戏（圆圈中最后剩下的孩子）
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
第50题
第55题 链表中环的入口位置
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思考：快慢指针解决
