javaisnotgood的博客

题目描述输入一个链表，反转链表后，输出新链表的表头。反转链表是面试的基础题，掌握是很有必要的。我们采用迭代思想进行链表反转首先我们定义三个指针，分别表示前一个节点pre，当前节点cur，中间节点temp每次循环时使得当前节点指向前一节点，然后节点后移进行下一反转。# -*- coding:utf-8 -*-# class ListNode:# def __in...

转载自https://blog.csdn.net/xiaoquantouer/article/details/51620657一、算法简述Floyd判圈算法（Floyd Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm），是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。...

import java.util.*;public class MyClass { //快速排序public static void quick_sort(int s[], int l, int r){ if (l < r) { //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1 int...

实现strStr()函数。给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。示例 1:输入: haystack = "hello", needle = "ll"输出: 2示例 2:输入: haystack = "aaaaa", needl...

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。示例:输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]输出: [1,2,4,7,5,3,6,8,9]解释:说明:给定矩阵中的元素总数不会超过 100000 。思路：横坐标为raw ...

给定一个没有重复数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]class Solution { public List<List<Integer>> permute(int[] nums)...

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].class Solution { public List<String> lett...

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例:输入: 5输出:[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]思路：杨辉三角一看大家应该就明白，就是每一个数都等于其左上右上的数的和，首先我们可以知道第一个list是1然...

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。思路：先找出所有以遍历的点为结尾的子序列的最大值，然后找出所...

O(1) 时间复杂度样例n=4，返回 true;n=5，返回 false.挑战O(1) time1.第一种解法通过for循环从0开始判断2的x次幂是否等于给定的数，这种方法的时间复杂度较大。public static boolean isPowOfTwo(int n) { int temp = 0; for (int i = 1; ; i++) { ...

牛顿迭代法的大题意思就是通过不停的迭代来逐渐的使方程收敛。因为切线是一条直线，也就是线性的，所以我们可以说，A点的切线是f（x）的线性逼近。离A点距离越近，这种逼近的效果也就越好，也就是说，切线与曲线之间的误差越小。所以我们可以说在A点附近，切线约等于f(x)；例如我们求m的平方根其实就是相当于求f(x) = x^2 - m方程与x轴交点也就是求想x^2 - m = 0 的根。Xn...

描述有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？样例给出 m = 3 和 n = 3, 返回 6.给出 m = 4 和 n = 5, 返回 35. start               end 分析：1.由于每一时刻只能...

描述给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。样例比如，给出下列数字三角形：[ [2], [3,4], [6,5,7], [4,1,8,3]]从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。思路:大家不要被这个样例所迷惑，这个题目的用意不是找每行的最小值，而是去找最短路径，所以数不能跨越两个数来...

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。样例给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。思路：删除有序数列中重复数字，返回无重复数组的长度。可以从相反的角度考虑，就是把所有数组中不相同的数字取出来，然后输出长度。public class Solution...

合并两个排序的整数数组A和B变成一个新的数组。你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。样例给出 A = [1, 2, 3, empty, empty], B = [4, 5]合并之后 A 将变成 [1,2,3,4,5]思路：   1. 选择从后往前覆盖，先比较最后一个数的大小，然后从后往前挨个比较大小大的插入，小的等待。2.当i和j都没有消耗完的时候，从后往前，...

比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母 注意事项在 A 中出现的 B 字符串里的字符不需要连续或者有序。样例给出 A = "ABCD" B = "ACD"，返回 true给出 A = "ABCD" B = "AABC"， 返 回 false 思路：题目的意思就是B中的字符要全部出现在A中，并且例如第二个样例中A在B中有两次，在A中也必须出现两次才算...

给定一个整数数组A。定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。样例给出A=[1, 2, 3]，返回 B为[6, 3, 2]采取分治法，减少了重复计算。result[i] = left[i] * right[i] ,left[i] = A[0]*A[1]***A[i-1]，right[i] = A[i+1]...

描述给定一个旋转排序数组，在原地恢复其排序。说明什么是旋转数组？比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]样例[4, 5, 1, 2, 3] -&gt; [1, 2, 3, 4, 5]挑战使用O(1)的额外空间和O(n)时间复杂度解决方案：1、暴力求解法，直接对给定数组进行排序。由于题中规定时间复杂度...

二分查找能解决从给定的一组有顺序的数中查找出某一个数这类问题。它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。left 为序列开始mid 为序列中间right 为序列结束位置value 为查找的关键字（默认序列为升序）思路就是先将序列中间位置记录的关键字mid与需要查找的关键字value比较，如果相同则查找成功，否则利用中间位置mid将序列分...

在java的位运算符中有一个异或的运算符，用符号(^)表示，其运算规则是:在两个二进制操作数的相同位中，相同则结果为0，不同则结果为1。例如：0011^1010 = 1001         2^3 = 其所对应二进制的10^11=01 = 1异或运算有三个特征，一个是0与一个数做异或操作还是本身，本身与本身做异或操作为0，异或操作还满足交换率。利用这一特点我们可以利用异或运算的特性来做异常数值的...

问题;对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。如果 source = "source" 和 target = "target"，返回 -1。如果 source = "abcdabcdefg" 和 target = "bcd"，返回 1。答案很简单利用Strin...

package day1;import java.math.BigDecimal;/** *  * @author zjs * */public class Solution {    public static long trailingZeros(long n) {    BigDecimal mult = new BigDecimal(1);//bigdecimal类中的乘法    in...