算法模版,今天开始背

这篇具有很好参考价值的文章主要介绍了算法模版,今天开始背。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. 二分查找算法
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界,target 肯定不存在,返回 -1
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

  1. 滑动窗口算法

上下是对称的文章来源地址https://www.toymoban.com/news/detail-646759.html


/* 滑动窗口算法框架 */
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据
    HashMap<Character, Integer> window = new HashMap<>();

    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时,可能导致超时
        System.out.printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            window.put(d, window.get(d) - 1);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
  1. 二叉树的层序遍历

// 输入一棵二叉树的根节点,层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    // 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 将下一层节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }
}
  1. 动态规划算法
以最小硬币数为例
class Solution {
    int[] memo;

    int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // 备忘录初始化为一个不会被取到的特殊值,代表还未被计算
        Arrays.fill(memo, -666);

        return dp(coins, amount);
    }

    int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // 查备忘录,防止重复计算
        if (memo[amount] != -666)
            return memo[amount];

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 在子问题中选择最优解,然后加一
            res = Math.min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}
  1. Nsum问题
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSum(nums,4,0,target);
    }

    public List<List<Integer>> nSum(int[] nums, int n, int start , long target){
        List<List<Integer>> result = new ArrayList<>();
        if(n==2){
            int left = start;
            int right = nums.length -1 ;
            while(left<right){
                int leftValue = nums[left];
                int rightValue = nums[right];
                int sum = leftValue + rightValue;
                if(sum==target){
                    List<Integer> collect = new ArrayList<>();
                    collect.add(leftValue);
                    collect.add(rightValue);
                    result.add(collect);    
                    while(left<right&&nums[left]==leftValue) left++;
                    while(left<right&&nums[right]==rightValue) right--;       
                }else if( sum > target){
                    right--;
                     while(left<right&&nums[right]==rightValue) right--;  
                }else{
                    left++;
                    while(left<right&&nums[left]==leftValue) left++;

                }
            }
        }else{
            for(int i = start;i<nums.length;i++){
                List<List<Integer>> temp = nSum(nums,n-1,i+1,target-nums[i]);
                for(List<Integer> list : temp){
                    list.add(nums[i]);
                    result.add(list);
                }
                while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
            }
        }
        return result;
    }

}

到了这里,关于算法模版,今天开始背的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Android开发UI新技能,你get这个新技能了吗?(附源码详解),从零开始学数据结构和算法

    2. 文本输入框 val state = +state { “Text Field to input” } TextField( value = state.value, onValueChange = { state.value = it } ) 3. 按钮 Button(text = “咬我啊”, onClick = { Log.v(“test”, “被咬了”) }) 4.弹出框 MaterialTheme { Column { val openDialog = +state { false } Button(“Click me”, onClick = { openDialog.value = true

    2024年04月12日
    浏览(37)
  • java入门,程序=数据结构+算法

    一、前言 在学习java的时候,我印象最深的一句话是:程序=数据结构+算法,对于写java程序来说,这就是java的入门。 二、java基本数据结构与算法 1、数据类型 java中的数据类型8种基本数据类型: 整型 byte 、short 、int 、long 浮点型 float 、 double 字符型 char 布尔型 boolean 还有包

    2024年02月05日
    浏览(59)
  • Java 数据结构与算法-树

    树的基础知识 树是算法面试经常遇到的数据结构之一,在实际工作中也有可能经常用到…… 应聘者在准备算法面试时最需要重视的是二叉树…… 二叉树是一种典型的具有递归性质的数据结构。二叉树的根节点可能有子节点,子节点又是对应子树的根节点,它可能也有自己的

    2024年02月08日
    浏览(52)
  • java数据结构与算法:栈

    代码: 测试: 链表头为堆栈顶 代码: 测试:

    2024年01月21日
    浏览(51)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(45)
  • 【数据结构】用Java实现七大排序算法

    目录 🌷1. 排序的概念及引用 1.1 排序的概念 1.2 衡量指标 1.2 十个排序算法  1.3 十个排序性能对比 🌷2. 冒泡排序 2.1 算法描述 2.2 动图 ⭐️代码优化 🌷3. 选择排序 3.1 算法描述 3.2 动图  3.3 代码 🌷4. 插入排序 4.1 算法描述 4.2 动图  4.3 代码 🌷5 希尔排序 5.1 描述 5.2 动图  

    2023年04月23日
    浏览(49)
  • 【算法与数据结构】Java实现查找与排序

    也叫做折半查找,属于有序查找算法。 前提条件 :数组数据必须有序,从小到大,或者从大到小都是可以的。 如果是无序的,也可以先进行排序。 但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数

    2024年01月19日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包