头像

zning




离线:3个月前


最近来访(52)
用户头像
Arthur_5
用户头像
林大B
用户头像
快活呀
用户头像
889
用户头像
小熊熊
用户头像
changyou1009
用户头像
涝魔王
用户头像
沐星不仙了
用户头像
教练....我想学算法
用户头像
当你的眼睛眯着笑
用户头像
眼泪划过的星空
用户头像
QQ家族副族长
用户头像
翻滚的小浪花
用户头像
沙漠之狐
用户头像
Cedric2022
用户头像
柠檬味的胡萝卜
用户头像
阿菜
用户头像
skydegree
用户头像
冷丁Hacker
用户头像
吴霖峰


zning
2019-10-11 11:20

题目来自剑指 offer第 42题

动态规划

思路

  1. 定义状态: dp[i] 为数组 [0…i]中的最大和, 一定包含dp[i]

注意是连续子数组, 所以必须包含最后一个元素, 否则就断了

  1. 定义输出: dp[]中最大的值

  2. 状态转移方程: dp[i] = dp[i - 1] >= 0 ? dp[i - 1] + nums[i] : nums[i]

因为一定包含 nums[i], 所以如果 dp[i-1] >=0, 求最大值, 就加上

代码
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length + 1];
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + nums[i];
        else dp[i] = nums[i];
        res = Math.max(res, dp[i]);
    }
    return res;
}



zning
2019-10-11 11:20

题目来自剑指 offer第 42题

动态规划

思路

  1. 定义状态: dp[i] 为数组 [0…i]中的最大和, 一定包含dp[i]

注意是连续子数组, 所以必须包含最后一个元素, 否则就断了

  1. 定义输出: dp[]中最大的值

  2. 状态转移方程: dp[i] = dp[i - 1] >= 0 ? dp[i - 1] + nums[i] : nums[i]

因为一定包含 nums[i], 所以如果 dp[i-1] >=0, 求最大值, 就加上

代码
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length + 1];
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + nums[i];
        else dp[i] = nums[i];
        res = Math.max(res, dp[i]);
    }
    return res;
}



zning
2019-10-11 11:03

题目中没有要求相对位置不变, 所以可以使用快排的思路解题

思路如下(类似快速排序, 快速排序本身就是不稳定的):

  • 设置两个指针,一个指针pBegin指向数组第一个元素,一个指针pEnd指向数组的最后一个元素;
  • 当pBegin < pEnd时:pBegin指针不断右移,直到遇到某个偶数为止;同样的,pEnd不断左移,直到遇到某个奇数为止。
  • 若此时pBegin < pEnd:交换两个元素,因此排在前面的奇数被交换到了后面
class Solution {
    public void reOrderArray(int[] array) {
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            while (array[i] % 2 == 1) i++;
            while (array[j] % 2 == 0) j--;
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

如果要求相对位置不变, 可使用类似于冒泡排序

class Solution {
    public void reOrderArray(int[] array) {
        for (int i = array.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (array[j] % 2 == 0 && array[j + 1] % 2 == 1) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}



zning
2019-10-11 10:26

题目来源: 剑指offer第 39题

方法一

数组中有一个数字出现次数超过了一半,说明这个数字的出现次数比其他所有数字的出现次数之和加起来还要多

  • 在遍历数组的时候记录两个值
  • 数组中的数字
  • 次数
  • 遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。
  • 遍历结束后,所保存的数字即为所求。最后再判断它是否符合条件。
代码
class Solution {
    public int moreThanHalfNum_Solution(int[] nums) {
        int res = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == res) count++;
            else count--;

            if (count == 0) {
                res = nums[i];
                count = 1;
            }
        }
        return res;
    }
}

方法二: 基于快排的切分法

由题意可知, 所求数字是排好序数组的中位数

  1. 在随机快速排序算法中, 我们先在数组中随机选取一个数字,然后调整数组中的数字的顺序

  2. 使得比选中的数字小的数字,都排在他的左边

  3. 比选中的数字大的数字,都排在他的右边,

  4. 如果选中的数字的下标刚好是 n/2, 那么这个数字就是数组的中位数

  5. 如果他的下标大于 n/2, 那么中位数应该位于他的左边, 继续在他的左边部分进行查找

  6. 如果他的下标小于 n/2, 那么中位数应该位于他的右边, 继续在他的右边部分进行查找

  7. 递归进行运算

代码
class Solution {
public int moreThanHalfNum_Solution(int[] nums) {
        return quickFind(nums, nums.length / 2);
    }

    // 快速排序方法查找
    private int quickFind(int[] nums, int index) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int p = partition(nums, l, r);
            if (p < index) {
                l = p + 1;
            } else if (p > index) {
                r = p - 1;
            } else {
                return nums[p];
            }
        }
        return -1;
    }

    private int partition(int[] nums, int l, int r) {
        int pVal = nums[l];
        while (l < r) {
            while (nums[r] >= pVal && l < r) r--;
            nums[l] = nums[r];
            while (nums[l] <= pVal && l < r) l++;
            nums[r] = nums[l];
        }
        nums[l] = pVal;
        return l;
    }
}



zning
2019-09-22 15:19

KMP字符串

理解KMP字符串

推荐文章(写的很好): KMP算法(研究总结,字符串)

题目 831

代码
import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 10010;     // 模板串的数据规模
    static final int M = 100010;    // 匹配字符串的数据规模
    static char[] p = new char[N];  // 模板串
    static char[] s = new char[M];  // 被匹配字符串
    static int[] next = new int[N]; // next数组

    public static void main(String[] args) throws IOException {
        // 对输入数据进行初始化
        int n = Integer.parseInt(reader.readLine()); // 模板串的长度
        String pStr = reader.readLine();
        for (int i = 1; i <= n; i++) p[i] = pStr.charAt(i - 1);

        int m = Integer.parseInt(reader.readLine()); // 被匹配字符串的长度
        String sStr = reader.readLine();
        for (int i = 1; i <= m; i++) s[i] = sStr.charAt(i - 1);

        // 求 next的过程
        for (int i = 2, j = 0; i <= n; i++) {   // i = 1的时候只有一个元素, 最长前缀的长度为 0
            while (j != 0 && p[i] != p[j + 1]) j = next[j];
            if (p[i] == p[j + 1]) j++;
            next[i] = j;
        }

        // kmp匹配过程
        // i指向 s将要匹配的位置, j指向已经匹配模板串已经匹配成功的位置
        for (int i = 1, j = 0; i <= m; i++) {
            while (j != 0 && s[i] != p[j + 1]) j = next[j];  // 进行 next跳转
            // 继续进行匹配, 如果此时模板串的字符和被匹配字符串的字符相等, 继续向下进行匹配++
            if (s[i] == p[j + 1]) j++;
            // 如果匹配成功
            if (j == n) {
                log.write(i - n + " "); // 将 s串中起点的位置写入
                j = next[j];    // 进行 next跳转
            }
        }
        log.flush();    // 关闭输入输出流
        reader.close();
        log.close();
    }
}



zning
2019-09-22 11:36

单调队列的使用

代码
import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 1000010;
    static int[] q = new int[N];  // 队列数组, 其中存放 arr的下标值
    static int[] arr = new int[N];
    static int hh = 0, tt = -1;  // tt指向栈顶元素

    public static void main(String[] args) throws IOException {
        // 对输入数据进行初始化
        String[] s1 = reader.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int k = Integer.parseInt(s1[1]);
        String[] s = reader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(s[i]);

        // 查找最小值
        for (int i = 0; i < n; i++) {
            // 判断队头是否已经滑出窗口, 如果滑出窗口, 则弹出队首元素,维护窗口大小不超过 k, 每次值滑动一次, 所以可以使用 if
            if (hh <= tt && i - k + 1 > q[hh])
                hh++;
            // 寻找窗口中的最小值
            while (hh <= tt && arr[q[tt]] >= arr[i]) tt--;

            q[++tt] = i;    // 将本轮下标添加到队列中
            // 保证满足窗口大小, 比如窗口大小为 3, 不能此时只进入 2个数字
            if (i + 1 >= k) log.write(arr[q[hh]] + " ");    // 窗口内的最小值为队首元素
        }
        log.write("\n");
        hh = 0;
        tt = -1;
        // 查找最大值
        for (int i = 0; i < n; i++) {
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && arr[q[tt]] <= arr[i]) tt--;
            q[++tt] = i;
            if (i + 1 >= k) log.write(arr[q[hh]] + " ");
        }
        // 关闭输入输出流
        log.flush();
        reader.close();
        log.close();
    }
}



zning
2019-09-22 09:55

使用 Scanner, System.out.println()

运行时间: 7806ms

代码
import java.util.*;

public class Main {

    static final int N = 100010;
    static int[] stk = new int[N];  // 栈数组
    static int tt = -1;  // tt指向栈顶元素

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            while (tt != -1 && stk[tt] >= x)
                tt--;

            if (tt != -1)
                System.out.print(stk[tt] + " ");
            else
                System.out.print("-1 ");
            // 将新元素添加到 stk中
            stk[++tt] = x;
        }

    }
}

使用 BufferReader, BufferWriter

运行时间: 2422ms

代码
import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 100010;
    static int[] stk = new int[N];  // 栈数组
    static int tt = -1;  // tt指向栈顶元素

    public static void main(String[] args) throws IOException {


        int n = Integer.parseInt(reader.readLine());

        String[] s = reader.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(s[i]);
            while (tt != -1 && stk[tt] >= x)
                tt--;

            if (tt != -1)
                log.write(stk[tt] + " ");
            else
                log.write("-1 ");

            // 将新元素添加到 stk中
            stk[++tt] = x;
        }
        // 关闭输入输出流
        log.flush();
        reader.close();
        log.close();
    }
}



zning
2019-09-22 09:11

具体过程见代码

代码
import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static int[] q = new int[N];      // 数据规模为 10w
    static int hh = 0, tt =-1;      // hh指向队头, tt指向队尾

    // 入队
    public static void push(int val) {
        q[++tt] = val;
    }

    // 出队
    public static void pop() {
        hh++;
    }

    // 判断队列是否为空
    public static boolean empty() {
        return hh > tt;
    }

    // 查询队头元素
    public static int query() {
        return q[hh];
    }

    // 查询队尾元素
    public static int queryToTail() {
        return q[tt];
    }
    // 程序入口
    public static void main(String[] args) throws IOException {
        int m = Integer.parseInt(reader.readLine());

        while (m-- > 0) {
            String[] s = reader.readLine().split(" ");
            if (s[0].equals("push")) {
                push(Integer.parseInt(s[1]));
            } else if (s[0].equals("pop")) {
                pop();
            } else if (s[0].equals("query")) {
                System.out.println(query());
            } else {    // s[0].equals("empty")
                if (empty()) System.out.println("YES");
                else System.out.println("NO");
            }
        }
    }
}



zning
2019-09-22 08:59

具体过程见代码

代码
import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static int[] stk = new int[N];      // 数据规模为 10w
    static int tt = 0;                  // 指向栈顶的指针

    // 入栈
    public static void push(int val) {
        stk[++tt] = val;
    }

    // 出栈
    public static void pop() {
        tt--;
    }

    // 判断栈是否为空
    public static boolean empty() {
        return tt == 0;
    }

    // 查询栈顶元素
    public static int query() {
        return stk[tt];
    }

    // 程序入口
    public static void main(String[] args) throws IOException {
        int m = Integer.parseInt(reader.readLine());

        while (m-- > 0) {
            String[] s = reader.readLine().split(" ");
            if (s[0].equals("push")) {
                push(Integer.parseInt(s[1]));
            } else if (s[0].equals("pop")) {
                pop();
            } else if (s[0].equals("query")) {
                System.out.println(query());
            } else {    // s[0].equals("empty")
                if (empty()) System.out.println("YES");
                else System.out.println("NO");
            }
        }
    }
}



zning
2019-09-22 07:28

链表

为什么使用数组来模拟链表

如果数据规模很大, 一个一个的new操作太慢了, 会超时, 使用数组会大大加快速度

单链表

数组模拟单链表

数组表示单链表.png

题目826

代码
import java.io.*;
import java.util.Scanner;

public class Main {
    private static int N = 100010;  // 数据规模为 10w

    private static int head;                // 表示头结点的下标
    private static int[] e = new int[N];    // 表示结点 i的值
    private static int[] ne = new int[N];   // 表示结点 i的 next指针是多少
    private static int idx;                 // 表示存储当前结点已经使用结点的下一个结点

    // 初始化数据
    private static void init() {
        head = -1;  // 没有头结点
        idx = 0;    // 没有存入数据
    }

    // 将 val插到头结点
    private static void addToHead(int val) {
        e[idx] = val;   // 赋值
        ne[idx] = head; // 插入之前头结点的前面
        head = idx;     // 更新头结点信息
        idx++;          // idx向右移动
    }

    // 将下标是 k的点后面的点删掉
    private static void remove(int k) {
        ne[k] = ne[ne[k]];  // 让下标为 k的结点指向 下个结点的下个结点
    }

    // 将 val插入下标为 k的点的后面
    private static void add(int k, int val) {
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }

    // 程序入口
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());

        init();     // 初始化操作

        // 进行 m次操作
        while (m-- > 0) {
            String[] s = reader.readLine().split(" ");

            if (s[0].equals("H")) {  // 插入头结点操作, 不能使用 ==, 要使用 equals()

                int val = Integer.parseInt(s[1]);
                addToHead(val);
            } else if (s[0].equals("I")) {   // 普通插入操作
                int k = Integer.parseInt(s[1]);
                int val = Integer.parseInt(s[2]);
                add(k - 1, val);    // 第 k个结点的下标为 k-1, 所以插入到下标为 k-1结点的后面
            } else {    // s[0] == "D", 删除操作
                int k = Integer.parseInt(s[1]);

                if (k == 0) {  // 题意: k = 0, 删除头结点
                    head = ne[head];
                } else
                    remove(k - 1);  // 第 k个结点的下标为 k-1, 所以是删除到下标为 k-1后面的后面
            }
        }

        // 打印输出
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}