给定两个整数
a和b，求它们的除法的商a/b，要求不得使用乘号'*'、除号'/'以及求余符号'%'。
注意：
truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2[−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
y总的模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用：
int bsearch_1(int left, int right)
{
while (left < right)
{
int mid = left + right >> 1;
if (check(mid)) right = mid; // check()判断mid是否满足性质
else left = mid + 1;
}
return left;
}
// 区间[left, r]被划分成[left, mid - 1]和[mid, r]时使用：
int bsearch_2(int left, int right)
{
while (left < right)
{
int mid = left + right + 1 >> 1;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}/**
* 调整为大顶堆
* @param arr 待调整的数组
* @param parent 当前父节点的下标
* @param length 需要对多少个元素进行调整
*/
private static void adjustHeap(int[] arr, int parent, int length){
//临时保存父节点
int temp = arr[parent];
//左子节点的下标
int child = 2 * parent + 1;
//如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
while(child < length){
//判断左子节点和右子节点的大小,若右边大，则把child定位到右边
if(child + 1 < length && arr[child] < arr[child + 1]){
child ++;
}
//若child大于父节点，则交换位置，否则退出循环
if(arr[child] > temp){
//父子节点交换位置
arr[parent] = arr[child];
//因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
//把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
parent = child;
child = 2 * parent + 1;
}else{
//如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
//因此无需继续循环
break;
}
}
//把当前节点值替换为最开始暂存的父节点值
arr[parent] = temp;
}
public static void main(String[] args) {
int[] arr = {4,1,9,3,7,8,5,6,2};
//构建一个大顶堆，从最下面的非叶子节点开始向上遍历
for (int i = arr.length/2 - 1 ; i >= 0; i--) {
adjustHeap(arr,i,arr.length);
}
System.out.println(Arrays.toString(arr));
}
//打印结果： [9, 7, 8, 6, 1, 4, 5, 3, 2]。 和我们分析的结果一模一样给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
写法一：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
if(nums.length==0){
return ans;
}
dfs(nums,0,new LinkedList<>(),ans);
System.out.println(ans.toString());
return ans;
}
private void dfs(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> ans){
if(index==nums.length){
ans.add(new LinkedList<>(subset));
return;
}
subset.add(nums[index]); //先选择下标为index的数
dfs(nums,index+1, subset, ans); //在选择index的情况下，确定index+1的选择情况
subset.removeLast(); //不选择下标为index的数
dfs(nums,index+1, subset, ans); //在不选择index的情况下，确定index+1的选择情况
}
}一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2解题小经验：
- 如果面试题要求在无权图中找出两个节点之间的最短距离，那么广度优先搜索可能是更适合的算法。
- 如果面试题要求找出符合条件的所有路径，那么深度优先搜索可能是最合适的算法。
给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值*。*numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int[] counts = new int[26];
for (int i = 0; i < s1.length(); i++) {
counts[s1.charAt(i) - 'a']++;
counts[s2.charAt(i) - 'a']--;
}
if (isAllZero(counts)) {
return true;
}
//i是右边界
for (int i = s1.length(); i < s2.length(); i++) {
counts[s2.charAt(i) - 'a']--;
counts[s2.charAt(i - s1.length()) - 'a']++;
if (isAllZero(counts)) {
return true;
}
}
return false;
}
private boolean isAllZero(int[] counts) {
for (int count : counts) {
if (count != 0) {
return false;
}
}
return true;
}
}给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
while (n > 0) {
fast = fast.next;
n--;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}