<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0014.Longest-Common-Prefix/">下一页➡️</a></p>

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

**Example 1**:

Input: strs = ["flower","flow","flight"]

Output: "fl"

**Example 2**:

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation: There is no common prefix among the input strings.

**Constraints:**

- 1 <= strs.length <= 200

- 0 <= strs[i].length <= 200

- strs[i] consists of only lower-case English letters.

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

- 对 strs 按照字符串长度进行升序排序，求出 strs 中长度最小字符串的长度 minLen

- 逐个比较长度最小字符串与其它字符串中的字符，如果不相等就返回 commonPrefix,否则就把该字符加入 commonPrefix

package leetcode

import "sort"

func longestCommonPrefix(strs []string) string {

sort.Slice(strs, func(i, j int) bool {

return len(strs[i]) <= len(strs[j])

})

minLen := len(strs[0])

if minLen == 0 {

return ""

}

var commonPrefix []byte

for i := 0; i < minLen; i++ {

for j := 1; j < len(strs); j++ {

if strs[j][i] != strs[0][i] {

return string(commonPrefix)

}

}

commonPrefix = append(commonPrefix, strs[0][i])

}

return string(commonPrefix)

}

<div style="display: flex;justify-content: space-between;align-items: center;">

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0013.Roman-to-Integer/">⬅️上一页</a></p>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0015.3Sum/">下一页➡️</a></p>

</div>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0014.Longest-Common-Prefix/">⬅️上一页</a></p>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0319.Bulb-Switcher/">下一页➡️</a></p>

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

**Example 1:**

Input: n = 3

Output: 1

Explanation: At first, the three bulbs are [off, off, off].

After the first round, the three bulbs are [on, on, on].

After the second round, the three bulbs are [on, off, on].

After the third round, the three bulbs are [on, off, off].

So you should return 1 because there is only one bulb is on.

**Example 2:**

Input: n = 0

Output: 0

**Example 3:**

Input: n = 1

Output: 1

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。

第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

- 计算 1 到 n 中有奇数个约数的个数

- 1 到 n 中的某个数 x 有奇数个约数,也即 x 是完全平方数

- 计算 1 到 n 中完全平方数的个数 sqrt(n)

package leetcode

import "math"

func bulbSwitch(n int) int {

return int(math.Sqrt(float64(n)))

}

<div style="display: flex;justify-content: space-between;align-items: center;">

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0318.Maximum-Product-of-Word-Lengths/">⬅️上一页</a></p>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0322.Coin-Change/">下一页➡️</a></p>

</div>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0319.Bulb-Switcher/">⬅️上一页</a></p>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0384.Shuffle-an-Array/">下一页➡️</a></p>

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

- Solution(int[] nums) Initializes the object with the integer array nums.

- int[] reset() Resets the array to its original configuration and returns it.

- int[] shuffle() Returns a random shuffling of the array.

**Example 1**:

Input

["Solution", "shuffle", "reset", "shuffle"]

[[[1, 2, 3]], [], [], []]

Output

[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation

Solution solution = new Solution([1, 2, 3]);

solution.shuffle(); // Shuffle the array [1,2,3] and return its result.

// Any permutation of [1,2,3] must be equally likely to be returned.

// Example: return [3, 1, 2]

solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]

solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

**Constraints:**

- 1 <= nums.length <= 200

- -1000000 <= nums[i] <= 1000000

- All the elements of nums are unique.

- At most 5 * 10000 calls in total will be made to reset and shuffle.

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

- Solution(int[] nums) 使用整数数组 nums 初始化对象

- int[] reset() 重设数组到它的初始状态并返回

- int[] shuffle() 返回数组随机打乱后的结果

- 使用 rand.Shuffle 进行数组随机打乱

package leetcode

import "math/rand"

type Solution struct {

nums []int

}

func Constructor(nums []int) Solution {

return Solution{

nums: nums,

}

}

func (this *Solution) Reset() []int {

return this.nums

}

func (this *Solution) Shuffle() []int {

arr := make([]int, len(this.nums))

copy(arr, this.nums)

rand.Shuffle(len(arr), func(i, j int) {

arr[i], arr[j] = arr[j], arr[i]

})

return arr

}

<div style="display: flex;justify-content: space-between;align-items: center;">

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0378.Kth-Smallest-Element-in-a-Sorted-Matrix/">⬅️上一页</a></p>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0385.Mini-Parser/">下一页➡️</a></p>

</div>

<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0384.Shuffle-an-Array/">⬅️上一页</a></p>