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”将着重于一个特殊的数据结构——线段树，它是处理区间查询和更新问题的有效工具。线段树是一种树形数据结构，用于高效地维护一段连续区间的信息，如区间求和、查找最值等操作。...
在"刷题算法提高阶段-数据结构7"这个主题中，我们主要关注的是通过实践来提升对数据结构的理解和应用能力，特别是针对解决具体问题的能力。 数据结构，简单来说，就是组织和存储数据的方式。不同的数据结构适用于...
本阶段的“刷题算法提高阶段-搜索5”聚焦于一种特殊的算法类型——搜索算法，特别是迭代加深ID*（IDA*）算法。搜索算法广泛应用于人工智能、游戏开发、路径规划、机器学习等多个方面。 迭代加深ID*（IDA*）算法是一...
在"刷题算法提高阶段-数据结构3"这个主题中，我们主要关注的是通过实践来提升对数据结构的理解和应用能力，特别是针对解决特定问题时如何选择合适的数据结构。 数据结构，简单来说，是组织和存储数据的方式。它决定...
"刷题算法提高阶段-搜索6"这个主题聚焦于一个特定的算法类别——搜索算法，特别是双端广度优先搜索（Bidirectional Breadth-First Search, 简称双向BFS）和A*搜索算法。这两种算法都是在解决复杂问题时，如路径寻找...
2021年的力扣刷题算法截图汇总是一个珍贵的学习资源，它可能包含了当年力扣上的热门问题及其解决方案的截图。由于标签为"python"，我们可以推断这些截图主要涉及使用Python语言解决这些问题。 在Python编程中，解决...
算法刷题集合算法刷题集合
"刷题算法提高阶段-搜索3"这个主题聚焦于搜索算法的深入学习，特别是深度优先搜索（DFS，Depth-First Search）的应用。在这个阶段，我们将会深入理解DFS如何帮助解决连通性和搜索顺序的问题。 深度优先搜索是一种...
在编程和算法学习的过程中，搜索算法是至关重要的一个部分，特别是在刷题提升阶段。"搜索4"这个主题可能指的是在一系列算法题目中专门探讨搜索算法的第四阶段，它通常涵盖深度优先搜索（DFS, Depth First Search）等...
Lintcode是一个在线编程平台，专注于算法和数据结构的实践，提供了大量的编程题目供用户解决。这个压缩包文件包含了在Lintcode上用Java和Python语言实现的算法和数据结构的解决方案。接下来，我们将深入探讨这些关键...
### Lintcode算法分析与解答概览 #### 目录结构解析 该文档主要分为两大部分：基础概念（Part I）和编码实践（Part II）。接下来将对这两部分中的核心知识点进行详细介绍。 #### Part I - 基础概念 这部分涵盖了...
【Java算法刷题笔记(LeetCode、牛客)】这篇笔记主要涵盖了三个核心知识点：双指针技巧、哈希表的应用以及深度优先搜索算法（DFS）。 1. **双指针技术**： 双指针是算法中常用的一种技巧，通常用于处理链表和数组的...
算法刷题的意义和方法 为什么要刷题 如何选择刷题平台 刷题步骤与方法 刷题实战案例 排序算法实战 查找算法实战 动态规划实战 贪心算法实战 分治算法实战 回溯算法实战 图算法实战 进阶技巧与心得 提升算法思维 如何...
力扣刷题集-更新至链表 本资源摘要信息主要涉及算法领域，着重于数组、链表、排序算法、二分查找等知识点。 数组 数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便地通过下标索引的方式获取到下标...
C++算法刷题笔记 本资源摘要信息将对C++算法刷题笔记中提到的知识点进行总结和解释。 1. 动态规划（Dynamic Programming） 动态规划是一种解决复杂问题的方法，通过将原问题分解为相对简单的子问题，来解决原问题...