java 如何实现 binary search 二分查找法?
顺序查找
如果让你在一堆书架上找到自己想要的书,你会怎么找呢?
实际上最简单最粗暴的方式就是一本一本的看过去。
这个用计算机实现就对应着顺序查找。
概念
顺序查找适合于存储结构为顺序存储或链接存储的线性表。
基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有...
2020-06-08 07:13:08 |
Algorithm
leecode 126 127-Word Ladder II-backtracking 回溯算法 + 剪枝 BFS DFS
题目 127
word-ladder
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
Ev...
2020-06-08 07:13:08 |
Algorithm
leecode 39 Combination Sum backtracking 回溯算法 + 剪枝
缘起
一个不会解的问题
https://leetcode.com/problems/combination-sum/
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集...
2020-06-08 07:13:08 |
Algorithm
leecode 详解 03-Manacher Algorithm 马拉车算法
Manacher’s Algorithm 马拉车算法。
马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性。
解决奇偶的问题
首先我们解决下奇数和偶数的问题,在每个字符间插入”#”,并且为了使得扩展的过程中,到边界后自动结束,在两端分别插入 ...
2020-06-08 07:13:08 |
Algorithm
【leetcode】020-39. 组合总和 Combination Sum + 40. 组合总和 II Combination Sum II + 77. 组合 combinations + 216. Combination Sum III + 377. 组合总和 Ⅳ
77. 组合
题目
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例
示例 1:
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:
输入:n = 1, k = 1
输出:[[1]]
```...
2020-06-08 07:13:08 |
Algorithm
【leetcode】019-36. 有效的数独 Valid Sudoku + 37. 解数独 sudoku solver
36. 有效的数独 Valid Sudoku
题目
请你判断一个 9 x 9 的数独是否有效。
只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:...
2020-06-08 07:13:08 |
Algorithm
【leetcode】018-34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
写在前面
有些题目看起来很简单,深挖下去往往有很多值得深思的东西。
本文就来讨论一下二分查找法的问题,以及这道题背后真正想考察的东西。
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:
你可...
2020-06-08 07:13:08 |
Algorithm
【leetcode】017-33. 搜索旋转排序数组 Search in Rotated Sorted Array + 81. Search in Rotated Sorted Array II + 153. Find Minimum in Rotated Sorted Array 寻找旋转排序数组中的最小值 + 154.Find Minimum in Rotated Sorted Array II
33. 搜索旋转排序数组 Search in Rotated Sorted Array
题目
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1...
2020-06-08 07:13:08 |
Algorithm