剑指Offer

剑指 Offer 04. 二维数组中的查找

Go题解：

func findNumberIn2DArray(matrix [][]int, target int) bool {
    
	//边界条件判断
	if len(matrix) == 0 {
    
		return false
	}
	//二维数据的大小：长、宽
	n := len(matrix)
	m := len(matrix[0])
	//设置初始遍历元素的位置，数组的右上角matrix[n-1][0]
	i, j := n-1, 0
	//从右上角开始遍历元素
	for i >= 0 && j < m {
    
		if matrix[i][j] == target {
    
			return true
		}
		if matrix[i][j] > target {
    
			i--
		} else if matrix[i][j] < target {
    
			j++
		}
	}
	return false
}

11. 旋转数组的最小数字

//直接排序求解
class Solution {
    
    public int minArray(int[] numbers) {
    
        Arrays.sort(numbers);
        return numbers[0];
    }
}

03. 数组中重复的数字

题目描述：找出数组当中重复的数字
解决思路：用集合保存出现过的数字，利用集合当中的数据是非重复的判断重复出现的数字。

• Java题解

class Solution {
    
   public int findRepeatNumber(int[] nums) {
    
        Set<Integer> set = new HashSet<>();
        int repeat = -1;
        for (int num : nums) {
    
            if (!set.add(num)) {
    
                repeat = num;
                break;
            }
        }
        return repeat;
   }
}

09. 用两个栈实现队列

问题描述：用两个栈模拟实现一个队列
解题思路：用 一个栈作为添加数据使用，另一个栈用作删除数据、模拟出队列使用

• Java题解

class CQueue {
    

    private Stack<Integer> addStack;
    private Stack<Integer> delStack;

    public CQueue() {
    
        addStack = new Stack<>();
        delStack = new Stack<>();
    }

    public void appendTail(int value) {
    
        addStack.push(value);
    }

    public int deleteHead() {
    
        //两个栈都为空，则返回-1
        if (addStack.isEmpty() && delStack.isEmpty()) {
    
            return -1;
        }
        if (!delStack.isEmpty()) {
    
            return delStack.pop();
        }
        while (!addStack.isEmpty()) {
    
            int val = addStack.pop();
            delStack.push(val);
        }
        return delStack.pop();
    }
}

10- I. 斐波那契数列

问题描述：求斐波那契（Fibonacci）数列的第 n 项。
题解：利用动态规划的算法进行解决。关键在于求出状态转移方程

• Java题解

/**
 * 理解动态规划的思想
 * 斐波那契数列： 0，1，1，2，3，5
 * 下标：         0，1，2，3，4，5
 *  ----------------------------------------
 *  个例演算：n = 5
 *  序号  a    b   sum
 *  0     0    1    1
 *  1     1    1    2
 *  2     1    2    3
 *  3     2    3    5
 *  4     3    5    7
 *  5     5    7    12
 *  所以最终经过5次运算返回结果 a 的值
 */
class Solution {
    
    public int fib(int n) {
    
        int a = 0, b = 1, sum;
        for (int i = 0; i < n; i++) {
    
            sum = (a + b) % (1000000007);
            a = b;
            b = sum;
        }
        return a;
    }
}

10- II. 青蛙跳台阶问题

/**
 * 斐波那契数列
 * 剑指 Offer 10- II. 青蛙跳台阶问题
 * 动态规划的思想：由动态转移方程入手
 * 1: 1
 * 2: 11 2
 * 3: 111  12  21
 */
class Solution {
    
    public int numWays(int n) {
    
        int a = 1, b = 1, sum;
        for (int i = 0; i < n; i++) {
    
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}