Lintcode刷题地址：http://www.lintcode.com/zh-cn/problem/#_=_
一些大厂面试时喜欢考查的，对于锻炼自己的逻辑思维也大有裨益~
发现对链表的考察较多。。
0.经典的二分查找法（前提为有序序列）
/**
* 非递归二分查找
*
* @param num
* @param number
* @return
*/
public static int binarySearch(int num[], int number) {
if (num == null || num.length == 0) {
return -1;
}
int start, end, mid;
start = 0;
end = num.length - 1;
while (start <= end) {
mid = (start + end) / 2;
if (num[mid] == number)
return mid;
else if (num[mid] > number) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
/**
* 递归查找
*
* @param num
* @param number
* @return
*/
public static int RecursivebinarySearch(int num[], int start, int end, int key) {
int mid = (start + end) / 2;
if (num == null || num.length == 0 || key < num[start] || key > num[end]) {
return -1;
} else if (num[mid] > key) {
return RecursivebinarySearch(num, start, mid - 1, key);
} else if (num[mid] < key) {
return RecursivebinarySearch(num, mid + 1, end, key);
} else {
return mid;
}
}
1.二叉树的路径和：
class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
public class Solution {
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
// write your code here
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(null == root) return result;
Stack<Integer> stack = new Stack<Integer>();
binaryTreePathSum(result, stack, root, 0, target);
return result;
}
public void binaryTreePathSum(List<List<Integer>> result, Stack stack, TreeNode root, int sum, int target) {
sum += root.val;
stack.push(root.val);
if(sum == target && root.left==null && root.right==null) {
List<Integer> list = new ArrayList<Integer>(stack);
result.add(list);
stack.pop();
return;
}else{
if(root.left != null) {
binaryTreePathSum(result, stack, root.left, sum, target);
}
if(root.right != null) {
binaryTreePathSum(result, stack, root.right, sum, target);
}
stack.pop();
}
}
}
2.合并排序数组
class Solution {
/**
* @param A and B: sorted integer array A and B.
* @return: A new sorted integer array
*/
public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
// write your code here
int bSize = B.size();
for(int i=0;i<bSize;i++)
A.add(B.get(i));
Collections.sort(A);
return A;
}
}
不用Java API的做法（一般是考这个）：
public int[] mergeSortedArr(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i,j,k = 0;
while(i<a.length && j<b.length) {//循环比较两个数最大长度的结果后，只会剩下一个数组的元素
if(a[i] <= b[j]) {
result[k++] = a[i++];
}else {
result[k++] = b[j++];
}
}
while(i<a.length) {
result[k++] = a[i++];
}
while(j<b.length) {
result[k++] = b[j++];
}
return result;
}
3.翻转单链表
方式一：递归
public ListNode reverse1(ListNode head) {
// 当为空或者本节点为末尾节点的时候
if (head == null || head.next == null) //也是递归结束的条件
return head;
ListNode temp = head.next;
ListNode reversedHead = reverse1(head.next);
// 获取先前的下一个节点，让该节点指向自身
temp.next = head;
// 破坏以前自己指向下一个节点
head.next = null;
// 层层传递给最上面的
return reversedHead;
}
方式二：非递归
public ListNode reverse(ListNode head){
ListNode p = head,q = null,front = null;
while(p!=null){
q = p.next;//设置q是p结点的后继结点,即用q来保持p的后继结点
p.next = front;//逆转,即使p.next指向p结点的前驱结点
front = p;//front向后移一步
p = q;//p向后移一步
}
head = front;//head指向原链表的最后一个结点，完成逆转
return head;
}
4.Replace With Greatest From Right
public class Solution {
/*
* @param : An array of integers.
* @return: nothing
*/
public void arrayReplaceWithGreatestFromRight(int[] nums) {
// Write your code here.
int size = nums.length;
int max = nums[size - 1];
nums[size - 1] = -1;
for(int i=size-2; i>=0; i--) {
int tmp = nums[i];
nums[i] = max;
if(tmp > max) {
max = tmp;
}
}
}
}
5.Sum of All Subsets
public class Solution {
/*
* @param : the given number
* @return: Sum of elements in subsets
*/
public int subSum(int n) {
// write your code here
if(n == 1) return 1;
List<Integer> list = new ArrayList<>();
for(int i=1; i<=n; i++) {
list.add(i);
}
int subsetSum = getSubsetSum(list);
return subsetSum;
}
public int getSubsetSum(List<Integer> list) {
int sum = 0;
List<List<Integer>> result = new ArrayList<>();
for(int i=0; i<Math.pow(2, list.size()); i++) {
List<Integer> subList = new ArrayList<>();
int index = i;
for(int j=0; j<list.size(); i++) {
if((index & 1) == 1) {
subList.add(j);
sum += j;
}
index >>= 1;
}
if(subList.size() == 0) continue;
result.add(subList);
}
return sum;
}
}
6.连接两个字符串中的不同字符
样例
给出 s1 = aacdb, s2 = gafd
返回 cbgf
给出 s1 = abcs, s2 = cxzca;
返回 bsxz
public static String concatenetedString(String s1, String s2) {
// write your code here
String str = "";
List<Character> common = new ArrayList<>();
char[] b = s1.toCharArray();
for(int i=0; i<b.length; i++) {
if(s2.indexOf(b[i]) > -1) {
common.add(b[i]);
}
}
List<Character> notin = new ArrayList<>();
char[] b2 = s2.toCharArray();
for(int i=0; i<b2.length; i++) {
if(!common.contains(b2[i])) {
notin.add(b2[i]);
}
}
for(int i=0; i<b.length; i++) {
if(!common.contains(b[i])) {
str += b[i];
}
}
for(int i=0; i<notin.size(); i++) {
str += notin.get(i);
}
return str;
}
7.快慢指针查找中点
public class NodeListTest {
public static void main(String[] args){
int[] array = {1,2,3,4,5,6,7};
Node node = NodeList.arrToNodeList(array);
NodeList.printNodeList(node);
System.out.println();
System.out.println(NodeList.getMidNode(node));
}
}
//链表节点类
class Node {
private Node next;//节点指向的下一个节点
private int val;//本节点的值
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node [val=" + val + "]";
}
}
//链表类
class NodeList {
private static Node head, tail, curr;
/**
* 将数组转换成链表，返回链表的头结点
* @param arr
* @return
*/
public static Node arrToNodeList(int arr[]) {
if(arr.length > 0) {
for(int i=0; i<arr.length; i++) {
curr = new Node();
//节点信息
curr.setNext(null);
curr.setVal(arr[i]);
if(head == null) {//对首节点的初始化赋值
head = curr;
tail = curr;
}else{//新的节点默认为尾节点
tail.setNext(curr);
tail = curr;
}
}
}
return head;
}
/**
* 打印该链表的所有节点元素
* @param head 头结点信息
*/
public static void printNodeList(Node head) {
System.out.print(head + ", ");
while(head.getNext() != null) {
head = head.getNext();
System.out.print(head + ", ");
}
}
/**
* 根据链表信息（只包含头结点）取出中间节点的信息
* @param head 头结点信息
* @return
*/
public static Node getMidNode(Node head) {
//慢指针（每次走一步），快指针（每次走两步）初始状态都指向头结点
Node stepOne=head, stepTwo = head;
while(stepTwo!=null && stepTwo.getNext()!=null) {
stepTwo = stepTwo.getNext().getNext();
stepOne = stepOne.getNext();
}
return stepOne;
}
}
8、判断一个链表是不是一个“环”
定义两个指针fast和slow，其中fast是快指针，slow是慢指针，二者的初始值都指向链表头，slow每前进一步，fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要和慢指针比较，直到当快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表(fast先行到达尾部为NULL，则为无环链表)。
public boolean isLoop(Node head){
Node fast = head;
Node slow = head;
if (fast == null) {
return false;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return !(fast == null || fast.next == null);
}
9、查找有序序列中指定的数字第一次出现的位置
如“12345555678”查第一个“5”出现的位置（提示：二分查找法进行改进）
int myBinarySearch(int num[],int len,int key)
{
int low=0;
int hight=len-1;
int mid=0;
int switchFind=0;
int index=0;
if (num[0]==key)
{
return 1;
}
while (low<=hight)
{
mid=(hight+low)/2;
if (num[mid]==key)
{
switchFind=1;
break;
}
else if (num[mid]>key)
{
hight=mid-1;
}
else if (num[mid]<key)
{
low=mid+1;
}
}
while (switchFind)
{
mid--;
if (num[mid]!=key)
{
index=mid;
return index+2;
}
}
return -1;
}
10、写一个方法判断一个数是不是2的幂？
n & (n-1) == 0
附Java位运算：https://blog.csdn.net/lazyman_54/article/details/51283459
11、斐波那契数列递归实现与改进
是从0开始的：0，1，1，2，3，5……（不是从1开始）
public static int Recursion(int n){
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return Recursion(n-1)+Recursion(n-2);
}
时间复杂度：O（n^n）
改进：Recursion(n-1)已经包含了Recursion(n-2)的结果了，所以用递归的话又会把Recursion(n-2)展开，造成效率低下，
可以把每次加的结果给缓存起来，如下：
public static long fil(int n){
long a=1;
long b=1;
long c=0;
if(n==1) return 1;
else if(n==2) return 1;
else if(n>2){
for (int i=3;i<=n;i++){
c=a+b;
a=b;
b=c;
}
return c;
}
else{
System.out.println("the number cannot be lower than zero");
return 0;
}
}
12、查找不重复的数字（其他数字都重复2遍）
对异或运算的巧妙运用（任何数异或00都得到这个数本身）：
例如：
十进制：15 转成二进制为：11111111
十进制：2 转成二进制为：00000010
按位进行异或操作的结果为：11111101 ——>13
如果我们将这个结果继续与其中的一个数进行异或运算，就可以得出另外一个数！ 2^15^15 = 2 or 2^15^2 = 15
public static int NumberOf1(int[] arr) {
int len = arr.length;
int res = -1;
if(len > 1) {
res = arr[0];
for (int i = 1; i < len; i++) {
res = res ^ arr[i];
}
}
return res;
}
13、字符串反转（用递归）
一般会想到用数组，String的charAt, toCharArray函数。
public static String strReverseWithArray(String string){
if(string==null||string.length()==0)return string;
int length = string.length();
char [] array = string.toCharArray();
for(int i = 0;i<length;i++){
array[i] = string.charAt(length-1-i);
}
return new String(array);
}
用递归的方式如下：
public static String strReverseWithRecursive(String string){
if(string==null||string.length()==0)return string;
int length = string.length();
if(length==1){
return string;
}else{
return strReverseWithRecursive(string.substring(1))+string.charAt(0);
}
}
14、求n的加法组合，将一个整数拆分成多个整数相加的形式
例1:
3=1+1+1
3=1+2
3=3
解决思路：https://blog.csdn.net/bluetjs/article/details/52370916
public class Sum1ToN {
private void print(List<Integer> list) {
for (Integer k : list) {
System.out.print(k + "+");
}
}
private void f(int n, List<Integer> list, int start) {
if (n == 1) {
print(list);
System.out.println(1);
} else {
for (int i = start; i <=n / 2; i++) {
list.add(i);
f(n - i, list, i);
list.remove(list.size() -1);
}
print(list);
System.out.println(n);
}
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
new Sum1ToN().f(9,list, 1);
}
}
相关推荐
"LintCode：LeetCode和LintCode刷题代码" 是一个专门针对这两个知名在线编程平台的题解资源集合，尤其适用于准备面试和提升JavaScript编程技术的开发者。 LeetCode和LintCode都是全球知名的在线编程挑战平台，它们...
leetcode题库 练武不练功，到头一场空， 为了提高自己的算法能力，在lintCode进行刷题。 其中solution包是Leetcode题库里面的非面试题。 interview是Leetcode题库里面的面试题。
c++ 树形dp 刷题 算法
刷题算法提高阶段-数据结构5
在这个“刷题算法提高阶段-搜索1”中，我们将重点探讨Flood Fill算法和寻找图的最短路径问题。 Flood Fill算法，又称“洪水填充”或“区域填充”，是一种常见的图像处理和图形学算法。它通常用于颜色替换或者找出...
本主题“刷题算法提高阶段-数据结构4”将着重于一个特殊的数据结构——线段树，它是处理区间查询和更新问题的有效工具。线段树是一种树形数据结构，用于高效地维护一段连续区间的信息，如区间求和、查找最值等操作。...
本阶段的“刷题算法提高阶段-搜索5”聚焦于一种特殊的算法类型——搜索算法，特别是迭代加深ID*（IDA*）算法。搜索算法广泛应用于人工智能、游戏开发、路径规划、机器学习等多个方面。 迭代加深ID*（IDA*）算法是一...
在"刷题算法提高阶段-数据结构3"这个主题中，我们主要关注的是通过实践来提升对数据结构的理解和应用能力，特别是针对解决特定问题时如何选择合适的数据结构。 数据结构，简单来说，是组织和存储数据的方式。它决定...
算法刷题集合算法刷题集合
在编程和算法学习的过程中，搜索算法是至关重要的一个部分，特别是在刷题提升阶段。"搜索4"这个主题可能指的是在一系列算法题目中专门探讨搜索算法的第四阶段，它通常涵盖深度优先搜索（DFS, Depth First Search）等...
Lintcode是一个在线编程平台，专注于算法和数据结构的实践，提供了大量的编程题目供用户解决。这个压缩包文件包含了在Lintcode上用Java和Python语言实现的算法和数据结构的解决方案。接下来，我们将深入探讨这些关键...
### Lintcode算法分析与解答概览 #### 目录结构解析 该文档主要分为两大部分：基础概念（Part I）和编码实践（Part II）。接下来将对这两部分中的核心知识点进行详细介绍。 #### Part I - 基础概念 这部分涵盖了...
算法刷题的意义和方法 为什么要刷题 如何选择刷题平台 刷题步骤与方法 刷题实战案例 排序算法实战 查找算法实战 动态规划实战 贪心算法实战 分治算法实战 回溯算法实战 图算法实战 进阶技巧与心得 提升算法思维 如何...
算法刷题 排序算法题目 题目1：数组排序 题目2：Kth Largest Element in an Array 搜索算法题目 题目1：二分查找 题目2：搜索旋转排序数组 动态规划题目 题目1：斐波那契数列 题目2：最长公共子序列 贪心算法题目 ...
这份文档是一份关于算法学习和刷题的笔记，特别强调了通过学习这些算法可以进入国内顶尖的互联网公司，如百度、阿里巴巴和腾讯（BAT）。文档的标题和描述都表明了这是一份完整的算法刷题指南。尽管由于OCR识别错误，...
持续刷题有助于巩固基础知识，提升编程手感，为职场发展打下坚实基础。 四、labuladong的算法小抄 "labuladong的算法小抄官方完整版.pdf"是这份资源的核心内容，作者labuladong是一位知名的算法讲解者，他的小抄以...
《数据结构与算法 LeetCode 刷题宝典》是一份深度剖析编程算法的文档，主要针对 LeetCode 平台上的经典问题，通过Python和C#两种编程语言进行解答。这份宝典旨在帮助开发者提升对数据结构和算法的理解，提高解决实际...
Python刷题合集-算法编程题.zip是一个包含多个Python算法编程题的压缩文件，旨在帮助学习Python的学生和开发者提高算法和编程能力。 内容概要： 该压缩文件包含多个Python算法编程题，包括经典的数据结构问题、排序...
Talk is cheap, show me the code！
leetcode/lintcode上的算法题 About 这个仓库最初的想法是把lintcode/lintocde上面的算法题目整理一下，因为很多题目太多了显得太乱了，就不继续在GitHub上面写了，以前写的一部分移到我的博客上面了。 GitHub上面...